Why std::vector iterator is invalidated after the erase() call?

Question

The C++ reference clearly state that calling std::vector::erase(it) on iterator will invalidate all iterators pointing to and after the erased element. http://en.cppreference.com/w/cpp/container/vector/erase

I do understand why such iterators became non-dereferenceable after the erase call, but i am curious why they need to became invalid, what implementation details require it?

For instance standard says that std::vector must be implemented with elements stored contiguously and that elements can be accessed not only through iterators, but also using offsets on regular pointers to elements so it seems logical that iterators for such container will probably be implemented as pointers - but then how pointers could became invalidated?

Answer 1

One of the principles on which the conceptual idea of iterator is built, is as follows: as long as iterator remains non-aliased, dereferenceable and non-modified, it should refer to the same entity. In other words, dereferencing the same iterator multiple times should yield the same value. Algorithms that use iterators may rely on that.

What you proposing would result in an iterator that would "magically" change the value it refers to even though the iterator itself remains unchanged. This is not acceptable within the conceptual idea of iterator.

---

On the second thought, what I said above is obviously flawed in a sense that we can always apply some modifying operation to the vector that shifts elements around (e.g. std::random_shuffle). Such operation would not invalidate any iterators, but would easily change the values the iterators refer to. How is that different from element shifting triggered by erase? It isn't.

Answer 2

"invalidated" can mean "no longer points to what it used to", not just "may not point to any valid element"

consider (uncompiled code):

vector<int> v = {0, 1, 2, 3, 4, 5};
vector<int>::iterator iter = v.begin() + 3;  // "points to" 3
assert(*iter == 3);
v.erase(v.begin());

At this point, iter has been invalidated. It no longer "points to" the same element that it did before.