迭代器与生成器

[webVueBlog]

理解迭代

1. ES5 新增了 Array.prototype.forEach()方法
2. 迭代会在一个有序集合上进行。（“有序”可以理解为集合中所有项都可以按照既定的顺序被遍历到，特别是开始和结束项有明确的定义。）数组是 JavaScript 中有序集合的最典型例子

let collection = ['foo', 'bar', 'baz'];
collection.forEach((item) => console.log(item));

迭代器模式

任何实现 Iterable 接口的数据结构都可以被实现 Iterator 接口的结构“消费”（consume）。迭代器（iterator）是按需创建的一次性对象。每个迭代器都会关联一个可迭代对象，而迭代器会暴露迭代其关联可迭代对象的 API。

1. 字符串
2. 数组
3. 映射
4. 集合
5. arguments对象
6. NodeList等DOM集合类型

let num = 1;
let obj = {};

// 这两种类型没有实现迭代器工厂函数
console.log(num[Symbol.iterator]); // undefined
console.log(obj[Symbol.iterator]); // undefined

let str = 'abc';
let arr = ['a', 'b', 'c'];
let map = new Map().set('a', 1).set('b', 2).set('c', 3);
let set = new Set().add('a').add('b').add('c');
let els = document.querySelectorAll('div');

// 这些类型都实现了迭代器工厂函数
console.log(str[Symbol.iterator]); // f values() { [native code] }
console.log(arr[Symbol.iterator]); // f values() { [native code] }
console.log(map[Symbol.iterator]); // f values() { [native code] }
console.log(set[Symbol.iterator]); // f values() { [native code] }
console.log(els[Symbol.iterator]); // f values() { [native code] }

// 调用这个工厂函数会生成一个迭代器
console.log(str[Symbol.iterator]()); // StringIterator {}
console.log(arr[Symbol.iterator]()); // ArrayIterator {}
console.log(map[Symbol.iterator]()); // MapIterator {}
console.log(set[Symbol.iterator]()); // SetIterator {}
console.log(els[Symbol.iterator]()); // ArrayIterator {}

接收可迭代对象的原生语言特性包括：

1. for-of循环
2. 数组解构
3. 扩展操作符
4. Array.from()
5. 创建集合
6. 创建映射
7. Promise.all()接收由期约组成的可迭代对象
8. Promise.race()接收由期约组成的可迭代对象
9. yield*操作符，在生成器中使用

let arr = ['foo', 'bar', 'baz'];
// for-of 循环
for (let el of arr) {
 console.log(el);
} 
// foo
// bar
// baz

// 数组解构
let [a, b, c] = arr;
console.log(a, b, c); // foo, bar, baz

// 扩展操作符
let arr2 = [...arr];
console.log(arr2); // ['foo', 'bar', 'baz']
// Array.from()
let arr3 = Array.from(arr);
console.log(arr3); // ['foo', 'bar', 'baz']

// Set 构造函数
let set = new Set(arr);
console.log(set); // Set(3) {'foo', 'bar', 'baz'}

// Map 构造函数
let pairs = arr.map((x, i) => [x, i]);
console.log(pairs); // [['foo', 0], ['bar', 1], ['baz', 2]]
let map = new Map(pairs);
console.log(map); // Map(3) { 'foo'=>0, 'bar'=>1, 'baz'=>2 }

如果对象原型链上的父类实现了 Iterable 接口，那这个对象也就实现了这个接口：
class FooArray extends Array {}
let fooArr = new FooArray('foo', 'bar', 'baz');
for (let el of fooArr) {
 console.log(el);
}
// foo
// bar
// baz

迭代器协议

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

// 可迭代对象
let arr = ['foo', 'bar'];
// 迭代器工厂函数
console.log(arr[Symbol.iterator]); // f values() { [native code] }
// 迭代器
let iter = arr[Symbol.iterator]();
console.log(iter); // ArrayIterator {}
// 执行迭代
console.log(iter.next()); // { done: false, value: 'foo' }
console.log(iter.next()); // { done: false, value: 'bar' }
console.log(iter.next()); // { done: true, value: undefined }

