skip to content

After an insert into a C++ std::vector, std::deque, std::list or std::map, which existing iterators and references stay valid?

level: middleimportance: must knowfreq 66%

answer

  1. contiguous versus node-based
  2. iterators and references can differ
  3. deque ends: references survive
  4. node containers never move elements

basics

~10 s

std::list and std::map insertion leaves every iterator and reference valid. std::vector keeps those before the insertion point unless it reallocates. std::deque invalidates all iterators, but insertion at either end keeps references valid.

solid answer

~40 s

The rules follow from how each container stores elements. `std::list`, `std::forward_list`, `std::map`, `std::set` and their multi variants are node-based: inserting links a new node and never moves existing ones, so no iterator or reference is invalidated, and erasing invalidates only the erased element. `std::vector` is contiguous: an insert that exceeds capacity reallocates and invalidates everything; otherwise iterators and references before the insertion point survive, while those at or after it, including `end()`, do not. `std::deque` splits the two: an insert in the middle invalidates all iterators and references, while an insert at either end invalidates all iterators but keeps references to elements valid. The hash containers may rehash on insert, which invalidates iterators but never references.

go deeper

for a junior

Recall the split: node containers like list and map keep iterators on insert, vector may move everything, deque sits in between.

for a middle

State each container's rule precisely, including vector's capacity case and deque's iterators-versus-references distinction, and tie each rule back to how the container stores elements.

for a senior

Use the rules when designing a structure that hands out long-lived iterators or pointers: pick a node container, reserve a vector, or store indices or keys instead.

for a principal

Weigh the stability of node containers against the cache and allocation cost they carry when a team defaults to vector, and document which structures promise stable references.

## Invalidation, iterators and references An iterator, pointer or reference into a container is **invalidated** when an operation means it may no longer be used: dereferencing it, incrementing it or comparing it is then undefined behaviour. The standard's default is reassuring: unless a container member function's description says otherwise, calling it does not invalidate iterators. The descriptions that do say otherwise are exactly the insert and erase rules below. Two kinds of handle are tracked separately: - **References and pointers** to an element stay valid as long as that element stays at the same address. - **Iterators** may carry extra state about the container's internal structure, so an operation can invalidate them even when no element moved. A third, easy to forget, is the **past-the-end iterator** returned by `end()`. It refers to no element, so even operations that move nothing can invalidate it. ## The rules by container | container | insert | erase | |---|---|---| | `std::vector` | reallocation: everything, including `end()`; otherwise those at or after the insertion point, including `end()` | iterators and references at or after the erase point | | `std::deque` | middle: all iterators and references; either end: all iterators, but no references | last element: past-the-end plus the erased; first but not last: only the erased; otherwise everything | | `std::list`, `std::forward_list` | nothing | only the erased elements | | `std::map`, `set`, `multimap`, `multiset` | nothing | only the erased elements | | `std::unordered_map` and the other hash containers | a rehash invalidates all iterators, never references | only the erased elements | ## Why each rule looks the way it does 1. **`std::vector` is contiguous.** All elements share one buffer. Growing past `capacity()` means a new buffer, so every handle is stale. Without reallocation, inserting at position `p` shifts every element from `p` onward one slot right, so handles at or after `p` now name a different element or none, while those before `p` are untouched. 2. **`std::deque`, in libc++ and libstdc++, stores elements in fixed-size blocks** reached through an index of block pointers. Adding at either end fills or adds a block without moving existing elements, so references survive, but the index may be rebuilt, so the standard declares every iterator invalidated. An insertion in the middle shifts elements and invalidates both. 3. **Node-based containers allocate each element separately.** `std::list` and the ordered associative containers link a new node in and never move existing ones, so insertion invalidates nothing and erasure invalidates only what was erased. This stability is a real reason to pick them. 4. **Hash containers** keep each element in its own node too, which is why references survive; a rehash only redistributes nodes among buckets, which invalidates iterators. ## Consequences for real code - A `std::map<int, Song>` can hand out iterators or `Song&` references to other components and keep inserting; they stay valid until that element is erased. - A `std::vector<Song>` cannot safely do the same. If other code must refer to elements across insertions, store **indices** or keys, call `reserve` with a hard upper bound and enforce it, or use a node-based container. - A `std::deque<Song>` that only grows at its ends can hand out references or pointers safely, but not iterators. - After any insert into a vector, re-obtain `end()` rather than reusing a saved one; even a non-reallocating insert invalidates it. ## Common mistakes - Treating "invalidated" as all-or-nothing. The deque end-insertion rule, where references survive but iterators do not, is the classic counterexample. - Assuming a vector insert affects only iterators after the new element. Iterators *at* the insertion point and `end()` are invalidated too, and a reallocation takes the earlier ones with it. - Assuming `std::map` insertion can rebalance iterators away. Rebalancing relinks nodes; it never moves elements or invalidates iterators to them. - Testing with a sanitizer only on small inputs: vector bugs appear when capacity runs out, which small tests may never reach. ## What interviewers listen for A strong answer names the contiguous versus node-based split, gives the vector capacity case precisely, separates iterators from references for deque, and mentions that `end()` is the handle most often forgotten. Tying each rule back to the storage layout shows understanding rather than memorisation.

  • Why can a std::deque keep references valid but not iterators after push_front?
    Inserting at either end never moves existing elements, so a reference or pointer to one still refers to the same object. A deque iterator, though, also carries bookkeeping about the internal block structure, which push_front may rebuild, so the standard declares every iterator invalidated even though the elements did not move.
  • Which operation invalidates iterators of a std::list?
    Only removing the element they refer to: `erase`, `pop_front`, `pop_back`, `remove` and similar. Insertion, `splice` within the same list, and `list::sort` keep every iterator and reference valid. That stability is the main reason to choose a node-based container when other code holds iterators long-term.

  • Says every insertion invalidates every iterator in every container
  • Treats iterators and references as always invalidated together
  • Believes std::map insert can invalidate other map iterators
  • Thinks std::deque push_back keeps its iterators valid
  • Says a std::vector insert only affects iterators after the new element