Iterator pattern explained with examples

Intent and the problem it solves

Intent: provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation. Iterator is one of the behavioral patterns in the Gang of Four (GoF) book.

Imagine a class that stores a company's org chart as a tree. Different parts of the program need to list all employees: one report goes level by level, another needs depth-first order. If each report walks the tree itself, every report depends on the tree's internal fields, and changing the tree to use a different storage breaks all of them.

With Iterator, the tree offers iterator objects. A report asks for an iterator and calls next() until it is done. The report does not know whether the data is a tree, an array or rows fetched from a database page by page.

Structure and participants

In JavaScript these roles have standard names, defined by the iteration protocols in ES2015. An iterable has a [Symbol.iterator]() method. An iterator has a next() method that returns { value, done }. Every for...of loop, spread [...x] and destructuring assignment uses these protocols.

TypeScript implementation: a hand-written iterator

This range class stores only its start, end and step, not a list of numbers. Its iterator computes each value on demand.

class Range implements Iterable<number> {
  constructor(private start: number, private end: number, private step = 1) {}

  [Symbol.iterator](): Iterator<number> {
    let current = this.start;
    const { end, step } = this;
    return {
      next(): IteratorResult<number> {
        if (current >= end) return { value: undefined, done: true };
        const value = current;
        current += step;
        return { value, done: false };
      },
    };
  }
}

const evens = new Range(0, 10, 2);
for (const n of evens) console.log(n); // 0 2 4 6 8 (one per line)
console.log([...evens]); // [ 0, 2, 4, 6, 8 ]
console.log(Math.max(...new Range(1, 4))); // 3

Each call to [Symbol.iterator]() returns a fresh iterator with its own current position. That is why evens can be looped over twice. If the collection returned the same iterator every time, the second loop would see no elements.

Generators: iterators with less code

A generator function, written with function*, creates an iterator automatically. Each yield produces the next value, and the function pauses until next() is called again. Here a binary tree offers an in-order traversal without exposing its nodes:

class TreeNode<T> {
  constructor(public value: T, public left?: TreeNode<T>, public right?: TreeNode<T>) {}
}

class BinaryTree<T> implements Iterable<T> {
  constructor(private root?: TreeNode<T>) {}

  *[Symbol.iterator](): Generator<T> {
    yield* inOrder(this.root);
  }
}

function* inOrder<T>(node?: TreeNode<T>): Generator<T> {
  if (!node) return;
  yield* inOrder(node.left);
  yield node.value;
  yield* inOrder(node.right);
}

const tree = new BinaryTree(
  new TreeNode(5, new TreeNode(3, new TreeNode(1)), new TreeNode(8)),
);
console.log([...tree]); // [ 1, 3, 5, 8 ]

for (const value of tree) {
  if (value > 3) break; // stops early; the rest is never computed
  console.log(value); // 1, then 3
}

When to use it and when not to

• Use it when a collection has a complex internal structure (tree, graph, paged API) and you want clients to loop over it simply.
• Use it to offer several traversal orders over the same data, such as depth-first and breadth-first.
• Use it for lazy or infinite sequences, where values are computed only when requested.
• Use it to give different collections one uniform loop interface.
• Do not write a custom iterator for data that is already an array. Return the array (or a read-only copy) and let callers use the built-in iteration.
• Do not use a lazy iterator when callers need random access by index or the length up front; an array is a better fit.

Real-world uses

• JavaScript: Array, Map, Set and String are iterables, and map.entries() or set.values() return iterators.
• Java: the java.util.Iterator interface with hasNext() and next(), used by the enhanced for loop on any Iterable.
• Python: the iterator protocol with __iter__ and __next__, and generator functions using yield.
• Databases and APIs: cursors over query results and paginated HTTP APIs expose results one page at a time, so clients can iterate over very large results without loading everything into memory.

Related patterns