C++ stl unordered_map 实现，参考有效性
对于 std::map 和 std::tr1::unordered_map，我从标准中看到:
For both std::map and std::tr1::unordered_map, I see from the standard that:
对 unordered_map 容器中元素的引用在所有情况，即使在重新哈希后也是如此.
References to elements in the unordered_map container remain valid in all cases, even after a rehash.
他们是如何做到这一点的(实施方面)?他们是否将所有条目维护为一种链表，然后哈希表只存储指向元素的指针?
How are they doing that (implementation-wise)? Are they maintaining all the entries as a kind of linked list and then the hash-table just stores pointers to the elements?
推荐答案
是的，涉及到链表，虽然不像你建议的那样.
Yes, linked lists are involved, although not quite in the way you suggest.
2011 标准说(23.2.5 第 8 段)，无序关联容器的元素被组织到桶中.具有相同哈希码的键出现在同一个桶中."
The 2011 standard says (23.2.5 para 8), "The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket."
在每个桶内，元素都在一个链表中(每个桶都有一个单独的列表，而不是整个容器的一个大列表).当容器被重新散列时，元素将被分配到新的存储桶，但指向每个元素的指针仍然有效.每个新存储桶中的链表由指向该存储桶中结束的现有元素的指针组装而成.
Within each bucket, the elements are in a linked list (a separate list for each bucket, not one big list for the whole container). When the container is rehashed, the elements will be assigned to new buckets, but the pointers to each element remain valid. The linked list in each new bucket is assembled from pointers to the existing elements that end up in that bucket.
迭代器因重新散列而失效，因为迭代器需要保存指向元素及其存储桶的指针(因此它可以从一个存储桶的最后一个元素步进到下一个存储桶的第一个元素).元素指针仍然有效，因此现有的指针和对元素的引用仍然有效，但桶指针因重新散列而无效，因此迭代器不可用.
Iterators are invalidated by a rehash, since an iterator needs to hold pointers to both the element and its bucket (so it can be stepped from the last element of one bucket to the first element of the next). The element pointer remains valid, so existing pointers and references to an element are still valid, but the bucket pointer is invalidated by a rehash, so the iterator isn't usable.
(这也是为什么无序容器只支持前向迭代器，而不是有序关联容器支持的双向迭代器.每个桶的元素都在一个单向链表中，所以你不能通过它们向后退步.)
(This is also why unordered containers only support forward iterators, instead of the bidirectional iterators supported by the ordered associative containers. The elements of each bucket are in a singly linked list, so you can't step backwards through them.)
相关文章