8

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)

a-z
  • 1,634
  • 4
  • 16
  • 35

3 Answers3

11

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...

Community
  • 1
  • 1
CygnusX1
  • 20,968
  • 5
  • 65
  • 109
  • This doesn't address the core question: Is `std::map` allowed to _move_ elements? – Andres Jaan Tack Mar 18 '12 at 09:23
  • If an element was moved, a pointer/reference to it would get invalidated (I am talking about plain pointers, not iterators). That is why - no - it is not allowed to move elements. ... well, in theory some implementation could copy the object somewhere and then move back to old position, but that would be somewhat strange. – CygnusX1 Mar 18 '12 at 10:24
  • Though strangely no such requirement is made of `erase`. – edA-qa mort-ora-y Mar 18 '12 at 11:13
  • 2
    Just for note: The text has been moved to new section p.744, 23.2.4#9 in newer version of standard draft. [N3797, 2013-10-13](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3797.pdf) – eonil Jan 28 '14 at 14:43
1

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.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
0

I believe the C++03 does not make any guarantees of stability of the data in the memory, and this would be an implementation detail (and actually not something you can safely assume without testing).

Note that the preservation of iterators to the map and the location of the actual vector in the memory are completely different things. The validity of iterators is clearly defined (both when they're valid and when they're not) in the C++ spec, but the actual internal behavior of the tree isn't.

That said, any decent compiler (for release builds/with optimizations enabled) would optimize the implementation to not actually copy the vector when it's being moved around in the tree, and C++11 implementations of std::map would use move semantics to guarantee that behavior.

What you cannot assume is that internally only pointers are moved.

Mahmoud Al-Qudsi
  • 28,357
  • 12
  • 85
  • 125
  • 1
    `std::map` is required to be a node-based container in all revisions of the standard, i.e. nodes which aren't erased from the map stay put in memory: neither iterators nor pointers to map elements become invalidated until the node is erased or the map is destroyed. – Dietmar Kühl Mar 18 '12 at 10:13
  • But it also preserves references (plain pointers), not just iterators. This allows you to argue about memory. Unless there is some strange memory address virtualisation... – CygnusX1 Mar 18 '12 at 10:25