迭代器和生成器

  • 版本网址缩略名: JavaScript/Guide/Iterators_and_Generators
  • 版本标题: 迭代器和生成器
  • 版本 id: 348553
  • 创建于:
  • 创建者: Joyce
  • 是否是当前版本?
  • 评论

修订内容

{{ Js_minversion_header("1.7") }}

处理一个集合中每一项是很常见的操作. JavaScript 提供了好几种方法来遍历一个集合, 从简单的 forfor each 循环至 map(), filter() and array comprehensions. 迭代器和生成器, 在 JavaScript 1.7中, 迭代器的概念属于核心语言中的重点 和提供了一种机制 来定义 for...in 的行为and for each 循环.

迭代器

迭代器是一个对象,知道如何存取物品从一个集合一次取出一项, 而跟踪它的当前序列所在的位置. 在 JavaScript中 迭代器是一个对象,它提供了一个next()方法返回序列中的下一个项目。当这个序列消亡时这个方法可以随时抛出一个StopIteration exception(异常)。

一旦创建,迭代器对象可以显式地通过不断调用next(),或隐式地使用JavaScript的 for...in and for each 构造.

简单的迭代器对象和数组可以使用Iterator()函数创建(下面是一个简单的对像):

var lang = { name: 'JavaScript', birthYear: 1995 };
var it = Iterator(lang);

一旦初始化,next()方法可以用来依次访问对象中的键-值:

var pair = it.next(); // Pair is ["name", "JavaScript"]
pair = it.next(); // Pair is ["birthYear", 1995]
pair = it.next(); // A StopIteration exception is thrown

一个 for...in 循环结构可以直接取代next()方法的调用。 当StopIteration exception异常抛出时这个循环会自动终止。

var it = Iterator(lang);
for (var pair in it)
  print(pair); // prints each [key, value] pair in turn

If we just want to iterate over the object's keys, we can pass a second argument of true to the Iterator() function:

var it = Iterator(lang, true);
for (var key in it)
  print(key); // prints each key in turn

One advantage of using Iterator() to access the contents of an object is that custom properties that have been added to Object.prototype will not be included in the sequence.

Iterator() can be used with arrays as well:

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (var pair in it)
  print(pair); // prints each [index, language] pair in turn

As with objects, passing true as the second argument will result in iteration occurring over the array indices:

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs, true);
for (var i in it)
  print(i); // prints 0, then 1, then 2

It is also possible to assign block scoped variables to both index and value within the for loop using the let keyword and a destructuring assignment:

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (let [i, lang] in it)
 print(i + ': ' + lang); // prints "0: JavaScript" etc.

Defining custom iterators

Some objects represent collections of items that should be iterated over in a specific way.

  • Iterating over a range object should return the numbers in that range one by one.
  • The leaves in a tree can be visited using depth-first or breadth-first traversal.
  • Iterating over an object representing the results from a database query should return rows one by one, even if the entire result set has not been loaded in to a single array.
  • An iterator on an infinite mathematical sequence (such as the Fibonacci sequence) should be able to return results one by one without creating an infinite length data structure.

JavaScript lets you write code that represents custom iteration logic and link it to an object.

We'll create a simple Range object which stores a low and high value.

function Range(low, high){
  this.low = low;
  this.high = high;
}

Now we'll create a custom iterator that can return a sequence of inclusive integers from that range. The iterator interface requires that we provide a next() method which either returns an item from the sequence or throws a StopIteration exception.

function RangeIterator(range){
  this.range = range;
  this.current = this.range.low;
}
RangeIterator.prototype.next = function(){
  if (this.current > this.range.high)
    throw StopIteration;
  else
    return this.current++;
};

Our RangeIterator is instantiated with a range instance, and maintains its own current property to track how far along in the sequence it has got.

Finally, to associate our RangeIterator with the Range object we need to add a special __iterator__ method to Range. This will be called when we attempt to iterate over a Range instance, and should return an instance of RangeIterator, which implements the iterator logic.

