迭代器模式（Iterator）詳解與範例

意圖與要解決的問題

意圖：提供一種依序存取聚合物件中各元素的方法，而不暴露其底層表示。迭代器是《設計模式》（Gang of Four，簡稱 GoF）一書中的行為型模式之一。

想像一個以樹狀結構儲存公司組織圖的類別。程式的不同部分都需要列出所有員工：一份報表要逐層列出，另一份需要深度優先順序。如果每份報表都自己走訪這棵樹，每份報表就都依賴樹的內部欄位，一旦樹改用別的儲存方式，全部都會壞掉。

有了迭代器，樹會提供迭代器物件。報表只要向它要一個迭代器，並反覆呼叫 next() 直到結束。報表不需要知道資料是樹、陣列，還是分頁從資料庫取得的資料列。

結構與參與者

在 JavaScript 中，這些角色有 ES2015 迭代協定所定義的標準名稱。可迭代物件（iterable）有一個 [Symbol.iterator]() 方法。迭代器（iterator）有一個 next() 方法，回傳 { value, done }。每個 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：java.util.Iterator 介面，具有 hasNext() 與 next()，增強型 for 迴圈可用於任何 Iterable。
• Python：迭代器協定使用 __iter__ 與 __next__，以及使用 yield 的產生器函式。
• 資料庫與 API：查詢結果上的游標與分頁式 HTTP API 一次只提供一頁結果，用戶端因此可以遍歷非常龐大的結果，而不必把全部載入記憶體。

相關模式