why erase operation from a map doesn't invalide iterator

Question

I'm wondering why an erase operation from a map inside a loop according to a predicate keep the iterator in a valide state, but not for a vector

Answer 1

Vector::erase invalidates iterators to all elements after the first element that was erased. This makes sense, as the vector is storing its data in an array. When an element is deleted, all elements after it need to be shifted along, e.g.

int test[] = {0, 1, 2, 3, 4, 5};
                             ^

In the above we have an iterator pointing to the value 5, which we want, however, element 1 gets erased, we would now have:

0, 2, 3, 4, 5 
               ^

The iterator is pointing past the end of the array, a problem.

With std::map, the data is stored in a binary tree, so when an element is erased, the left/right pointers of some of the nodes are modified, but their location in memory isn't changed. As a result, any existing iterators pointing to elements that havent been erased are still valid.