Iterator and Reference Invalidation

Part I · Module 20 · Chapter 20.3 · Iterator and Reference Invalidation

1. What Invalidation Means

An iterator denotes a position in a container. Invalidation is any operation after which that position no longer denotes what it did — because the element moved, because the memory was freed, or because the structure the iterator navigates was rebuilt.

Using an invalidated iterator is undefined behaviour. Not "returns a wrong value", not "throws": undefined, which is a statement about the standard offering no guarantee rather than about what will actually happen. What actually happens is the subject of this chapter.

Three things can be invalidated and they are not the same:

• An iterator, which may carry more than an address — a std::deque's is 16 bytes (Chapter 20.1 §2) and an unordered container's must know its bucket.
• A pointer or reference to an element, which is just an address.
• The past-the-end iterator, which is invalidated by operations that change the size even when nothing else is.

Chapter 19.1 §7 measured a container where the first two answers differ: std::unordered_map invalidates iterators on a rehash and never invalidates references. So "is it invalidated?" has to be asked separately for each.

2. The Rules, In One Place

Module 19 measured these container by container; this is the consolidated form.

vector  push_back/insert/reserve/resize : ALL iterators+refs if capacity changes
vector  erase                           : from the erase point onward
deque   any insert                      : all iterators; refs only at the ends
list    insert                          : nothing;  erase: the erased only
map/set insert                          : nothing;  erase: the erased only
unordered insert                        : iterators on rehash; refs NEVER

Two of those rows need their qualifier read carefully.

std::vector's rule is conditional on a run-time property. "If capacity changes" is not knowable from the type, which is why Chapter 19.1 §5's two probes on the same std::vector<int> gave opposite answers — 4 of 4 elements moved when full, 0 of 4 with spare capacity. The practical reading is to assume invalidation always, because you cannot see the capacity at the call site.

std::deque's insert invalidates all iterators even when no element moves. Chapter 19.1 §5 measured 0 of 4 elements changing address on a deque insertion, and the iterators are still invalid, because the block index may have been reallocated and a deque iterator points into it. This is the clearest case in the library of the two promises genuinely coming apart.

3. A Dangling Pointer Returns the Old Value

std::vector<int> v{11,22,33,44};
v.shrink_to_fit();                 // size == capacity
const int* p = &v[0];
const void* d0 = v.data();
v.push_back(55);                   // reallocates: p now dangles

before push_back: *p = 11 at 0x100de19a0
data() moved: YES
the freed block still holds the bytes, so a read through p is UB
that typically RETURNS 11 rather than crashing

The block was freed, not scrubbed. A read through p is undefined behaviour and the machine will usually hand back 11, because the bytes are still there and the page is still mapped. Nothing crashes, nothing warns, and the program continues with a value that is right by accident.

That is the shape of every bug in this chapter: the undefined behaviour is indistinguishable from correct behaviour on the inputs you tested. Chapter 13.4 §3's point that nothing objects applies, with the additional sting that here the operation which caused it — appending to a vector — looks like a pure addition.

The defence is Chapter 19.1 §13's: hold an index, not a pointer. An index is not an address and reallocation cannot invalidate it.

4. The Erase-In-A-Loop Bug

This is the chapter's central measurement and the most common instance of the problem in real code. The intent is to remove every element equal to 2.

for (auto it = v.begin(); it != v.end(); ++it)
    if (*it == 2) v.erase(it);          // it is invalidated, then incremented

erase returns an iterator and invalidates the one passed in. The loop ignores the return and increments the invalidated iterator. Undefined behaviour, in three lines that read perfectly naturally.

Here it is on two inputs, against a correct version:

A. duplicates SEPARATED by other values
     input                  1 2 3 2 5 2 7   (size 7)
     broken loop            1 3 5 7   (size 4)
     correct loop           1 3 5 7   (size 4)
     -> the broken loop gets the RIGHT answer here.

B. duplicates ADJACENT
     input                  1 2 2 3 2 2 2 7   (size 8)
     broken loop            1 2 3 2 7   (size 5)
     correct loop           1 3 7   (size 3)

On input A the broken loop is correct. On input B it leaves three 2s behind. The mechanism is visible once you follow it: v.erase(it) shifts the tail down one, so the position it referred to now holds what used to be the next element, and ++it steps past that element without examining it. When duplicates are separated, the skipped element is never a 2 and the bug has no effect. When they are adjacent, every second one survives.

