跳转到内容

迭代器

Edit links
25% developed
来自 Wikibooks，开放世界中的开放书籍

解释器 计算机科学设计模式
迭代器 		中介者
目录

提供一种方法来顺序访问聚合对象中的元素，而无需公开其底层表示。

示例

在 Java 中，接口 java.util.Iterator<E> 是迭代器模式的一种实现。这样，所有实现 java.lang.Iterable<T> 接口的对象都不需要此模式的便捷实现。

成本

此模式有一定的成本。仅对重要数量的代码实现此模式。IDE 重构帮不上你太多忙。

创建

此模式的创建也有一定的成本。

维护

此模式易于维护。

移除

此模式的移除也有一定的成本。

建议

  • 在迭代器类的名称中使用“iterator”一词，以便向其他开发人员指示模式的使用。

实现

Java 中的实现

Java 拥有 Iterator 接口。

一个简单的示例，展示了如何使用 Iterator 返回 [start, end] 之间的整数

import java.util.Iterator;
import java.util.NoSuchElementException;

public class RangeIteratorExample {
    public static Iterator<Integer> range(int start, int end) {
        return new Iterator<>() {
            private int index = start;
      
            @Override
            public boolean hasNext() {
                return index < end;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return index++;
            }
        };
    }
    
    public static void main(String[] args) {
        var iterator = range(0, 10);
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        
        // or using a lambda
        iterator.forEachRemaining(System.out::println);
    }
}

从 Java 5 开始，实现 Template:Javadoc:SE 接口的对象（该接口从其唯一方法返回一个 Iterator）可以使用 Java 的 foreach 循环 语法进行遍历。Template:Javadoc:SE 接口来自 Java 集合框架，扩展了 Iterable。

Family 类实现 Iterable 接口的示例
import java.util.Iterator;
import java.util.Set;

class Family<E> implements Iterable<E> {
    private final Set<E> elements;
  
    public Family(Set<E> elements) {
        this.elements = Set.copyOf(elements);
    }
    
    @Override
    public Iterator<E> iterator() {
        return elements.iterator();
    }
}
IterableExample 类演示了 Family 类的用法
public class IterableExample {
    public static void main(String[] args) {
        var weasleys = Set.of(
            "Arthur", "Molly", "Bill", "Charlie",
            "Percy", "Fred", "George", "Ron", "Ginny"
            );
        var family = new Family<>(weasleys);
    
        for (var name : family) {
            System.out.println(name + " Weasley");
        }
    }
}
输出
Ron Weasley
Molly Weasley
Percy Weasley
Fred Weasley
Charlie Weasley
George Weasley
Arthur Weasley
Ginny Weasley
Bill Weasley

以下是 Java 中的另一个示例

