# Containers, memory layouts, and iterator invalidation

> How physical memory layouts dictate pointer, reference, and iterator invalidation across vector, deque, list, node-based maps, unordered hash tables, and C++23 flat_map.

- **Source:** C++ Atlas (https://cppatlas.com/topics/containers-and-iterator-invalidation)
- **Track:** Containers and strings
- **Estimated reading time:** 9 minutes
- **ISO C++ clauses:** [container.requirements] (https://eel.is/c++draft/container.requirements), [sequence.reqmts] (https://eel.is/c++draft/sequence.reqmts), [vector.modifiers] (https://eel.is/c++draft/vector.modifiers), [deque.modifiers] (https://eel.is/c++draft/deque.modifiers), [associative.reqmts] (https://eel.is/c++draft/associative.reqmts), [unord.req] (https://eel.is/c++draft/unord.req), [flat.map] (https://eel.is/c++draft/flat.map)
- **cppreference links:** [Containers library](https://en.cppreference.com/w/cpp/container), [std::vector](https://en.cppreference.com/w/cpp/container/vector), [std::deque](https://en.cppreference.com/w/cpp/container/deque), [std::list](https://en.cppreference.com/w/cpp/container/list), [std::map](https://en.cppreference.com/w/cpp/container/map), [std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map), [std::flat_map](https://en.cppreference.com/w/cpp/container/flat_map), [std::vector<bool>](https://en.cppreference.com/w/cpp/container/vector_bool), [Container (named requirement)](https://en.cppreference.com/w/cpp/named_req/Container), [ContiguousContainer (named requirement)](https://en.cppreference.com/w/cpp/named_req/ContiguousContainer)
- **Prerequisites:** object-lifetime-and-storage, copy-and-move, smart-pointers-and-allocators

Iterator invalidation rules are not arbitrary library trivia—they fall straight out of each container's physical memory layout. Once you separate **pointer/reference stability** (whether elements stay at the same address) from **iterator stability** (whether traversal handles remain valid), you can predict invalidation guarantees on demand.

## Why physical layout predicts invalidation

Standard containers organize memory using four distinct strategies:

1. **Single contiguous buffer** (`std::vector`, `std::string`, `std::flat_map`): elements occupy adjacent slots in one heap array; growing capacity or shifting mid-array relocates elements in memory.
2. **Spine of fixed-size chunks** (`std::deque`): a central pointer table addresses fixed-size contiguous pages; appending at either end grows the spine without relocating existing elements.
3. **Linked heap nodes** (`std::list`, `std::forward_list`, `std::map`, `std::set`): every element lives inside its own heap node linked by pointers, so elements never relocate until erased.
4. **Bucket pointer array plus linked nodes** (`std::unordered_map`, `std::unordered_set`): elements live in individual heap nodes, while a contiguous bucket array indexes node chains.

> **Mental model.** Ask two questions before mutating a container: does the operation move existing elements to new addresses (invalidating pointers and references), and does it rewrite traversal metadata or sentinel slots (invalidating iterators)?

## Contiguous sequences and the reallocation cliff

In `std::vector`, `push_back` or `emplace_back` behaves differently depending on spare capacity. When `size() < capacity()`, appending writes into uninitialized tail storage and invalidates **only** `end()`; every existing iterator, pointer, and reference remains valid. When `size() == capacity()`, reallocation allocates a larger buffer, relocates elements via `std::move_if_noexcept`, frees the old array, and invalidates **all** iterators, pointers, and references. Remember that `std::move_if_noexcept` silently falls back to copying if a type's move constructor lacks `noexcept` and its copy constructor is available, preserving the strong exception guarantee.

Inserting or erasing in the middle of a `vector` without reallocation shifts trailing elements, invalidating iterators, pointers, and references at and after the modified index (plus `end()`). Beware the self-aliasing boundary in `[sequence.reqmts]`: single-element insertion or append from the same container (`v.push_back(v[0])`) is **guaranteed** to work even across reallocation, whereas inserting an iterator range from the same container (`v.insert(v.end(), v.begin(), v.end())`) is undefined behavior!

`std::vector<bool>` is a bit-packed space optimization rather than a true `ContiguousContainer`. Its `operator[]` returns a proxy `std::vector<bool>::reference` object instead of `bool&`, breaking reference binding and hiding a dangling pointer hazard.

> **Pitfall.** Writing `auto flag = flags[0];` on a `std::vector<bool>` deduces `flag` as a proxy `reference` rather than `bool`. If `flags` reallocates or leaves scope, inspecting `flag` later triggers use-after-free; always annotate `bool flag = flags[0];` when copying out a bit.

## Deque: chunked blocks and pointer stability

`std::deque` maintains a dynamic array of pointers (the spine) pointing to fixed-size contiguous blocks. Because pushing at either end allocates a new block when needed and only reallocates the **spine**—never copying existing elements—`std::deque` splits iterator validity from pointer and reference validity.

Under `[deque.modifiers]`, `push_back`, `push_front`, `emplace_back`, and `emplace_front` invalidate **all iterators** (because deque iterators cache pointers into the spine array), yet **preserve all pointers and references** to existing elements. Erasure at the boundaries is even more surgical: `pop_front` (or erasing the first element when `size() > 1`) invalidates only iterators and references to the erased element while leaving `end()` intact; `pop_back` (or erasing the last element) invalidates only handles to the erased element and `end()`. Inserting or erasing anywhere in the middle invalidates **all** iterators, pointers, and references to every element in the deque.

## Node containers, rehashing, and node handles

Tree and list containers (`std::list`, `std::forward_list`, `std::map`, `std::set`, `std::multimap`, `std::multiset`) allocate each element in a standalone node. Inserting elements **never** invalidates any iterator, pointer, or reference, and erasing invalidates **only** handles pointing to erased nodes.

Unordered hash containers (`std::unordered_map`, `std::unordered_set`) combine a dynamic bucket pointer array with linked element nodes. Erasing an element invalidates only handles to that erased node. When insertion pushes `size() > max_load_factor() * bucket_count()`, or when `rehash()` or `reserve()` expands the bucket array, hash tables rebuild their bucket table—invalidating **all iterators** while keeping every element pointer and reference valid!

C++17 introduced `extract()` and `merge()` via `node_type` handles, letting you unlink a node from one `map` or `unordered_map` and transplant it into another with zero key/value copies or moves. Extracting invalidates iterators to the removed element, while pointers and references to that element stay valid once reinserted. For safe conditional deletion, prefer C++20 `std::erase` and `std::erase_if` over manual loop-and-erase boilerplate.

> **Standardese.** Under `[unord.req]`, rehashing an unordered associative container invalidates all iterators and may reorder elements across buckets, yet references and pointers to elements in the container remain valid.

```cpp
#include <deque>
#include <flat_map>
#include <unordered_map>
#include <vector>

void invalidation_patterns() {
    std::vector<int> vec{1, 2, 3};
    vec.push_back(vec[0]); // Well-defined self-aliasing even if vec reallocates

    std::deque<int> dq{10, 20, 30};
    int& front_ref = dq.front();
    dq.push_back(40); // Invalidates ALL iterators, yet front_ref remains valid!
    (void)front_ref;

    std::unordered_map<int, int> umap{{1, 100}};
    int& mapped_ref = umap.at(1);
    umap.rehash(64); // Invalidates ALL iterators, yet mapped_ref remains valid!
    (void)mapped_ref;

    auto node = umap.extract(1); // Moves node without copying key or value
    std::unordered_map<int, int> dest;
    dest.insert(std::move(node));

    std::flat_map<int, int> fmap{{2, 20}, {1, 10}};
    std::erase_if(fmap, [](const auto& kv) { return kv.first == 1; });
}
```

## C++23 flat_map and flat_set trade-offs

C++23 `<flat_map>` and `<flat_set>` are container adaptors storing keys and mapped values in parallel sorted contiguous sequences (typically two `std::vector` objects) instead of heap-allocated tree nodes. Searching benefits from hardware prefetching and zero per-node pointer overhead, making lookup and iteration dramatically faster on small-to-medium maps.

That contiguous layout comes with two costs: single-element `insert` and `erase` run in O(N) time by shifting trailing entries, and—like `std::vector`—any insertion or erasure may invalidate **all** iterators, pointers, and references across the entire container.

> **Pitfall.** Replacing `std::map` with `std::flat_map` silently removes pointer and reference stability. Code that saves `&cache[key]` before inserting another key compiles identically and turns into a dangling pointer on the next insertion.

Invalidation behavior across the major standard container families lines up cleanly with their backing storage:

| Container | Insert / Push (No Growth) | Reallocate / Rehash | Erase |
| --- | --- | --- | --- |
| `std::vector` | Only `end()` on `push_back`; `[pos, end()]` on mid-insert | All iterators, pointers, and references | `[pos, end()]` |
| `std::deque` | At ends: all iterators; pointers & refs stay valid | Middle insert: all iterators, pointers, and refs | Ends: erased (+ `end()` at back); middle: all |
| `std::list` / `std::map` | None | N/A (node-based) | Erased element(s) only |
| `std::unordered_map` | None (unless load factor triggers rehash) | All iterators; pointers & refs stay valid | Erased element(s) only |
| `std::flat_map` | All iterators, pointers, and references | All iterators, pointers, and references | All iterators, pointers, and references |

## What to remember

- Distinguish **iterator** invalidation from **pointer and reference** invalidation: `std::deque::push_back` and `std::unordered_map::rehash` invalidate every iterator while keeping element addresses intact.
- In `std::vector`, reallocation invalidates everything, non-reallocating `push_back` invalidates only `end()`, and range `insert` from `[i, j)` into the same `vector` is undefined behavior even though `v.push_back(v[0])` is valid.
- Mark element move constructors `noexcept` so `std::vector` growth can move instead of copying via `std::move_if_noexcept`, and never capture `std::vector<bool>` elements with `auto`.
- Use `extract()` and `merge()` to relocate nodes between associative or unordered containers without copying keys or values, and reach for `std::erase_if` for safe predicate erasure.
- Treat C++23 `std::flat_map` and `std::flat_set` like `std::vector` for invalidation: any insertion or deletion can invalidate every iterator, pointer, and reference.

## Concept Map Outline

- **Containers & invalidation:** Physical memory layout directly predicts iterator, pointer, and reference invalidation.
  - **Contiguous buffers (vector):** One heap array maximizes cache locality while reallocation moves every element.
    - **Reallocation invalidates everything:** Growing capacity invalidates all iterators, pointers, and references.
    - **push_back within capacity:** When capacity suffices, appending invalidates only the past-the-end iterator.
    - **move_if_noexcept growth guard:** Missing noexcept on move constructors forces vector reallocation to copy.
    - **vector<bool> proxy reference:** operator[] returns a bit-proxy rather than bool&, dangling if deduced via auto.
  - **Chunked blocks (deque):** A spine of fixed pages lets ends grow without moving existing elements.
    - **Ends keep pointers & refs:** push_back and push_front preserve pointers and references to existing elements.
    - **Ends invalidate all iterators:** Spine reallocation invalidates every deque iterator on push_back or push_front.
    - **Middle insert or erase:** Modifying interior positions invalidates all iterators, pointers, and references.
  - **Node-based trees & lists:** Standalone heap nodes give complete stability across insertions and other erasures.
    - **Insertions never invalidate:** Adding nodes preserves all iterators, pointers, and element references.
    - **Erasures isolate removed node:** Erasing invalidates only iterators, pointers, and references to removed elements.
    - **C++17 extract & merge:** Transfers heap nodes between maps without copying or moving keys and values.
  - **Unordered hash tables:** Bucket array plus linked nodes separates iterator invalidation from node addresses.
    - **Rehash invalidates iterators only:** Growing bucket tables invalidates all iterators while keeping node pointers valid.
    - **Erasure preserves siblings:** Removing a bucket entry invalidates only handles to the erased element.
  - **C++23 flat_map & erasure:** Sorted parallel contiguous arrays trade node stability for cache speed.
    - **Any mutation invalidates handles:** Insertions and erasures shift contiguous slots, invalidating all pointers and iterators.
    - **Uniform C++20 std::erase_if:** Safely deletes matching elements across sequence and associative containers.

## Standardese Quiz Questions

### Question 1 [warmup] ([unord.req])

A std::unordered_map<int, Widget> triggers a rehash during emplace(). Which handles to existing elements remain valid?

A. All iterators, pointers, and references remain valid
B. All iterators are invalidated, while pointers and references to existing elements remain valid
C. Iterators remain valid, while pointers and references become dangling
D. All iterators, pointers, and references are invalidated

**Answer (B):** All iterators are invalidated, while pointers and references to existing elements remain valid

**Why:** Rehashing rebuilds the bucket array and may change element iteration order, invalidating every iterator ([unord.req]). Because elements live in individually allocated nodes that are relinked rather than relocated, pointers and references to elements stay valid.

### Question 2 [warmup] ([vector.modifiers])

A std::vector<int> holds 5 elements with capacity() == 16, and you call v.push_back(42);. Which existing handles are invalidated?

A. Only the past-the-end iterator (v.end()); existing element iterators, pointers, and references remain valid
B. All iterators, pointers, and references, including v.begin()
C. None at all, including v.end()
D. Only pointers and references to v.back()

**Answer (A):** Only the past-the-end iterator (v.end()); existing element iterators, pointers, and references remain valid

**Why:** Under [vector.modifiers], if no reallocation occurs (size() < capacity()), push_back invalidates only the past-the-end iterator (end()), leaving iterators, pointers, and references to all pre-existing elements valid.

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

In the snippet below, what happens to it and ref after dq.push_back(40) executes?

```cpp
std::deque<int> dq{10, 20, 30};
auto it = dq.begin();
int& ref = dq.front();
dq.push_back(40);
```

A. Both it and ref remain valid unless the spine reallocates
B. Both it and ref are guaranteed to be invalidated
C. it is invalidated (even if existing elements didn't move), whereas ref remains valid and still refers to 10
D. ref is invalidated, whereas it remains valid

**Answer (C):** it is invalidated (even if existing elements didn't move), whereas ref remains valid and still refers to 10

**Why:** Under [deque.modifiers], push_back and push_front invalidate all iterators to the deque (because deque iterators reference the spine array), yet have no effect on the validity of references or pointers to existing elements.

### Question 4 [tricky] ([vector.bool])

What happens when compiling and running the following snippet using std::vector<bool>?

```cpp
std::vector<bool> flags{true, false};
auto b = flags[0];
flags.assign(1000, false);
bool val = b;
```

A. Well-defined: val is true because auto deduced bool
B. Fails to compile because std::vector<bool>::operator[] returns void
C. Well-defined: flags.assign updates b to false automatically
D. Undefined behavior: auto b deduced a proxy std::vector<bool>::reference pointing into the old buffer freed by flags.assign(...)

**Answer (D):** Undefined behavior: auto b deduced a proxy std::vector<bool>::reference pointing into the old buffer freed by flags.assign(...)

**Why:** std::vector<bool> returns a bit-proxy reference class from operator[] rather than bool& ([vector.bool]). auto b = flags[0] stores that proxy pointing into flags's bit-word storage; once flags.assign(1000, false) reallocates, b dangles and bool val = b; exhibits undefined behavior.

### Question 5 [standardese] ([sequence.reqmts])

Compare v.push_back(v[0]); vs v.insert(v.end(), v.begin(), v.end()); on a non-empty std::vector<int> v at full capacity (v.size() == v.capacity()). What does the C++ standard say?

```cpp
std::vector<int> v{1, 2, 3};
v.shrink_to_fit();
// Case 1: v.push_back(v[0]);
// Case 2: v.insert(v.end(), v.begin(), v.end());
```

A. Both Case 1 and Case 2 are undefined behavior when v reallocates
B. Both Case 1 and Case 2 are guaranteed to succeed since C++11
C. Case 1 (v.push_back(v[0])) is well-defined and must handle self-aliasing, whereas Case 2 (v.insert with iterators into *this) is undefined behavior
D. Case 2 is well-defined, whereas Case 1 is undefined behavior

**Answer (C):** Case 1 (v.push_back(v[0])) is well-defined and must handle self-aliasing, whereas Case 2 (v.insert with iterators into *this) is undefined behavior

**Why:** Since C++11 ([sequence.reqmts]), single-element insertion/append (push_back(v[0]) or insert(pos, x)) must work even when x aliases an element inside *this during reallocation. Conversely, range insert(p, i, j) carries the precondition that i and j are not iterators into *this—making Case 2 undefined behavior.

### Question 6 [standardese] ([deque.modifiers])

According to [deque.modifiers], if dq has 4 elements and you call dq.pop_front(), which iterators and references are invalidated?

A. All iterators to dq, including dq.end(), plus references to the first element
B. Only iterators and references to the erased first element (dq.end() and all other elements' iterators/references remain valid)
C. All iterators and references to every element in dq
D. Only dq.end() and dq.begin()

**Answer (B):** Only iterators and references to the erased first element (dq.end() and all other elements' iterators/references remain valid)

**Why:** Under [deque.modifiers], erasing at the beginning (pop_front() or erase starting at begin(), provided the last element is not also erased) invalidates only iterators and references to the erased elements—preserving dq.end() and all other iterators and references. (By contrast, pop_back() also invalidates dq.end().)
