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.)

Answer 2

The following C++ defect report (fixed in C++0x) contains a brief discussion of the meaning of "invalidate":

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#414

int A[8] = { 1,3,5,7,9,8,4,2 };
std::vector<int> v(A, A+8);

std::vector<int>::iterator i1 = v.begin() + 3;
std::vector<int>::iterator i2 = v.begin() + 4;
v.erase(i1);

Which iterators are invalidated by v.erase(i1): i1, i2, both, or neither?

On all existing implementations that I know of, the status of i1 and i2 is the same: both of them will be iterators that point to some elements of the vector (albeit not the same elements they did before). You won't get a crash if you use them. Depending on exactly what you mean by "invalidate", you might say that neither one has been invalidated because they still point to something, or you might say that both have been invalidated because in both cases the elements they point to have been changed out from under the iterator.

It seems that the specification is "playing safe" regarding iterator and reference invalidation. It says that they're invalidated even though, as you and Matt Austern both noted, there's still a vector element at the same address. It just has a different value.

So, those of us following the standard must program as if that iterator can't be used any more, even though no implementation is likely to do anything that would actually stop them working, except perhaps a debugging iterator that could do extra work to let us know we're off-road.

In fact that defect report relates to exactly the case you're talking about. As far as the C++03 standard actually says, at least in that clause, your iterator isn't invalidated. But that was considered an error.

Answer 3

An iterator basically wraps a pointer. Some operations on containers have the effect of reallocating some or all of the data behind the scenes. In that case, all current pointers/iterators are left pointing to the wrong memory locations.

Answer 4

The image "in your mind" is an implementation detail, and it could be that your iterator isn't implemented that way. Likely it is, but it could be that it isn't.

The "ivalidates all other iterators" language is their way of saying that the implemenation is allowed the freedom to do anything its coders' skeevie hearts feel like to the contaier when you perform that operation, including things that require internal changes to iterators. Since the only iterator it has access to is the one you passed in, that's the only one that it can fix up if need be.

If you want the behavior in your head for a vector, it is easy to get. Just use an index into the vector instead of an iterator. Then it works just like you think.

Answer 5

Chances are that your iterator is actually pointing at the 3 -- but it's not certain.

The general idea is to allow vector to allocate new storage and move your data from one block of storage to another when/if it sees fit to do so. As such, when you insert or delete data, the data might move to some other part of memory entirely.

At least that was sort of the intent. It turns out that other rules probably prevent it from moving the data when you delete -- but the iterator is invalidated anyway, probably because somebody didn't quite understand all the implications of those other rules when this one was made.

Answer 6

From SGI http://www.sgi.com/tech/stl/Vector.html

[5] A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.

So you can erase starting from end

int i;
vector v;
for ( i = v.size(), i >=0, i--)
{
   if (v[i])
      v.erase(v.begin() + i);
}

OR use iterator returned from vector erase()

std::vector<int> v; 
for (std::vector<int>::iterator it = v.begin(); it != v.end(); )
         it = v.erase(it);