So this is not a bug that fails. It is a bug whose failure is data-dependent, and a test written with comfortably-spaced test data passes.

5. No Tool on This Machine Reports It

The obvious response is that this is what sanitizers are for. Measured, across five build configurations:

  BUG                        -O2        ASan       UBSan      libc++ debug
  erase-in-loop (20.3)        silent     silent     silent     silent
  bad comparator (20.6)       CAUGHT     CAUGHT     CAUGHT     CAUGHT

Every configuration ran the broken loop to completion, exited 0, and printed nothing. -O0 likewise.

The reason is mechanical rather than a deficiency. After v.erase(it), the iterator it still points inside the vector's allocated block — the block was not freed and the size merely decreased. AddressSanitizer detects accesses outside allocated regions; this access is inside one. There is no red zone to step on. libc++'s debug hardening checks bounds against size(), and the position is still within bounds. UndefinedBehaviorSanitizer instruments arithmetic and casts, not container invariants.

Contrast the second row, which is Chapter 20.6 §4's invalid comparator. That one is caught by everything, including a libc++ assertion that names the cause outright:

sort.h:603: libc++ Hardening assertion __first != __end failed: Would read out of
bounds, does your comparator satisfy the strict-weak ordering requirement?

ASan reports it as a heap-buffer-overflow, a READ of size 4 0 bytes after an 8000-byte region, from inside __introsort at sort.h:804, and the plain -O2 build dies with exit 138 — SIGBUS.

The difference between the two rows is not how serious the undefined behaviour is. It is whether the violation happens to walk off the end of an allocation. A bad comparator drives std::sort's inner loop past the array bound, which is exactly what ASan exists to see. An invalidated vector iterator stays politely inside the buffer, which is exactly what ASan cannot see.

6. The Three Correct Forms

// 1. adopt the iterator erase returns
for (auto it = v.begin(); it != v.end(); )
    if (*it == 2) it = v.erase(it);
    else          ++it;

// 2. remove-erase: one pass, no per-element shift
v.erase(std::remove(v.begin(), v.end(), 2), v.end());

// 3. C++20
std::erase(v, 2);

adopt erase()'s return : 1 3 5 7   (size 4)
remove + erase (1 pass): 1 3 5 7   (size 4)

Both agree with each other on both inputs — measured above, including the adjacent-duplicate case where the broken loop failed.

Form 1 is the general one: it works for every container, and for std::list and std::map it is the only option since there is no std::remove equivalent that relinks. Note the missing ++it in the for header — the increment has moved into the else, which is the whole fix.

Form 2 is better for the contiguous containers and is the subject of §7. Form 3 is what C++20 added so that nobody has to remember form 2.

The reason form 2 is preferable where available is cost. Form 1 calls erase once per removed element, and each call shifts the entire tail — so removing k elements from n is O(n·k). std::remove compacts the kept elements in a single pass, O(n) total, and then one erase truncates. Chapter 20.4 §1 lists the algorithm among the modifying group, and §7 below measures what it actually does.

7. std::remove Does Not Remove

Form 2 above has a trap of its own, and it is common enough to deserve measuring.

std::vector<int> v{1,2,3,2,5,2,7};
auto newEnd = std::remove(v.begin(), v.end(), 2);

after remove(): size is STILL 7
[begin,newEnd) is the kept range of 4: 1 3 5 7
[newEnd,end) is unspecified leftovers: 5 2 7
after erase(newEnd,end()): size 4

std::remove is an algorithm, and an algorithm has only iterators — it cannot change a container's size, because it has no access to the container. What it does is move the kept elements to the front and return an iterator to one past the last kept one. The container's size is untouched.

So std::remove(v.begin(), v.end(), 2); on its own is a no-op with respect to size, and the tail holds 5 2 7 — values that look entirely real. A later loop over v sees seven elements, four correct and three garbage that happen to be plausible integers. This is the same failure mode as §4 arriving by a different route, and it is why the pairing is called the remove-erase idiom: the two calls are one operation.

std::remove_if has the same contract, and so do std::unique and std::remove_copy's relatives. In C++20, std::erase and std::erase_if do the whole job and should be preferred.

