std::map and behavior of already inserted data

Question

Does std::map move around already inserted values when inserting new data ?

GManNickG · Accepted Answer · 2010-03-19T13:17:37.233

13

The map is implemented as a tree, and when you insert a new element, the tree may need to be rebalanced.

This does not invalidate any iterators or references to elements in the tree. This balancing is done via the manipulation of pointers, so you have nothing to worry about; the nodes themselves stay put.

Balancing involves changing the structure of the tree by telling nodes who their children, parents, and siblings are via re-assigning pointers, but this is an implementation detail. Logically nothing has changed.

edited Mar 19 '10 at 13:17

answered Mar 19 '10 at 12:26

GManNickG

494,350
52
494
543

2

I'm wondering, if `it` is an iterator to an element, then before and after an insertion `*it` refers to the same map entry but is it guaranteed that `&*it` remains the same? In most implementations I would expect this to be true, but it would be possible to implement an iterator with sufficient proxying that the elements could move around but the iterators retain consistency. – CB Bailey Mar 19 '10 at 12:33
10

@Charles 23.1.2/8 also states that no references to the container are invalidated. – Andreas Brinck Mar 19 '10 at 12:39
@Charles: Good question, I never thought about it. Thanks @Andreas for the answer. – GManNickG Mar 19 '10 at 12:42
@Charles, iterators point to nodes. The actual position of the node in the tree is irrelevant. *Values* reside in the nodes. So `&*it` won't change, unless you're fearless and remove the node during the iteration. – Nick Dandoulakis Mar 19 '10 at 12:43
@Nick: Iterators only *represent* pointers; how they manage to do that doesn't necessarily have to be by pointer. Like Charles mentioned, it could be possible to achieve this by a proxy, allowing elements to change position. – GManNickG Mar 19 '10 at 12:47
@Andreas: Thanks for the reference; I was fairly sure that there was such a restriction but had a moment of doubt when I couldn't find it. – CB Bailey Mar 19 '10 at 13:00
2

@Charles: maybe the wording of the answer is not clear enough: nodes will NOT be moved. The shape of the balanced tree (logical structure) will change, but elements will never be reseated in a different part of memory. Each node is created in a position in memory, and that will never change. When the tree is rebalanced the values of the left, right and parent pointers will change to point to different nodes, but the node itself will still be in the same memory address, although in a different path from the root of the tree. – David Rodríguez - dribeas Mar 19 '10 at 13:03
@Charles taken care of by http://stackoverflow.com/questions/1068557/c-storing-references-to-values-in-stdmap/1069200#1069200 and http://stackoverflow.com/questions/2364662/for-how-long-the-iterator-returned-by-stdset-find-lives/2364680#2364680 have fun :) – Johannes Schaub - litb Mar 19 '10 at 13:05
There is one question however in the iterator invalidation trick: I am not sure that `end` is guaranteed to remain the same when insertion or removal are done... I am not sure that there is any guarantee on this part from the standard. – Matthieu M. Mar 19 '10 at 13:05
I guess that the answer is actually misleading: 'Inserting may move nodes around as an implementation detail, but logically nothing has changed.' If the memory could be moved then the guarantee that @Andreas pointed from 23.1.2/8 could not be fulfilled by that implementation. – David Rodríguez - dribeas Mar 19 '10 at 13:11
@David: I did in fact use terrible wording, it's my forté. I meant exactly what you said. In fact, I'm going to steal it now. – GManNickG Mar 19 '10 at 13:15
@Matthieu, interesting issue. Maybe that `end` issue is why it says "iterators to the container" instead of "iterators to the elements"? Contrast this to `23.1/11` which uses a different wording for the general case. – Johannes Schaub - litb Mar 19 '10 at 15:14

score 2 · Answer 2 · answered Mar 19 '10 at 12:31

The standard does not mandate specific implementations of the STL, only the behavior and runtime characteristics. That said, a skip list or tree is a very likely implementation of std::map, so links will be updated, and the relative ordering will change, but the actual data is not going to be moving around.

score 0 · Answer 3 · answered Mar 19 '10 at 12:38

Consider a typical node in doubly linked list:

template <class T>
struct Node
{
  Node* mPrevious;
  Node* mNext;
  T mValue;
};

When inserting a new node between two existing ones, all you have to do is some rewiring.

void insert(Node* target, Node* newNode)
{
  target->mPrevious->mNext = newNode;
  target->mPrevious = newNode;

  newNode->mPrevious = target->mPrevious;
  newNode->mNext = target;
}

The behavior is similar with an std::map (or std::set, std::multimap or std::multiset since they are all implemented using the same underlying structure in general).

It means that any iterator pointing to an existing element remains valid too. I do insist on the existing element bit. The iterator returned by end should be recomputed after insertion or removal and is better not cached.

score 0 · Answer 4 · answered Mar 19 '10 at 16:03

The C++ standard does not dictate the implementation of std::map only its behavior and efficiency. Implementations are allowed to move items around; however, this may be inefficient.

Most std::map containers are implemented using a tree data structure with links. When inserting or reordering items, the links are changed, but the data is not moved. Moving items would slow the execution time of the std::map.

std::map and behavior of already inserted data

4 Answers4