Iterator invalidation rules

Question

What are the iterator invalidation rules for C++ containers?

Preferably in a summary list format.

_{(Note: This is meant to be an entry to Stack Overflow's C++ FAQ. If you want to critique the idea of providing an FAQ in this form, then the posting on meta that started all this would be the place to do that. Answers to that question are monitored in the C++ chatroom, where the FAQ idea started out in the first place, so your answer is very likely to get read by those who came up with the idea.)}

Answer 1

C++03 (Source: Iterator Invalidation Rules (C++03))

---

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.