8. Node-Based Containers Are Safe, and That Is Usable

The rules in §2 give std::list, std::map and std::set a much stronger guarantee, and it is worth measuring because it changes what code you are allowed to write.

erased 4 even keys; the iterator to 5 still reads 50
remaining: 1 3 5 7

after 1001 insertions the held iterator still reads 2
size 1004, and nothing was relocated

In the first, a filtered erase removed four of eight map entries while an iterator to a surviving key stayed valid throughout. In the second, a std::list iterator survived 1,001 insertions at both ends.

So in a node-based container you may keep iterators, pointers and references across arbitrary modification, and only erasing that element invalidates them. That is a real design capability: a cache that hands out stable handles, a scheduler holding a position in a queue, an index into keyed data that does not have to be rebuilt. Chapter 19.5 §6 made the same measurement from the container's side.

The filtered-erase loop is still form 1 from §6, because erase still invalidates the iterator you pass it — it is only the other iterators that survive.

9. Range-Based for Evaluates end Once

Chapter 20.1 §5 noted this in passing; it belongs here as a hazard.

for (const auto& x : v) {
    if (x == 2) v.push_back(99);      // UB: the loop's end is already fixed
}

The loop caches begin and end before the first iteration. A push_back that reallocates invalidates both, and the loop keeps running against stale iterators. There is no diagnostic and, for the same reason as §5, probably no sanitizer report either.

The rule is simple and absolute: do not modify a container's size while iterating over it, in a range-based for or otherwise. If you must, collect the changes and apply them after the loop, or use an index-based loop and re-check v.size() each iteration, or use the algorithm that does it in one pass.

10. The Invalidation Table

The past-the-end iterator is additionally invalidated by anything that changes the size, in every container.

11. What to Actually Do

• Do not modify a container's size while iterating over it. The single most useful rule here.
• Adopt the iterator erase returns, and move the ++it into the else.
• Prefer std::erase / std::erase_if (C++20), or the remove-erase idiom before that.
• Never call std::remove without the following erase. Measured: the size was unchanged and the tail held plausible values.
• Inside a vector, hold an index rather than a pointer or iterator across any modification.
• Inside a node-based container, hold iterators freely — the guarantee is real and useful.
• In an unordered container, hold pointers and distrust iterators.
• Assume a vector insertion invalidates, because the capacity is not visible at the call site.
• Do not treat a clean sanitizer run as evidence about this class of bug. Measured: all four were silent.
• Test with adjacent duplicates whenever a filter or dedup is involved.

12. Mistakes Worth Making Once

The broken erase loop. Measured right on one input, wrong on another, silent under every tool. Make it once with both inputs and the lesson sticks.

std::remove without erase. Size unchanged; the tail reads 5 2 7.

push_back inside a range-based for. end was fixed before the first iteration.

Holding &v[0] across an append. Measured: the read returns the old value.

Assuming a std::deque insertion keeps iterators valid because it keeps references valid. It does not; this is the one container where the two rules differ in that direction.

Erasing from a std::map in a range-based for. The other iterators survive, but the loop's own does not — use form 1.

Believing a clean ASan run means the container code is correct. It means nothing crossed an allocation boundary.

Reusing an iterator after insert on a vector you just reserved. reserve itself invalidates everything, which surprises people who think of it as preparation rather than reallocation.

13. Interview Relevance

The frozen curriculum marks this chapter Critical, and the erase-loop question is asked constantly.

"What is wrong with this loop?" — shown the broken form. Name the invalidation, name the fix, and then volunteer the two things that make it dangerous: it is data-dependent, so it can pass a test, and no sanitizer reports it. That second point is unusual enough to be memorable.

"When are std::vector iterators invalidated?" Any operation that can change capacity — push_back, insert, reserve, resize, shrink_to_fit — plus everything from an erase point onward. The strong answer notes the condition is a run-time property, so you assume it always.

"What does std::remove do?" Moves the kept elements forward and returns the new logical end; it cannot change the size because it has only iterators. Pair it with erase.

"Does inserting into a std::map invalidate iterators?" No — only erasing that element. And std::unordered_map invalidates iterators on rehash while never invalidating references.

