What is iterator invalidation?
Answer:
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) [23.2.
4.3/1]
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) [23.2.
1.3/1]
list: all iterators and references unaffected [23.2.2.3/1]
Associative containers
[multi]{set,map}: all iterators and references unaffected [23.1.2/8]
Container adaptors
stack: inherited from underlying container
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
[23.2.4.3/3]
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) [23.2.1.3/4]
list: only the iterators and references to the erased element is invalidated
[23.2.2.3/3]
Associative containers
[multi]{set,map}: only iterators and references to the erased elements are
invalidated [23.1.2/8]
Container adaptors
stack: inherited from underlying container
queue: inherited from underlying container
priority_queue: inherited from underlying container
Resizing
vector: as per insert/erase [23.2.4.2/6]
deque: as per insert/erase [23.2.1.2/1]
list: as per insert/erase [23.2.2.2/1]
Note 1
Unless otherwise specified (either explicitly or by defining a function in
terms of other functions), invoking a container member function or passing a
container as an argument to a library function shall not invalidate
iterators to, or change the values of, objects within that container. [23.1/
11]
Note 2
It's not clear in C++2003 whether "end" iterators are subject to the above
rules; you should assume, anyway, that they are (as this is the case in
practice).
Note 3
The rules for invalidation of pointers are the sames as the rules for
invalidation of references.