unordered_map中bucket的实现

Question

我在某处读到，一旦一个桶容纳了超过 8 个元素，它就会变成一棵红黑树，而不是一个链表。我知道 java 使用此策略，但我确定 c++

Answer 1

该标准不强制要求任何特定的实施。

libstdc++ 和 Microsoft 实现中仅使用链表（我没有研究其他实现，所以这里我只考虑这两个）。它们都使用一个长链表（libstdc++ - 单链表，Microsoft - 双链表）来保存所有存储桶。这允许快速迭代整个容器并对operator++迭代器进行操作O(1)。

libstdc++ 中的存储桶数组保存指向第一个存储桶元素之前的一个元素的指针（因为它是单链表）。在 Microsoft 实现中，存储桶数组包含成对的迭代器 - 指向第一个存储桶元素和最后一个存储桶元素之后的迭代器。

libstdc++ 的示意图*：

Microsoft 的示意图*：

* 两个图均对应于std::unordered_set<Key>. 对于std::unordered_map<Key, Value>,key应替换为std::pair<Key, Value>.