let arr = ['foo'];
let iter = arr[Symbol.iterator]();
console.log(iter.next()); // { done: false, value: 'foo' }
console.log(iter.next()); // { done: true, value: undefined }
console.log(iter.next()); // { done: true, value: undefined }
console.log(iter.next()); // { done: true, value: undefined } 

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' }

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 }

// 这个类实现了可迭代接口（Iterable）
// 调用默认的迭代器工厂函数会返回
// 一个实现迭代器接口（Iterator）的迭代器对象
class Foo {
 [Symbol.iterator]() {
 return {
 next() {
 return { done: false, value: 'foo' };
 }
 }
 }
}
let f = new Foo();

// Array 类型实现了可迭代接口（Iterable）
// 调用 Array 类型的默认迭代器工厂函数
// 会创建一个 ArrayIterator 的实例
let a = new Array();
// 打印出 ArrayIterator 的实例
console.log(a[Symbol.iterator]()); // Array Iterator {}

自定义迭代器

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

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

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, 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 

let arr = ['foo', 'bar', 'baz'];
let iter1 = arr[Symbol.iterator]();
console.log(iter1[Symbol.iterator]); // f values() { [native code] }
let iter2 = iter1[Symbol.iterator]();
console.log(iter1 === iter2); // true

let arr = [3, 1, 4];
let iter = arr[Symbol.iterator]();

for (let item of arr ) { console.log(item); }
// 3
// 1
// 4
for (let item of iter ) { console.log(item); }
// 3
// 1
// 4 

提前终止迭代器

1. return()方法用于指定在迭代器提前关闭时执行的逻辑
2. for-of 循环通过 break、continue、return 或 throw 提前退出
3. 解构操作并未消费所有值。

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 

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

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 

生成器

生成器是 ECMAScript 6 新增的一个极为灵活的结构，拥有在一个函数块内暂停和恢复代码执行的能力

生成器的形式是一个函数，函数名称前面加一个星号（*）表示它是一个生成器。

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

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

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

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

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

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

// 等价的生成器函数：
function* generatorFnA() {}
function *generatorFnB() {}
function * generatorFnC() {}

// 等价的生成器方法：
class Foo {
 *generatorFnD() {}
 * generatorFnE() {}
} 

调用生成器函数会产生一个生成器对象。生成器对象一开始处于暂停执行（suspended）的状态。与迭代器相似，生成器对象也实现了 Iterator 接口，因此具有 next()方法。调用这个方法会让生成器开始或恢复执行。

function* generatorFn() {}
const g = generatorFn();
console.log(g); // generatorFn {<suspended>}
console.log(g.next); // f next() { [native code] } 

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

function* generatorFn() {}
let generatorObject = generatorFn();
console.log(generatorObject); // generatorFn {<suspended>}
console.log(generatorObject.next()); // { done: true, value: undefined }

function* generatorFn() {
 return 'foo';
}
let generatorObject = generatorFn();
console.log(generatorObject); // generatorFn {<suspended>}
console.log(generatorObject.next()); // { done: true, value: 'foo' }

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

function* generatorFn() {
 console.log('foobar');
}
// 初次调用生成器函数并不会打印日志
let generatorObject = generatorFn();
generatorObject.next(); // foobar

function* generatorFn() {}
console.log(generatorFn);
// f* generatorFn() {}
console.log(generatorFn()[Symbol.iterator]);

// f [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关键字之前会正常执行。遇到这个关键字后，执行会停止，函数作用域的状态会被保留。停止执行的生成器函数只能通过在生成器对象上调用 next()方法来恢复执行

function* generatorFn() {
 yield;
}
let generatorObject = generatorFn();
console.log(generatorObject.next()); // { done: false, value: undefined }
console.log(generatorObject.next()); // { done: true, value: undefined } 

