Iterator invalidation¶
Level: 201 · for C and C++ programmers
One line: Deleting from a container while walking it is the one bug on this list that usually does not crash — it returns a wrong answer, quietly, and no sanitizer objects.
The program¶
#include <cstdio>
#include <vector>
int main() {
std::vector<int> scores{5, 0, 0, 4, 3};
for (auto it = scores.begin(); it != scores.end(); ++it) {
if (*it == 0) {
scores.erase(it); /* it is now invalid */
}
}
for (int s : scores) {
std::printf("%d ", s);
}
std::printf("\n");
}
Two zeros go in. The loop is asked to remove both.
What it did¶
One zero survived, and the program exited 0 with no complaint from anything. erase shifted every later element down by one and returned; ++it then advanced past the element that had just moved into the erased slot, so the second zero was never looked at. This is the exact shape of the Python bug where for x in lst: lst.remove(x) turns [1, 2, 3, 4] into [2, 4].
Now move one element. With the zero at the end instead:
Erasing the last element makes it equal to end(); ++it then steps past it, and the next *it reads off the end of the buffer. Same bug, same three lines, one element moved — silently wrong in the first case, a segfault in the second. Which of those you get is a property of your data, so it is the kind of bug that ships.
AddressSanitizer catches the second and not the first:
==86141==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000000e0
READ of size 4 at 0x6020000000e0 thread T0
#0 0x000107ae4aec in main erase_at_the_end.cpp:8
On the original it prints 5 0 4 3 and exits cleanly, exactly like the unsanitized build. That is not a gap in AddressSanitizer — it watches memory, and the first version never touches memory it should not. Nothing about the addresses is wrong. Only the answer is.
The other half of this bug, worth naming because it fails differently: push_back may reallocate, and every iterator, pointer and reference into the vector is invalid the moment it does. Hold int &first = scores[0], push once, read first, and it prints 0 instead of 5 on this machine — a genuine use-after-free, which AddressSanitizer does catch.
Why the standard allows it¶
The standard defines exactly which operations invalidate which iterators — for vector::erase, everything at or after the erased position — and using an invalidated iterator is undefined behaviour. So the rule is written down, precisely, in a place the compiler cannot check and the reader has to remember. erase even returns the iterator you should continue from; the bug is that nothing requires you to use it.
What Rust does instead¶
The standard-library answer is one call, and it makes one pass:
let mut scores = vec![5, 0, 0, 4, 3];
scores.retain(|&s| s != 0);
println!("{scores:?}"); // [5, 4, 3]
When the decision is more involved than a predicate, the shape is: read first, finish reading, then mutate.
Verified output of iterator_invalidation.rs — regenerated by tools/run_examples.py, never hand-typed.
The second half of that output comes from collecting the indices to remove, which ends the borrow, and only then removing them — back to front, so the earlier indices stay valid.
The refusal¶
Write the C++ loop directly and the borrow checker names both halves:
error[E0502]: cannot borrow `scores` as mutable because it is also borrowed as immutable
--> erase_while_walking.rs:6:13
|
4 | for (i, score) in scores.iter().enumerate() {
| -------------------------
| |
| immutable borrow occurs here
| immutable borrow later used here
5 | if *score == 0 {
6 | scores.remove(i);
| ^^^^^^^^^^^^^^^^ mutable borrow occurs here
This is the plainest illustration of what the borrow rule is for. It is not a memory-safety rule that happens to catch a logic bug as a side effect — iterator invalidation is precisely the thing "no mutation while a read is outstanding" was designed to describe, and it catches the silently-wrong version and the segfaulting version with the same message, before either runs.
If you are coming from another language¶
- C++ — you know the fix:
it = scores.erase(it);and do not increment on that branch, orstd::erase_if(scores, …)since C++20, or the erase–remove idiom before that. The languages differ in what happens when you forget. Here the compiler will not build the loop; there, whether you find out depends on where in the container the matching element sits. - Python —
for x in lst: lst.remove(x)is the same bug with the same skipping behaviour, and the fix is the same shape: a comprehension that builds a new list, or iterating over a copy. Python will not crash — the list is bounds-checked — so it is always the quiet version, which arguably makes it worse.retainis a comprehension that reuses the buffer. - ABAP —
DELETE itabinside aLOOP AT itabover the same table is this bug exactly. ABAP permits it and shifts the index under the loop, so you skip rows in the same pattern; the usual advice is to collect the indices and delete descending afterwards, which is precisely the second half of the Rust example above. The difference is that there it is advice, and here the compiler refuses the alternative.
Practice¶
The bug that returns a wrong answer. Describe what the C++ erase-while-iterating loop actually does — it usually does not crash — and say why no sanitizer objects.
Then write the same intent in Rust and record the error code. Say which ordinary borrowing rule produced it. Finish with three correct versions and their trade-offs, and say why this is the most instructive bug in the chapter.
Solution
iterator_invalidation_kata.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.
//! Kata solution: the bug that does not crash.
//!
//! rustc --edition 2024 iterator_invalidation_kata.rs -o /tmp/iik && /tmp/iik
fn main() {
println!("THE C++ SHAPE");
println!(" for (auto it = v.begin(); it != v.end(); ++it)");
println!(" if (*it % 2 == 0) v.erase(it);");
println!(" erase invalidates `it`, and ++it then advances a dangling");
println!(" iterator. With a vector this usually does not crash -- the");
println!(" memory is still mapped -- it just SKIPS the element after each");
println!(" removal and returns a wrong answer. No sanitizer objects to a");
println!(" read that is in bounds.");
println!();
println!("THE SAME LOOP IN RUST");
println!(" for x in &v {{ if *x % 2 == 0 {{ v.retain(...) }} }}");
println!(" E0502: cannot borrow `v` as mutable because it is also borrowed");
println!(" as immutable. `&v` in the for loop is a shared borrow held for");
println!(" the whole loop body, and mutation needs an exclusive one.");
println!();
println!(" The rule doing the work is the ordinary one -- many readers or");
println!(" one writer -- applied to a loop. There is no iterator-specific");
println!(" machinery, and no runtime modification counter of the kind");
println!(" Java's ConcurrentModificationException needs.");
println!();
println!("WHAT TO WRITE INSTEAD");
let mut v: Vec<u32> = (1..=10).collect();
println!(" start {v:?}");
v.retain(|x| x % 2 != 0);
println!(" retain(odd) {v:?} <- one pass, the library owns the loop");
let source: Vec<u32> = (1..=10).collect();
let kept: Vec<u32> = source.iter().copied().filter(|x| x % 2 != 0).collect();
println!(" filter+collect {kept:?} <- a new Vec, the old one untouched");
let mut idx: Vec<u32> = (1..=10).collect();
let mut i = 0;
while i < idx.len() {
if idx[i] % 2 == 0 { idx.remove(i); } else { i += 1; }
}
println!(" index loop {idx:?} <- correct, and O(n^2); the bug the");
println!(" C++ version had is impossible here");
println!(" because there is no iterator to");
println!(" invalidate -- only an index you");
println!(" are responsible for");
println!();
println!("WHY THIS ONE IS THE MOST INSTRUCTIVE ON THE LIST");
println!(" Every other bug in this chapter has a chance of announcing");
println!(" itself: a segfault, a corrupted allocator, a sanitizer report.");
println!(" This one returns a plausible answer. It is the case where");
println!(" 'undefined behaviour' costs you a wrong number in a report");
println!(" rather than a crash you can debug -- and the compile error is");
println!(" the only thing that would ever have told you.");
assert_eq!(v, vec![1, 3, 5, 7, 9]);
assert_eq!(kept, v);
assert_eq!(idx, v);
}
Verified output of iterator_invalidation_kata.rs — regenerated by tools/run_examples.py, never hand-typed.
THE C++ SHAPE
for (auto it = v.begin(); it != v.end(); ++it)
if (*it % 2 == 0) v.erase(it);
erase invalidates `it`, and ++it then advances a dangling
iterator. With a vector this usually does not crash -- the
memory is still mapped -- it just SKIPS the element after each
removal and returns a wrong answer. No sanitizer objects to a
read that is in bounds.
THE SAME LOOP IN RUST
for x in &v { if *x % 2 == 0 { v.retain(...) } }
E0502: cannot borrow `v` as mutable because it is also borrowed
as immutable. `&v` in the for loop is a shared borrow held for
the whole loop body, and mutation needs an exclusive one.
The rule doing the work is the ordinary one -- many readers or
one writer -- applied to a loop. There is no iterator-specific
machinery, and no runtime modification counter of the kind
Java's ConcurrentModificationException needs.
WHAT TO WRITE INSTEAD
start [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
retain(odd) [1, 3, 5, 7, 9] <- one pass, the library owns the loop
filter+collect [1, 3, 5, 7, 9] <- a new Vec, the old one untouched
index loop [1, 3, 5, 7, 9] <- correct, and O(n^2); the bug the
C++ version had is impossible here
because there is no iterator to
invalidate -- only an index you
are responsible for
WHY THIS ONE IS THE MOST INSTRUCTIVE ON THE LIST
Every other bug in this chapter has a chance of announcing
itself: a segfault, a corrupted allocator, a sanitizer report.
This one returns a plausible answer. It is the case where
'undefined behaviour' costs you a wrong number in a report
rather than a crash you can debug -- and the compile error is
the only thing that would ever have told you.
See also¶
- Borrowing — one mutable borrow or many shared ones, which is the whole rule
- Iterators are lazy — why the borrow lives as long as the chain does
- Use-after-free — the reallocation half of this bug
- The bugs Rust is a reply to — the other eight
Po polsku¶
To jedyny błąd z tej listy, który zwykle nie wywala programu. Usuwanie z kontenera w trakcie chodzenia po nim po prostu zwraca złą odpowiedź — cicho, powtarzalnie i bez skargi ze strony jakiegokolwiek sanitizera. Dlatego jest groźniejszy niż naruszenie ochrony pamięci: to drugie znajdziesz w pięć minut, a przeskoczony element potrafi mieszkać w produkcji latami.
Mechanizm wart jest nazwania po polsku, bo tłumaczy objaw: przy usunięciu elementu reszta przesuwa się w lewo, a iterator rusza dalej ze swojej pozycji, więc przeskakuje sąsiada. Przy dokładaniu dochodzi drugi wariant — realokacja bufora unieważnia wszystkie wskaźniki i iteratory, które wskazywały na stary, a to potrafi się już skończyć odczytem zwolnionej pamięci.
Rust traktuje to jako to, czym jest naprawdę: pożyczanie. Chodzenie po kontenerze pożycza go współdzielnie, usuwanie żąda pożyczenia wyłącznego, a reguła „wielu czytających albo jeden piszący" nie pozwala mieć obu naraz — odmowa przychodzi przy kompilacji. Kiedy naprawdę trzeba usuwać w trakcie przebiegu, idiomem jest retain albo drain: jedno przejście, nic nie zostaje unieważnione.
Szukaj po polsku: unieważnienie iteratora · pożyczanie w Ruscie · retain i drain · rust iterator invalidation · E0502