import java.util.BitSet;
import java.util.Iterator;
public class BitSetIterator implements Iterator<Boolean> {
    private final BitSet bitset;
    private int index = 0;
    public BitSetIterator(BitSet bitset) {
        this.bitset = bitset;
    }
    public boolean hasNext() {  
        return index < bitset.length();
    }
    public Boolean next() {
        if (index >= bitset.length()) {
            throw new NoSuchElementException();
        }
        return bitset.get(index++);
    }
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

两个不同的使用示例

import java.util.BitSet;
public class TestClientBitSet {
    public static void main(String[] args) {
        // create BitSet and set some bits
        BitSet bitset = new BitSet();
        bitset.set(1);
        bitset.set(3400);
        bitset.set(20);
        bitset.set(47);
        for (BitSetIterator iter = new BitSetIterator(bitset); iter.hasNext(); ) {
            Boolean b = iter.next();              
            String tf = (b.booleanValue() ? "T" : "F");
            System.out.print(tf);
        }
        System.out.println();
    }
}

import java.util.ArrayList;
import java.util.Collection;
public class TestClientIterator  {
    public static void main(String[] args) {
        Collection<Object> al = new ArrayList<Object>();
        al.add(new Integer(42));
        al.add("test");
        al.add(new Double("-12.34"));
        for (Iterator<Object> iter = al.iterator(); iter.hasNext(); ) {
            System.out.println(iter.next());
        }
        for (Object o : al) {
            System.out.println(o);
        }
    }
}
JavaScript 中的实现

JavaScript 作为 ECMAScript 6 的一部分，支持任何提供 next() 方法的对象的迭代器模式，该方法返回一个具有两个特定属性的对象：done 和 value。以下是一个显示反向数组迭代器的示例

function reverseArrayIterator(array) {
    var index = array.length - 1;
    return {
       next: () =>
          index >= 0 ?
           {value: array[index--], done: false} :
           {done: true}
    }
}

const it = reverseArrayIterator(['three', 'two', 'one']);
console.log(it.next().value);  //-> 'one'
console.log(it.next().value);  //-> 'two'
console.log(it.next().value);  //-> 'three'
console.log(`Are you done? ${it.next().done}`);  //-> true

但是，大多数情况下，希望在对象上提供 Iterator[1] 语义，以便可以通过 for...of 循环自动迭代它们。JavaScript 的一些内置类型（如 Array、Map 或 Set）已经定义了自己的迭代行为。可以通过定义对象的元 @@iterator 方法（也称为 Symbol.iterator）来实现相同的效果。这将创建一个 Iterable 对象。

以下是一个范围函数的示例，该函数使用常规 for 循环生成从 start 到 end（不包括 end）的值列表，以生成数字

function range(start, end) {
  return {
    [Symbol.iterator]() { // #A
      return this;
    },
    next() {
      if (start < end) {
        return { value: start++, done: false }; // #B
      }
      return { done: true, value: end }; // #B
    }
  }
}

for (number of range(1, 5)) {
  console.log(number);   // -> 1, 2, 3, 4
}

还可以操作内置类型的迭代机制，例如字符串

let iter = ['I', 't', 'e', 'r', 'a', 't', 'o', 'r'][Symbol.iterator]();
iter.next().value; //-> I
iter.next().value; //-> t
C# 中的实现

.NET Framework 具有支持简单迭代的特殊接口：System.Collections.IEnumerator 用于非泛型集合，System.Collections.Generic.IEnumerator<T> 用于泛型集合。

C# 语句 foreach 旨在轻松迭代实现 System.Collections.IEnumerator 和/或 System.Collections.Generic.IEnumerator<T> 接口的集合。从 C# v2 开始，foreach 也能够迭代实现 System.Collections.Generic.IEnumerable<T> 和 System.Collections.Generic.IEnumerator<T> 的类型[2]

使用 foreach 语句的示例

var primes = new List<int>{ 2, 3, 5, 7, 11, 13, 17, 19 };
long m = 1;
foreach (var prime in primes)
    m *= prime;

以下是 C# 中的另一个示例

using System;
using System.Collections;
  class MainApp
  {
    static void Main()
    {
      ConcreteAggregate a = new ConcreteAggregate();
      a[0] = "Item A";
      a[1] = "Item B";
      a[2] = "Item C";
      a[3] = "Item D";
      // Create Iterator and provide aggregate
      ConcreteIterator i = new ConcreteIterator(a);
      Console.WriteLine("Iterating over collection:");
 
      object item = i.First();
      while (item != null)
      {
        Console.WriteLine(item);
        item = i.Next();
      }
      // Wait for user
      Console.Read();
    }
  }
  // "Aggregate"
  abstract class Aggregate
  {
    public abstract Iterator CreateIterator();
  }
  // "ConcreteAggregate"
  class ConcreteAggregate : Aggregate
  {
    private ArrayList items = new ArrayList();
    public override Iterator CreateIterator()
    {
      return new ConcreteIterator(this);
    }
    // Property
    public int Count
    {
      get{ return items.Count; }
    }
    // Indexer
    public object this[int index]
    {
      get{ return items[index]; }
      set{ items.Insert(index, value); }
    }
  }
  // "Iterator"
  abstract class Iterator
  {
    public abstract object First();
    public abstract object Next();
    public abstract bool IsDone();
    public abstract object CurrentItem();
  }
  // "ConcreteIterator"
  class ConcreteIterator : Iterator
  {
    private ConcreteAggregate aggregate;
    private int current = 0;
    // Constructor
    public ConcreteIterator(ConcreteAggregate aggregate)
    {
      this.aggregate = aggregate;
    }
    public override object First()
    {
      return aggregate[0];
    }
    public override object Next()
    {
      object ret = null;
      if (current < aggregate.Count - 1)
      {
        ret = aggregate[++current];
      }
 
      return ret;
    }
    public override object CurrentItem()
    {
      return aggregate[current];
    }
    public override bool IsDone()
    {
      return current >= aggregate.Count ? true : false ;
    }
  }
PHP 5 中的实现

PHP 通过 Iterator 接口支持迭代器模式，作为标准发行版的一部分。[3] 实现该接口的对象可以使用 foreach 语言结构进行迭代。

使用 PHP 的模式示例

<?php

// BookIterator.php

namespace DesignPatterns;

class BookIterator implements \Iterator
{
    private int $i_position = 0;
    private BookCollection $booksCollection;

