Swi*_*tch 12 c++ stl unordered-map reference map
对于这两个std::map和std::tr1::unordered_map,我从标准看:
在所有情况下,对unordered_map容器中元素的引用仍然有效,即使在重新散列之后也是如此.
他们是如何做到的(以实施方式)？他们是否将所有条目都维护为一种链表,然后哈希表只存储指向元素的指针？
Ros*_*ith 26
是的,涉及链接列表,尽管不像你建议的那样.
2011标准说(23.2.5第8段),"一种无序关联容器中的元素组织成桶.具有相同散列码的键显示在同一个桶".
在每个存储桶中,元素位于链接列表中(每个存储桶的单独列表,而不是整个容器的一个大列表).当容器被重新散列时,元素将被分配给新的桶,但是指向每个元素的指针仍然有效.每个新存储桶中的链接列表都是从指向最终存储在该存储桶中的现有元素的指针组合而成.
迭代器由于重新散列而失效,因为迭代器需要保持指向元素及其桶的指针(因此它可以从一个桶的最后一个元素步进到下一个桶的第一个元素).元素指针仍然有效,所以现有的指针和引用的元件仍然有效,但挖斗指针由无效翻版,因此迭代器是不可用的.
(这也是无序容器只支持前向迭代器而不是有序关联容器支持的双向迭代器的原因.每个桶的元素都在一个单独的链表中,所以你不能倒退它们.)
| 归档时间： |
|
| 查看次数： |
5821 次 |
| 最近记录： |