C++ and iterator invalidation

Question

So I'm going through Accelerated C++ and am somewhat unsure about iterator invalidation in C++. Maybe it's the fact that it is never explained how these iterators are constructed is the problem.

Here is one example:

Vector with {1,2,3}

If my iterator is on {2} and I call an erase on {2} my iterator is invalid. Why? In my head, {3} is shifted down so the memory location of where {2} was so the iterator is still pointing to a valid element. The only way I would see this as being not true is if iterators were made before hand for each element and each iterator had some type of field containing the address of the following element in that container.

My other question has to do with the statement such as "invalidates all other iterators". Erm, when I loop through my vector container, I am using one iterator. Do all those elements in the vector implicitly have their own iterator associated with them or am I missing something?

Answer 1

In my head, {3} is shifted down so the memory location of where {2} was so the iterator is still pointing to a valid element.

That may be the case. But it’s equally valid that the whole vector is relocated in memory, thus making all iterators point to now-defunct memory locations. C++ simply makes no guarantees either way. (See comments for discussion.)

Do all those elements in the vector implicitly have their own iterator associated with them or am I missing something?

You’re merely missing the fact that you may have other iterators referencing the same vector besides your loop variable. For example, the following loop is an idiomatic style that caches the end iterator of the vector to avoid redundant calls:

vector<int> vec;
// …

for (vector<int>::iterator i(vec.begin()), end(vec.end()); i != end; ++i) {
    if (some_condition)
        vec.erase(i); // invalidates `i` and `end`.
}

(Nevermind the fact that this copy of the end iterator is in fact unnecessary with the STL on modern compilers.)