43

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?

Mark Canlas
  • 9,385
  • 5
  • 41
  • 63
  • 2
    Also this [Iterator Invalidation Rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules) – mwerschy Jun 03 '13 at 19:36
  • I might need a little better explanation of this, I didn't think it had anything to do with high/low level languages. I know you can't modify the list during iteration in `C#`. – Nick Freeman Jun 03 '13 at 19:36
  • @NickFreeman it has nothing to do with high vs low levels. It has everything to do with implementation. It is entirely possible (although complex) to create a container in C# which would allow for iteration while enumerating, so long as you keep the state of each in-check. – Richard J. Ross III Jun 03 '13 at 19:40
  • Well, I've never heard of iterator invalidation in my experience with languages not C++, so I assume it has something to do with low level/performance concerns, otherwise all collections would be the same. – Mark Canlas Jun 03 '13 at 19:57

3 Answers3

47

  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.

user2357112
  • 260,549
  • 28
  • 431
  • 505
djechlin
  • 59,258
  • 35
  • 162
  • 290
  • 10
    This is why I love the fact that Visual Studio has debug builds. By default, the standard C++ containers will check if they're valid in debug builds, helping to find these insidious errors. – Mooing Duck Jun 03 '13 at 19:41
  • @MooingDuck you shouldn't rely upon that behavior, though. If you become too attached to awesome compiler features, when you move over to a different platform (which may happen some time in the future), you will get burned, hard and fast. – Richard J. Ross III Jun 03 '13 at 19:42
  • 6
    @RichardJ.RossIII: Depend on? Clearly not. But it's nice to have an extra layer of protection for when I do screw up. – Mooing Duck Jun 03 '13 at 19:52
  • But what kind of iterator implementation lets that happen at all? Isn't that kind of ghetto/unsafe? – Mark Canlas Jun 03 '13 at 19:59
  • 7
    @MarkCanlas: That's how C++ works. Most errors that can only be caught at runtime aren't required to be checked automatically; otherwise, the runtime cost would be unacceptable in many situations. So a "safe" implementation (as Mooing Duck describes) will check for this error; a "fast" implementation won't, and will be much faster. – Mike Seymour Jun 03 '13 at 20:17
  • According to this article, std::map does not invalidate the iterators upon erase (which I assume is what you meant, as there is no std::map.remove() function): http://stackoverflow.com/questions/4343220/does-insertion-to-stl-map-invalidate-other-existing-iterator –  Jan 11 '15 at 18:04
  • @racarate: Iterators to the other elements of the map are okay, but `it` is invalidated, since it points to the erased element. – user2357112 Apr 16 '16 at 23:01
  • @djechlin, Is it safe to keep iterating over the map in the second example after the call to `erase()`? Because `end()` was not invalidated. Right? – VL-80 Feb 09 '17 at 16:22
  • @djechlin, Never mind, I found my answer [here](http://stackoverflow.com/a/433207/1418463) – VL-80 Feb 09 '17 at 16:47
11

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.

Richard J. Ross III
  • 55,009
  • 24
  • 135
  • 201
5

The problem occurs when a container that is being processed using an iterator has its shape changed during the process. (We will assume a single-threaded application; concurrent access to a mutable container is a whole 'nother can of worms which we won't get into on this page). By "having its shape change", one of the following types of mutations is meant:

  • An insertion into the container (at any location)
  • Deletion of an element from the container
  • Any operation that changes a key (in an AssociativeContainer)
  • Any operation which changes the order of the elements in a sorted container.
  • Any more complicated operation consisting of one or more of the above (such as splitting a container into two).

(From: http://c2.com/cgi/wiki?IteratorInvalidationProblem)

The concept is actually fairly simple, but the side-effects can be quite annoying. I would add that this problem affects not only C/C++ but slews of other low-level or mid-level languages, as well. (In some cases, even if they don't allow direct heap allocation)

djechlin
  • 59,258
  • 35
  • 162
  • 290
David Titarenco
  • 32,662
  • 13
  • 66
  • 111
  • Keys can't be changed in any associative container that I know of. – Mooing Duck Jun 03 '13 at 19:42
  • @MooingDuck it really depends on what you consider a 'key change' to be. I could remove the value for one key, and add that value for another key, isn't that a 'key change'? Just because containers don't natively support something, doesn't mean it can't be done. – Richard J. Ross III Jun 03 '13 at 19:44
  • @RichardJ.RossIII: I believe the post/link are referring to actual modification of the _key itself_, not the value associated with said key. Modifying the associated data require iterator invalidation in most cases. Modifying the _key itself_ would require a (theoretical) erasure/reinsertion. – Mooing Duck Jun 03 '13 at 19:46
  • @MooingDuck once again, not necessarily. If my implementation is an array of keys, and an array of values, where the index of a value corresponds to it's key, I could simply change the value in the key array! Similarly, if it's an array of key-value pairs, nothing says I can't just change the 'key' portion of the pair. It's obviously not implemented in the C++ STL, but it's not impossible. – Richard J. Ross III Jun 03 '13 at 19:48
  • @RichardJ.RossIII: I see your point. I mean, that would scale poorly, but that's irrelevant to your point. I can even see how that could invalidate an iterator! O.o – Mooing Duck Jun 03 '13 at 19:54