C++ STL Interview Questions: Iterator Invalidation, Containers, and Complexity

C++ STL interview questions test whether your container choice stays correct after the next mutation. Knowing that a vector offers fast indexed access is not enough if a later append invalidates the pointer you saved. The important contract combines complexity, ownership, and iterator validity.

This guide uses a C++17 baseline for familiar containers and labels C++20 conveniences where mentioned. The traces are original exercises, and the standard-library rules are checked against specification and vendor documentation. Do not treat one implementation's capacity growth or one successful run of undefined behavior as a portable guarantee.

Here, we concentrate on mutation: what remains valid, what becomes stale, and how to choose a data structure from the actual workload.

What is iterator invalidation?

An iterator is a position-like object used to traverse a range. Container operations can make an existing iterator no longer valid for subsequent operations. References and pointers to elements have related but not always identical invalidation rules, and the past-the-end iterator deserves separate attention.

Invalidation is not the same as an iterator being automatically set to null. The stored bits may look unchanged. Dereferencing an invalid iterator can appear to work until a different allocation pattern, compiler build, or input exposes the bug.

Start an interview answer by naming the container and operation. "Insertion invalidates iterators" is too broad: vector reallocation, list insertion, and unordered-map rehash have different contracts. Also say whether you mean iterators, element references, pointers, or end().

Use a small ownership inventory before each mutation: which handles exist, which elements they designate, and what operation is about to occur. Then apply the documented rule. This method is more reliable than memorizing one sentence per container.

What happens when vector grows?

For vector insertion that reallocates storage, existing element pointers, references, and iterators are invalidated. Without reallocation, handles before the insertion point remain valid, while those at or after it are invalidated. The past-the-end iterator changes as the size changes.

An original trace makes the distinction concrete. Assume a vector has size three and capacity four, holding [10,20,30]. Save a pointer to the first element and save end(). Appending 40 fits the existing capacity: the element pointer remains valid, but the old end iterator does not.

Now append 50. Capacity is insufficient, so reallocation occurs and the old element pointer becomes invalid too. Do not guess the new capacity: the growth factor is an implementation choice, not a universal "always doubles" rule.

The values may still be [10,20,30,40,50], which makes this bug easy to miss in value-only tests. Correct contents do not imply that previously saved handles remain usable.

Does reserve make all vector mutations safe?

No. reserve controls capacity, not every invalidation rule. It does not change size, construct new elements for indexing, or make insertion and erase at arbitrary positions preserve all handles. If reserve itself increases capacity, it invalidates existing handles through reallocation.

std::vector<int> values;
values.reserve(100);
// values[0] = 7;  // invalid: size is still zero
values.push_back(7);

Use resize when you need the vector to contain a specified number of elements, subject to the element type's construction requirements. Use reserve to avoid unnecessary reallocations when an expected final size is known.

Consider a vector with ample spare capacity and insert at the beginning. Existing elements shift, so handles at or after that insertion point still become invalid. A capacity argument does not defeat the operation's positional effects.

Also avoid calling reserve(size()+1) before every append as a supposed optimization. Forcing tightly increasing capacities can undermine amortized growth and create unnecessary reallocations. Reserve from a meaningful workload estimate, then measure if capacity management is actually a bottleneck.

How do I erase while iterating correctly?

Use the iterator returned by erase rather than incrementing an invalidated one. For vector, erase invalidates iterators and references at or after the erased position, including the old end iterator.

for (auto it = values.begin(); it != values.end(); ) {
    if (*it < 0) {
        it = values.erase(it);
    } else {
        ++it;
    }
}

This loop is clear, but repeated middle erases can require repeated shifting and become quadratic. Correctness and efficiency are separate questions. For bulk filtering, the erase-remove idiom can compact survivors in one pass before one final erase:

values.erase(
    std::remove_if(values.begin(), values.end(),
                   [](int x) { return x < 0; }),
    values.end());

Include <algorithm> for remove_if. It rearranges elements and returns a new logical end; it does not reduce the container's size by itself. The final erase removes the trailing range. C++20 provides std::erase_if overloads for a more direct spelling on supported containers.

For an original fixture [4,-1,-2,7], test adjacent rejected values. A buggy increment-after-erase loop often skips one of them. Also test all rejected, none rejected, and an empty vector. These cases expose the control-flow error without requiring a large benchmark.

Which container preserves the handles I need?

Choose from the exact operations, not a slogan about arrays and linked lists. This compact table captures common cases; consult the full contract for less common operations such as swap, assignment, or allocator-sensitive moves.

Container and operation	Iterator effect	Element reference/pointer effect
vector reallocation	All invalidated	All invalidated
vector erase	At/after position invalidated	At/after position invalidated
list insertion	Existing iterators preserved	Existing elements preserved
list erase	Erased element invalidated	Erased element invalidated
unordered_map rehash	Iterators invalidated	References/pointers to elements preserved
map insertion	Existing iterators preserved	Existing elements preserved

Node-based containers can preserve handles across operations that would move vector elements, but they bring allocation overhead and different locality. A list is not automatically faster just because insertion is constant time once the position is known.

