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

Posted on In , , Symbols count in article: 9.3k Reading time ≈ 8 mins.

理解迭代

迭代：按照顺序返回多次执行一段程序，通常会有明确的终止条件

迭代会在一个有序集合上进行，“有序”是指集合中所有的项都可以按照既定的顺序被遍历到，特别是开始项和结束项有明确的定义

循环迭代的弊端：

  • 迭代之前需要事先知道如何使用数据结构：数组中的每一项都只能先通过引用取得数组对象，然后再通过[]操作符取得特定索引位置上的项。这种情况并不适用于所有数据结构
  • **遍历顺序并不是数据结构固有的:**通过递增索引来访问数据是特定于数组类型的方式，并不适用于其他具有隐式顺序的数据结构

ES5新增了Array.prototyoe.forEach方法，但是仍然有弊端：这个方法解决了单独记录索引和通过数组对象取得值的问题，不过，没有办法标识迭代何时终止，因此这个方法只适用于数组，而且回调结构也比较笨拙

因此迭代器模式诞生

迭代器模式

迭代器模式描述了一个方案，即可以把有些结构称为“可迭代对象”（iterable）（比如：数组或者集合这样的集合类型对象，它们包含的元素都是有限的，并且具有无歧义的遍历顺序），因为它们实现了正式的Iterable 接口，而且可以通过迭代器Iterator 消费

  • 可迭代对象不一定是集合对象，也可以是仅仅具有类似数组行为的其他数据结构，比如计数循环，该循环中生成的值是暂时性的，但循环本身是在执行迭代，计数循环和数组都具有可迭代对象的行为

  • 任何实现Iterable接口的数据结构都可以被实现Iterator接口的结构“消费”（consume），迭代器（iterator）是按需创建的一次性对象，每个迭代器都会关联一个可迭代对象，而迭代器会暴露迭代其关联可迭代对象的API，迭代器无须了解与其关联的可迭代对象的结构，只需要知道如何取得连续的值，这种概念上的分离正是Iterable 和Iterator 的强大之处

可迭代协议

实现Iterable接口（可迭代协议）要求同时具备两种能力：

  • 支持迭代的自我识别能力
  • 创建实现Iterator接口的对象的能力

在ECMAScript中，这意味着必须暴露一个属性作为“默认迭代器”，而且这个属性必须使用特殊的**Symbol.iterator** 作为键，这个默认迭代器属性必须引用一个迭代器工厂函数，调用这个工厂函数必须返回一个新迭代器

  • 很多内置类型都实现了Iterable 接口
    • String
    • Array
    • Map
    • arguments对象
    • NodeList等DOM集合类型
  • 检查是否存在默认迭代器可以暴露这个工厂函数
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
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 {}

  • 实际写代码过程中，不需要显式调用这个工厂函数来生成迭代器,实现可迭代协议的所有类型都会自动兼容接收可迭代对象的任何语言特性

    • 接收可迭代对象的原生语言特性包括:
      • for of 循环
      • 数组解构
      • 扩展运算符
      • Array.from()
      • 创建Set
      • 创建Map
      • Promise.all()接收由Promise组成的可迭代对象
      • Promise.race()接收由Promise组成的可迭代对象
      • 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
    28
    29
    30
    31
    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接口，那这个对象也就实现了这个接口

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class FooArray extends Array {}

    let fooArr = new FooArray('foo', 'bar', 'baz');
    for (let el of fooArr) {
        console.log(el);
    }
    // foo
    // bar
    // baz

迭代器协议

