Low-level designCore8 min

Iterator

Let a collection hand out its elements one at a time, without showing how it stores them. Callers write one simple loop, and the collection can change its insides without breaking any of them.

Watch it evolve1 / 8
The problem

Seats in carriages in a train

Train hands out its carriages, and each Carriage its seats. Two clients read every seat.

80
Start
Stage 1
Stage 2
Final

1 · The situation

Seats in carriages in a train

A rail operator's booking app models a Train as a list of Carriages, each holding its Seats. Two parts of the app read every seat: Availability counts the free ones for the booking page, and AccessGuide lists the wheelchair spaces and whether they're booked.

The first version lets them in: Train.carriages() returns the carriages, Carriage.seats() the seats, and each client walks both levels. Python writes free_seats() and wheelchair_spaces().

The first versionJava
import java.util.ArrayList;
import java.util.List;

record Seat(String id, boolean free, boolean wheelchair) {}

class Carriage {
    private final List<Seat> seats;

    Carriage(List<Seat> seats) {
        this.seats = List.copyOf(seats);
    }

    List<Seat> seats() {
        return seats;
    }
}

class Train {
    private final List<Carriage> carriages;

    Train(List<Carriage> carriages) {
        this.carriages = List.copyOf(carriages);
    }

    List<Carriage> carriages() {
        return carriages;
    }
}

class Availability {
    int freeSeats(Train train) {
        int count = 0;
        for (Carriage c : train.carriages()) {
            for (Seat s : c.seats()) {
                if (s.free()) count++;
            }
        }
        return count;
    }
}

class AccessGuide {
    List<String> wheelchairSpaces(Train train) {
        List<String> out = new ArrayList<>();
        for (Carriage c : train.carriages()) {
            for (Seat s : c.seats()) {
                if (s.wheelchair()) out.add(s.id() + (s.free() ? " (free)" : " (booked)"));
            }
        }
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        Train train = new Train(List.of(
                new Carriage(List.of(
                        new Seat("C1-01", false, false),
                        new Seat("C1-02", true, false),
                        new Seat("C1-03", true, true))),
                new Carriage(List.of(
                        new Seat("C2-01", false, true),
                        new Seat("C2-02", true, false),
                        new Seat("C2-03", true, false)))));
        System.out.println("Free seats: " + new Availability().freeSeats(train));
        List<String> spaces = new AccessGuide().wheelchairSpaces(train);
        System.out.println("Wheelchair spaces: " + String.join(", ", spaces));
    }
}
**«record»Seat− id: String− free: boolean− wheelchair: booleanCarriage− seats: List<Seat>~ seats(): List<Seat>Train− carriages: List<Carriage>~ carriages(): List<Carriage>Availability~ freeSeats(Train): intAccessGuide~ wheelchairSpaces(Train): List<String>

The class diagram of this version, drawn from its code: both clients depend on the train, its carriages and the seats.

A train of two carriages:

Free seats: 4
Wheelchair spaces: C1-03 (free), C2-01 (booked)

2 · The change

Double-decker carriages

The operator buys double-decker trains. A carriage now has a lower and an upper deck, each with its own seats. Every client that reaches into the structure has to change:

Each client walks the structure itselfJava
class Availability {
    int freeSeats(Train train) {
        int count = 0;
        for (Carriage c : train.carriages()) {
            for (Seat s : c.seats()) {
                if (s.free()) count++;
            }
        }
        return count;
    }
}

Code

What double decks cost it

Carriage

A list of decks instead of seats; seats() changes or goes

Availability

A third nested loop

AccessGuide

A third nested loop

Every future client

The same three levels, written again

The clients only want "every seat on the train". They've had to learn how the train stores seats, so a change to storage is a change to every one of them, and the diagram shows it: both depend on Carriage, a class they have no other use for.

3 · The refactor

Let the train hand out its seats

Start from the first version. Instead of handing out its carriages, the train hands out its seats, one at a time, through each language's iteration protocol:

In Java, Train implements Iterable and returns a Flatten iterator that walks each carriage in turn. JavaScript and Python write the same walk as a generator; C++ returns a view that joins the carriages' seats.

Java
class Train implements Iterable<Seat> {
    private final List<Carriage> carriages;

    Train(List<Carriage> carriages) {
        this.carriages = List.copyOf(carriages);
    }

    public Iterator<Seat> iterator() {
        return new Flatten<>(carriages.iterator());
    }
}
*«create»*«record»Seat− id: String− free: boolean− wheelchair: booleanFlatten− groups: Iterator<? extends Iterable<T>>− current: Iterator<T>+ hasNext(): boolean+ next(): TCarriage− seats: List<Seat>+ iterator(): Iterator<Seat>Train− carriages: List<Carriage>+ iterator(): Iterator<Seat>Availability~ freeSeats(Train): intAccessGuide~ wheelchairSpaces(Train): List<String>

Each step prints the same lines. The last runs on double-decker carriages:

Free seats: 4
Wheelchair spaces: C1-03 (free), C2-01 (booked)
Clients walk the structure
3
The train iterates
1

Classes edited for double decks. Before: Carriage and both clients. After: Carriage alone, plus the new Deck.

4 · The pattern

Iterator: visit every element, one at a time