Range.prototype.__iterator__ = function(){
  return new RangeIterator(this);
};

Having hooked in our custom iterator, we can iterate over a range instance with the following:

var range = new Range(3, 5);
for (var i in range)
  print(i); // prints 3, then 4, then 5 in sequence

Generators: a better way to build Iterators

While custom iterators are a useful tool, their creation requires careful programming due to the need to explicitly maintain their internal state. Generators provide a powerful alternative: they allow you to define an iterative algorithm by writing a single function which can maintain its own state.

A generator is a special type of function that works as a factory for iterators. A function becomes a generator if it contains one or more yield expressions.

{{ NoteStart() }}The yield keyword is only available to code blocks in HTML wrapped in a <script type="application/javascript;version=1.7"> block (or higher version). XUL script tags have access to these features without needing this special block.{{ NoteEnd() }}

When a generator function is called the body of the function does not execute straight away; instead, it returns a generator-iterator object. Each call to the generator-iterator's next() method will execute the body of the function up to the next yield expression and return its result. When either the end of the function or a return statement is reached, a StopIteration exception is thrown.

This is best illustrated with an example:

function simpleGenerator(){
  yield "first";
  yield "second";
  yield "third";
  for (var i = 0; i < 3; i++)
    yield i;
}

var g = simpleGenerator();
print(g.next()); // prints "first"
print(g.next()); // prints "second"
print(g.next()); // prints "third"
print(g.next()); // prints 0
print(g.next()); // prints 1
print(g.next()); // prints 2
print(g.next()); // StopIteration is thrown

A generator function can be used directly as the __iterator__ method of a class, greatly reducing the amount of code needed to create custom iterators. Here is our Range rewritten to use a generator:

function Range(low, high){
  this.low = low;
  this.high = high;
}
Range.prototype.__iterator__ = function(){
  for (var i = this.low; i <= this.high; i++)
    yield i;
};
var range = new Range(3, 5);
for (var i in range)
  print(i); // prints 3, then 4, then 5 in sequence

Not all generators terminate; it is possible to create a generator that represents an infinite sequence. The following generator implements the Fibonacci sequence, where each element is the sum of the two previous elements:

function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    yield current;
  }
}

var sequence = fibonacci();
print(sequence.next()); // 1
print(sequence.next()); // 1
print(sequence.next()); // 2
print(sequence.next()); // 3
print(sequence.next()); // 5
print(sequence.next()); // 8
print(sequence.next()); // 13

Generator functions can take arguments, which are bound the first time the function is called. Generators can be terminated (causing them to raise a StopIteration exception) using a return statement. The following fibonacci() variant takes an optional limit argument, and will terminate once that limit has been passed.

function fibonacci(limit){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    if (limit && current > limit)
      return;
    yield current;
  }
}

Advanced generators

Generators compute their yielded values on demand, which allows them to efficiently represent sequences that are expensive to compute, or even infinite sequences as demonstrated above.

In addition to the next() method, generator-iterator objects also have a send() method which can be used to modify the internal state of the generator. A value passed to send() will be treated as the result of the last yield expression that paused the generator. You must start a generator by calling next() at least once before you can use send() to pass in a specific value.

Here is the fibonacci generator using send() to restart the sequence:

function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    var reset = yield current;
    if (reset){
        fn1 = 1;
        fn2 = 1;
    }
  }
}

var sequence = fibonacci();
print(sequence.next());     // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3
print(sequence.next());     // 5
print(sequence.next());     // 8
print(sequence.next());     // 13
print(sequence.send(true)); // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3
Note: As a point of interest, calling send(undefined) is equivalent to calling next(). However, starting a newborn generator with any value other than undefined when calling send() will result in a TypeError exception.

You can force a generator to throw an exception by calling its throw() method and passing the exception value it should throw. This exception will be thrown from the current suspended context of the generator, as if the yield that is currently suspended were instead a throw value statement.

