C++中STL :: MAP的内部实现

我想知道，MAP如何在C++中使用，而不是MultiMap只是简单的Map，在内部实现。C++中STL :: MAP的内部实现

什么，我最能想到的是：

对于整数映射：A Balanced Binary Search Tree could be used .

对于字符串映射：Compressed Trie or something similar could be used .

我真的很好奇，它是如何真正在STL实现地图。 采用一些散列函数或者是它的东西，从这个完全不同的。

来源

2013-07-23 Spandan

为什么不寻找到的源代码？ – ogni42

@ ogni42：我在哪里可以找到它？ – Spandan

我相信'std :: map'通常使用[Red-black tree]（http://en.wikipedia.org/wiki/Red%E2%80%93black_tree）实现，而'std :: unordered_map'是一个[哈希表]（http://en.wikipedia.org/wiki/Hash_table）。 – Blastfurnace

订购容器包括std::map被实现为平衡二叉树（通常是RB树，但任何其他平衡树将符合要求）。

对于这种类型的问题，你需要的信息，最重要的一条是在容器中，这是标准的任务运作的每一个的复杂性要求。这也是最重要的答案，也就是说，只要符合复杂性要求，实际实施并不重要。

来源

2013-07-23 14:21:06

C++中STL :: MAP的内部实现

回答

相关问题