Why does the erase operation of the card do not exclude the iterator

Question

I am wondering why the operation of erasing from the map inside the loop according to the predicate keeps the iterator in the valide state, but not for the vector

Answer 1

Vector::erase cancels iterators for all elements after the first element that has been deleted. This makes sense since the vector stores its data in an array. When an element is deleted, all elements after it should be shifted along, for example.

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

In the above example, we have an iterator pointing to the value 5 that we want, however element 1 is erased, now we have:

 0, 2, 3, 4, 5 ^ 

An iterator points to the end of the array, the problem.

With std::map data is stored in a binary tree, so when an element is erased, the pointers on the left and right of some nodes change, but their location in memory does not change. As a result, all existing iterators pointing to elements that have been erased remain valid.

Answer 2

erm ... simple answer:

Because the standard requires this behavior.

If you want to know how to read trees (avl, rb) (maybe start with linked lists)

You can easily imagine this in your mind, thinking what happens when you delete an element from the middle of the vector (i.e. a C-style array, subsequent elements move), as opposed to deleting from a list / tree (no elements move, update link pointers only).

Note that the traversal can be made safe for vectors (using an ordinal index instead of iterators), but this is not the case: the iterator interface requires the increment to lead to the next valid iterator. This will be incorrect (even if the "trivial" T * iterator is used in the implementation) for the vector.

Answer 3

See http://www.sgi.com/tech/stl/Map.html

A map has the important property that inserting a new element into a map does not invalidate iterators pointing to existing elements. Erasing an element from the map also does not cancel any iterators, except, of course, for iterators that actually point to the element to be erased.

This is actually a feature. This does not invalidate them, because it is not necessary. For the vector that you need, because at least all the elements to the right of the erased will be shifted, and the pointers will change.