If a yield is not encountered during the processing of the thrown exception, then the exception will propagate up through the call to throw(), and subsequent calls to next() will result in StopIteration being thrown.

Generators have a close() method that forces the generator to close itself. The effects of closing a generator are:

  1. Any finally clauses active in the generator function are run.
  2. If a finally clause throws any exception other than StopIteration, the exception is propagated to the caller of the close() method.
  3. The generator terminates.

Generator expressions

{{ Js_minversion_header("1.8") }}

A significant drawback of array comprehensions is that they cause an entire new array to be constructed in memory. When the input to the comprehension is itself a small array the overhead involved is insignificant — but when the input is a large array or an expensive (or indeed infinite) generator the creation of a new array can be problematic.

Generators enable lazy computation of sequences, with items calculated on-demand as they are needed. Generator expressions are syntactically almost identical to array comprehensions — they use parenthesis instead of braces (and for...in instead of for each...in) — but instead of building an array they create a generator that can execute lazily. You can think of them as short hand syntax for creating generators.

Suppose we have an iterator it which iterates over a large sequence of integers. We want to create a new iterator that will iterate over their doubles. An array comprehension would create a full array in memory containing the doubled values:

var doubles = [i * 2 for (i in it)];

A generator expression on the other hand would create a new iterator which would create doubled values on demand as they were needed:

var it2 = (i * 2 for (i in it));
print(it2.next()); // The first value from it, doubled
print(it2.next()); // The second value from it, doubled

When a generator expression is used as the argument to a function, the parenthesis used for the function call means that the outer parenthesis can be omitted:

var result = doSomething(i * 2 for (i in it));

{{ autoPreviousNext("JSGChapters") }}

修订版来源

<p>{{ Js_minversion_header("1.7") }}</p>
<p>处理一个集合中每一项是很常见的操作. JavaScript 提供了好几种方法来遍历一个集合, 从简单的 <code><a href="/zh-CN/JavaScript/Reference/Statements/for" title="zh-CN/Core_JavaScript_1.5_Reference/Statements/for">for</a></code> 和 <code><a href="/zh-CN/JavaScript/Reference/Statements/for_each...in" title="zh-CN/JavaScript/Reference/Statements/for each...in">for each</a></code> 循环至 <code><a href="/zh-CN/JavaScript/Reference/Global_Objects/Array/map" title="zh-CN/Core_JavaScript_1.5_Reference/Global_Objects/Array/map">map()</a></code>, <code><a href="/zh-CN/JavaScript/Reference/Global_Objects/Array/filter" title="zh-CN/Core_JavaScript_1.5_Reference/Global_Objects/Array/filter">filter()</a></code> and <a href="/zh-CN/JavaScript/Guide/Predefined_Core_Objects#Array_comprehensions" title="zh-CN/JavaScript/Guide/Predefined Core Objects#Array comprehensions">array comprehensions</a>. 迭代器和生成器, 在 JavaScript 1.7中, 迭代器的概念属于核心语言中的重点 和提供了一种机制 来定义 <code><a href="/zh-CN/JavaScript/Reference/Statements/for...in" title="zh-CN/Core_JavaScript_1.5_Reference/Statements/for...in">for...in</a></code> 的行为and <code><a href="/zh-CN/JavaScript/Reference/Statements/for_each...in" title="zh-CN/JavaScript/Reference/Statements/for each...in">for each</a></code> 循环.</p>
<h2 id="Iterators">迭代器</h2>
<p>迭代器是一个对象,知道如何存取物品从一个集合一次取出一项, 而跟踪它的当前序列所在的位置. 在 JavaScript中 迭代器是一个对象,它提供了一个next()方法返回序列中的下一个项目。<code>当这个序列消亡时这个方法可以随时抛出一个</code><code>StopIteration</code> exception(异常)。</p>
<p>一旦创建,迭代器对象可以显式地通过不断调用next(),或隐式地使用JavaScript的 <code><a href="/zh-CN/JavaScript/Reference/Statements/for...in" title="zh-CN/Core_JavaScript_1.5_Reference/Statements/for...in">for...in</a></code> and <code><a href="/zh-CN/JavaScript/Reference/Statements/for_each...in" title="zh-CN/JavaScript/Reference/Statements/for each...in">for each</a></code> 构造.</p>
<p>简单的迭代器对象和数组可以使用Iterator()函数创建(下面是一个简单的对像):</p>
<pre class="brush: js">
var lang = { name: 'JavaScript', birthYear: 1995 };
var it = Iterator(lang);
</pre>
<p>一旦初始化,next()方法可以用来依次访问对象中的<span style="color:#0000cd;">键-值</span>:</p>
<pre class="brush: js">
var pair = it.next(); // Pair is ["name", "JavaScript"]
pair = it.next(); // Pair is ["birthYear", 1995]
pair = it.next(); // A StopIteration exception is thrown
</pre>
<p>一个 <code><a href="/zh-CN/JavaScript/Reference/Statements/for...in" title="zh-CN/Core_JavaScript_1.5_Reference/Statements/for...in">for...in</a></code> 循环结构可以直接取代next()方法的调用。 <code>当StopIteration</code> exception异常抛出时这个循环会自动终止。</p>
<pre class="brush: js">
var it = Iterator(lang);
for (var pair in it)
  print(pair); // prints each [key, value] pair in turn