"Can you modify a container inside a range-based for?" Reading, yes. Changing the size, no: end is evaluated once.

"How would you remove all elements matching a predicate?" std::erase_if in C++20, the remove-erase idiom before it, and form 1 for node-based containers. Mentioning that form 1 is O(n·k) and remove-erase is O(n) is the detail that lands.

14. What You Should Be Able to Say Now

• That invalidation applies separately to iterators, to references, and to the past-the-end iterator.
• The consolidated rules in §2, including the two rows whose qualifiers matter.
• That a dangling read returns the old value rather than crashing, measured.
• That the broken erase loop is correct on separated duplicates and wrong on adjacent ones.
• That -O0, -O2, ASan, UBSan and libc++ debug hardening all report nothing, and the mechanical reason why.
• That the same four tools all catch an invalid comparator, and that the discriminator is whether the bug crosses an allocation boundary.
• That std::remove leaves the size unchanged and the tail holding plausible values.
• The three correct removal forms and why remove-erase is O(n) against form 1's O(n·k).
• That a range-based for fixes end before the first iteration.

15. Exercises

Exercise 1 — both inputs. Reproduce §4 with both datasets and confirm that the broken loop is right once and wrong once. Then find a third input on which it removes nothing at all.

Exercise 2 — the detection matrix. Build the broken loop under -O0, -O2, ASan, UBSan and libc++ debug hardening, and record exit codes and output. Then do the same for Chapter 20.6's a <= b comparator and compare the two rows.

Exercise 3 — why ASan cannot see it. Explain in three sentences, using the words "allocation boundary", why the erase bug is invisible and the comparator bug is not. Then construct a variant of the erase bug that ASan does catch.

Exercise 4 — the cost of form 1. Time form 1 against remove-erase for removing half the elements of a 200,000-element vector. Confirm the O(n·k) versus O(n) shapes.

Exercise 5 — remove without erase. Call std::remove alone, then print size() and every element. Explain what a later std::accumulate over the container would return.

Exercise 6 — the range-based trap. Write the push_back-inside-range-for bug, run it under every tool, and report what you find. Then fix it by collecting and applying after.

Exercise 7 — node stability. Hold ten std::map iterators, perform 100,000 insertions and 1,000 unrelated erasures, and verify all ten still read correctly. Then erase one of the ten and show which single iterator went bad.

Exercise 8 — the index defence. Rewrite a loop that holds a vector iterator across a push_back so that it holds an index instead, and verify both versions under ASan.

16. Summary

• Invalidation is three separate questions — iterators, references, and the past-the-end iterator — and Chapter 19.1 §7's unordered_map is the container where the answers differ.
• Measured: a dangling pointer read returns the old value. The block is freed, not scrubbed.
• Measured: the broken erase loop returns 1 3 5 7 — CORRECT — on separated duplicates, and 1 2 3 2 7 against the correct 1 3 7 on adjacent ones. The failure is data-dependent, so a test can pass.
• Measured: -O0, -O2, ASan, UBSan and libc++ debug hardening are ALL silent on it — because the stale iterator stays inside the allocated block and below size().
• Measured: the same four tools all CATCH an invalid comparator — SIGBUS, a heap-buffer-overflow 0 bytes past an 8000-byte region, and a libc++ assertion naming strict weak ordering. The discriminator is the allocation boundary, not the severity.
• Measured: std::remove leaves size() at 7 and the tail holding 5 2 7, which look like data.
• Three correct forms: adopt erase's return, remove-erase, or C++20 std::erase — and remove-erase is O(n) where the first is O(n·k).
• Measured: node-based containers keep held iterators valid across 1,001 list insertions and a filtered map erase.
• A range-based for evaluates end once, so changing the size inside one is undefined behaviour.
• A clean sanitizer run is evidence about one family of bugs and silence about this one.

Three chapters have now established the interface — positions, categories, and the rules for when a position dies. Chapter 20.4 makes the case for using the library that is built on it, and the argument it does not make is the one usually offered. The standard algorithms are not measurably faster than the loops they replace; that is measured directly, including a case where std::find compiles to a call into a hand-tuned libc routine and still finishes in the same time. The real case is the one this chapter just demonstrated: a named algorithm cannot contain the bug you have just spent sixteen sections learning to detect, because it has no loop for you to get wrong.