If the workload repeatedly finds an item by index and then inserts nearby, the cost of finding that position matters. A linked list's traversal may dominate. State the whole operation, not only the final pointer update.

Why can unordered_map rehash break a loop without destroying elements?

Rehash reorganizes the bucket structure and invalidates iterators, while references and pointers to existing elements remain valid under the standard contract. An iterator carries traversal assumptions that are different from an element's continued existence.

Suppose you iterate an unordered map and insert missing keys during the loop. An insertion can trigger rehash, invalidating the loop iterator. Even if rehash does not occur in a particular test, you still need a deliberate policy about whether newly inserted entries should be visited.

A safer design often collects pending insertions separately and applies them after traversal. Alternatively, choose an operation and capacity strategy whose guarantees fit a carefully specified algorithm. Reserving enough capacity can address rehash risk in a bounded case, but does not answer the semantic question of what the traversal should include.

Do not describe average constant-time lookup as worst-case constant time. Hash quality, collisions, load factor, and input distribution matter. An interview answer should state expected versus worst-case complexity and avoid assuming that every key type has a cheap, well-distributed hash.

How should I compare vector, deque, list, and map?

Begin with the workload: indexed reads, ordered traversal, front/back insertion, arbitrary erase, key lookup, stable handles, and memory footprint. Then identify the operations that dominate and the invariants that cannot be compromised.

A vector is a strong default for contiguous storage and indexed access. A deque supports efficient operations at both ends, but its iterator invalidation rules differ from vector's and its storage is not one contiguous array. A list supports stable node handles for many operations, but indexed access requires traversal.

Ordered associative containers provide key ordering and logarithmic lookup/insertion in their standard complexity contracts. Unordered containers provide average constant-time key operations under suitable conditions, without a sorted iteration order. Neither is universally better.

An original scenario: a dashboard repeatedly scans every item and occasionally appends a batch. Vector locality may be attractive. Change the requirement to stable references with frequent erasure of known nodes, and the design discussion changes. Change it again to lookup by ID, and a separate index may matter more than the sequence container.

The best answer names what you are optimizing and what you are giving up. "Use a hash map because it is O(1)" is not enough when the output must be sorted and the workload performs full scans.

Which complexity claims need qualifications?

Vector append is amortized constant time, not constant time for every call. Reallocation can move or copy existing elements. Erasing near the beginning shifts more survivors than erasing the last element. A costly element operation changes practical performance even when the container's operation count is familiar.

List insertion is constant time once you have the position; finding the nth element is linear. Ordered-map lookup is logarithmic in comparisons, but comparisons may themselves be expensive. Unordered-map lookup includes hashing and equality work, not just a magic array access.

Sorting a vector of large records may be more expensive than sorting lightweight handles, but indirection can harm locality elsewhere. Do not optimize one phase without considering the rest of the pipeline and ownership lifetime.

For a performance follow-up, propose a representative benchmark with realistic element size, mutation frequency, and access pattern. Report latency distributions or throughput as appropriate, and verify identical results. Microbenchmarks with integers do not automatically settle a workload involving strings, allocation, and cache misses.

How can I catch invalid-iterator bugs?

Compiler and library debug modes can detect some misuse. Microsoft's debug iterator support is one example. Sanitizers can reveal memory errors caused by stale pointers or iterators, but no single tool detects every logical invalidation case.

In particular, an invalid iterator may still point into allocated memory, so absence of an address-sanitizer report is not proof of validity. The documented container contract remains the primary reasoning tool.

Construct tests that force the relevant transition. For reallocation, observe capacity and append beyond it instead of assuming a fixed initial capacity. For erase, keep handles before, at, and after the erased position and reason about which may legally be used afterward.

Do not deliberately dereference invalid handles merely to see whether they crash and then treat that observation as a test oracle. A good test validates a corrected implementation's observable result. Use instrumentation and debug modes to assist diagnosis, not to redefine undefined behavior as reliable behavior.

What is a strong answer to a mutation-heavy exercise?

Try this prompt: maintain a collection of jobs, remove cancelled jobs, append newly discovered jobs, and produce a stable priority-sorted report. First define whether appended jobs belong to the current pass or the next pass. Then define what makes priorities tie and whether external code holds handles to jobs.

One possible design separates phases: compact survivors, append the new batch, then sort a reporting view with an explicit tie-break. If external handles must remain stable, store ownership separately or use a representation that supports that requirement. Do not silently invalidate clients' references for a faster local loop.

Write a fixture with adjacent cancellations, no survivors, a large appended batch, and tied priorities. Check both values and the promised handle/identity behavior. A correct report with dangling external pointers is still a broken design.

When you can explain all five for the same small example, you are reasoning about the STL rather than reciting it.

Sources and Further Reading

Checked September 23, 2026. C++17 is the article baseline; C++20 conveniences are labeled and implementation-specific observations are not presented as guarantees.

• C++ working draft: vector modifiers and invalidation
• C++ working draft: unordered associative container requirements
• Microsoft: debug iterator support