Is the second part of the card <.., ..> stable?

Question

If we changed map <int, vector<int> > to vector when the red-black map tree has changed, or it stores pointers to vector or something like that and does not move them (otherwise, working with maps will not be O (lg n) more, for example, if we click elements s)

Answer 1

See this: std :: map, a pointer to the value of the map key, is this possible?

second top answer:

Section 23.1.2 # 8 (requirements for associative containers):

"Insertion elements should not affect the validity of iterators and references to the container, and erase members should only invalidate iterators and references to erased elements."

Thus, it is guaranteed that saving pointers to data elements of a map element will be valid if you do not delete this element.

So, if the links are saved, the data cannot be copied to another part of the memory. And if so, I see no reason in making any copy at all ...

Answer 2

No, vectors will not move. Tree manipulations only rearrange pointers between nodes. They do not move nodes or their contents in memory.

Answer 3

I believe that C ++ 03 does not guarantee any guarantees of data stability in memory, and this will be an implementation detail (and in fact, this is not something that can be safely assumed without testing).

Note that storing iterators on a map and placing the actual vector in memory are completely different things. The validity of iterators is clearly defined (both in the case when they are valid and when they are not) in the C ++ specification, but the actual internal behavior of the tree is not.

Nevertheless, any worthy compiler (for creating releases / with optimizations enabled) optimizes the implementation so that it does not actually copy the vector when it is moved in the tree, and C ++ 11 std::map implementations will use moving semantics to guarantee this behavior.

What you cannot imagine is that only internal pointers move.