Iterator gives sequential access to the elements of a collection, the aggregate, without exposing how it stores them. The aggregate creates an iterator, an object that remembers where it is and hands out the next element on request. Every caller writes the same loop, whatever the collection's shape.

*«create»*«create»*«record»Seat− id: String− free: boolean− wheelchair: booleanFlatten− groups: Iterator<? extends Iterable<T>>− current: Iterator<T>+ hasNext(): boolean+ next(): TDeck− seats: List<Seat>+ iterator(): Iterator<Seat>Carriage− decks: List<Deck>+ iterator(): Iterator<Seat>Train− carriages: List<Carriage>+ iterator(): Iterator<Seat>Availability~ freeSeats(Train): intAccessGuide~ wheelchairSpaces(Train): List<String>

The roles in the booking code: Train and Carriage are aggregates, Flatten the iterator in Java, and the two clients loop without knowing about carriages or decks.

Role

In the booking app

Its job

Iterator

Flatten in Java; a generator or a view elsewhere

Remembers the position, and hands out the next element

Aggregate

Train, Carriage, Deck

Creates iterators over its own elements

Client

Availability, AccessGuide

Loops, knowing only the element type

The iterator moves to the next carriage only when the current one runs out. The client sees only seats.

Each language builds the pattern into its loop, so a class that follows the protocol works with the language's own for:

Language

The protocol

The loop that uses it

Java

Iterable.iterator() returns an Iterator with hasNext() and next()

for (Seat s : train)

C++

begin() and end() iterators; C++20 views such as views::join build them

for (const Seat& s : train.seats())

JavaScript

[Symbol.iterator]() returns an object whose next() gives { value, done }; a generator writes one

for (const s of train)

Python

__iter__() returns an iterator with __next__(); a generator writes one

for s in train:

5 · What it costs

State that can go stale

  • An iterator holds a position. If the collection changes while it's being walked, the position can skip an element or point past the end. Java's standard collections detect this on a best-effort basis and throw ConcurrentModificationException, which is meant for finding bugs, not for relying on.
  • One pass, in one order. An iterator walks once, forward. A caller that needs random access, the size, or a second pass needs something more.
  • A hand-written iterator is fiddly. Flatten is a dozen lines of state; generators and views do the same in one, which is why most code uses them.

Situation

Iterator?

Callers need every element, and the storage may change

Yes: expose iteration, not the structure

Callers need indexed access or the count

Offer those too, or return a read-only list

The collection is a plain list that will stay one

Just return the list, read-only

Elements come from a file or a network, one at a time

Yes: an iterator never needs them all in memory

6 · Getting it right

Hand out a walk, not your internals

  • Don't return your internal collection. A caller holding the list can change it. Return an iterator, or a read-only view.
  • Prefer the language's protocol. A class that implements Iterable, __iter__ or Symbol.iterator works with every loop, library and tool that expects one.
  • Offer named walks for common questions. A wheelchairSeats() that yields only those spaces keeps the filter in one place.
  • Don't modify while iterating, unless the iterator itself offers a way, such as Java's Iterator.remove().

Language

The shortest way to write one

Java

Return another collection's iterator, or a stream's iterator(); write an Iterator class when the walk has its own state

C++

Return a view built from std::views; write an iterator type only when no view fits

JavaScript

A generator method, *[Symbol.iterator](), with yield and yield*

Python

A generator __iter__ with yield and yield from

7 · Look-alikes

Walking a structure, from inside or out

Iterator is about walking a collection. Several patterns and idioms do something close:

Idea

Who controls the loop

Use it when

Iterator (external)

The caller: it asks for each next element

The caller needs to stop early, or combine walks

Internal iteration, such as forEach or a stream

The collection: it calls a function for each element

Each element gets the same treatment, start to end

Composite

Nobody walks it: each node asks its children

Every node answers the same question for its subtree

Visitor

The structure, which hands each node to a visitor

New operations over a fixed set of node types

Composite and Iterator often meet: an iterator that walks a composite tree in order, as Flatten walks carriages and decks, lets clients treat the whole tree as one flat sequence.

8 · In practice

Iterators you use every day

Every for loop over a collection in these four languages goes through the pattern. JavaScript's for...of calls [Symbol.iterator]() and then next() until it returns done: true; Java's enhanced for works on anything Iterable; Python's for calls iter() and next(); a C++ range-based for calls begin() and end().

The practice checks have no Iterator detector, and all three versions read as clean. What they show is the dependency change: in the first version's diagram both clients depend on Carriage, and after the refactor they don't.

Check yourself

4 questions

1. The operator adds a dining car with no seats. What changes?
2. Why is returning the internal list of carriages worse than returning an iterator?
3. A client removes seats from a list while a for-each loop walks it. What does Java's ArrayList do?
4. When is internal iteration (forEach) the better fit?

Takeaways

Remember this

  • Iterator hands out a collection's elements one at a time, hiding how they are stored.
  • Clients write one loop and depend only on the element type, not on the structure.
  • The collection can change its storage, such as adding decks, without touching its clients.
  • Each language builds the pattern into its for loop; follow its protocol, often with a generator or view.
  • Don't modify a collection while iterating it, except through the iterator.