If you need to worry about iterator invalidation it may be that you should be using an existing algorithm so that you do not need to modify the container’s contents directly.
You definitely need to understand invalidation however, if you want to write an algorithm.
Insertion
Sequence containers
vector
All iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated).
Reason: A vector
is a contiguous array, so an insertion causes a block shift which moves all elements after the point of insertion. If the capacity is increased, the whole block is reallocated, potentially changing its address, and so the addresses of all elements.
deque
All iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected).
Reason: A deque
is an array of fixed-size arrays (see Deque in C). Addition to the either end (i.e., to the free space in one of the arrays on an end), cannot cause elements to move, so references remain valid. However, as iterators are based on counting, they are all invalidated by addition.
list
All iterators and references unaffected.
Reason: A list
is a linked list. Only the connections between nodes are affected by addition, not the nodes themselves.
Associative containers
set, map, multiset, multimap
All iterators and references unaffected.
Reason: They are all binary trees. Only the connections between nodes are affected by addition, not the nodes themselves.
Container adaptors
stack and queue
Inherited from underlying container.
priority_queue
Inherited from underlying container.
Erasure
Sequence containers
vector
Every iterator and reference after the point of erase is invalidated.
Reason:An erasure causes a block shift leftwards of the succeeding elements, so iterators to them become invalid.
deque
All iterators and references are invalidated, unless the erased members are at an end (front or back) of the deque (in which case only iterators and references to the erased members are invalidated)
Reason:Removing from the end arrays cannot affect the other elements.
list
Only the iterators and references to the erased element is invalidated
Reason: As per addition.
Associative containers
set, map, multiset, multimap
Only iterators and references to the erased elements are invalidated.
Reason: As per addition.
Container adaptors
stack, queue, and priority_queue
Inherited from underlying container.
Resizing
vector, deque, and list
As per insert/erase.
One thought on “Iterator invalidation rules for C++ containers”
Comments are closed.