迭代器API使用next()方法在可迭代对象中遍历数据，每次调用next()都会返回一个`IteratorResult1对象，这个对象包含两个属性：

  • done：布尔值，表示是否还可以调用next()取得下一个值，注意：done:true表示耗尽

  • value：包含可迭代对象的下一个值（done:false）或者是undefined（done:true）

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
// 可迭代对象
let arr = ['foo', 'bar'];

// 迭代器工厂函数
console.log(arr[Symbol.iterator]);   // f values() {[native code]}

// 迭代器
let iter = arr[Symbol.iterator]();
console.log(iter);    // ArrayIterator();

// 执行迭代
iter.next();    // {done: false, value:'foo'}
iter.next();    // {done: false, value: 'bar'}
iter.next();    // {done: true, value:undefined}

/*
	迭代器并不知道怎么可以从可迭代对象取得下一个值，也不知道可迭代对象多大，只要迭代器到达done:true状态，后续调用next()就一直返回同样的值
*/
let arr = ['foo', 'bar'];
let iter = arr[Symbol.iterator]();

// 执行迭代
iter.next();    // {done: false, value:'foo'}
iter.next();    // {done: false, value: 'bar'}
iter.next();    // {done: true, value:undefined}
iter.next();    // {done: true, value:undefined}
iter.next();    // {done: true, value:undefined}
  1. 每个迭代器都表示对可迭代对象的一次性有序遍历，不同迭代器的实例相互之间没有联系，只会独立地遍历可迭代对象
1
2
3
4
5
6
7
8
9
10
let arr = ['foo', 'bar'];

let iter1 = arr[Symbol.iterator]();
let iter2 = arr[Symbol.iterator]();

iter1.next();    // {done: false, value:'foo'}
iter2.next();    // {done: false, value:'foo'}

iter1.next();    // {done: false, value: 'bar'}
iter2.next();    // {done: false, value: 'bar'}
  1. 迭代器并不与可迭代对象某个时刻的快照绑定，而仅仅是使用游标来记录遍历可迭代对象的历程，如果可迭代对象在迭代期间被修改了，那么迭代器也会反映相应的变化
1
2
3
4
5
6
7
8
9
10
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. 显示迭代器和原生迭代器有差别
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
// 这个类实现了可迭代接口（Iterable）
// 调用默认的迭代器工厂函数会返回
// 一个实现迭代器接口（Iterator）的迭代器对象
class Foo {
    [Symbol.iterator]() {
		return {
			next() {
				return { done: false, value: 'foo' };
			}
		}
	}
}

let f = new Foo();

// 打印出实现了迭代器接口的对象
console.log(f[Symbol.iterator]()); // { next: f() {} }

// Array 类型实现了可迭代接口（Iterable）
// 调用Array 类型的默认迭代器工厂函数
// 会创建一个ArrayIterator 的实例
let a = new Array();

// 打印出ArrayIterator 的实例
console.log(a[Symbol.iterator]()); // Array Iterator {}

自定义迭代器（手写）

任何实现Iterator接口的对象都可以作为迭代器使用

  1. 初步实现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
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
// 初步实现Iterator接口
class Counter {
    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);

/*
	let iter = counter[Symbol.iterator]();    

	console.log(iter);       // {count: 1, limit: 3}
	console.log(iter.next());   // {done: false, value: 1};
	console.log(iter.next());   // {done: false, value: 2};
	console.log(iter.next());   // {done: false, value: 3};
	
*/

console.log(counter);     // {count: 1, limit: 3}

for (let i of counter) {
    console.log(i)
}

// 1
// 2
// 3



/*
	这个迭代器仍有不足的地方，因为它的每个实例都只能迭代一次
*/
console.log(counter)    // {count: 4, limit: 3}
// 再次
for (let i of counter) {
    console.log(i)
}
// {nothing logged}
  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
32
33
34
35
36
37
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

提前终止迭代器

可选的return()方法用于指定在迭代器提前关闭时执行的逻辑，执行迭代的结构在想让迭代器知道它不想遍历到可迭代对象耗尽时，就可以“关闭”迭代器

可能的情况有：

  • for-of 循环通过break、continue、return 或throw 提前退出
  • 解构操作并未消费所有值

return()方法必须返回一个有效的IteratorResult对象，简单的情况下，可以只返回{done:true}

  • 在内置结构中，还有值可以迭代，但是不会消费这些值的时候，会自动调用return()方法
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
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(3);

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. 如果迭代器没有关闭，则还可以继续从上次离开的地方继续迭代（比如数组的迭代器就是不能关闭的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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. 因为return()方法是可选的，所以并非所有的迭代器都是可关闭的，要检测某个迭代器是否可关闭，可以测试这个迭代器实例的return属性是不是函数对象，但是，仅仅给一个不可关闭的迭代器增加这个方法并不能让它变可关闭的，这是因为调用return()方法不会强制迭代器进入关闭状态，即便如此，return()方法还是会被调用
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
let a = [1, 2, 3, 4, 5];

let iter = a[Symbol.iterator]();   // 我们知道数组的迭代器是不可关闭的

iter.return = function() {     //  给数组的迭代器增加一个return方法
	console.log('Exiting early');   
	return { done: true };
};


for (let i of iter) {
	console.log(i);
	if (i > 2) {
		break      // break满足迭代器调用return()的条件
	}
}
// 1
// 2
// 3
// Exiting early   调用return了

for (let i of iter) {
	console.log(i);
}
// 4
// 5