迭代器模式详解与示例

意图与它要解决的问题

意图：提供一种方法，顺序访问聚合对象中的各个元素，而又不暴露该对象的内部表示。迭代器是《设计模式》（Gang of Four，GoF）一书中的行为型模式之一。

设想一个把公司组织架构存成树的类。程序的不同部分都需要列出所有员工：一份报表按层级逐层输出，另一份需要深度优先顺序。如果每份报表都自己遍历这棵树，每份报表就都依赖树的内部字段，一旦把树改成别的存储方式，它们会全部出错。

有了迭代器，树会提供迭代器对象。报表只需要获取一个迭代器，并不断调用 next() 直到结束。报表并不知道数据是一棵树、一个数组，还是从数据库逐页取回的行。

结构与参与者

在 JavaScript 中，这些角色有标准名称，由 ES2015 的迭代协议定义。可迭代对象（iterable）拥有 [Symbol.iterator]() 方法。迭代器（iterator）拥有返回 { value, done } 的 next() 方法。每一个 for...of 循环、展开语法 [...x] 和解构赋值都使用这些协议。

TypeScript 实现：手写迭代器

这个 range 类只保存起点、终点和步长，而不是一个数字列表。它的迭代器按需计算每个值。

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

每次调用 [Symbol.iterator]() 都会返回一个带有自己 current 位置的新迭代器，因此 evens 可以被循环两次。如果集合每次返回同一个迭代器，第二次循环就看不到任何元素。

生成器：用更少的代码写迭代器

用 function* 编写的生成器函数会自动创建迭代器。每个 yield 产出下一个值，函数随后暂停，直到再次调用 next()。下面的二叉树提供了中序遍历，而不暴露其节点：

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
}

何时使用，何时不用

• 当集合的内部结构复杂（树、图、分页 API），而你希望客户端能简单地循环访问时使用。
• 当需要对同一份数据提供多种遍历顺序（例如深度优先和广度优先）时使用。
• 用于惰性序列或无限序列，其中的值只在被请求时才计算。
• 用它为不同的集合提供统一的循环接口。
• 对已经是数组的数据，不要再写自定义迭代器。直接返回数组（或只读副本），让调用方使用内置的迭代方式即可。
• 当调用方需要按索引随机访问或需要提前知道长度时，不要使用惰性迭代器；数组更合适。

实际应用

• JavaScript：Array、Map、Set 和 String 都是可迭代对象，map.entries() 或 set.values() 返回迭代器。
• Java：带有 hasNext() 和 next() 的 java.util.Iterator 接口，任何 Iterable 上的增强 for 循环都用它。
• Python：由 __iter__ 和 __next__ 构成的迭代器协议，以及使用 yield 的生成器函数。
• 数据库和 API：查询结果的游标和分页 HTTP API 每次只提供一页结果，客户端因此可以遍历非常大的结果集，而不必全部载入内存。

相关模式