What is iterator invalidation?

I see it referenced a lot but no clear answer of what exactly it is. My experience is with higher level languages, so I'm unfamiliar about the presence of invalidity in a collections framework.

What is iterator invalidation?

Why does it come up? Why is it difficult to deal with?

Solution 1:

1. Iterators are glorified pointers. Iterator invalidation is a lot like pointer invalidation; it means it suddenly points to junk data.

2. Because it's very natural but wrong to do things like this:

   for(iterator it = map.begin(); it != map.end(); ++it) {
       map.erase(it->first);
       // whoops, now map has been restructured and iterator 
       // still thinks itself is healthy
   }
   

3. Because that error right there? No compiler error, no warning, you lose. You just have to be trained well enough to watch for them and prevent them. Very insidious bugs if you don't know what you're doing. One of the design philosophies of C++ is speed over safety. The runtime check that would lead iterator invalidation to an exception instead of unspecified behavior is too expensive, in the view of C++ language designers.

You should be on high alert when you are iterating over a data structure and modifying structure itself, instead of merely the objects held in them. At that point you should probably run to the documentation and check whether the operation was illegal.

Solution 2:

Iterator invalidation is what happens when an iterator type (an object supporting the operators ++, and *) does not correctly represent the state of the object it is iterating. For example:

int *my_array = new int[15];
int *my_iterator = &my_array[2];

delete[] my_array;

std::for_each(my_iterator, my_iterator + 5, ...); // invalid

That results in undefined behavior because the memory it is pointing to has been reclaimed by the OS.

This is only one scenario, however, and many other things cause an iterator to be 'invalidated', and you must be careful to check the documentation of the objects you are using.