</pre>
<p>If we just want to iterate over the object's keys, we can pass a second argument of <code>true</code> to the <code>Iterator()</code> function:</p>
<pre class="brush: js">
var it = Iterator(lang, true);
for (var key in it)
  print(key); // prints each key in turn
</pre>
<p>One advantage of using <code>Iterator()</code> to access the contents of an object is that custom properties that have been added to <code>Object.prototype</code> will not be included in the sequence.</p>
<p><code>Iterator()</code> can be used with arrays as well:</p>
<pre class="brush: js">
var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (var pair in it)
  print(pair); // prints each [index, language] pair in turn
</pre>
<p>As with objects, passing <code>true</code> as the second argument will result in iteration occurring over the array indices:</p>
<pre class="brush: js">
var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs, true);
for (var i in it)
  print(i); // prints 0, then 1, then 2
</pre>
<p>It is also possible to assign block scoped variables to both index and value within the for loop using the <code>let</code> keyword and a destructuring assignment:</p>
<pre class="brush: js">
var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (let [i, lang] in it)
 print(i + ': ' + lang); // prints "0: JavaScript" etc.
</pre>
<h2 id="Defining_custom_iterators">Defining custom iterators</h2>
<p>Some objects represent collections of items that should be iterated over in a specific way.</p>
<ul>
  <li>Iterating over a range object should return the numbers in that range one by one.</li>
  <li>The leaves in a tree can be visited using depth-first or breadth-first traversal.</li>
  <li>Iterating over an object representing the results from a database query should return rows one by one, even if the entire result set has not been loaded in to a single array.</li>
  <li>An iterator on an infinite mathematical sequence (such as the Fibonacci sequence) should be able to return results one by one without creating an infinite length data structure.</li>
</ul>
<p>JavaScript lets you write code that represents custom iteration logic and link it to an object.</p>
<p>We'll create a simple <code>Range</code> object which stores a low and high value.</p>
<pre class="brush: js">
function Range(low, high){
  this.low = low;
  this.high = high;
}
</pre>
<p>Now we'll create a custom iterator that can return a sequence of inclusive integers from that range. The iterator interface requires that we provide a <code>next()</code> method which either returns an item from the sequence or throws a <code>StopIteration</code> exception.</p>
<pre class="brush: js">
function RangeIterator(range){
  this.range = range;
  this.current = this.range.low;
}
RangeIterator.prototype.next = function(){
  if (this.current &gt; this.range.high)
    throw StopIteration;
  else
    return this.current++;
};
</pre>
<p>Our <code>RangeIterator</code> is instantiated with a range instance, and maintains its own <code>current</code> property to track how far along in the sequence it has got.</p>
<p>Finally, to associate our <code>RangeIterator</code> with the <code>Range</code> object we need to add a special <code>__iterator__</code> method to <code>Range</code>. This will be called when we attempt to iterate over a <code>Range</code> instance, and should return an instance of <code>RangeIterator</code>, which implements the iterator logic.</p>
<pre class="brush: js">
Range.prototype.__iterator__ = function(){
  return new RangeIterator(this);
};
</pre>
<p>Having hooked in our custom iterator, we can iterate over a range instance with the following:</p>
<pre class="brush: js">
var range = new Range(3, 5);
for (var i in range)
  print(i); // prints 3, then 4, then 5 in sequence
