ES6 iterator 和 generator
ES6 引入了新的遍历数据的机制 Iterator 迭代器。它是一种接口，为各种不同的数据结构提供统一的访问机制。任何数据结构只要部署 Iterator 接口，就可以完成遍历操作（即依次处理该数据结构的所有成员）。基于 iterator 机制，es6 提供了很多新的操作符，例如 for of 以及解构、展开操作符等。
Generator 是 ES6 提供的一种异步编程解决方案，类似于其他语言中的协程。它是的一个函数可以在执行过程中中止，之后重新回来继续执行，而不是一次性执行完。执行 Generator 函数会返回一个遍历器对象，也就是说，Generator 函数除了状态机，还是一个遍历器对象生成函数。返回的遍历器对象，可以依次遍历 Generator 函数内部的每一个状态。
本文将基于例子阐述 iterator 和 generator 的机制和用法，主要是用法?。
实现 ArrayList 和 LinkedList
LinkedList 和 ArrayList 是两种基础的数据结构。它们都可以归类为 List 数据结构。不同处在于查询、插入、删除的复杂度不同。那么我们先实现一下两个数据结构试试，为了简单起见，只实现 get 方法，毕竟我们只要要阐述下 iterator 和 generator 的用法，意思一下即可：
- ArrayList
class ArrayList {
constructor(data) {
this.list = [...data];
this.size = data.length;
}
get(index) {
return this.list[index];
}
}- LinkedList
class LinkedList {
constructor(data) {
let last = null;
for (let i = data.length - 1; i >= 0; i--) {
const el = { data: { value: data[i] }, next: last };
last = el;
}
this.head = last;
this.size = data.length;
}
get(index) {
let counter = 0;
let el = this.head;
while (counter < index) {
el = el.next;
counter++;
}
return el.data;
}
}可以看到，对于 LinkedList，其查找复杂度是 O(N) 的。
现在我们看下面一个例子，我们要从两个 List 对象中过滤出小于 3 的数：
const list1 = new ArrayList([1, 2, 3]);
const list2 = new LinkedList([1, 2, 3]);
const filtered1 = [];
for (let i = 0; i < list1.size; i++) {
const element = list1.get(i);
if (element.value < 3) {
filtered1.push(element);
}
}
const filtered2 = [];
for (let i = 0; i < list2.size; i++) {
const element = list2.get(i);
if (element.value < 3) {
filtered2.push(element);
}
}乍一看好像没啥问题，但是对于 LinkedList，我们在遍历其元素时做了大量的重复工作，每次我们都重新遍历 list 去寻找 index 对应的值，这是非常低效的。为了解决这个问题，我们可以实现一个 forEach 方法：
class ArrayList {
constructor(data) {
this.list = data.map(value => ({ value }));
this.size = data.length;
}
get(index) {
return this.list[index];
}
forEach(fn) {
for (let i = 0; i < this.list.length; i++) {
fn(this.list[i]);
}
}
}
class LinkedList {
constructor(data) {
let last = null;
for (let i = data.length - 1; i >= 0; i--) {
const el = { data: { value: data[i] }, next: last };
last = el;
}
this.head = last;
this.size = data.length;
}
get(index) {
let counter = 0;
let el = this.head;
while (counter < index) {
el = el.next;
counter++;
}
return el.data;
}
forEach(fn) {
let element = this.head;
while (element !== null) {
fn(element.data);
element = element.next;
}
}
} 看上去很完美，我们只要调用 forEach 方法来遍历 list 即可：
const filtered = [];
list.forEach((element) => {
if (element.value < 3) {
filtered.push(element);
}
});但是，这个方法还有两个缺点没有解决：
- 不能从循环中跳出，即无法执行 break 操作
- 无法使用 iterator 支持的一些语法模式，例如展开操作符
...,for of循环
这个时候，就需要我们的 iterator 上场了。
实现 list 的 iterator
ES6 规定，默认的 Iterator 接口部署在数据结构的 Symbol.iterator 属性，或者说，一个数据结构只要具有 Symbol.iterator 属性，就可以认为是“可遍历的”（iterable）。Symbol.iterator 属性本身是一个函数，就是当前数据结构默认的遍历器生成函数。执行这个函数，就会返回一个遍历器。至于属性名 Symbol.iterator，它是一个表达式，返回 Symbol 对象的iterator 属性，这是一个预定义好的、类型为 Symbol 的特殊值。
class ArrayList {
constructor(data) {
this.list = data.map(value => ({ value }));
this.size = data.length;
}
get(index) {
return this.list[index];
}
forEach(fn) {
for (let i = 0; i < this.list.length; i++) {
fn(this.list[i]);
}
}
[Symbol.iterator]() {
const self = this;
let i = 0;
return {
next() {
let value;
let done = true;
if (self.list[i] !== undefined) {
value = self.list[i];
done = false;
i += 1;
}
return {
value,
done
};
}
};
}
}
class LinkedList {
constructor(data) {
let last = null;
for (let i = data.length - 1; i >= 0; i--) {
const el = { data: { value: data[i] }, next: last };
last = el;
}
this.head = last;
this.size = data.length;
}
get(index) {
let counter = 0;
let el = this.head;
while (counter < index) {
el = el.next;
counter++;
}
return el.data;
}
forEach(fn) {
let element = this.head;
while (element !== null) {
fn(element.data);
element = element.next;
}
}
[Symbol.iterator]() {
let el = this.head;
return {
next() {
let value;
let done = true;
if (el !== null) {
value = el.data;
done = false;
el = el.next;
}
return {
value,
done
};
}
};
}
}此时，我们可以使用 for of 和展开操作符了：
const list = new LinkedList();
for (let element of list) {
console.log(element);
}
console.log([...list]);到此，我们发现的问题都用 iterator 解决了。然而我们实现的 next 方法是易出错的，而且看上去很不直观。这个时候，generator 就要派上用场了。
使用 generator
ES6 引入了 generator 函数，它和普通函数类似（不过函数前面需要加个 *），但是能在一次执行中多次返回。这是因为它内部会返回一个 generator 对象，这个对象实现了 iterator 协议，也就是说，它返回的也是一个迭代器对象。在 generator 函数中，提供了 yield 操作符。yield操作符表达式对应了每次调用 next 方法得到的结果。这意味着我们能像写 forEach 一样，直接在一个循环中调用 yield 来实现迭代器：
class ForEachLinkedListIterator {
*[Symbol.iterator]() {
let element = this.head;
while (element !== null) {
yield element.data;
element = element.next;
}
}
}
class ForEachArrayListIterator {
*[Symbol.iterator]() {
for (let i = 0; i < this.list.length; i++) {
yield this.list[i];
}
}
}好，到此为止，我们基于 iterator 和 generator 实现了我们想要的数据结构。希望通过该例子，你能对 iterator 和 generator 有了一个直观的理解。当然，本文对于 iterator 和 generator 的基础阐述是相当不够的，这些可以去 mdn 上查看。
