12

对于std::mapstd::tr1::unordered_map,我从标准中看到:

对 unordered_map 容器中元素的引用在所有情况下都保持有效,即使在重新散列之后也是如此。

他们是如何做到的(实施方面)?他们是否将所有条目维护为一种链表,然后哈希表只存储指向元素的指针?

4

1 回答 1

27

是的,涉及到链表,尽管不像你建议的那样。

2011 年标准说(23.2.5 第 8 段),“无序关联容器的元素被组织成桶。具有相同哈希码的键出现在同一个桶中。”

在每个桶中,元素都在一个链表中(每个桶有一个单独的列表,而不是整个容器的一个大列表)。当容器被重新散列时,元素将被分配给新的桶,但指向每个元素的指针仍然有效。每个新桶中的链表由指向该桶中现有元素的指针组装而成。

迭代器通过 rehash 无效,因为迭代器需要同时保存指向元素及其存储桶的指针(因此它可以从一个存储桶的最后一个元素步进到下一个存储桶的第一个元素)。元素指针仍然有效,因此现有的指针和对元素的引用仍然有效,但桶指针被 rehash 无效,因此迭代器不可用。

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

于 2012-07-05T03:45:19.023 回答