Rules for Iterator Invalidation [duplicate]

Question

What are the usual rules for Iterator invalidation when operating over STL container classes(Vector,Dequeue,list,map,multimap,set,multiset). Is it possible to categorize and sum up some general rules/guidelines that a C++ STL programmer must be aware of while working with containers and their Iterators?

Answer 1

These rules are container specific. In fact, these are important criteria for deciding which container you use.

For instance, iterators to an std::vector can get invalidated when an object is inserted (depends in where the object is inserted and if reallocation takes place), and they get invalidated when an object is removed before the iterator. An std::list does not have this problem. Inserting and removing objects (except for the object the iterator points to) does not invalidate the iterator.

SGI provides good documentation on this.

Answer 2

The invalidation rules are inspired from the very fundamental Data Structures and Algorithms used to implement these containers. If you do not plan to learn the fundamentals, then you will need to remember the iterator documentation by heart.

The C++ standard defines the behaviors of iterator in a way that makes it possible to implement with simple C pointers. It does not require the library to actually use pointers; it simply makes it possible to do so.

Basically, an iterator is invalidated if an operation causes an underlying storage element (a heap array used in a vector, a linked-list node used in a list, or a tree node used in a map or set) to be deallocated, or shifed into a different memory location.

A vector is usually implemented by allocating an array from the dynamic memory (heap). In order to reduce the number of reallocations, the array is always allocated with some slack, i.e. initially unused space. As elements are added to the array, the slack space is being used up. When all slack space has been taken up and a new element needs to be inserted, then a new array with a bigger size will be allocated. This will cause the invalidation of all iterators pointing to the old array.

Likewise, when an element is erased from a vector, this will cause all subsequent elements to be copied forward. An iterator pointing to the shifted elements will still reference the same index in the array, but that index now contains a different element. This is also an example of invalidation.

For list, map and set, the tree-node or list-node remains valid until the element it contains is erased. Note that an iterator pointing to an invalidated node cannot be used for anything; not even for iterator increment/decrement. This is because in a linked-list or tree implementation, the iterator depends on child pointers that are stored in the node itself.

In order to always guarantee correct operation, the standard is worded in a more restrictive way than if simple data structures are used (which, paradoxically gives more freedom to library implementers to use more advanced data structures). For example, see http://c2.com/cgi/wiki?IteratorInvalidationProblem and http://www.threadingbuildingblocks.org/codesamples.php .