What happens when a collection is structurally modified while one of its iterators is in use, and what strategies do libraries use to define that behaviour?
answer
- structural change invalidates the cursor
- modCount vs expectedModCount → fail-fast, best-effort
- snapshot / copy-on-write: stale but never throws
- weakly consistent: no CME, each element at most once
- iterator.remove() or removeIf; C++ = undefined behaviour
basics
~20 sThe cursor can be left pointing at the wrong place, so elements get skipped or repeated. Libraries pick a policy: fail fast with an error, iterate a snapshot taken when the iterator was created, or allow a "weakly consistent" walk that may or may not see later changes.
solid answer
~60 sStructural modification (adding/removing elements, resizing, rehashing) invalidates a cursor's assumptions. Three mainstream policies: 1. **Fail-fast** — the collection keeps a modification counter; the iterator records it at creation and compares on each step, throwing (e.g. `ConcurrentModificationException`) on mismatch. This is a *best-effort bug detector*, explicitly not a correctness guarantee: unsynchronized races can miss it, and it does not make the collection thread-safe. 2. **Snapshot / copy-on-write** — the iterator captures the backing array at creation and traverses that; writers copy. Never throws, never sees later writes, `remove()` via the iterator is unsupported, and writes cost O(n). 3. **Weakly consistent** — concurrent structures let traversal proceed without locking; the iterator reflects the state at some point at or after creation, may or may not show later updates, never throws, and shows each element at most once. Sanctioned in-loop mutation goes through `iterator.remove()`; safer alternatives are `removeIf`/bulk operations, collecting changes and applying them after the loop, or iterating a defensive copy. Unsafe languages (C++ iterator invalidation) simply make it undefined behaviour.
code
pseudocode · 15 lines// Silent skip — index cursor + removal, no exception required
for (i = 0; i < list.size(); i++)
if (bad(list[i])) list.removeAt(i) // element i+1 shifts into i, never examined
// Fail-fast detection (best effort)
class ArrayAggregate { var modCount = 0; fun add(x){ ...; modCount++ } }
class Cursor(val expected = modCount) {
fun next(): T { if (modCount != expected) throw ConcurrentModification(); ... }
}
// Correct in-loop removal
val it = list.iterator()
while (it.hasNext()) if (bad(it.next())) it.remove() // updates expected count
// Or bulk: list.removeIf { bad(it) }go deeper
Say that modifying while looping can skip or repeat elements or throw, and that the fix is iterator.remove() or a bulk removeIf.
Explain the modification-counter mechanism, that it is best-effort, and that single-threaded for-each removal is the usual trigger.
Compare fail-fast, copy-on-write snapshot and weakly-consistent semantics with their costs, and point out the silent-skip cases where nothing throws.
Treat it as contract design: pick and document iteration semantics for your own aggregates and public APIs, weigh persistent/immutable structures or versioned robust iterators, and note that traversal is a compound operation so external locking must span the whole loop.
## Why modification during iteration is dangerous An iterator holds a *position expressed in terms of the current internal layout*. Change the layout and the position silently means something else: - **Index cursor into an array-backed list.** You are at index 3 and someone removes index 1: every later element shifts down one, so the element that was at 4 is now at 3 — you already passed 3, so it is **skipped**. Insert instead, and one element is **visited twice**. Nothing crashes; the loop just produces wrong results. - **Hash table rehash.** Adding an entry crosses the load factor, buckets double, every entry moves. Your "bucket 7, chain slot 2" position now refers to unrelated data; you may revisit and miss arbitrarily many entries. - **Linked node cursor.** Removing the node you are on can leave you on a detached node whose `next` points into the old structure (or to null), so the traversal ends early or wanders a stale chain. - **Native/unsafe containers.** A C++ `std::vector` push_back that reallocates invalidates *all* iterators, references and pointers into it; dereferencing one afterwards is **undefined behaviour** — potentially a use-after-free, not an exception. `std::list` by contrast only invalidates iterators to erased elements. Knowing the per-container invalidation rules is part of the language's contract. Note the important distinction: **structural** modification (changing the set of elements or the layout) is the hazard. Replacing the *value* at an existing position (e.g. `list.set(i, v)`, or mutating a stored object's non-key field) is generally not structural and does not invalidate cursors. ## Policy 1 — fail-fast Mechanism: the aggregate maintains an integer `modCount` incremented on every structural change. `iterator()` copies it into `expectedModCount`. Each `next()` (and often `hasNext()`'s companion checks) compares them and throws `ConcurrentModificationException` (CME) on mismatch. The iterator's own `remove()` updates `expectedModCount`, which is why it is the one legal way to mutate mid-loop. Properties and gotchas: - It is **best-effort**. The documented wording is that it must not be relied on for correctness: it is a *bug detector*, thrown on a best-effort basis. Under an unsynchronized data race there is no happens-before edge on `modCount`, so the check can miss the modification entirely and you get silently wrong results instead of an exception. - CME **does not imply threads**. Single-threaded `for (x in list) if (p(x)) list.remove(x)` is the most common cause. - A famous surprise: removing the **second-to-last** element of an array list in a for-each loop often does *not* throw, because after the removal `hasNext()` sees `cursor == size` and terminates the loop before any check runs — so the last element is silently skipped. This is exactly why "it didn't throw" is not evidence of correctness. - CME is *not* a concurrency solution. Wrapping a collection in a synchronizing wrapper still requires the client to hold the lock across the *whole* traversal, because the traversal is a compound operation. ## Policy 2 — snapshot / copy-on-write Mechanism: the iterator grabs a reference to the immutable backing array present at creation. Every write replaces the array with a fresh copy under a lock. Existing iterators keep walking the old array. Properties: - Traversal is completely isolated: **never throws**, needs no locks, and is trivially thread-safe. - It sees a **stale** view — writes after iterator creation are invisible. If your loop is a long-running dispatch of event listeners, this is usually exactly what you want. - `iterator.remove()`/`set` are unsupported (the snapshot is immutable, and mutating it would not affect the real collection). - Cost: every write is O(n) copy and allocates. Great for read-mostly, tiny-write workloads (listener lists); terrible for write-heavy ones. - A cheaper variant of the same idea available in *any* library: iterate a defensive copy you made yourself. ## Policy 3 — weakly consistent Used by lock-free/striped concurrent collections. The iterator traverses the live structure without locking and offers a deliberately weak contract: - it reflects the state of the collection **at some point at or since** iterator creation; - it **may or may not** reflect modifications made after creation; - it **never throws** CME; - it returns each element **at most once**, and never returns a value twice for the same key. This is the pragmatic compromise for concurrent maps/queues: unlimited concurrent readers and writers, no global lock, at the price of no point-in-time snapshot. Related weakenings appear on derived operations too — a `size()` or aggregate computed during concurrent mutation may reflect a state that never existed atomically. ## Other points on the spectrum - **Robust iterators** (in the GoF sense): iterators that stay valid across modification, typically by registering with the aggregate so it can fix up cursors on change, or by using versioned/persistent data structures where every edit produces a new version and old cursors keep walking the old one. Powerful, rarely implemented, because bookkeeping cost falls on every write. - **Immutable/persistent collections** make the whole question disappear: nobody can modify what you are iterating; "modification" produces a new structure sharing most of its nodes. - **Locking the entire traversal** (`synchronized (coll) { for (...) }`, or an explicit read lock) is correct but converts iteration into a critical section — long loops then block all writers, and calling user code (callbacks, listeners) while holding that lock invites deadlock. ## Practical guidance 1. To remove while looping, use the iterator's own `remove()`, or a bulk predicate operation (`removeIf`/`retainAll`) which does it correctly and often faster. 2. To add while looping, don't: collect additions in a local list and append after the loop, or build a new collection functionally. 3. Across threads, pick a collection whose *documented* iteration semantics you want (snapshot vs weakly consistent) instead of adding locks around a non-thread-safe one. 4. Never treat the absence of an exception as proof of correctness — the skipped-element case throws nothing. 5. When designing your own aggregate, **document the policy explicitly**. "Undefined behaviour if modified during iteration" is an acceptable contract; leaving it unspecified is not.
- Why is a fail-fast exception described as best-effort rather than guaranteed?Because the modification counter is read and written without synchronization. In a data race there is no happens-before relationship, so the iterating thread may never observe the writer's increment and will silently produce wrong results. It is a debugging aid for the common single-threaded misuse, not a concurrency mechanism.
- Removing the second-to-last element of an array-backed list inside a for-each loop often doesn't throw. Why, and what actually happens?After the removal the size drops by one, so the iterator's `hasNext()` sees cursor == size and ends the loop before any modification check executes. No exception is thrown and the final element is silently never visited — a correctness bug that looks like a passing test.
- What do you give up by choosing a copy-on-write collection to avoid these problems?Freshness and write throughput: iterators see the snapshot from creation and never observe later writes, iterator-based mutation is unsupported, and every write copies the whole backing array. It is right for read-mostly, small, rarely-written data such as listener registries, and wrong for write-heavy collections.
You are reading a numbered attendance list while someone deletes rows above you. You are on row 3; row 1 disappears; everyone shifts up; you continue at row 4 and never notice you skipped a person. No alarm sounds — that silent skip, not the crash, is the real danger.
saying these in an interview costs you the question
- Believing a fail-fast exception makes a collection thread-safe, or that its absence proves the loop was correct.
- Thinking `ConcurrentModificationException` only arises with multiple threads — the usual cause is single-threaded removal inside a for-each loop.
- Assuming every language throws: in C++ a reallocating insert invalidates iterators and using them is undefined behaviour, which may corrupt memory rather than raise an error.
- Calling a weakly-consistent iterator a "snapshot" — it is not point-in-time; it may or may not show concurrent updates.
- Removing by index in an ascending for-loop and expecting every element to be examined; each removal shifts the tail and skips one (iterating backwards or using a bulk predicate avoids it).
- Holding a collection-wide lock for the entire traversal while invoking client callbacks inside it — correct in isolation but a common source of deadlock and long write stalls.