C++ STL无序映射表unordered_map的实现，引用有效性

Question

对于std::map和std::tr1::unordered_map，从标准中可以看出：

无论何种情况下，对于unordered_map容器中元素的引用在rehash之后仍然有效。

它们是如何实现这一点的？它们是否将所有条目都维护为某种链表，然后哈希表只存储指向元素的指针？

- Switch

Answer 1

是的，链表确实涉及其中，但不完全像你所想的那样。

2011年的标准（23.2.5第8段）表示：“无序关联容器的元素组织成桶。具有相同哈希码的键出现在同一个桶中。”

在每个桶内部，元素以链表形式存在（每个桶有一个单独的链表，而不是整个容器有一个大链表）。当重新散列容器时，元素将被分配到新的桶中，但指向每个元素的指针仍然有效。每个新桶中的链表是由指向最终落入该桶中的现有元素的指针组装而成。

迭代器会因为重新散列而失效，因为迭代器需要保存指向元素和其桶的指针（这样可以从一个桶的最后一个元素走到下一个桶的第一个元素）。元素指针仍然有效，因此对元素的现有指针和引用仍然有效，但桶指针会因重新散列而失效，因此迭代器不能使用。

（这也是为什么无序容器仅支持前向迭代器，而不像有序关联容器支持双向迭代器的原因。每个桶的元素都在一个单向链表中，因此无法通过它们向后移动）

- Ross Smith

---

在询问了一个相关问题后，我找到了这个链接。请随意发表您的观点，但我认为您的答案表明这里没有风险: http://stackoverflow.com/questions/38314154/risk-of-invalidation-of-stdarray-data-in-associative-container - johnbakers