Leon's blog
leon yu
2024-08-27
目录

迭代器与生成器

# 迭代器

# 迭代器模式

笔记

迭代器模式（特别是在ECMAScript 这个语境下）描述了一个方案，即可以把有些结构称为“可迭代对象”（iterable），因为它们实现了正式的Iterable 接口，而且可以通过迭代器Iterator 消费。可迭代对象是一种抽象的说法。基本上，可以把可迭代对象理解成数组或集合这样的集合类型的对象。它们包含的元素都是有限的，而且都具有无歧义的遍历顺序。

不过，可迭代对象不一定是集合对象，也可以是仅仅具有类似数组行为的其他数据结构。

临时性可迭代对象可以实现为生成器，本章后面会讨论。

如果对象原型链上的父类实现了Iterable 接口，那这个对象也就实现了这个接口：

# 迭代器协议

笔记

迭代器是一种一次性使用的对象，用于迭代与其关联的可迭代对象。迭代器API 使用next()方法在可迭代对象中遍历数据。每次成功调用next()，都会返回一个IteratorResult 对象，其中包含迭代器返回的下一个值。若不调用next()，则无法知道迭代器的当前位置。

next()方法返回的迭代器对象IteratorResult 包含两个属性：done 和value。done 是一个布尔值，表示是否还可以再次调用next()取得下一个值；value 包含可迭代对象的下一个值（done 为false），或者undefined（done 为true）。done: true 状态称为“耗尽”。

每个迭代器都表示对可迭代对象的一次性有序遍历。不同迭代器的实例相互之间没有联系，只会独 立地遍历可迭代对象：

let arr = ['foo', 'bar'];
let iter1 = arr[Symbol.iterator]();
let iter2 = arr[Symbol.iterator]();
console.log(iter1.next()); // { done: false, value: 'foo' }
console.log(iter2.next()); // { done: false, value: 'foo' }
console.log(iter2.next()); // { done: false, value: 'bar' }
console.log(iter1.next()); // { done: false, value: 'bar' }
1
2
3
4
5
6
7

迭代器并不与可迭代对象某个时刻的快照绑定，而仅仅是使用游标来记录遍历可迭代对象的历程。 如果可迭代对象在迭代期间被修改了，那么迭代器也会反映相应的变化：

let arr = ['foo', 'baz'];
let iter = arr[Symbol.iterator]();
console.log(iter.next()); // { done: false, value: 'foo' }
// 在数组中间插入值
arr.splice(1, 0, 'bar');
console.log(iter.next()); // { done: false, value: 'bar' }
console.log(iter.next()); // { done: false, value: 'baz' }
console.log(iter.next()); // { done: true, value: undefined }
1
2
3
4
5
6
7
8

提示

迭代器维护着一个指向可迭代对象的引用，因此迭代器会阻止垃圾回收程序回收可迭代对象。

# 自定义迭代器

与Iterable 接口类似，任何实现Iterator 接口的对象都可以作为迭代器使用。下面这个例子中的Counter 类只能被迭代一定的次数：

class Counter {
  // Counter 的实例应该被迭代 limit 次
  constructor(limit) {
    this.count = 1
    this.limit = limit
  }

  next() {
    if (this.count <= this.limit) {
      return { done: false, value: this.count++ }
    } else {
      return { done: true, value: undefined }
    }
  }

  [Symbol.iterator]() {
    return this
  }
}
let counter = new Counter(3)
for (let i of counter) {
  console.log(i)
}
// 1
// 2
// 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这个类实现了Iterator 接口，但不理想。这是因为它的每个实例只能被迭代一次。

为了让一个可迭代对象能够创建多个迭代器，必须每创建一个迭代器就对应一个新计数器。为此，可以把计数器变量放到闭包里，然后通过闭包返回迭代器：

class Counter {
  constructor(limit) {
    this.limit = limit
  }

  [Symbol.iterator]() {
    let count = 1
    let limit = this.limit
    return {
      next() {
        if (count <= limit) {
          return { done: false, value: count++ }
        } else {
          return { done: true, value: undefined }
        }
      }
    }
  }
}
let counter = new Counter(3);
for (let i of counter) { console.log(i); }
// 1
// 2
// 3
for (let i of counter) { console.log(i); }
// 1
// 2
// 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

每个以这种方式创建的迭代器也实现了Iterable 接口。Symbol.iterator 属性引用的工厂函数会返回相同的迭代器。因为每个迭代器也实现了Iterable 接口，所以它们可以用在任何期待可迭代对象的地方。

