C ++ stl unordered_map实现，引用有效性 [英] C++ stl unordered_map implementation, reference validity

问题描述

对于 std :: map 和 std :: tr1 :: unordered_map ，我看到从标准：

在unordered_map容器中引用元素在
中仍然有效，即使在重新哈希后也是如此。

他们是如何做的（实现方式）？它们是否将所有条目保存为一种链接列表，然后散列表只存储指向元素的指针？

解决方案

是的，涉及链接列表，尽管不太符合你的建议。

2011标准说（23.2.5第8段），无序的关联

在每个桶中，元素都在一个链表中（一个单独的列表每个桶，而不是整个容器的一个大列表）。当容器被重新调用时，元素将被分配给新的桶，但是指向每个元素的指针仍然有效。每个新存储桶中的链接列表都是从指向现有元素的指针汇编到一起的。

迭代器由rehash无效，因为迭代器需要保持指向元素及其桶的指针（因此它可以从一个桶的最后一个元素步进到下一个桶的第一个元素）。元素指针保持有效，因此现有的指针和对元素的引用仍然有效，但是桶指针通过rehash无效，因此迭代器不可用。

（这也是为什么无序容器只支持前向迭代器，而不是有序关联容器支持的双向迭代器）。每个桶的元素都在一个单独的链表中，所以你不能向后退。）

For both std::map and std::tr1::unordered_map, I see from the standard that:

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.

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.)

这篇关于C ++ stl unordered_map实现，引用有效性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！