Is second part of map<..,..> stable?

Question

If we have a map <int, vector<int> > are vectors moved when the red-black tree of map changes or it stores pointers to vectors or something like that and does not move them(else working with maps won't be O(lg n) anymore e.g. if we push_back elements to some vectors)

Answer 1

See this one: std::map, pointer to map key value, is this possible?

the second top answer:

Section 23.1.2#8 (associative container requirements):

"The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements."

So yes storing pointers to data members of a map element is guaranteed to be valid, unless you remove that element.

So, if the references are preserved, the data cannot be copied into a different part of memory. And if that is the case, I don't see the point in performing any copy at all...

Answer 2

No, the vectors won't be moved around. The manipulations of the tree just rearrange pointers between the nodes. They don't move nodes or their contents in memory.