Published on

迭代器模式详解

Authors
  • avatar
    Name
    青雲
    Twitter

迭代器模式（Iterator Pattern）是一种行为型设计模式，它提供了一种方法顺序访问一个聚合对象中的各个元素，而无需暴露该对象的内部表示。通过迭代器模式，可以对不同的数据结构进行遍历，而不需要了解这些数据结构的内部实现。

为什么需要迭代器模式？

我们去餐厅吃饭，餐厅提供了一份菜单，菜单上列出了所有可供选择的菜品。菜单就是一个集合，每道菜品是集合中的元素。

如果没有迭代器，你需要直接与菜单的内部结构打交道来查找你想要了解的菜品信息。例如，如果菜单以数组形式组织，你需要知道怎么操作数组来查询菜品；如果菜单是一个复杂的数据结构，比如树或图，那么查找过程会更加复杂。这样不仅提高了使用者的负担，也使得菜单的修改（如结构调整）变得更加困难，因为每次修改后，顾客都可能需要以新的方式查询菜品。

有了迭代器模式后，事情就变得简单多了。餐厅提供一个「菜单迭代器」，这个迭代器知道如何遍历菜单中的每一道菜，而你只需要通过迭代器提供的接口（如 next() 获取下一道菜，hasNext() 检查是否还有更多的菜），就可以逐个查阅菜单项，完全无需关心菜单背后的数据结构是怎样的。这样即使菜单的内部结构变了，只要迭代器的接口保持不变，顾客查看菜单的方式就不需要改变。

在软件开发中，不同的集合结构（如数组、链表、树等）有不同的遍历方式。如果直接在客户端代码中实现遍历逻辑，不仅会导致代码重复，还会使代码紧耦合。这种情况会增加维护成本，限制代码的灵活性和可扩展性。

迭代器模式通过将遍历过程封装到迭代器对象中，使得客户端代码只需依赖于迭代器接口，而不需要了解具体集合结构的实现。这使得代码更具通用性和可移植性。

基本概念

迭代器模式主要包含以下角色：

  1. 迭代器接口（Iterator）：定义访问和遍历元素的方法。
  2. 具体迭代器（Concrete Iterator）：实现迭代器接口，定义迭代算法。
  3. 聚合（Aggregate）：定义创建相应迭代器的方法。
  4. 具体聚合（Concrete Aggregate）：实现聚合接口，提供具体集合的迭代器。

实现示例

假设我们有一个数组和一个链表，希望对它们进行遍历。可以使用迭代器模式来实现。

定义迭代器接口

// 迭代器接口，定义访问和遍历元素的方法
interface Iterator<T> {
  next(): T | null;
  hasNext(): boolean;
}

定义聚合接口

// 聚合接口，定义创建迭代器的方法
interface Aggregate<T> {
  createIterator(): Iterator<T>;
}

实现具体迭代器和具体聚合类

数组迭代器和数组聚合类

class ArrayIterator<T> implements Iterator<T> {
  private items: T[];
  private currentIndex: number = 0;

  constructor(items: T[]) {
    this.items = items;
  }

  next(): T | null {
    if (this.hasNext()) {
      return this.items[this.currentIndex++];
    }
    return null;
  }

  hasNext(): boolean {
    return this.currentIndex < this.items.length;
  }
}

class ArrayAggregate<T> implements Aggregate<T> {
  private items: T[];

  constructor(items: T[]) {
    this.items = items;
  }

  createIterator(): Iterator<T> {
    return new ArrayIterator(this.items);
  }
}

