迭代器和生成器 | 生成器（含手写生成器应用）

Posted on In , , Symbols count in article: 11k Reading time ≈ 10 mins.

生成器

生成器是ES6新增的解构，拥有在一个函数块内暂停和恢复代码执行的能力

生成器基础

生成器的形式是一个函数，函数名称前面加一个星号（*）【星号不受两侧空格影响】表示它是一个生成器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
	只要是可以定义函数的地方，就可以定义生成器
*/ 

// 生成器函数声明
function * generatorFn() {}

// 生成器函数表达式
let generatorFn = function *() {}

// 作为对象字面量方法的生成器函数
let person = {
    * generatorFn() {}
}

// 作为类实例方法的生成器函数
class Person {
    * generatorFnn() {}
}

// 作为类静态方法的生成器函数
class Person {
    static * generatorFn() {}
}

  • 调用生成器函数会生成一个生成器对象

    • 生成器对象一开始处于暂停状态（suspended）

  • 生成器方法也实现了Iterator接口，因此也可以调用next()方法，一旦调用这个方法，就会让生成器开始或者恢复执行（相当于激活了~）

    • next()方法返回值类似于迭代器，有一个done属性和一个value属性

    • 函数体为空的生成器中间不会停留，调用一次next()就会让生成器达到done:true状态

      1
      2
      3
      4
      5
      6
      function *generatorFn() {}   // 定义一个生成器对象，生成器对象是一个函数

      let g = generatorFn();   // 调用生成器对象

      console.log(g);         //  generatorFn {<suspended>}   生成器对象处于暂停状态
      console.log(g.next());  //  {value: undefined, done: true}

    • value属性是生成器的返回值，默认为undefined，可以通过生成器函数的返回值指定

      1
      2
      3
      4
      5
      6
      7
      8
      function *generatorFn() {
          return 'foo'
      }

      let g = generatorFn();

      console.log(g);         //  generatorFn {<suspended>}   
      console.log(g.next());   // {value: 'foo', done: true}

  • 生成器函数只会在初次调用next()方法后开始执行

    1
    2
    3
    4
    5
    6
    7
    8
    function *generatorFn() {
        console.log('foo');
    }

    let g = generatorFn();    // 并不会打印foo

    console.log(g);         //  generatorFn {<suspended>}   
    g.next()   // 'foo'

  • 生成器对象实现了Iterator接口，它们默认的迭代器是自引用的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    function *generatorFn() {}

    console.log(generatorFn);   // ƒ *generatorFn() {}
    console.log(generatorFn()[Symbol.iterator]);  // ƒ [Symbol.iterator]() { [native code] }
    console.log(generatorFn());  // generatorFn {<suspended>}
    console.log(generatorFn()[Symbol.iterator]());   // generatorFn {<suspended>}

    const g  = generatorFn();
    console.log(g === g[Symbol.iterator]());  // true

通过yield中断执行

yield关键字可以让生成器停止和开始执行

yield关键字只能在生成器函数内部使用

yield可以作为函数的中间返回语句使用，yield关键字可以作为函数的中间参数使用，yield关键字可以同时用于输入和输出

  • 生成器函数在遇到yield关键字之前正常执行，遇到这个关键字之后，执行会停止，函数作用域的状态会被保留，停止执行的生成器函数只能通过在生成器对象上调用next()方法来恢复执行
1
2
3
4
5
6
7
8
function *generatorFn() {
    yield;
}

let g = generatorFn();

console.log(g.next());   // {done: false, value: undefined}
console.log(g.next());   // {done: false, value: undefined}
  • yield关键字有点像函数中间的返回语句，它生成的值会出现在next()方法返回的对象里（不同的是：通过yield关键字退出的生成器函数会处在done:false状态；通过retrun关键字退出的生成器函数会处于done:true状态）
1
2
3
4
5
6
7
8
9
10
11
function *generatorFn() {
    yield 'foo';
    yield 'bar';
    return 'baz';
}

let g = generatorFn();

console.log(g.next());    // {done: false, value: 'foo'}
console.log(g.next());    // {done: false, value: 'bar'}
console.log(g.next());    // {done: true, value: 'baz'}
  • 生成器函数内部的执行流程会针对每个生成器对象区分作用域，在一个生成器对象上调用next()不会影响其他生成器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function *generatorFn() {
    yield 'foo';
    yield 'bar';
    return 'baz';
}

let g1 = generatorFn();
let g2 = generatorFn();

console.log(g1.next());    // {done: false, value: 'foo'}
console.log(g2.next());    // {done: false, value: 'foo'}