    public function __construct(BookCollection $booksCollection)
    {
        $this->booksCollection = $booksCollection;
    }

    public function current()
    {
        return $this->booksCollection->getTitle($this->i_position);
    }

    public function key(): int
    {
        return $this->i_position;
    }

    public function next(): void
    {
        $this->i_position++;
    }

    public function rewind(): void
    {
        $this->i_position = 0;
    }

    public function valid(): bool
    {
        return !is_null($this->booksCollection->getTitle($this->i_position));
    }
}

<?php

// BookCollection.php

namespace DesignPatterns;

class BookCollection implements \IteratorAggregate
{
    private array $a_titles = array();

    public function getIterator()
    {
        return new BookIterator($this);
    }

    public function addTitle(string $string): void
    {
        $this->a_titles[] = $string;
    }

    public function getTitle($key)
    {
        if (isset($this->a_titles[$key])) {
            return $this->a_titles[$key];
        }
        return null;
    }

    public function is_empty(): bool
    {
        return empty($this->$a_titles);
    }
}

<?php

// index.php

require 'vendor/autoload.php';
use DesignPatterns\BookCollection;

$booksCollection = new BookCollection();
$booksCollection->addTitle('Design Patterns');
$booksCollection->addTitle('PHP7 is the best');
$booksCollection->addTitle('Laravel Rules');
$booksCollection->addTitle('DHH Rules');

foreach ($booksCollection as $book) {
    var_dump($book);
}

输出

string(15) "Design Patterns"
string(16) "PHP7 is the best"
string(13) "Laravel Rules"
string(9) "DHH Rules"

另一个示例：作为 PHP 5 中的默认行为，在 foreach 结构中使用对象将遍历所有公共值。PHP 提供多个 Iterator 类，允许你迭代常见的列表，例如目录、XML 结构和递归数组。可以通过实现 Iterator 接口来定义你自己的 Iterator 类，这将覆盖默认行为。Iterator 接口定义

interface Iterator
{
    // Returns the current value
    function current();
    
    // Returns the current key
    function key();
    // Moves the internal pointer to the next element
    function next();
    
    // Moves the internal pointer to the first element
    function rewind();
    
