Iterator Invalidation Problem

Iterator invalidation can occur when using iterators (usually ExternalIterators, though InternalIterators can be affected too) to traverse a mutable container.

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

In general, simple mutations that don't change the "shape" of the container (such as replacing the third element of an array with a new value) don't cause problems.

The problem is, of course, that any outstanding iterators which refer to the container may become invalid, or be caused to point to a different element (or even a different container). If performing a traversal, the traversal invariant (each node visited exactly once) may be violated by this. In some cases, there is no way to detect that the iterator has been invalidated, and further use of it results in UndefinedBehavior! (In languages that have UndefinedBehavior, that is. Otherwise probably an exception or some unpredictable traversal order.)

The CeePlusPlus StandardTemplateLibrary, for example, meticulously documents exactly what effects container mutations have on STL iterators; in many cases iterators can become invalidated with UndefinedBehavior the result. (Often, this depends on the underlying state of the container--for example, appending an element to a vector<T> will invalide all existing iterators--turning them all into WildPointers, essentially--if the append causes a resize. Which doesn't always occur; as vector<T> generally doubles its size when it needs more room (DoubleAfterFull); so most such allocations are harmless).

The problem is excacerbated by the fact that for many efficient container implementations, iterators have internal (and somewhat incestuous) knowedge of the containers they point to, and/or are often very low-level abstractions under the hood. Again picking on C++, vector<T>::iterator is usually little more than a T* pointing somewhere into the middle of the array.

Possible solutions to this problem:

• Disallow mutable containers altogether. Problem solved. Perhaps use CopyOnWrite semantics such that each iterator points to a 'logical' copy of the data.
• Use some sort of ReaderWriter? locking; while an iterator for the container is outstanding, disallow mutation (other than the simple, harmless case). Can be made to work with InternalIterators; can be problematic with ExternalIterators as "iterator leaks" become a possibility.
• Require that all container modifications invalidate all iterators, and require that iterator invalidation generate a runtime error whenever it occurs (in other words, disallow UndefinedBehavior). The JavaLanguage collections API takes this approach.
• Require that iterators contain a reference to the descriptor for the relevant container (some object/state which doesn't move over the lifetime of the container).