C++:std :: unordered_map是否保证基于节点？

Question

什么是典型的布局std::unordered_map<K, V>？是K与V对象存储在桶本身,还是做桶存储指向包含密钥和值的节点？

我试图弄清楚使用std::unordered_map<K, V>对比的性能影响std::unordered_map<K, V*>.假设我只是设置和查找值,有没有理由更喜欢后者,即使值非常大？我能想象的唯一原因是,这些值是否存储在桶中,并且每次重新处理容器时都需要重新分配.

标准中有什么可以保证不会发生这种情况吗？

Answer 1

[unord.req]/8:

重新散列使迭代器无效,元素之间的顺序更改以及桶元素出现的更改,但不会使指针或对元素的引用无效.

事实上,指针和对元素的引用不会通过重新散列(或插入/删除,参见/ 13)而失效,这意味着它们必须基于节点.

C++ 17甚至公开节点句柄,以便您可以在两个unordered_maps 之间传输节点.