Who should own the traversal state in the Iterator pattern, and what breaks when the aggregate itself holds the cursor?
answer
- position in the cursor, not the container
- one field ⇒ one traversal at a time
- nested loops / reentrancy / two threads break
- Iterable = repeatable, Iterator = one live position
- tree cursor = explicit stack, graph cursor = frontier + visited
basics
~20 sThe iterator owns the position, not the collection. If the collection stores a single "current index" field, only one traversal can run at a time — nested loops, two threads, or two callers stepping through the same collection will fight over that one position.
solid answer
~50 sTraversal state (current index, current node, the explicit stack for a tree walk, the bucket and chain position for a hash table) belongs in the iterator object, which is created fresh per traversal. This gives independence: N concurrent or nested traversals need N iterators and never interfere. It also keeps the aggregate focused on storage invariants (SRP) and lets one aggregate offer several traversal orders as separate iterator classes without growing new state fields. Putting the cursor in the aggregate produces a "one traversal at a time" object: nested loops corrupt each other, recursion breaks, reentrant calls from callbacks break, iteration is not thread-safe even with only readers, and callers must remember to `reset()`. It also fails Command/Query separation — reading elements mutates the collection. A related design question is *how much* state to keep: an index-based cursor is cheap but can silently shift under structural change; a node/link-based cursor survives some edits but can be left pointing at a detached node.
code
pseudocode · 16 lines// ANTI-PATTERN: cursor inside the aggregate
class Playlist { var i = 0; reset(){i=0}; hasMore()= i<n; next()= songs[i++] }
p.reset()
while (p.hasMore()) { // outer
a = p.next()
p.reset()
while (p.hasMore()) { // inner destroys the outer position
b = p.next() // -> infinite loop
}
}
// FIX: fresh cursor per traversal
outer = p.iterator(); while (outer.hasNext()) {
inner = p.iterator(); while (inner.hasNext()) { compare(outer.peek(), inner.next()) }
}go deeper
Say the position lives in the iterator and give the nested-loop breakage as the concrete reason.
Add reentrancy, thread-safety for read-only use, and CQS; distinguish Iterable (repeatable) from Iterator (one live position).
Discuss what traversal state really is for trees/graphs/hash tables, index-cursor vs node-cursor invalidation, and the API risk of returning a single-pass iterator where callers expect a collection.
Generalize to distributed cursors: a resumable page token is externalized traversal state, and putting it on the server turns a stateless service into a sticky, single-consumer one with expiry and failover problems.
## What "traversal state" actually is It is everything needed to answer "where am I, and how do I get to the next element": - array-backed list → an integer index (plus maybe the expected size); - linked list → a pointer to the current (or next) node; - hash table → a bucket index *and* a position within that bucket's chain; - binary tree, in-order → an explicit stack of ancestor nodes (or a pointer plus parent links, or a coroutine's suspended frame); - graph → a frontier queue/stack **plus a visited set**; - paginated remote source → a page token/cursor string and an offset within the current page. Note how quickly this grows beyond "an index". That growth is the reason it must not live in the aggregate: the aggregate would need one such field set per *simultaneous* traversal, which is unbounded. ## The failure mode of an aggregate-owned cursor An interface like ``` class Playlist { reset(); hasMoreSongs(): bool; nextSong(): Song } ``` looks convenient and is a classic anti-pattern. Concretely it breaks: 1. **Nested traversal.** Comparing every song with every other song (`for a in p: for b in p:`) needs two independent positions. With one field the inner loop's `reset()` and advances destroy the outer loop's position — usually an infinite loop or a silently truncated outer pass. 2. **Reentrancy.** If any code inside the loop body calls a method that itself iterates the same playlist — directly, via a callback, via logging, via an event handler — it corrupts the caller's position. This bug is invisible in code review because the second traversal is often several frames away. 3. **Recursion.** A recursive walk over a composite naturally has one active traversal per recursion level. 4. **Concurrency.** Two threads merely *reading* the collection now race on the shared cursor field: both may skip elements or return the same one twice. Read-only traversal should be safe by construction, and with per-iterator state it is. 5. **Command/Query Separation.** `nextSong()` returns a value *and* mutates the object. That means iteration cannot be done on a shared, conceptually immutable collection, and every caller must worry about who touched the cursor last. 6. **API discipline.** Callers must remember `reset()` before every use; forgetting it yields an empty or partial traversal — a failure that depends on history rather than on the call itself. 7. **Multiple orders.** Adding a reverse or shuffled walk means adding *more* mutable fields to the aggregate rather than a small independent class. ## Corollaries of iterator-owned state - **Iterators are usually single-use and cheap.** You create one per loop and drop it; most languages fold this away (escape analysis, structs, or the language's `for` construct doing it invisibly). Do not "optimize" by caching one iterator on the collection — you have just recreated the anti-pattern. - **Distinguish `Iterable`/`Aggregate` from `Iterator`.** The iterable can be traversed many times (each call to `iterator()` returns a fresh position); the iterator is one live traversal, generally not restartable. An API that returns a *stream/iterator* where callers expect a *collection* surprises them when the second traversal yields nothing. Some languages guard this: a Java `Stream` throws `IllegalStateException` on reuse. - **Snapshot vs live view.** An iterator-owned cursor still *references* the live aggregate, so structural change can invalidate it (see fail-fast/snapshot/weakly-consistent semantics). Owning the position is not the same as owning the data. - **Index cursors vs node cursors.** An index cursor is compact but positional: inserting before the cursor makes it silently re-visit an element, and removing before it makes it silently skip one. A node/link cursor is stable against edits elsewhere in the structure but can be left dangling on a removed node. Neither is "robust" without extra design (parent links, versioned nodes, tombstones). - **Iterators can also be *saved*.** Because they are objects, a cursor can be stored, passed to another component, or serialized into a page token so a client resumes days later — impossible if the position is a hidden field in a server-side collection. ## When aggregate-held position is acceptable When the object genuinely *is* a single-position cursor by nature: a file handle with a seek pointer, a database `ResultSet`, a network stream, a tape. Those are single-consumer resources; the state is inherent to the resource, not an implementation shortcut. Even then, real APIs usually let you open a second handle to get a second position — the same principle, one cursor per traversal.
- What traversal state does an in-order binary-tree iterator need, and why is it more than a pointer?It needs the path back up: an explicit stack of ancestors (push left spine, pop to visit, then descend the right child), or parent pointers, or a suspended coroutine frame. A bare "current node" cannot tell you where to go after finishing a subtree, which is exactly why an external tree iterator is more work than a recursive internal walk.
- Is it ever right to return an Iterator instead of a collection from a public method?Yes, when the sequence is lazy, large, or resource-backed — but document it as single-pass. The hazard is callers assuming re-iterability; some APIs guard it by throwing on a second traversal, and a defensively written client materializes into a list if it needs multiple passes.
- Two threads iterate the same immutable collection. Is that safe?Yes, provided each thread creates its own iterator and the data is genuinely unmodified — the only mutable state is per-iterator and thread-confined. Sharing a single iterator between threads is not safe: `hasNext`/`next` together form a non-atomic check-then-act.
A library book with a single ribbon bookmark sewn into the spine: only one reader can keep a place, and the moment a second reader moves it, the first loses their page. Loose bookmarks — one per reader — are the iterator.
saying these in an interview costs you the question
- "Caching one iterator on the collection avoids allocation" — it reintroduces the single-traversal defect and makes read-only use unsafe.
- Assuming `hasNext()` + `next()` used by two threads on one shared iterator is safe — it is a classic check-then-act race and can throw or return duplicates.
- Treating `Iterable` and `Iterator` as interchangeable, then being surprised that the second loop over the same iterator/stream sees nothing.
- Believing that because the iterator owns the position it also owns a snapshot of the data — it normally references the live aggregate.
- Thinking an index cursor is always fine: inserting or removing before the cursor silently re-visits or skips an element even when nothing throws.