通过 yield 关键字退出的生成器函数会处在 done: false 状态；通过 return 关键字退出的生成器函数会处于 done: true 状态

function* generatorFn() {
 yield 'foo';
 yield 'bar';
 return 'baz';
}
let generatorObject = generatorFn();
console.log(generatorObject.next()); // { done: false, value: 'foo' }
console.log(generatorObject.next()); // { done: false, value: 'bar' }
console.log(generatorObject.next()); // { done: true, value: 'baz' }

生成器函数内部的执行流程会针对每个生成器对象区分作用域。

function* generatorFn() {
 yield 'foo';
 yield 'bar';
 return 'baz';
}
let generatorObject1 = generatorFn();
let generatorObject2 = generatorFn();
console.log(generatorObject1.next()); // { done: false, value: 'foo' }
console.log(generatorObject2.next()); // { done: false, value: 'foo' } 
console.log(generatorObject2.next()); // { done: false, value: 'bar' }
console.log(generatorObject1.next()); // { done: false, value: 'bar' } 

// 有效
function* validGeneratorFn() {
 yield;
}

// 无效
function* invalidGeneratorFnA() {
 function a() {
 yield;
 }
}

// 无效
function* invalidGeneratorFnB() {
 const b = () => {
 yield;
 }
}

// 无效
function* invalidGeneratorFnC() {
 (() => {
 yield;
 })();
} 

1. 生成器对象作为可迭代对象

2. 使用 yield 实现输入和输出

3. 产生可迭代对象

4. 使用 yield*实现递归算法

5. 生成器对象作为可迭代对象

function* generatorFn() {
 yield 1;
 yield 2;
 yield 3;
}
for (const x of generatorFn()) {
 console.log(x);
}
// 1
// 2
// 3 

通过一个简单的循环来实现

function* nTimes(n) {
 while(n--) {
 yield;
 }
}

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

2. 使用 yield 实现输入和输出

第一次调用 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

yield 关键字可以同时用于输入和输出

function* generatorFn() {
 return yield 'foo';
}
let generatorObject = generatorFn();
console.log(generatorObject.next()); // { done: false, value: 'foo' }
console.log(generatorObject.next('bar')); // { done: true, value: 'bar' } 

定义了一个无穷计数生成器函数

function* generatorFn() {
 for (let i = 0;;++i) {
 yield i;
 }
}
let generatorObject = generatorFn();
console.log(generatorObject.next().value); // 0
console.log(generatorObject.next().value); // 1
console.log(generatorObject.next().value); // 2
console.log(generatorObject.next().value); // 3
console.log(generatorObject.next().value); // 4
console.log(generatorObject.next().value); // 5 

function* nTimes(n) {
 for (let i = 0; i < n; ++i) {
 yield i;
 }
}
for (let x of nTimes(3)) {
 console.log(x);
}
// 0
// 1
// 2

function* nTimes(n) {
 let i = 0;
 while(n--) {
 yield i++;
 }
}
for (let x of nTimes(3)) {
 console.log(x);
}
// 0
// 1
// 2 

这样使用生成器也可以实现范围和填充数组：

function* range(start, end) {
 while(end > start) {
 yield start++;
 }
}
for (const x of range(4, 7)) {
 console.log(x);
}
// 4
// 5
// 6

function* zeroes(n) {
 while(n--) {
 yield 0;
 }
}
console.log(Array.from(zeroes(8))); // [0, 0, 0, 0, 0, 0, 0, 0]

3. 产生可迭代对象

// 等价的 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

function* generatorFn() {
 yield* [1, 2];
 yield *[3, 4];
 yield * [5, 6];
}
for (const x of generatorFn()) {
 console.log(x);
}
// 1
// 2
// 3
// 4
// 5
// 6 

因为 yield*实际上只是将一个可迭代对象序列化为一连串可以单独产出的值