# 提前终止迭代器

内置语言结构在发现还有更多值可以迭代，但不会消费这些值时，会自动调用 return()方法。

class Counter {
  constructor(limit) {
    this.limit = limit;
  }
  [Symbol.iterator]() {
    let count = 1,
    limit = this.limit;
    return {
      next() {
        if (count <= limit) {
          return { done: false, value: count++ };
        } else {
          return { done: true };
        }
      },
      return() {
        console.log('Exiting early');
        return { done: true };
      }
    };
  }
}
let counter1 = new Counter(5);
for (let i of counter1) {
  if (i > 2) {
    break;
  }
  console.log(i);
}
// 1
// 2
// Exiting early
let counter2 = new Counter(5);
try {
  for (let i of counter2) {
if (i > 2) {
  throw 'err';
}
  console.log(i);
}
} catch(e) {}
// 1
// 2
// Exiting early
let counter3 = new Counter(5);
let [a, b] = counter3;
// Exiting early
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

如果迭代器没有关闭，则还可以继续从上次离开的地方继续迭代。比如，数组的迭代器就是不能关闭的：

let a = [1, 2, 3, 4, 5];
let iter = a[Symbol.iterator]();
for (let i of iter) {
  console.log(i);
  if (i > 2) {
    break
  }
}
// 1
// 2
// 3
for (let i of iter) {
  console.log(i);
}
// 4
// 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

因为return()方法是可选的，所以并非所有迭代器都是可关闭的。要知道某个迭代器是否可关闭，可以测试这个迭代器实例的return 属性是不是函数对象。不过，仅仅给一个不可关闭的迭代器增加这个方法并不能让它变成可关闭的。这是因为调用return()不会强制迭代器进入关闭状态。即便如此，return()方法还是会被调用。

let a = [1, 2, 3, 4, 5];
let iter = a[Symbol.iterator]();
iter.return = function() {
  console.log('Exiting early');
  return { done: true };
};
for (let i of iter) {
  console.log(i);
  if (i > 2) {
    break
  }
}
// 1
// 2
// 3
// 提前退出
for (let i of iter) {
  console.log(i);
}
// 4
// 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 生成器

笔记

生成器是ECMAScript 6 新增的一个极为灵活的结构，拥有在一个函数块内暂停和恢复代码执行的能力。这种新能力具有深远的影响，比如，使用生成器可以自定义迭代器和实现协程。

生成器的形式是一个函数，函数名称前面加一个星号（*）表示它是一个生成器。只要是可以定义函数的地方，就可以定义生成器。

