本文继续对JavaScript高级程序设计第四版 第七章 迭代器与生成器 进行学习
一、迭代器模式
在阅读js红宝书第七章之前,建议先阅读以下前置链接了解一下迭代器模式:
迭代器实际上是对“遍历容器”这一操作进行了封装。
在编程中我们往往会用到各种各样的容器,但由于这些容器的底层实现各不相同,所以对他们进行遍历的方法也是不同的。例如,数组使用指针算数就可以遍历,但链表就要在不同节点直接进行跳转。这是非常不利于代码重用的。
例如你有一个简单的查找容器中最小值的函数findMin,如果没有迭代器,那么你就必须定义适用于数组版本的findMin和适用于链表版本的findMin,如果以后有更多容器需要使用findMin,那就只好继续添加重载……而如果每个容器又需要更多的函数例如findMax,sort,那简直就是重载地狱……
我们的救星就是迭代器啦!如果我们将这些遍历容器的操作都封装成迭代器,那么诸如findMin一类的算法就都可以针对迭代器编程而不是针对具体容器编程,工作量一下子就少了很多!
至于指针,由于指针也可以用来遍历容器(数组),所以指针也可是算是迭代器的一种。但是指针还有其他功能,并不只局限于遍历数组。因为使用指针变量数组的操作太深入人心,c++stl中的迭代器就是刻意仿照指针来设计接口的
二、C#中如何实现迭代器
由于我之前使用过一段时间C#,难免会和ES6中的迭代器进行对比,当然各大语言中都有自己的迭代器实现方式,基本都是类似的。
参考C#实现迭代器
迭代器模式(Iterator),提供一种方法顺序访问一个聚合对象中的各种元素,而又不暴露该对象的内部表示。C#中使用IEnumerator接口实现,Java中使用Iterator接口实现,其中原理都差不多,下面我就用C#代码来演示下迭代器的实现。
namespace System.Collections
{
public interface IEnumerator
{
object Current { get; }
bool MoveNext();
void Reset();
}
}
下面是对这两个接口的实现代码
using System.Collections;
public class SpecialEnumerator : IEnumerator
{
private SpecialList _list;
private int _index;
private object _current;
internal SpecialEnumerator(SpecialList list)
{
_list = list;
_index = -1;
_current = null;
}
public object Current => _current;
public bool MoveNext()
{
if (_index < _list._size - 1)
{
_current = _list._items[++_index];
return true;
}
return false;
}
public void Reset()
{
_current = null;
_index = 0;
}
}
using System.Collections;
public class SpecialList : IEnumerable
{
public object[] _items;
public int _size;
private const int _defaultCapacity = 4;
public SpecialList() : this(_defaultCapacity) { }
public SpecialList(int capacity)
{
_items = new object[capacity];
_size = 0;
}
public void Add(object obj)
{
_items[_size++] = obj;
}
public IEnumerator GetEnumerator()
{
return new SpecialEnumerator(this);
}
}
现在可以使用foreach了:
void test()
{
var list = new SpecialList();
list.Add("111");
list.Add("222");
list.Add("333");
foreach (var item in list)
{
print("test:" + item);
}
}
最后再补充一下,大家可能会觉得额外实现SpecialEnumerator类比较繁琐,其实如果你的列表遍历规则比较简单的话,可以使用yield语法来代替SpecialEnumerator类,只要这样写就行。如下:
1.yield
using System;
using System.Collections;
namespace xx
{
class Program
{
static void Main(string[] args)
{
HelloCollection helloCollection = new HelloCollection();
foreach (string s in helloCollection)
{
Console.WriteLine(s);
}
Console.ReadKey();
}
}
//public class HelloCollection : IEnumerable
//{
// public IEnumerator GetEnumerator()
// {
// yield return "Hello";
// yield return "World";
// }
//}
public class HelloCollection : IEnumerable
{
public IEnumerator GetEnumerator()
{
Enumerator enumerator = new Enumerator(0);
return enumerator;
}
public class Enumerator : IEnumerator, IDisposable
{
private int state;
private object current;
public Enumerator(int state)
{
this.state = state;
}
public bool MoveNext()
{
switch (state)
{
case 0:
current = "Hello";
state = 1;
return true;
case 1:
current = "World";
state = 2;
return true;
case 2:
break;
}
return false;
}
public void Reset()
{
throw new NotSupportedException();
}
public object Current
{
get { return current; }
}
public void Dispose()
{
}
}
}
}
上面注释的部分引用了"yield return”,其功能相当于下面所有代码!可以看到如果不适用yield需要些很多代码来支持遍历操作。 yield return 表示在迭代中下一个迭代时返回的数据,除此之外还有yield break, 其表示跳出迭代。
三、ES6中的自定义迭代器
参考es6 迭代器(遍历器)Iterator 自定义遍历器 lterator/简单模拟values方法 for of运行机制 Array/Set/Map默认迭代器接口 对象设置迭代器
ECMAScript 6 规范新增了两个高级特性:迭代器和生成器。使用这两个特性,能够更清晰、高效、方便地实现迭代。
const banji = {
name:'一级',
stus:[
'张三1号','张三2号','张三3号','张三4号','张三5号'
],
[Symbol.iterator](){ //添加 iterator 接口
let index = 0
let _this = this
return {
next(){
let done = index >= _this.stus.length //是否结束遍历
let value = _this.stus[index++]
return {value,done}
}
}
}
}
for(let v of banji){
console.log(v)
}
上面的代码是网上的一个例子,第一个疑问就是Symbol.iterator,这个在js红宝书第三章中曾有介绍。
1.第三章关于Symbol.iterator的部分内容
ECMAScript 6 也引入了一批常用内置符号(well-known symbol),用于暴露语言内部行为,开发者可以直接访问、重写或模拟这些行为。这些内置符号都以 Symbol 工厂函数字符串属性的形式存在。
这些内置符号最重要的用途之一是重新定义它们,从而改变原生结构的行为。比如,我们知道for-of 循环会在相关对象上使用 Symbol.iterator 属性,那么就可以通过在自定义对象上重新定义Symbol.iterator 的值,来改变 for-of 在迭代该对象时的行为。根据 ECMAScript 规范,这个符号作为一个属性表示“一个方法,该方法返回对象默认的迭代器。由 for-of 语句使用”。换句话说,这个符号表示实现迭代器 API 的函数。for-of 循环这样的语言结构会利用这个函数执行迭代操作。循环时,它们会调用以 Symbol.iterator为键的函数,并默认这个函数会返回一个实现迭代器 API 的对象。
这些内置符号也没有什么特别之处,它们就是全局函数 Symbol 的普通字符串属性,指向一个符号的实例。所有内置符号属性都是不可写、不可枚举、不可配置的。
2.工作原理
- 创建一个指针对象,指向当前数据结构的起始位置
- 第一次调用对象的 next() 方法,指针自动指向数据结构的第一个成员
- 接下来不断调用 next() 方法,指针一直往后移动,直至指向最后一个成员
- 每调用 next 方法返回一个包含 value 和 done 属性的对象
for of循环首先会调用 arr 数组中 Symbol.iterator 属性对象的函数,就会获 取到该数组对应的迭代器,接下来 iterator.next()被调用,迭代器结果对象 的 value 属性会被放入到变量 i 中。数组中的数据项会依次存入到变量 i 中,直到迭代器结果对象中的 done 属性变成 true 为止,循环就结束。
可以看出,和C#的迭代器是很类似的,只不过没有Reset。
四、读了上面的前置内容,可以重新回到红宝书第7章了
1.实现 Iterable 接口
很多内置类型都实现了 Iterable 接口:
- 字符串
- 数组
- 映射
- 集合
- arguments 对象
- 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 {}
实际写代码过程中,不需要显式调用这个工厂函数来生成迭代器。实现可迭代协议的所有类型都会自动兼容接收可迭代对象的任何语言特性。接收可迭代对象的原生语言特性包括:
- for-of 循环
- 数组解构
- 扩展操作符
- Array.from()
- 创建集合
- 创建映射
- Promise.all()接收由期约组成的可迭代对象
- Promise.race()接收由期约组成的可迭代对象
- 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
2.提前终止迭代器
可选的 return()方法用于指定在迭代器提前关闭时执行的逻辑。执行迭代的结构在想让迭代器知道它不想遍历到可迭代对象耗尽时,就可以“关闭”迭代器。可能的情况包括:
- for-of 循环通过 break、continue、return 或 throw 提前退出;
- 解构操作并未消费所有值。
return()方法必须返回一个有效的 IteratorResult 对象。简单情况下,可以只返回{ done: true }。
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
因为 return()方法是可选的,所以并非所有迭代器都是可关闭的。要知道某个迭代器是否可关闭,可以测试这个迭代器实例的 return 属性是不是函数对象。
五、生成器
生成器是 ECMAScript 6 新增的一个极为灵活的结构,拥有在一个函数块内暂停和恢复代码执行的能力。这种新能力具有深远的影响,比如,使用生成器可以自定义迭代器和实现协程。
迭代器是一个可以由任意对象实现的接口,支持连续获取对象产出的每一个值。任何实现 Iterable接口的对象都有一个 Symbol.iterator 属性,这个属性引用默认迭代器。默认迭代器就像一个迭代器工厂,也就是一个函数,调用之后会产生一个实现 Iterator 接口的对象。
迭代器必须通过连续调用 next()方法才能连续取得值,这个方法返回一个 IteratorObject。这个对象包含一个 done 属性和一个 value 属性。前者是一个布尔值,表示是否还有更多值可以访问;后者包含迭代器返回的当前值。这个接口可以通过手动反复调用 next()方法来消费,也可以通过原生消费者,比如 for-of 循环来自动消费。
生成器是一种特殊的函数,调用之后会返回一个生成器对象。生成器对象实现了 Iterable 接口,因此可用在任何消费可迭代对象的地方。生成器的独特之处在于支持 yield 关键字,这个关键字能够暂停执行生成器函数。使用 yield 关键字还可以通过 next()方法接收输入和产生输出。在加上星号之后,yield 关键字可以将跟在它后面的可迭代对象序列化为一连串值。
1.生成器基础
生成器的形式是一个函数,函数名称前面加一个星号(*)表示它是一个生成器。只要是可以定义函数的地方,就可以定义生成器。
// 生成器函数声明
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()方法。调用这个方法会让生成器开始或恢复执行。
2.通过 yield 中断执行
yield 关键字可以让生成器停止和开始执行,也是生成器最有用的地方。生成器函数在遇到 yield关键字之前会正常执行。遇到这个关键字后,执行会停止,函数作用域的状态会被保留。停止执行的生成器函数只能通过在生成器对象上调用 next()方法来恢复执行:
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' }
生成器函数内部的执行流程会针对每个生成器对象区分作用域。在一个生成器对象上调用 next()不会影响其他生成器:
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' }
yield 关键字只能在生成器函数内部使用,用在其他地方会抛出错误。类似函数的 return 关键字,yield 关键字必须直接位于生成器函数定义中,出现在嵌套的非生成器函数中会抛出语法错误
// 有效
function* validGeneratorFn() {
yield;
}
// 无效
function* invalidGeneratorFnA() {
function a() {
yield;
}
}
// 无效
function* invalidGeneratorFnB() {
const b = () => {
yield;
}
}
// 无效
function* invalidGeneratorFnC() {
(() => {
yield;
})();
}
3.生成器对象作为可迭代对象
在生成器对象上显式调用 next()方法的用处并不大。其实,如果把生成器对象当成可迭代对象,那么使用起来会更方便:
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
传给生成器的函数可以控制迭代循环的次数。在 n 为 0 时,while 条件为假,循环退出,生成器函数返回。
4.使用 yield 实现输入和输出(这一节没看懂有啥用)
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' }
因为函数必须对整个表达式求值才能确定要返回的值,所以它在遇到 yield 关键字时暂停执行并计算出要产生的值:"foo"。下一次调用 next()传入了"bar",作为交给同一个 yield 的值。然后这个值被确定为本次生成器函数要返回的值。
5.可以使用星号增强 yield 的行为
可以使用星号增强 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
6. 使用 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
在这个例子中,每个生成器首先都会从新创建的生成器对象产出每个值,然后再产出一个整数。结果就是生成器函数会递归地减少计数器值,并实例化另一个生成器对象。从最顶层来看,这就相当于创建一个可迭代对象并返回递增的整数。
7.生成器作为默认迭代器
因为生成器对象实现了 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
这里,for-of 循环调用了默认迭代器(它恰好又是一个生成器函数)并产生了一个生成器对象。这个生成器对象是可迭代的,所以完全可以在迭代中使用。
8.提前终止生成器
与迭代器类似,生成器也支持“可关闭”的概念。一个实现 Iterator 接口的对象一定有 next()方法,还有一个可选的 return()方法用于提前终止迭代器。生成器对象除了有这两个方法,还有第三个方法:throw()。