# Iterator invalidation

> An iterator is a handle into a container's storage, and an operation invalidates it exactly when that storage or the machinery for finding it changes. Learn each container's layout and the invalidation rules can be derived rather than memorized.

- **Source:** C++ Atlas (https://cppatlas.com/topics/iterator-invalidation)
- **Track:** Containers and strings
- **Estimated reading time:** 12 minutes
- **ISO C++ clauses:** [container.reqmts] (https://eel.is/c++draft/container.reqmts), [vector.modifiers] (https://eel.is/c++draft/vector.modifiers), [vector.capacity] (https://eel.is/c++draft/vector.capacity), [deque.modifiers] (https://eel.is/c++draft/deque.modifiers), [list.modifiers] (https://eel.is/c++draft/list.modifiers), [associative.reqmts] (https://eel.is/c++draft/associative.reqmts), [unord.req] (https://eel.is/c++draft/unord.req), [string.require] (https://eel.is/c++draft/string.require)
- **cppreference links:** [Iterator invalidation rules for C++ containers](https://en.cppreference.com/w/cpp/container), [std::vector::erase](https://en.cppreference.com/w/cpp/container/vector/erase), [std::deque::insert](https://en.cppreference.com/w/cpp/container/deque/insert), [std::unordered_map::rehash](https://en.cppreference.com/w/cpp/container/unordered_map/rehash), [std::erase_if (std::map)](https://en.cppreference.com/w/cpp/container/map/erase_if)
- **Prerequisites:** sequence-containers, associative-and-unordered-containers

## The one idea

An iterator, a pointer and a reference to an element are three ways of naming an element, and they break for different reasons. A pointer or reference breaks when the element moves or dies. An iterator breaks in those cases too, and also when the **navigation machinery** it depends on changes: the block index of a `deque`, the bucket array of a hash table, the end of a `vector`.

So there is no table to memorize. For each container ask three questions of an operation. Did any element move in memory? Did an element die? Did the structure used to reach elements change?

> **Mental model.** Invalidation is a statement about storage, not about the operation's name. If an operation leaves every element where it is, only iterators tied to a changed structure break. If it moves elements, all names for them break.

Once invalidated, an iterator is in a singular state. The only things you may do with it are assign to it or destroy it. Dereferencing, incrementing and comparing it are all undefined behavior, even when the memory it points at looks fine.

## `vector`: contiguous storage

A `vector` has two events. **Reallocation** moves every element into a new block, so all iterators, pointers, references, and the end iterator die. This happens when the new size would exceed `capacity()`. Without reallocation, elements before the point of change stay put.

- Insertion without reallocation invalidates iterators and references at or after the insertion point, and the end iterator. Those before the point stay valid.
- Insertion that reallocates invalidates everything.
- Erasure invalidates iterators and references at or after the erased position, including the end iterator, because later elements shift down.
- `reserve` and `shrink_to_fit` invalidate everything if they reallocate, and nothing otherwise. `clear` and `assign` invalidate everything.

After `v.reserve(n)`, the standard guarantees no reallocation until the size would exceed `capacity()`, so iterators to existing elements survive appends up to that limit.

```cpp
#include <vector>

void demo() {
  std::vector<int> v{1, 2, 3};
  v.reserve(100);
  auto it = v.begin();
  v.push_back(4);   // no reallocation: it is still valid, v.end() is not
  *it = 0;          // OK

  auto e = v.end();
  v.push_back(5);
  // e is invalidated even if there was no reallocation
  (void)e;
}
```

Erasure and the saved `end()` cause the most bugs. `end()` is the one iterator that every erase and every insertion invalidates, so a loop that caches it is wrong the moment the loop body changes the vector.

## `deque`: the asymmetric one

A `deque` stores elements in fixed-size blocks and finds them through an index of blocks. Adding an element at either end may allocate a new block and grow that index, and iterators are tied to the index, so all iterators die. Elements themselves are never moved by an end insertion, so pointers and references survive.

- Insertion at the front or back invalidates all iterators, including `end()`, but no references or pointers.
- Insertion in the middle shifts elements, so it invalidates all iterators and references.
- Erasing the last element invalidates only the erased element's iterators and references, plus the end iterator.
- Erasing the first element, if it is not also the last, invalidates only that element's iterators and references.
- Erasing from the middle invalidates everything, including the end iterator.

```cpp
#include <deque>

void demo() {
  std::deque<int> d{1, 2, 3, 4};
  auto it = d.begin() + 2;     // refers to 3
  int& r = d[3];               // refers to 4
  d.erase(d.begin());          // erasing the first element: it and r stay valid
  d.push_back(5);              // it is invalid now; r is still valid
  r = 0;                       // OK
}
```

The erase-at-front rule surprises people who know that `vector` and `deque` look alike. Nothing shifts, because the front is simply abandoned.

## Node containers: `list`, `forward_list`, `map`, `set` and friends

Every element has its own node, and nodes never move. So insertion invalidates nothing, and erasure invalidates only iterators and references to the erased elements. This is the whole rule for `list`, `forward_list`, `set`, `map` and their multi versions.

Two details are worth knowing. The `end()` iterator of these containers stays valid under erase, since it does not name an element. And `list::splice` keeps iterators valid, with the caveat that they now belong to the destination list.

## Unordered containers

The nodes are stable, but iterators can walk across buckets, and the bucket array can be rebuilt. The rules are:

- Insertion that does not trigger a rehash invalidates nothing.
- Insertion that triggers a rehash invalidates all iterators, but not pointers or references to elements.
- `rehash` and `reserve` invalidate all iterators and no references.
- Erasure invalidates only the erased elements.

```cpp
#include <unordered_map>

void demo() {
  std::unordered_map<int, int> m{{1, 10}};
  auto it = m.find(1);
  int& r = it->second;
  m.reserve(1000);          // may rehash
  r = 20;                   // OK: references survive
  // *it = ...;             // undefined behavior: iterators do not
}
```

> **Pitfall.** Inserting into an unordered container while iterating over it is only safe if you know no rehash can occur. With `m.reserve` large enough up front it cannot, but without it, an insertion in a loop body can invalidate the loop's own iterator.

## `string`, swap, move and `end()`

`std::string` follows the conservative rule that nearly any non-const member call may invalidate iterators, pointers and references. The exceptions are `operator[]`, `at`, `data`, `front`, `back` and the iterator getters. One reason is the small-string optimization: short strings live inside the object, so even a swap or a move can relocate characters. Treat any mutation of a string as invalidating everything. The topic on strings covers the rest.

For the other containers, `swap` invalidates nothing. Iterators, pointers and references keep referring to the same elements, which now belong to the other container. `std::array` is the exception: its swap exchanges element values, so iterators stay associated with their original array and now see the swapped values.

```cpp
#include <vector>

void demo() {
  std::vector<int> a{1, 2, 3}, b{4, 5};
  auto it = a.begin();
  a.swap(b);
  // it still refers to the element 1, which is now b[0]
  // it == b.begin() is true; *it is 1
  (void)it;
}
```

The same logic covers moving. For all containers except `array`, move construction and move assignment with an allocator that propagates (always true for `std::allocator`) leave references, pointers and iterators into the source valid, and they refer to the elements now in the destination. This is what makes `std::vector` moves constant time. The moved-from container itself is valid but unspecified, and the `end()` iterator is never covered by these guarantees.

> **Standardese.** [container.reqmts] states that, unless otherwise specified, `swap` does not invalidate iterators, references or pointers into the swapped containers, and that move construction does not invalidate them for any container except `array`. In both cases a note adds that `end()` names no element and may be invalidated.

## Erasing while iterating

The rule for every erasing loop is the same: use the iterator the erase function returns, because the old one is dead. `erase` returns an iterator to the element after the last one removed, so the loop can carry on from there.

```cpp
#include <list>
#include <map>
#include <vector>

void demo() {
  std::vector<int> v{1, 2, 3, 4, 5, 6};
  for (auto it = v.begin(); it != v.end();) {
    if (*it % 2 == 0) it = v.erase(it);   // returns the next valid position
    else ++it;
  }

  std::map<int, int> m{{1, 1}, {2, 2}, {3, 3}, {4, 4}};
  for (auto it = m.begin(); it != m.end();) {
    if (it->first % 2 == 0) it = m.erase(it);  // C++11: erase returns the next
    else ++it;
  }

  std::list<int> l{1, 2, 3, 4};
  for (auto it = l.begin(); it != l.end();) {
    if (*it % 2 == 0) l.erase(it++);   // OK only for node containers
    else ++it;
  }
}
```

The `erase(it++)` form works because the increment happens before the call and node containers invalidate only the erased element. It would be undefined behavior for a `vector`.

Better still, do not write the loop. C++20 added `std::erase_if(container, pred)` for the sequence containers and for every associative and unordered container, and it returns the number of elements removed. For `vector` it is the erase-remove idiom in one call. The loop above that is needed only when the body needs to do more than remove.

## Why use after invalidation is undefined behavior

The standard says an invalidated iterator is singular and may only be assigned to or destroyed. The reason is practical: an iterator in most containers is a pointer or a pointer plus bookkeeping, and checking validity on every dereference would add a cost the standard does not mandate. After a reallocation, the old pointer addresses freed memory. After a rehash, the old iterator points into a bucket array that no longer exists.

That something "worked in testing" is therefore not evidence. A debug mode can catch it: libstdc++ built with `_GLIBCXX_DEBUG` aborts with a message about a singular iterator, and MSVC's iterator debugging does something similar. These are tools to find the bug, not a promise that the program is defined without them.

## What to remember

- Ask three questions: did elements move, did an element die, did the structure for finding elements change?
- `vector`: reallocation kills everything; otherwise only iterators and references at or after the change, and `end()`.
- `deque`: end insertion kills iterators but not references; erasing the first or last element is gentle; the middle kills everything.
- Node containers: insertion invalidates nothing; erase invalidates only the erased elements.
- Unordered containers: a rehash kills iterators but not references or pointers.
- `string` is conservative; `swap` and move keep iterators valid and moved to the other container, except `array`.
- `end()` is not an element, so most guarantees do not cover it. Do not cache it across modifications.
- In erase loops use the iterator that `erase` returns, or call `std::erase_if`.
- Using an invalidated iterator is undefined behavior even if it appears to work.

## Concept Map Outline

- **Iterator invalidation:** An iterator dies when storage or navigation structure changes; derive the rules from the layout.
  - **Three questions:** Ask: did elements move, did one die, did the structure used to find elements change.
    - **Singular state:** An invalidated iterator may only be assigned to or destroyed; any other use is undefined.
    - **Iterators vs references:** Iterators also depend on index structures, so they can die while references survive.
  - **vector:** Contiguous storage: reallocation moves everything, shifting moves the tail.
    - **Reallocation:** When size would exceed capacity, all iterators, pointers, references and end() are invalidated.
    - **No reallocation:** Insert or erase invalidates iterators and references at or after the change, plus end().
    - **reserve guarantee:** After reserve(n), appends up to capacity do not reallocate, so earlier iterators survive.
  - **deque:** Blocks plus an index: asymmetric rules for iterators and references.
    - **End insertion:** Push at either end invalidates all iterators including end(), but no references or pointers.
    - **Erase at an end:** Erasing the first (not last) element hits only that element; erasing the last also kills end().
    - **Middle edit:** Any insertion or erasure in the middle invalidates all iterators and references.
  - **Node containers:** list, forward_list, set, map and multi versions never move elements.
    - **Insert:** Insertion invalidates nothing.
    - **Erase:** Only iterators and references to the erased elements are invalidated; end() survives.
    - **splice:** Iterators remain valid but now belong to the destination list.
  - **Unordered containers:** Stable nodes, rebuildable bucket array.
    - **Rehash:** A rehash invalidates all iterators but not pointers or references to elements.
    - **No rehash:** Insertion without rehash invalidates nothing; erase affects only erased elements.
  - **Special cases:** Swap, move, string and end() need separate care.
    - **swap and move:** Iterators stay valid and refer into the other container; array swap exchanges values instead.
    - **string:** Conservative: almost any non-const member may invalidate; operator[], at, data and iterator getters do not.
    - **Erase loops:** Use it = c.erase(it) or std::erase_if; never reuse the erased iterator.

## Standardese Quiz Questions

### Question 1 [warmup] ([vector.capacity], [vector.modifiers])

What does the standard say about this program?

```cpp
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{1, 2, 3};
  v.reserve(100);
  auto it = v.begin();
  v.push_back(4);
  std::cout << *it << '\n';
}
```

A. It prints 1
B. Undefined behavior: `push_back` invalidates all iterators
C. It prints 4
D. Implementation-defined

**Answer (A):** It prints 1

**Why:** After `reserve(100)`, no reallocation takes place until the size would exceed the capacity. Appending a fourth element therefore leaves every iterator before the insertion point valid, so `it` still refers to the element 1. Only `end()` is invalidated. The second option would be right if `push_back` had to reallocate.

### Question 2 [warmup] ([list.modifiers], [container.reqmts])

What does this program print?

```cpp
#include <iostream>
#include <iterator>
#include <list>

int main() {
  std::list<int> l{1, 2, 3};
  auto a = l.begin();
  auto b = std::next(a);
  auto c = std::next(b);
  l.erase(b);
  std::cout << *a << ' ' << *c << '\n';
}
```

A. Undefined behavior: `erase` invalidates every iterator
B. Undefined behavior: `erase` invalidates iterators after the erased element
C. 1 3

**Answer (C):** 1 3

**Why:** `list` has one node per element and erasing one node touches only its neighbours' links. Only iterators and references to the erased element are invalidated, so `a` and `c` are still valid and the output is `1 3`. The other options describe `vector::erase`, where elements after the erase point shift.

### Question 3 [warmup] ([vector.modifiers], [stmt.ranged])

What does the standard say about this program?

```cpp
#include <vector>

int main() {
  std::vector<int> v{1, 2, 3};
  for (int x : v)
    if (x == 2) v.push_back(4);
}
```

A. It visits 1, 2, 3 and then 4
B. Undefined behavior: the loop's cached `end()` iterator is invalidated
C. It visits 1, 2, 3 and stops, because the range was fixed on entry
D. Ill-formed: a container cannot be modified inside a range-for

**Answer (B):** Undefined behavior: the loop's cached `end()` iterator is invalidated

**Why:** A range-for evaluates `begin()` and `end()` once, then keeps using those iterators. `push_back` invalidates `end()` even when it does not reallocate, and invalidates every iterator when it does, so the loop increments and compares invalidated iterators. The third option is the intuition the standard does not back, and the fourth is wrong because the code compiles.

### Question 4 [tricky] ([deque.modifiers])

What does the standard guarantee this program prints?

```cpp
#include <deque>
#include <iostream>

int main() {
  std::deque<int> d{1, 2, 3, 4};
  auto it = d.begin() + 2;  // refers to 3
  d.erase(d.begin());
  std::cout << *it << '\n';
}
```

A. 4
B. Unspecified
C. Undefined behavior: erase invalidates all deque iterators
D. 3

**Answer (D):** 3

**Why:** Erasing the first element of a `deque` (but not the last) invalidates only iterators and references to the erased element, because the other elements do not move. `it` still refers to the element 3. The third option is the rule for erasing in the middle, where every iterator is invalidated; the first imagines elements shifting down as in a `vector`.

### Question 5 [tricky] ([unord.req], [container.reqmts])

Which of the two uses after `reserve` is valid?

```cpp
#include <iostream>
#include <unordered_map>

int main() {
  std::unordered_map<int, int> m{{1, 10}};
  auto it = m.find(1);
  int& r = it->second;
  m.reserve(1000);
  std::cout << r << '\n';          // use A
  std::cout << it->second << '\n'; // use B
}
```

A. Both
B. Only A
C. Only B
D. Neither

**Answer (B):** Only A

**Why:** `reserve` may rehash, and a rehash invalidates all iterators but not pointers or references to elements, because the elements live in nodes that are not moved. Use A is valid and use B is undefined behavior. The tempting answer "Both" assumes that if the element survives, the iterator does too.

### Question 6 [tricky] ([container.reqmts])

What does the standard guarantee this program prints?

```cpp
#include <iostream>
#include <vector>

int main() {
  std::vector<int> a{1, 2, 3}, b{4, 5};
  auto it = a.begin();
  a.swap(b);
  std::cout << *it << ' ' << (it == b.begin()) << '\n';
}
```

A. 4 0
B. 1 0
C. 1 1
D. Undefined behavior: swap invalidates iterators

**Answer (C):** 1 1

**Why:** Unless a container says otherwise, `swap` invalidates no references, pointers or iterators to elements; they keep referring to the same elements, which now belong to the other container. So `it` still names the element 1, which is now the first element of `b`, and the comparison is true. `std::array` is the exception, since its swap exchanges elements.

### Question 7 [standardese] ([vector.modifiers])

After the erase, which of the iterators `a` and `c` may the program still use?

```cpp
#include <vector>

int main() {
  std::vector<int> v{1, 2, 3, 4};
  [[maybe_unused]] auto a = v.begin();
  auto b = a + 1;
  [[maybe_unused]] auto c = a + 2;
  v.erase(b);
}
```

A. Only `a`
B. Both `a` and `c`
C. Only `c`
D. Neither

**Answer (A):** Only `a`

**Why:** `vector::erase` invalidates iterators and references at or after the point of the erase. `a` precedes it and stays valid; `c` is after it, so using `c` is undefined behavior even though, on typical implementations, it would point at the element 4. The shifted element is what makes "Both" tempting.

### Question 8 [standardese] ([container.reqmts])

What does the standard guarantee this program prints?

```cpp
#include <iostream>
#include <utility>
#include <vector>

int main() {
  std::vector<int> v{1, 2, 3};
  int* p = v.data();
  std::vector<int> w = std::move(v);
  std::cout << *p << ' ' << (p == w.data()) << '\n';
}
```

A. Undefined behavior: the moved-from vector released its storage
B. 1 0, because the elements were copied
C. 1 1
D. Unspecified

**Answer (C):** 1 1

**Why:** The container requirements say that, apart from `array`, no move constructor invalidates references, pointers or iterators (other than `end()`) into the source. They keep referring to the same elements, which now belong to `w`. So `p` is valid and equals `w.data()`. The moved-from `v` itself is left in a valid but unspecified state, which is a separate matter from its former elements.