function* generatorFnA() {
 for (const x of [1, 2, 3]) {
 yield x;
 }
}
for (const x of generatorFnA()) {
 console.log(x);
}
// 1
// 2
// 3
function* generatorFnB() {
 yield* [1, 2, 3];
}
for (const x of generatorFnB()) {
 console.log(x);
} 
// 1
// 2
// 3

yield*的值是关联迭代器返回 done: true 时的 value 属性。对于普通迭代器来说，这个值是undefined：

function* generatorFn() {
 console.log('iter value:', yield* [1, 2, 3]);
}
for (const x of generatorFn()) {
 console.log('value:', x);
}
// value: 1
// value: 2
// value: 3
// iter value: undefined

对于生成器函数产生的迭代器来说，这个值就是生成器函数返回的值：

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

4. 使用 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

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

使用递归生成器结构和 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 

图数据结构非常适合递归遍历，而递归生成器恰好非常合用。为此，生成器函数必须接收一个可迭代对象，产出该对象中的每一个值，并且对每个值进行递归。

这个实现可以用来测试某个图是否连通，即是否没有不可到达的节点。只要从一个节点开始，然后尽力访问每个节点就可以了。
结果就得到了一个非常简洁的深度优先遍历

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;
 }
} 

生成器作为默认迭代器

因为生成器对象实现了 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 

提前终止生成器

一个实现 Iterator 接口的对象一定有 next()方法，还有一个可选的 return()方法用于提前终止迭代器

还有第三个方法：throw()。

function* generatorFn() {}
const g = generatorFn();
console.log(g); // generatorFn {<suspended>}
console.log(g.next); // f next() { [native code] }
console.log(g.return); // f return() { [native code] }
console.log(g.throw); // f throw() { [native code] }

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

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

function* generatorFn() {
 for (const x of [1, 2, 3]) {
 yield x;
 }
}
const g = generatorFn();
console.log(g); // generatorFn {<suspended>}
console.log(g.return(4)); // { done: true, value: 4 }
console.log(g); // generatorFn {<closed>}

与迭代器不同，所有生成器对象都有 return()方法，只要通过它进入关闭状态，就无法恢复了。后续调用 next()会显示 done: true 状态，而提供的任何返回值都不会被存储或传播

function* generatorFn() {
 for (const x of [1, 2, 3]) {
 yield x;
 }
} 
const g = generatorFn();
console.log(g.next()); // { done: false, value: 1 }
console.log(g.return(4)); // { done: true, value: 4 }
console.log(g.next()); // { done: true, value: undefined }
console.log(g.next()); // { done: true, value: undefined }
console.log(g.next()); // { done: true, value: undefined } 

function* generatorFn() {
 for (const x of [1, 2, 3]) {
 yield x;
 }
}
const g = generatorFn();
for (const x of g) {
 if (x > 1) {
 g.return(4);
 }
 console.log(x);
}
// 1
// 2

throw()方法会在暂停的时候将一个提供的错误注入到生成器对象中。

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) {
 console.log(e); // foo
}
console.log(g); // generatorFn {<closed>} 

不过，假如生成器函数内部处理了这个错误，那么生成器就不会关闭，而且还可以恢复执行。错误处理会跳过对应的 yield

function* generatorFn() {
 for (const x of [1, 2, 3]) {
 try {
 yield x;
 } catch(e) {}
 }
}
const g = generatorFn();
console.log(g.next()); // { done: false, value: 1}
g.throw('foo');
console.log(g.next()); // { done: false, value: 3}

生成器在 try/catch 块中的 yield 关键字处暂停执行。

在暂停期间，throw()方法向生成器对象内部注入了一个错误：字符串"foo"。

这个错误会被 yield 关键字抛出。因为错误是在生成器的 try/catch 块中抛出的，所以仍然在生成器内部被捕获。
可是，由于 yield 抛出了那个错误，生成器就不会再产出值 2。

🆗