console.log(g1.next());    // {done: false, value: 'bar'}
console.log(g2.next());    // {done: false, value: 'bar'}
（1）生成器对象作为可迭代对象
1
2
3
4
5
6
7
8
9
10
11
12
13
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
12
13
function *nTimes(n) {   // 这个函数可以控制迭代循环的次数
    while (n--) {   // 当n为0时，while判断返回为false，循环退出
        yield;
    }
}

for (let _ of nTimes(3)) {
    console.log('foo');
}

// foo
// foo
// foo
（2）使用yield实现输入和输出

注意： 第一次调用next()传入的值不会被使用，因为这一次调用是为了开始执行生成器函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// yield关键字可以作为函数的中间参数使用
function *generatorFn(initial) {
    console.log(initial);
    console.log(yield);
    console.log(yield);            
}

let g = generatorFn('foo');     // 这时候生成器处于暂停状态，是不会输出任何结果的，必须使用next激活
g.next('bar')   // foo    第一次调用next()传入的值不会被使用，因为这一次调用是为了开始执行生成器函数
g.next('baz')   // baz
g.next('qux')   // qux

// yield关键字可以同时用于输入和输出
function *generatorFn() {
    return yield 'foo';
}

let g = generatorFn();    // generatorFn {<suspended>}  

console.log(g.next());   // 激活生成器函数   {value: 'foo', done: false}
console.log(g.next('bar'));  // {value: 'bar', done: true}

因为函数必须对整个表达式求值才能确定要返回的值，所以它在遇到yield关键字时暂停执行并计算出要产生的值："foo"，下一次调用next()传入了"bar"，作为交给同一个yield的值，然后这个值被确定为本次生成器函数要返回的值

（3）yield关键字可以允许使用多次

应用场景1：定义一个生成器函数，它会根据配置的值迭代相应次数并产生迭代的索引

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
// 实现1
function * nTimes(n) {
    for (let i = 0; i < n; i++) {
        yield i;
    }
}

for (let x of nTimes(3)) {
    console.log(x);
}

// 0
// 1
// 2


// 实现2
function * nTimes(n) {
    let i = 0;
    while (n--) {
        yield i++;
    }
}

for (let x of nTimes(3)) {
    console.log(x);
}

// 0
// 1
// 2

应用场景2：使用生成器实现范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function *range(start, end) {
    while (end > start) {
        yield start;
        start++;
    }
}

for (let x of range(4,7)) {
    console.log(x);
}

// 4
// 5
// 6

应用场景3：使用生成器实现填充数组

1
2
3
4
5
6
7
function *zeros(n) {
    while (n--) {
        yield 0;
    }
}

console.log(Array.from(zeros(8)))   // [0, 0, 0, 0, 0, 0, 0, 0]
（4）产生可迭代对象

可以使用星号（*）【星号两侧的空格不影响其行为】增强yield的值，让它能够迭代一个可迭代对象，从而一次产出一个值

  • yield*实际上只是将一个可迭代对象序列化为一连串可以单独产出的值
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
// 等价的generatorFn
// function * generatorFn() {
// 		for (const x of [1, 2, 3]) {
// 			yeild x;	
// 		}
// }

function * generatorFn() {
    yield * [1,2,3];
}

let g = generatorFn();

console.log(g.next().value);   // 1
console.log(g.next().value);   // 2 
console.log(g.next().value);   // 3

// 或者是
let g1 = generatorFn();

for (let x of g) {
    console.log(x);
}

// 1
// 2
// 3

  • yield*的值是关联迭代器返回done:true时的value属性

    • 对于普通的迭代器来说，这个值是undefined
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function * generatorFn() {
        console.log('iter value:', yield*[1,2,3])
    }

    for (const x of generatorFn()) {
        console.log(x);
    }

    // 1
    // 2
    // 3
    // iter value: undefined
    • 对于生成器函数产生的迭代器来说，这个值就是生成器函数返回的值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    function *innerGeneratorFn() {
        yield 'foo';
        return 'bar';
    }

    function *outerGeneratorFn(genObj) {
        console.log('iter value:', yield * innerGeneratorFn())
    }

    for (const x of outerGeneratorFn()) {
        console.log('value:', x);
    }

    // value: foo
    // iter value: bar
（5）使用yield*实现递归算法

实现递归操作是yield*最有用的地方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
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
48
49
50
51
52
53
54
55
56
57
58
// 创建节点 节点的邻里关系
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:1,3,4,5
// 1:0,3,4
// 2:4
// 3:1,0
// 4:2,0,1
// 5:0

