Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Iterator

Walk a collection one element at a time without knowing how it is stored. Each iterator keeps its own position, so two traversals can run at once, and a good one says what happens when the collection changes during the walk.

Three loops that know too much

Three features of a chat app read a whole conversation: exporting it to a text file, searching it, and counting unread messages. Each one contains the same loop, for (let i = 0; i < history.messages.length; i++), reading history.messages[i], because MessageHistory keeps every message in one array, oldest first.

The next task changes that. Some group chats have passed 50,000 messages, more than the team wants in memory at once, so MessageHistory will store messages in chunks of 200, history.chunks, and leave old chunks in the phone's storage until something reads them. Every loop that indexes history.messages has to be rewritten for chunks, and rewritten again the next time the storage changes. The three features know how the history is stored, and that knowledge is what makes the change expensive.

Ask for the next message, not for the array

Iterator gives the walk its own object. Instead of handing out its storage, the history hands out an iterator with two operations: hasNext() says whether any element is left, and next() returns that element and moves on. The export loop becomes const it = history.createIterator(); while (it.hasNext()) write(it.next());, and nothing in it says array or chunk.

The pattern's name for the collection is the aggregate. It creates its own iterator, here through createIterator(), so only the collection and its iterator need to know how its storage is laid out. What it returns is a concrete iterator, here a ChunkIterator that keeps two numbers: which chunk it is in, and its position inside that chunk. The three features see only the iterator interface, so when the storage changes again, the collection and its iterator change and the three features do not.

Two walks over one history

MessageHistory created both iterators with createIterator(). Each one keeps its own position, so the export can be deep into the history while the search is still near the start.

Why the position lives in the iterator

A shorter design puts next() on MessageHistory itself, with the current position stored in the history. It works as long as only one loop runs at a time. Then a user starts a search while an export is halfway through:

  1. The export calls history.next() and gets message 4,001. The shared position moves to 4,002.
  2. The search resets the shared position to the start and reads messages 1 to 900.
  3. The export calls history.next() again and gets message 901.
  4. The export carries on to the end, writing messages 901 to 4,001 a second time.

The exported file is wrong, and nothing in it points to the search as the cause. With one iterator per traversal, the export and the search each hold their own ChunkIterator, and neither can move the other's position. That is why the pattern keeps the thing that holds the elements apart from the thing that walks them.

Who drives the loop

In the loop above, the caller holds the iterator and decides when to call next(). That is external iteration: the caller can stop at the first match, or walk two conversations side by side to merge them by time. Internal iteration turns it around: history.forEach((message) => …) runs the loop inside the collection and calls your function once per element. It is shorter, but the collection sets the pace, and in JavaScript forEach cannot stop early except by throwing.

Most developers meet the pattern built into their language: for (const m of history) in JavaScript or for m in history in Python asks the collection for an iterator and calls next() until it reports the end. A generator is the easiest way to write such an iterator: a function that yields one message at a time and stays paused between values, holding the position for you. Each loop asks the collection for a new generator, so two loops still get two positions.

A message arrives during the export

Exporting 50,000 messages takes a few seconds, and messages keep arriving or being deleted. If an earlier message in chunk 21 is deleted while an iterator's next read is position 150 of that chunk, every later message in the chunk moves back one place, and a naive ChunkIterator skips the message that moved from 150 to 149. What an iterator does when its collection changes underneath it is a decision, and its documentation should state it. Two common answers:

  • Fail-fast. The collection counts its structural changes, the iterator remembers the count it started with, and next() throws if the two differ. The iterators of Java's ArrayList and HashMap work this way and throw ConcurrentModificationException, unless the change was made through the iterator's own remove(). Java documents this as a best effort for finding bugs, not a guarantee.
  • Snapshot. The iterator walks the elements the collection held, in their order, when the iterator was created. Java's CopyOnWriteArrayList copies its internal array on every write, so an iterator keeps reading the old copy: it never reports a concurrent change, and it never sees elements added after it started. The price is a full copy on each write, which suits a list read far more often than changed.

For the export, a snapshot is what the user expects: the file holds the messages the chat had when they pressed Export. Two numbers in a ChunkIterator do not give that on their own: the history also has to keep a stable view of its chunks until the export finishes. The most common fail-fast surprise needs no second thread. If a loop deletes messages through the collection while walking it, the next call to next() throws, because the loop itself changed the count the iterator started with. Remove through the iterator, or collect what to remove and delete it after the loop.

Fail-fast is not thread safety: its check may not even notice another thread's change. A collection that one thread changes while another walks it needs a design made for that, such as a collection built for concurrent use, as CopyOnWriteArrayList is, or a lock held around every access; Mutex and semaphore explains the lock.

Iterators are not limited to lists; a tree built with Composite can be walked the same way. To run a different operation on each kind of node, rather than only reach every node, read Visitor.

Two iterators in the Challenge

The Iterator Pattern Challenge allows six nodes, exactly enough to draw the export and the search: an Iterator interface, a MessageHistory aggregate, two clients, and one concrete iterator node per traversal. Both iterator nodes are ChunkIterator objects, of the one class that implements the interface, and each holds its own position. Label each aggregate-to-iterator edge createIterator(). In a drawing that reads correctly, a client may ask the aggregate for an iterator but reaches the messages only through next(), and the position lives in each iterator, never in the aggregate.

Practice this