std::unordered_map insert 仅使迭代器无效,但对元素节点的引用和指针无效

std::unordered_map insert invalidates only iterators but not references and pointers to the element node

有人可以解释为什么插入 std::unordered_map 容器只会使迭代器无效,而不会使引用和指针无效。此外,我无法理解 https://en.cppreference.com/w/cpp/container/unordered_map/insert 中的以下语句是什么意思

If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid.

插入 unordered_map 不会使引用无效,因为它不会移动数据,但是底层数据结构可能会发生相当大的变化。没有具体说明它是如何实现的细节,不同的编译器以不同的方式实现。例如,MSVC 有一个用于数据存储的链表,我相信还有一个 look-up 的向量。并且 insert 会导致重新散列,这意味着 look-up 被完全改变并且链表被显着重新排序 - 但原始数据没有被移动。

迭代器引用这个底层结构,对它的任何更改都可能导致迭代器失效。基本上,它们包含的信息比指针和引用更多,随后可能会失效。

令人困惑的段落是关于 insertnode_type - 先前提取的节点。检查方法 unordered_map::extract

https://en.cppreference.com/w/cpp/container/unordered_map/extract

出于某种原因,在提取节点时禁止使用 pointers/references。插入后可以再次使用它们。不知道为什么会这样

关于问题的第二部分,它指的是C++17中引入的Node handle。它是 move-only 类型,直接拥有底层键和值。它可用于在不重新分配的情况下更改元素的键,以及在不复制或移动的情况下转移元素所有权。

由于允许更改const-like数据(如key),我个人认为只有在与容器隔离时才允许进行此类编辑才有意义,即在节点中时形式;这就是为什么指针和对其底层数据的引用在插入回容器后应该失效的原因。

同样,由于插入不会引起任何重新分配,一旦节点被插入回容器,在提取之前指向数据的指针和引用将再次有效。