生成器函数必须接收一个可迭代对象，产出该对象中的每一个值，并且对每个值进行递归，这个实现可以用来测试某个图是否连通，即是否没有不可到达的节点。只要从一个节点开始，然后尽力访问每个节点就可以了；结果就得到了一个非常简洁的深度优先遍历：

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
// 创建节点 节点的邻里关系
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.beighbors);
                  }
              }
          }
          
          // 取得集合中的第一个节点
          const firstNode = this.nides[Symbol.iterator]().next.value();
          
          // 使用递归生成器迭代每一个节点
          for (const node of traverse([firstNode])) {
              visitedNodes.add(node);
          }
          
          return visitedNodes.size === this.nodes.size;
      }
}

生成器作为默认迭代器

因为生成器实现了Iterator接口，而且生成器函数和默认迭代器被调用之后都产生迭代器，所以生成器适合作为默认迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

/*
	for-of 循环调用了默认迭代器（它恰好又是一个生成器函数）并产生了一个生成器对象
	这个生成器对象是可迭代的，所以完全可以在迭代中使用
*/

提前终止生成器

return() 和 throw() 方法都可以用于强制生成器进入关闭状态

（1）return()

return()方法会强制生成器进入关闭状态，提供给return的值就是终止迭代器对象的值

1
2
3
4
5
6
7
8
9
10
function * generatorFn() {
    for (const x of [1,2,3]) {
        yield x;
    }
}

const g = generatorFn(); 
console.log(g);  // generatorFn {<suspended>}
console.log(g.return(4)); // {value: 4, done: true};
console.log(g);  // generatorFn {<closed>}

  • 与迭代器不同，所有生成器对象都有return()方法，只要通过它进入关闭状态，就无法恢复了

  • 后续调用next()会显示done: true 状态，而提供的任何返回值都不会被存储或传播

1
2
3
4
5
6
7
8
9
10
11
12
function * generatorFn() {
    for (const x of [1,2,3]) {
        yield x;
    }
}

const g = generatorFn(); 
console.log(g);  // generatorFn {<suspended>}
console.log(g.return(4)); // {value: 4, done: true};
console.log(g.next());  // {value: undefined, done: true};
console.log(g.next());  // {value: undefined, done: true};
console.log(g.next());  // {value: undefined, done: true};
  • for-of 循环等内置语言结构会忽略状态为done: true 的IteratorObject 内部返回的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function * generatorFn() {
    for (const x of [1,2,3]) {
        yield x;
    }
}

const g = generatorFn();

for (let x of g) {
    if (x > 1) {
        g.return(4);
    }
    console.log(x);
}

// 1
// 2
（2）throw()

throw()方法会在暂停的时候将一个提供的错误注入到生成器对象中，如果错误未被处理，生成器就会关闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function * generatorFn() {
    for (const x of [1,2,3]) {
        yield x;
    }
}

const g = generatorFn();

console.log(g);  // generatorFn {<suspended>}

try {
    g.throw('foo');
} catch(e) {   // 错误会被catch捕获
    cnosole.log(e);   // foo
}
console.log(g);  // generatorFn {<closed>}
  • 假如生成器函数内部处理了这个错误，那么生成器就不会关闭，而且还可以恢复执行，错误处理会跳过对应的yield，因此在这个例子中会跳过一个值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function * generatorFn() {
    for (const x of [1,2,3]) {
        try {
            yield x;
        } catch(e) {
            console.log(e);
        }
    }
}

const g = generatorFn();

console.log(g.next());   // {value: 1, done: true};
g.throw('foo');          // foo
console.log(g.next());   // {value: 2, done: true};

/*
	跳过了value2
*/

在这个例子中，生成器在try/catch块中的yield关键字处暂停执行。在暂停期间，throw()方法向生成器对象内部注入了一个错误：字符串"foo"。这个错误会被yield关键字抛出。因为错误是在生成器的try/catch块中抛出的，所以仍然在生成器内部被捕获可是，由于yield抛出了那个错误，生成器就不会再产出值2。此时，生成器函数继续执行，在下一次迭代再次遇到yield关键字时产出了值3

注意：如果生成器对象还没有开始执行，那么调用throw()抛出的错误不会在函数内部被捕获，因为这相当于在函数块外部抛出了错误

1
2
3
4
5
6
7
8
9
10
11
12
function * generatorFn() {
    for (const x of [1,2,3]) {
        try {
            yield x;
        } catch(e) {
            console.log(e);
        }
    }
}

const g = generatorFn();
g.throw('foo');   // Uncaught foo  相当于在外部抛出了错误