    // If the current element is valid (boolean)
    function valid();
}

这些方法都在完整的 foreach( $object as $key=>$value ) 序列中使用。方法按以下顺序执行

rewind() 
while valid() {
    current() in $value 
    key() in $key 
    next()
} 
End of Loop

根据 Zend 的说法，current() 方法在 valid() 方法之前和之后都被调用。

Perl 中的实现

在 Perl 中，提供迭代器接口的对象要么 重载 <>（迭代器运算符），[4] 要么提供一个散列或 绑定散列 接口，可以使用 each 进行迭代。[5] <> 和 each 都在迭代完成时返回 undef。重载的 <> 运算符

# fibonacci sequence
package FibIter;
use overload
    '<>' => 'next_fib';
sub new {
    my $class = shift;
    bless { index => 0, values => [0, 1] }, $class
}
sub next_fib {
    my $self = shift;
    my $i = $self->{index}++;
    $self->{values}[$i] ||=
        $i > 1 ? $self->{values}[-2]+$self->{values}[-1]
               : ($self->{values}[$i]);
}
# reset iterator index
sub reset {
    my $self = shift;
    $self->{index} = 0
}
package main;
my $iter = FibIter->new;
while (my $fib = <$iter>) {
    print "$fib","\n";
}

迭代散列（或绑定散列）

# read from a file like a hash
package HashIter;
use base 'Tie::Hash';
sub new {
    my ($class, $fname) = @_;
    my $obj = bless {}, $class;
    tie %$obj, $class, $fname;
    bless $obj, $class;
}
    
sub TIEHASH {
    # tie hash to a file
    my $class = shift;
    my $fname = shift or die 'Need filename';
    die "File $fname must exist"
         unless [-f $fname];
    open my $fh, '<', $fname or die "open $!";
    bless { fname => $fname, fh => $fh }, $class;
}
sub FIRSTKEY {
    # (re)start iterator 
    my $self = shift;
    my $fh = $self->{fh};
    if (not fileno $self->{fh}) {
        open $fh, '<', $self->{fname} or die "open $!";
    }
    # reset file pointer
    seek( $fh, 0, 0 );
    chomp(my $line = <$fh>);
    $line
}
sub NEXTKEY {
    # next item from iterator
    my $self = shift;
    my $fh = $self->{fh};
    return if eof($fh);
    chomp(my $line = <$fh>);
    $line
}
sub FETCH {
    # get value for key, in this case we don't
    # care about the values, just return 
    my ($self, $key) = @_;  
    return
}
sub main;
# iterator over a word file
my $word_iter = HashIter->new('/usr/share/dict/words');
# iterate until we get to abacus
while (my $word = each( %$word_iter )) {
    print "$word\n";
    last if $word eq 'abacus'
}
# call keys %tiedhash in void context to reset iterator
keys %$word_iter;
Python 中的实现

Python 将迭代器的语法作为语言本身的一部分进行规定，以便语言关键字（如 for）与 Python 所称的可迭代对象一起使用。可迭代对象具有一个 __iter__() 方法，该方法返回一个迭代器对象。“迭代器协议”要求 next() 返回下一个元素，或者在到达序列末尾时引发 StopIteration 异常。迭代器还提供一个 __iter__() 方法，该方法返回自身，以便它们也可以被迭代；例如，使用 for 循环。从 2.2 版开始提供生成器。

在 Python 3 中，next() 重命名为 __next__()。[6]

在 Python 中，迭代器是遵循迭代器协议的对象。你可以使用 iter() 方法从任何序列（即集合：列表、元组、字典、集合等）获取迭代器。获取迭代器的另一种方法是创建生成器，生成器是一种迭代器。要从迭代器获取下一个元素，可以使用 next() 方法（Python 2）/ next() 函数（Python 3）。当没有更多元素时，它会引发 StopIteration 异常。要实现你自己的迭代器，你只需要一个实现 next() 方法（Python 2）/ __next__() 方法（Python 3）的对象。以下是两个用例

# from a sequence
x = [42, "test", -12.34]
it = iter(x)
try:
  while True:
    x = next(it) # in Python 2, you would use it.next()
    print x
except StopIteration:
  pass
# a generator
def foo(n):
  for i in range(n):
    yield i
it = foo(5)
try:
  while True:
    x = next(it) # in Python 2, you would use it.next()
    print x
except StopIteration:
  pass
Raku 中的实现

Raku 提供了迭代器的 API，作为语言本身的一部分，用于可以使用 for 和相关迭代结构（如分配给 Positional 变量）进行迭代的对象。[7][8] 可迭代对象必须至少实现一个 iterator 方法，该方法返回一个迭代器对象。“迭代器协议”要求 pull-one 方法在可能的情况下返回下一个元素，或者如果无法生成更多值则返回哨兵值 IterationEnd。迭代 API 是通过组合 Iterable 角色、Iterator 或两者，并实现所需的方法来提供的。

要检查类型对象或对象实例是否可迭代，可以使用 does 方法

say Array.does(Iterable);     #=> True
say [1, 2, 3].does(Iterable); #=> True
say Str.does(Iterable);       #=> False
say "Hello".does(Iterable);   #=> False

当且仅当调用者符合参数类型时，does 方法才返回 True。

以下是一个 range 子例程的示例，它模拟了 Python 的 range 函数

multi range(Int:D $start, Int:D $end where * <= $start, Int:D $step where * < 0 = -1) {
    (class {
        also does Iterable does Iterator;
        has Int ($.start, $.end, $.step);
        has Int $!count = $!start;

        method iterator { self }
        method pull-one(--> Mu) {
            if $!count > $!end {
                my $i = $!count;
                $!count += $!step;
                return $i;
            }
            else {
                $!count = $!start;
                return IterationEnd;
            }
        }
    }).new(:$start, :$end, :$step)
}

multi range(Int:D $start, Int:D $end where * >= $start, Int:D $step where * > 0 = 1) {
    (class {
        also does Iterable does Iterator;
        has Int ($.start, $.end, $.step);
        has Int $!count = $!start;

        method iterator { self }
        method pull-one(--> Mu) {
            if $!count < $!end {
                my $i = $!count;
                $!count += $!step;
                return $i;
            }
            else {
                $!count = $!start;
                return IterationEnd;
            }
        }
    }).new(:$start, :$end, :$step)
}

my \x = range(1, 5);
.say for x;
# OUTPUT:
# 1
# 2
# 3
# 4

say x.map(* ** 2).sum;
# OUTPUT:
# 30

my \y = range(-1, -5);
.say for y;
# OUTPUT:
# -1
# -2
# -3
# -4

say y.map(* ** 2).sum;
# OUTPUT:
# 30
MATLAB 中的实现

MATLAB 支持使用“原生”数组或 cell 数组进行外部和内部隐式迭代。在外部迭代的情况下，用户有责任推进遍历并请求下一个元素，可以在数组存储结构中定义一组元素，并使用 for 循环结构遍历这些元素。例如，

% Define an array of integers
myArray = [1,3,5,7,11,13];
for n = myArray
   % ... do something with n
   disp(n)  % Echo integer to Command Window
end

使用 for 关键字遍历整数数组。在内部迭代的情况下，用户可以向迭代器提供一个操作，以便在集合的每个元素上执行该操作并隐式返回相应的输出数组。此外，arrayfun 和 cellfun 函数可以分别用于在“原生”数组和 cell 数组上执行自定义或用户定义的操作。例如，

function simpleFun
% Define an array of integers
myArray = [1,3,5,7,11,13];
% Perform a custom operation over each element
myNewArray = arrayfun(@(a)myCustomFun(a),myArray);
         
% Echo resulting array to Command Window          
myNewArray
   
   
function outScalar = myCustomFun(inScalar)
% Simply multiply by 2
outScalar = 2*inScalar;

定义一个主函数 simpleFun，该函数使用内置函数 arrayfun 将自定义子函数 myCustomFun 隐式应用于数组的每个元素。

或者，可能希望通过定义迭代器模式的自定义面向对象 MATLAB 实现来从用户那里抽象数组存储容器的机制。在 MATLAB Central 文件交换项目 设计模式：迭代器（行为型） 中演示了这种支持外部迭代的实现。这是在 MATLAB 软件版本 7.6 (R2008a) 中引入的新类定义语法[9] 中编写的，其特点是使用列表抽象数据类型 (ADT) 的一维 cell 数组实现作为存储异构（数据类型）元素集的机制。它提供了使用 hasNext()、next() 和 reset() 方法在 while 循环中进行显式正向列表遍历的功能。

参考文献

  1. ↑ “迭代器和生成器”. 检索于 2016年3月18日.
  2. ↑ “C# foreach 语句”.
  3. ↑ “PHP：迭代器”. 检索于 2013年6月23日.
  4. ↑ 文件句柄对象实现了这一点，以便逐行读取其内容
  5. ↑ 在 Perl 5.12 中，数组和 绑定数组 可以像哈希一样使用 each 进行迭代
  6. ↑ “Python v2.7.1 文档：Python 标准库：5. 内置类型”. 检索于 2011年5月2日.
  7. ↑ “Raku 文档：角色 Iterable”. 检索于 2020年12月9日.
  8. ↑ “Raku 文档：角色 Iterator”. 检索于 2020年12月9日.
  9. ↑ “MATLAB 软件版本 7.6 引入的新类定义语法”. MathWorks 公司，2009年3月. 检索于 2009年9月22日.


Clipboard

待办事项
添加更多插图。


解释器 计算机科学设计模式
迭代器 		中介者


您对本页面有任何疑问？
在这里提问


在本手册中创建新页面


检索自 "https://wikibooks.cn/w/index.php?title=Computer_Science_Design_Patterns/Iterator&oldid=4287075"
华夏公益教科书