// 生成器函数声明
function* generatorFn() {}
// 生成器函数表达式
let generatorFn = function* () {}
// 作为对象字面量方法的生成器函数
let foo = {
  * generatorFn() {}
}
// 作为类实例方法的生成器函数
class Foo {
  * generatorFn() {}
}
// 作为类静态方法的生成器函数
class Bar {
  static * generatorFn() {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提示

箭头函数不能用来定义生成器函数。

标识生成器函数的星号不受两侧空格的影响。

yield 关键字只能在生成器函数内部使用，用在其他地方会抛出错误。类似函数的return 关键字，yield 关键字必须直接位于生成器函数定义中，出现在嵌套的非生成器函数中会抛出语法错误

# 生成器对象作为可迭代对象

在生成器对象上显式调用next()方法的用处并不大。其实，如果把生成器对象当成可迭代对象，那么使用起来会更方便。

function* generatorFn() {
  yield 1;
  yield 2;
  yield 3;
}
for (const x of generatorFn()) {
  console.log(x);
}
// 1
// 2
// 3
1
2
3
4
5
6
7
8
9
10
11

# 使用 yield 实现输入输出

除了可以作为函数的中间返回语句使用，yield 关键字还可以作为函数的中间参数使用。上一次让生成器函数暂停的yield 关键字会接收到传给next()方法的第一个值。这里有个地方不太好理解——第一次调用next()传入的值不会被使用，因为这一次调用是为了开始执行生成器函数：

function* generatorFn(initial) {
  console.log(initial);
  console.log(yield);
  console.log(yield);
}
let generatorObject = generatorFn('foo');
generatorObject.next('bar'); // foo
generatorObject.next('baz'); // baz
generatorObject.next('qux'); // qux
1
2
3
4
5
6
7
8
9

# 产生可迭代对象

可以使用星号增强yield 的行为，让它能够迭代一个可迭代对象，从而一次产出一个值：

// 等价的generatorFn：
// function* generatorFn() {
// for (const x of [1, 2, 3]) {
// yield x;
// }
// }
function* generatorFn() {
  yield* [1, 2, 3];
}
let generatorObject = generatorFn();
for (const x of generatorFn()) {
  console.log(x);
}
// 1
// 2
// 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 使用 yield*实现递归算法

yield*最有用的地方是实现递归操作，此时生成器可以产生自身。

function* nTimes(n) {
  if (n > 0) {
    yield* nTimes(n - 1);
    yield n - 1;
  }
}
for (const x of nTimes(3)) {
  console.log(x);
}
// 0
// 1
// 2
1
2
3
4
5
6
7
8
9
10
11
12

在这个例子中，每个生成器首先都会从新创建的生成器对象产出每个值，然后再产出一个整数。结果就是生成器函数会递归地减少计数器值，并实例化另一个生成器对象。从最顶层来看，这就相当于创建一个可迭代对象并返回递增的整数。

使用递归生成器结构和yield*可以优雅地表达递归算法。下面是一个图的实现，用于生成一个随机的双向图：

class Node {
  constructor(id) {
    this.id = id
    this.neighbors = new Set()
  }
  connect(node) {
    if (node !== this) {
      this.neighbors.add(node)
      node.neighbors.add(this)
    }
  }
}
class RandomGraph {
  constructor(size) {
    this.nodes = new Set()
    // 创建节点
    for (let i = 0; i < size; ++i) {
      this.nodes.add(new Node(i))
    }
    // 随机连接节点
    const threshold = 1 / size
    for (const x of this.nodes) {
      for (const y of this.nodes) {
        if (Math.random() < threshold) {
          x.connect(y)
        }
      }
    }
  }
  // 这个方法仅用于调试
  print() {
    for (const node of this.nodes) {
      const ids = [...node.neighbors].map((n) => n.id).join(",")
      console.log(`${node.id}: ${ids}`)
    }
  }
}
const g = new RandomGraph(6)
g.print()
// 示例输出：
// 0: 2,3,5
// 1: 2,3,4,5
// 2: 1,3
// 3: 0,1,2,4
// 4: 2,3
// 5: 0,4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

图数据结构非常适合递归遍历，而递归生成器恰好非常合用。为此，生成器函数必须接收一个可迭代对象，产出该对象中的每一个值，并且对每个值进行递归。这个实现可以用来测试某个图是否连通，

即是否没有不可到达的节点。只要从一个节点开始，然后尽力访问每个节点就可以了。结果就得到了一个非常简洁的深度优先遍历：

class Node {
  constructor(id) {
    ...
  }
  connect(node) {
    ...
  }
}

class RandomGraph {
  constructor(size) {
    ...
  }
  print() {
    ...
  }
  isConnected() {
    const visitedNodes = new Set();
    function* traverse(nodes) {
      for (const node of nodes) {
        if (!visitedNodes.has(node)) {
          yield node;
          yield* traverse(node.neighbors);
        }
      }
    }
    // 取得集合中的第一个节点
    const firstNode = this.nodes[Symbol.iterator]().next().value;
    // 使用递归生成器迭代每个节点
    for (const node of traverse([firstNode])) {
      visitedNodes.add(node);
    }
    return visitedNodes.size === this.nodes.size;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 生成器作为默认迭代器

因为生成器对象实现了Iterable 接口，而且生成器函数和默认迭代器被调用之后都产生迭代器，所以生成器格外适合作为默认迭代器。下面是一个简单的例子，这个类的默认迭代器可以用一行代码产出类的内容：

class Foo {
  constructor() {
    this.values = [1, 2, 3];
  }
  *[Symbol.iterator]() {
    yield* this.values;
  }
}

const f = new Foo()
for (const x of f) {
  console.log(x);
}
// 1
// 2
// 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 提前终止生成器

生成器函数返回的生成器对象可以手动停止，有三种方法可以做到这一点：

  • return()：调用return()方法可以提前终止生成器函数。传递给return()方法的值，就是生成器函数的返回值。在生成器函数中，return()方法之后的任何代码都不会执行了。

  • throw()：调用throw()方法会抛出错误，并终止生成器。在生成器函数中，throw()方法之后的任何代码都不会执行了。

#核心技术
最近更新～: 2024/08/28, 12:02:09
集合引用类型
对象、类与面向对象编程

← 对象、类与面向对象编程→

最近更新
01
应用层
01-11
02
计算机网络和因特网
12-22
03
关于
12-22
更多文章>
Theme by Vdoing | Copyright © 2024-2025 主题来自 Evan Xu | MIT License