why erase operation from a map doesn't invalide iterator

I'm wondering why an erase operation from a ma开发者_开发技巧p inside a loop according to a predicate keep the iterator in a valide state, but not for a vector

---

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.

---

erm... simple answer:

Because the standard requires this behaviour.

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

You can easily picture it in your mind by thinking what happens when you remove an item from the middle of a vector (i.e. C-style array; subsequent items get moved), as opposed to removing from a list/tree (no items get moved, only link pointers are updated).

Note that traversal could be made safe for vectors (by using ordinal index instead of iterators), but that is not the point: the iterator interface requires that an increment will lead to the next valid iterator. That won't be true (not even if the 'trivial' iterator of T* is being used in the implementation) for a vector.

---

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

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

It actually is a feature. It doesn't invalidate them because it doesn't have to. For vector you do have to since at least all elements to the right of the erased one get shifted and pointers change.