</pre>
<h2 id="Generators.3A_a_better_way_to_build_Iterators">Generators: a better way to build Iterators</h2>
<p>While custom iterators are a useful tool, their creation requires careful programming due to the need to explicitly maintain their internal state. Generators provide a powerful alternative: they allow you to define an iterative algorithm by writing a single function which can maintain its own state.</p>
<p>A generator is a special type of function that works as a factory for iterators. A function becomes a generator if it contains one or more <code>yield</code> expressions.</p>
<p>{{ NoteStart() }}The <code>yield</code> keyword is only available to code blocks in HTML wrapped in a <code>&lt;script type="application/javascript;version=1.7"&gt;</code> block (or higher version). <a href="/en-US/docs/XUL" title="en-US/docs/XUL">XUL</a> script tags have access to these features without needing this special block.{{ NoteEnd() }}</p>
<p>When a generator function is called the body of the function does not execute straight away; instead, it returns a generator-iterator object. Each call to the generator-iterator's <code>next()</code> method will execute the body of the function up to the next <code>yield</code> expression and return its result. When either the end of the function or a <code>return</code> statement is reached, a <code>StopIteration</code> exception is thrown.</p>
<p>This is best illustrated with an example:</p>
<pre class="brush: js">
function simpleGenerator(){
  yield "first";
  yield "second";
  yield "third";
  for (var i = 0; i &lt; 3; i++)
    yield i;
}

var g = simpleGenerator();
print(g.next()); // prints "first"
print(g.next()); // prints "second"
print(g.next()); // prints "third"
print(g.next()); // prints 0
print(g.next()); // prints 1
print(g.next()); // prints 2
print(g.next()); // StopIteration is thrown
</pre>
<p>A generator function can be used directly as the <code>__iterator__</code> method of a class, greatly reducing the amount of code needed to create custom iterators. Here is our <code>Range</code> rewritten to use a generator:</p>
<pre class="brush: js">
function Range(low, high){
  this.low = low;
  this.high = high;
}
Range.prototype.__iterator__ = function(){
  for (var i = this.low; i &lt;= this.high; i++)
    yield i;
};
var range = new Range(3, 5);
for (var i in range)
  print(i); // prints 3, then 4, then 5 in sequence
</pre>
<p>Not all generators terminate; it is possible to create a generator that represents an infinite sequence. The following generator implements the Fibonacci sequence, where each element is the sum of the two previous elements:</p>
<pre class="brush: js">
function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    yield current;
  }
}

