Iterator invalidation rules for C++ containers

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.

Related

One thought on “Iterator invalidation rules for C++ containers”

Comments are closed.