std::map and behavior of already inserted data

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.