Can somebody explain why insertion into std::unordered_map container only invalidates iterators but not references and pointers. Also I am not able to understand what the below statement from https://en.cppreference.com/w/cpp/container/unordered_map/insert mean

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.

CodePudding user response：

Insertion of unordered_map doesn't invalidate references because it doesn't move the data, however the underlying data structure might change rather significantly. Details of how exactly it is implemented aren't specified and different compilers do it differently. For instance, MSVC has a linked list for data storage and, I believe, a vector for the look-up. And insert can cause rehash, meaning look-up gets changed completely and the linked list gets reorded significantly - but original data is not moved.

The iterators refer to this underlying structure and any changes to it can cause iterators to invalidate. Basically, they contain more info than pointers and references and subsequently can get invalidated.

The confusing passage is about insert of a node_type - nodes that were previously extracted. Checkout the method unordered_map::extract

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

For some reason it is forbidden to use pointers/references while the node is extracted. After inserting it is allowed to use them again. I don't know why it is so.

CodePudding user response：

In terms of the second part of the question, it is referring to the Node handle introduced in C 17. It is a move-only type, that has direct ownership of the underlying key and value. It can be used to change the key of an element without reallocation and transfer element ownership without copy or move.

Since it's allowed to change const-like data(such as key), I personally think it makes sense to only allow such edit to happen when it is isolated from the container, ie when it is in the node form; which is why pointer and reference to it underlying data should be invalidated once they are insert back to the container.

Similarly, since the insertion does not incur any reallocations, once the node is inserted back to the container, pointer and references that were point to the data before they were extract will be valid again.