链表迭代器和链表聚合类

 class ListNode<T> {
  value: T;
  next: ListNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

class LinkedListIterator<T> implements Iterator<T> {
  private currentNode: ListNode<T> | null;

  constructor(head: ListNode<T> | null) {
    this.currentNode = head;
  }

  next(): T | null {
    if (this.hasNext()) {
      const value = this.currentNode!.value;
      this.currentNode = this.currentNode!.next;
      return value;
    }
    return null;
  }

  hasNext(): boolean {
    return this.currentNode !== null;
  }
}

class LinkedListAggregate<T> implements Aggregate<T> {
  private head: ListNode<T> | null = null;

  add(value: T): void {
    const newNode = new ListNode(value);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  createIterator(): Iterator<T> {
    return new LinkedListIterator(this.head);
  }
}

使用迭代器模式

// 创建数组并使用迭代器遍历
const arrayAggregate = new ArrayAggregate<number>([1, 2, 3, 4, 5]);
const arrayIterator = arrayAggregate.createIterator();
while (arrayIterator.hasNext()) {
  console.log(arrayIterator.next()); // 输出: 1 2 3 4 5
}

// 创建链表并使用迭代器遍历
const linkedListAggregate = new LinkedListAggregate<number>();
linkedListAggregate.add(1);
linkedListAggregate.add(2);
linkedListAggregate.add(3);
linkedListAggregate.add(4);
linkedListAggregate.add(5);
const linkedListIterator = linkedListAggregate.createIterator();
while (linkedListIterator.hasNext()) {
  console.log(linkedListIterator.next()); // 输出: 1 2 3 4 5
}

应用场景

数组和集合的遍历

JavaScript 原生的 Array 对象和 ES6 引入的 Set、Map 等集合类型都支持迭代器接口，使得遍历这些集合变得简单和一致。通过使用 for...of 循环或手动调用迭代器的 next 方法，可以直接遍历集合对象。

const array = [1, 2, 3, 4, 5];
const iterator = array[Symbol.iterator]();

while (true) {
  const { value, done } = iterator.next();
  if (done) break;
  console.log(value);
}

// 使用 for...of 循环
for (const value of array) {
  console.log(value);
}

自定义数据结构遍历

在前端开发中，我们常常会使用一些自定义的数据结构，比如树、图等。通过实现迭代器接口，可以为这些数据结构提供统一的遍历操作。

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  addChild(child) {
    this.children.push(child);
  }

  [Symbol.iterator]() {
    return this.preorderTraversal();
  }

  *preorderTraversal() {
    yield this.value;
    for (const child of this.children) {
      yield* child.preorderTraversal();
    }
  }
}

// 使用示例
const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
root.addChild(child1);
root.addChild(child2);
child1.addChild(new TreeNode(4));
child1.addChild(new TreeNode(5));

for (const value of root) {
  console.log(value); // 输出: 1 2 4 5 3
}

异步数据流遍历

迭代器模式不仅限于同步操作，在前端开发中，处理异步数据流也是一个常见需求。使用 async 迭代器，可以以一致的方式处理异步数据流。

async function* asyncGenerator() {
  yield new Promise(resolve => setTimeout(() => resolve(1), 1000));
  yield new Promise(resolve => setTimeout(() => resolve(2), 1000));
  yield new Promise(resolve => setTimeout(() => resolve(3), 1000));
}

// 使用示例
(async () => {
  for await (const value of asyncGenerator()) {
    console.log(value); // 每间隔 1 秒输出 1 2 3
  }
})();

典型案例

Babel

Babel 是一个广泛使用的 JavaScript 编译器，通过实现访问者模式和迭代器模式，能够遍历和转换 JavaScript 的抽象语法树（AST）。

// 使用 Babel 遍历和修改 AST
const parser = require('@babel/parser');
const traverse = require('@babel/traverse').default;
const generator = require('@babel/generator').default;

const code = 'const x = 1;';
const ast = parser.parse(code);

const visitor = {
  VariableDeclaration(path) {
    path.node.kind = 'let';
  }
};

traverse(ast, visitor);
const newCode = generator(ast).code;
console.log(newCode); // 输出: let x = 1;

Lodash

Lodash 是一个非常流行的 JavaScript 工具库，提供了很多集合迭代函数，例如 _.map，_.filter，_.reduce 等，这些函数都采用了迭代器模式在内部实现对集合的遍历。

const _ = require('lodash');

const array = [1, 2, 3, 4, 5];
const result = _.map(array, x => x * 2);
console.log(result); // 输出: [2, 4, 6, 8, 10]

Immutable.js

Immutable.js 提供了持久性不可变数据结构，其集合类型（如 List，Map 等）均实现了迭代器接口，从而支持直接使用 for...of 循环和其他迭代方法。

const { List } = require('immutable');

const list = List([1, 2, 3, 4, 5]);

for (const value of list) {
  console.log(value); // 输出: 1 2 3 4 5
}

优缺点

优点

  1. 分离遍历行为与聚合对象：
    • 迭代器模式将遍历行为从聚合对象中分离出来，使得聚合对象不需要关心具体的遍历实现。这提供了一种解耦机制，让聚合对象只关注其数据存储和管理，而不需关心如何遍历这些数据。
  2. 支持多种遍历方式：
    • 可以为同一个聚合对象提供不同的迭代器，从而实现不同的遍历方式（如前序、中序、后序遍历等）。这使得代码更加灵活和可扩展，能够根据需求选择适当的遍历方法。
  3. 简化聚合类：
    • 聚合类不需要实现复杂的遍历逻辑，只需提供创建迭代器的方法，使得聚合类更简洁、更易于维护。这种简化使得聚合类在设计上更加聚焦，其职责更加单一。
  4. 一致性和通用性：
    • 通过提供一致的迭代器接口，客户端代码可以一致地使用迭代器接口进行遍历，而不需要了解具体集合结构的实现。这提高了代码的通用性和可复用性。

缺点

  1. 增加类的数量：
    • 每个聚合类都需要一个对应的迭代器类，这会增加系统的类数量，可能增加代码的复杂度。在设计和实现上需要考虑类数量的管理和维护。
  2. 遍历方法的修改不便：
    • 如果需要修改遍历方法，必须修改迭代器类，这可能会影响到其他使用相同迭代器的地方。因此，在设计迭代器时，需要慎重考虑和预见未来的扩展和修改需求。
  3. 性能开销：
    • 在某些情况下，尤其是对于大型数据结构，迭代器引入的额外对象和方法调用可能会带来性能开销。需要根据具体应用场景评估迭代器的性能影响。

总结

迭代器模式通过将遍历行为封装到独立的迭代器对象中，使得客户端代码可以统一使用迭代器接口进行遍历，而不需要了解具体集合结构的实现。它在提供一致遍历方法、解耦遍历逻辑和聚合对象、支持多种遍历方式等方面具有明显的优势。然而，迭代器模式也引入了额外的类和复杂度，可能带来一定的性能开销。在实际开发中，需要权衡这些优缺点，根据具体情况采用迭代器模式来提高代码的通用性和可维护性。

Discuss on Twitter • View on GitHub