Iterator Cancellation Policy

Question

What are the usual rules for invalidating Iterator when working on STL container classes (Vector, Dequeue, list, map, multimap, set, multiset). Is it possible to classify and summarize some general rules / recommendations that a C ++ STL programmer should know when working with containers and their iterators?

Answer 1

These rules are container specific. In fact, these are important criteria for determining which container you are using.

For example, iterators in std::vector may be invalid when the object is inserted (depending on where the object is inserted and redistribution occurs), and they become invalid when the object is deleted before the iterator. std::list does not have this problem. Inserting and deleting objects (except for the object that the iterator points to) does not cancel the iterator.

SGI provides good documentation about this.

Answer 2

Invalidity rules are based on the most fundamental Data Structures and algorithms used to implement these containers. If you do not plan to learn the basics, then you will need to memorize the iterator documentation by heart.

The C ++ standard defines the behavior of an iterator in such a way that it can be implemented using simple C pointers. This does not require the library to actually use pointers; it just lets you do it.

In principle, an iterator is invalid if the operation calls the underlying storage element (the heap array used in vector , the linked list node used in list , or the node tree used in map or set ) that should be freed or moved to another memory location.

A vector usually implemented by allocating an array from dynamic memory (heap). To reduce the number of redistributions, the array is always allocated with some delay, i.e. Initially unused space. When elements are added to the array, the waiting space is reduced. When all the free space is occupied, and you need to add a new element, then a new array with a large size will be selected. This will invalidate all iterators pointing to the old array.

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

For list , map and set tree-node or list-node remains valid until the element contained in it is deleted. Note that an iterator pointing to an invalid node cannot be used for anything; even to increase and decrease the iterator. This is because in the implementation of a linked list or tree, the iterator depends on the child pointers that are stored in the node itself.

To always guarantee proper operation, the standard is formulated in a more rigorous way than when using simple data structures (which, paradoxically, gives more opportunities for library implementers to use more complex data structures). For example, see http://c2.com/cgi/wiki?IteratorInvalidationProblem and http://www.threadingbuildingblocks.org/codesamples.php .