Iterator

Purpose

An Iterator separates the job of walking a collection from the collection itself. The client asks for a cursor and then advances it, and at no point does it learn whether it is standing on an array, a linked list, a hash table or a tree.

Two things fall out of that. The collection is free to change its internal representation without breaking any caller, which is the encapsulation argument. And an algorithm written against the cursor works on every collection that can produce one, which is the reuse argument. The second turned out to be the more valuable of the two, and it is the one the C++ standard library was built on.

Design

The Aggregate declares an operation that returns an Iterator, which makes it a Factory Method. The Iterator declares the cursor operations: start, advance, test for the end, read the current element. Each concrete collection supplies a matching concrete iterator that knows the private layout of the collection it came from, which is why the iterator is usually written as a nested or friend class.

The main variation is who drives. An external iterator hands the cursor to the client, which decides when to advance and can stop early or run two cursors at once. An internal iterator keeps control and calls a function you supply for each element, which is simpler to write and impossible to break out of cleanly. Most languages give you external iteration in the loop syntax and internal iteration in the library, as foreach versus List.ForEach.

Example

The interesting half of this at Autobot Robotics was on the embedded controller, where there is no foreach, no allocation after startup and no standard library worth the name. The controller keeps three collections with three completely different shapes: a fixed-size ring buffer of recent vision frames, a free-list of motion segments linked through their own storage, and a static array of axis records.

The diagnostics and telemetry code needed to walk all three. The first version had three copies of every reporting routine, one per container, and they drifted. The ring buffer copy had a wrap-around bug that the array copy could not have had, and it was found in the field because a fault report printed the last eight frames in the wrong order.

The fix was a cursor struct with moveNext() and current(), one implementation per container, allocated on the stack. The reporting routines were written once. Meanwhile the office-side reporting service, which is C# and reads the same data out of PostgreSQL, never wrote an iterator at all: it wrote yield return and let the compiler generate one. Same pattern, and only one of the two teams had to know it existed.

interface FrameIterator {
    bool moveNext();
    Frame current();
}

class FrameRing {                        // the aggregate
    private Frame[] slots;
    private int head, count;

    public FrameIterator getIterator() { return new RingIterator(this); }
}

class RingIterator : FrameIterator {     // the concrete iterator
    private FrameRing ring;
    private int seen;

    public RingIterator(FrameRing r) { ring = r; seen = 0; }

    public bool moveNext() {
        // step the cursor, handle the wrap, return false at the end
    }

    public Frame current() {
        // return the frame the cursor is standing on
    }
}

class Diagnostics {
    public void dump(FrameIterator it) {
        while (it.moveNext()) {
            // report on it.current()
        }
    }
}

// The same thing on the office side. The compiler writes the iterator.
class FrameLog {
    public IEnumerable<Frame> recent() {
        for (int i = 0; i < count; i++) {
            yield return slots[(head + i) % slots.Length];
        }
    }
}

Seen in the Wild

This is the pattern most thoroughly absorbed into languages. .NET has IEnumerable and IEnumerator wired into the foreach statement, with yield return generating the iterator class for you. Java has Iterable and Iterator behind its enhanced for loop, and Python has __iter__ and __next__ behind its for statement, plus generators. The C++ standard library goes furthest: its algorithms are written against iterator categories rather than containers, so std::sort works on anything that can produce a random access iterator, including a raw pointer into an array.

Comparisons

• Factory Method is how the aggregate produces the right iterator without the client naming its class.
• Composite is the case that makes iterators awkward. Walking a tree with an external iterator means the iterator has to carry its own explicit stack, which is exactly the code the pattern was supposed to hide.
• Visitor is the usual alternative for trees. An iterator visits nodes in an order it chose; a Visitor lets each node decide how its children are reached.
• Memento can capture the state of an iteration, so a position can be saved and returned to without exposing what a position is.
• Pipes and Filters is where lazy iterators end up. A chain of map and filter over an enumerable is a pipeline whose stages happen to be iterators.

Why It Exists

Criticisms

Iterators and mutation get along badly. Modify a collection while a cursor is open and you get, depending on the language, an exception, a skipped element, or undefined behavior reading freed memory. Java's fail-fast iterators throw ConcurrentModificationException as a courtesy; C++ simply invalidates the iterator and lets you find out later. This is not an implementation defect, it is inherent: a cursor is a pointer into a structure whose shape the collection is free to change.

The abstraction also hides cost, which is its job and its problem. Walking a linked list by index is quadratic and looks identical to walking an array. A lazy iterator over a database query can issue a round trip per element, which is the N+1 problem wearing a foreach as a disguise. The code reads as one loop and behaves as a thousand queries.

Finally, the interface is thin to the point of being lossy. A cursor gives you forward, one element at a time, one pass. Anything else, counting without consuming, going backwards, splitting the work across threads, knowing whether the source is finite, needs a richer contract that the plain pattern does not provide. Every mature library ends up growing one, which is what .NET's IQueryable and Java's Spliterator are: admissions that a bare iterator was not quite enough.