我想知道，如何MAP在 C++ 中使用，而不是 MultiMap只是简单的 Map，在内部实现。
我能想到的最好的是：
对于整数映射：A Balanced Binary Search Tree could be used .
对于字符串映射：Compressed Trie or something similar could be used .
我真的很好奇，它是如何在 STL Map 中真正实现的。是否使用了一些散列函数，或者它与 this 完全不同。
问问题
19911 次
2 回答
8
有序容器，包括被std::map实现为平衡二叉树（通常是 RB 树，但任何其他平衡树都符合要求）。
对于此类问题，您需要的最重要的信息是容器中每个操作的复杂性要求，这是标准要求的。也就是，最重要的答案，就是只要满足复杂度要求，实际实现并不重要。
于 2013-07-23T14:21:06.010 回答
3
c++ 中的 std::map 是使用红黑树实现的。
在内部，“map”类公开继承“__Tree”类，它提供了红黑树的实现。 请参阅 <map.h> 中的“类图”片段
这个 __Tree 类用于 map/multimap/set/multiset。 请参阅 <xtree.h> 中的“class __Tree”中的此片段
于 2020-01-26T09:33:52.397 回答