var sequence = fibonacci();
print(sequence.next()); // 1
print(sequence.next()); // 1
print(sequence.next()); // 2
print(sequence.next()); // 3
print(sequence.next()); // 5
print(sequence.next()); // 8
print(sequence.next()); // 13
</pre>
<p>Generator functions can take arguments, which are bound the first time the function is called. Generators can be terminated (causing them to raise a <code>StopIteration</code> exception) using a <code>return</code> statement. The following <code>fibonacci()</code> variant takes an optional limit argument, and will terminate once that limit has been passed.</p>
<pre class="brush: js">
function fibonacci(limit){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    if (limit &amp;&amp; current &gt; limit)
      return;
    yield current;
  }
}
</pre>
<h2 id="Advanced_generators">Advanced generators</h2>
<p>Generators compute their yielded values on demand, which allows them to efficiently represent sequences that are expensive to compute, or even infinite sequences as demonstrated above.</p>
<p>In addition to the <code>next()</code> method, generator-iterator objects also have a <code>send()</code> method which can be used to modify the internal state of the generator. A value passed to <code>send()</code> will be treated as the result of the last <code>yield</code> expression that paused the generator. You must start a generator by calling <code>next()</code> at least once before you can use <code>send()</code> to pass in a specific value.</p>
<p>Here is the fibonacci generator using <code>send()</code> to restart the sequence:</p>
<pre class="brush: js">
function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    var reset = yield current;
    if (reset){
        fn1 = 1;
        fn2 = 1;
    }
  }
}

var sequence = fibonacci();
print(sequence.next());     // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3
print(sequence.next());     // 5
print(sequence.next());     // 8
print(sequence.next());     // 13
print(sequence.send(true)); // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3</pre>
<div class="note">
  <strong>Note:</strong> As a point of interest, calling <code>send(undefined)</code> is equivalent to calling <code>next()</code>. However, starting a newborn generator with any value other than undefined when calling <code>send()</code> will result in a <code>TypeError</code> exception.</div>
<p>You can force a generator to throw an exception by calling its <code>throw()</code> method and passing the exception value it should throw. This exception will be thrown from the current suspended context of the generator, as if the <code>yield</code> that is currently suspended were instead a <code>throw <em>value</em></code> statement.</p>
<p>If a yield is not encountered during the processing of the thrown exception, then the exception will propagate up through the call to <code>throw()</code>, and subsequent calls to <code>next()</code> will result in <code>StopIteration</code> being thrown.</p>
<p>Generators have a <code>close()</code> method that forces the generator to close itself. The effects of closing a generator are:</p>
<ol>
  <li>Any <code>finally</code> clauses active in the generator function are run.</li>
  <li>If a <code>finally</code> clause throws any exception other than <code>StopIteration</code>, the exception is propagated to the caller of the <code>close()</code> method.</li>
  <li>The generator terminates.</li>
</ol>
<h2 id="Generator_expressions">Generator expressions</h2>
<p>{{ Js_minversion_header("1.8") }}</p>
<p>A significant drawback of <a href="/zh-CN/JavaScript/Guide/Predefined_Core_Objects#Array_comprehensions" title="zh-CN/JavaScript/Guide/Predefined Core Objects#Array comprehensions">array comprehensions</a> is that they cause an entire new array to be constructed in memory. When the input to the comprehension is itself a small array the overhead involved is insignificant — but when the input is a large array or an expensive (or indeed infinite) generator the creation of a new array can be problematic.</p>
<p>Generators enable lazy computation of sequences, with items calculated on-demand as they are needed. <em>Generator expressions</em> are syntactically almost identical to array comprehensions — they use parenthesis instead of braces (and <code>for...in</code> instead of <code>for each...in</code>) — but instead of building an array they create a generator that can execute lazily. You can think of them as short hand syntax for creating generators.</p>
<p>Suppose we have an iterator <code>it</code> which iterates over a large sequence of integers. We want to create a new iterator that will iterate over their doubles. An array comprehension would create a full array in memory containing the doubled values:</p>
<pre class="brush: js">
var doubles = [i * 2 for (i in it)];
</pre>
<p>A generator expression on the other hand would create a new iterator which would create doubled values on demand as they were needed:</p>
<pre class="brush: js">
var it2 = (i * 2 for (i in it));
print(it2.next()); // The first value from it, doubled
print(it2.next()); // The second value from it, doubled
</pre>
<p>When a generator expression is used as the argument to a function, the parenthesis used for the function call means that the outer parenthesis can be omitted:</p>
<pre class="brush: js">
var result = doSomething(i * 2 for (i in it));
</pre>
<p>{{ autoPreviousNext("JSGChapters") }}</p>
恢复到这个版本