C 中 STL::MAP 的内部实现

Question

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

我能想到的最好的是：

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

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

我真的很好奇，它是如何在 STL Map 中真正实现的。 是否使用了一些散列函数，或者它与 this 完全不同。

原文由 Spandan 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

有序 容器，包括 std::map 被实现为平衡二叉树（通常是 RB 树，但任何其他平衡树都可以满足要求）。

对于此类问题，您需要的最重要的信息是容器中每个操作的复杂性要求，这是标准要求的。也就是，最重要的答案，就是只要满足复杂度要求，实际实现并不重要。

原文由 David Rodríguez - dribeas 发布，翻译遵循 CC BY-SA 3.0 许可协议