迭代器

迭代器（iterator），是使使用者可在容器物件（container，例如鏈表或陣列）上遍訪的物件，設計人員使用此介面無需關心容器物件的記憶體分配的實現細節。其行為很像資料庫技術中的游標（cursor），迭代器最早出現在1974年設計的CLU程式語言中。

在各種語言實作迭代器的方式皆不盡同，有些物件導向語言像Java、C#、Ruby、Python、Delphi都已將迭代器的特性內建語言當中，完美的跟語言整合，可稱之為隱式迭代器。但像是C++語言本身就沒有迭代器的特色，但STL仍利用模板實作了功能強大的迭代器。STL容器的數據的記憶體地址可能會重新分配（reallocate），與容器綁定的迭代器仍然可以定位到重新分配後的正確的記憶體地址。

## 描述

### 內部迭代器

內部的迭代器是高階函數（通常接受匿名函數），比如`map`、 `reduce`等，它實現跨經一個容器的遍歷，依次將給定函數應用到每個元素。

### 外部迭代器和迭代器模式

外部的迭代器可以被認為是某種類型的指針，它有兩個主要操作：引用在一個對象搜集 (抽象數據類型)（collection）中的一個特定元素（稱為元素訪問），和修改自身使其指向下一個元素（稱為元素遍歷）。還必須有一種方式建立迭代器並指向容器的第一個元素，還要有某種方式確定何時迭代器已經窮盡了容器中所有的元素。依據語言和意向用途，迭代器還可以提供額外的操作或展示不同的行為。

迭代器的主要用途是允許用戶處理一個容器的所有元素，而將使用者隔離於容器的內部結構。這允許容器以任何它希望的方式存儲元素，而允許用戶把它們看作就是簡單的序列或列表。迭代器類通常設計為緊密協作於對應的容器類。容器類通常提供建立迭代器的方法。

循環計數器有時也被稱為循環迭代器。但是循環計數器只提供遍歷功能而不提供訪問功能。

#### 生成器

實現迭代器的一種方式是使用受限形式的協程，也叫做生成器。不同於子例程，生成器協程可以向它的調用者多次產生返回值，而非只是返回一次。多數迭代器可自然的表達為生成器，但是因為生成器在被多次啟用之間保存了自己的局部狀態，它們特別適合於複雜的、有狀態的迭代器，比如樹遍歷器。在不同的作者和語言之間，術語「生成器」和「迭代器」的用法上有微妙的差異和區別。有些語言將二者視為同一介面，有些語言如JavaScript則將之獨立化。在Python中，生成器是一個迭代器構造器，即返回一個迭代器的函數。下面的Python生成器返回一個斐波那契數列的迭代器，使用到了Python的`yield`語句：

```Python
def fibonacci(limit):
    a, b = 0, 1
    for _ in range(limit):
        yield a
        a, b = b, a+b

for number in fibonacci(100):  # 这个生成器构造了一个迭代器
    print(number)
```

### 隱式迭代器

一些面向對象語言比如C#、C++（後期版本）、 Delphi（後期版本）、Go、Java（後期版本）、Lua、Perl、Python、Ruby，提供了迭代一個容器對象的元素的內置方式，而不用介入一個顯式的迭代器對象。實際的迭代器對象可以在現實中存在，即便如此，它也不被暴露在這個語言的原始碼中。

隱式迭代器經常通過`foreach`語句（或等價者）來顯現出來，比如下面的Python例子：

```Python
for value in iterable:
    print(value)
```

在Python中，可迭代者（iterable）是可以被轉換成迭代器的一個對象，接著在這個`for`循環期間從頭至尾迭代它，這是隱含完成的。

在Smalltalk家族語言和受其啟發的語言中，它們可以由搜集（collection）對象自身建立。比如下面Ruby例子：

```Ruby
iterable.each do |value|
  puts value
end
```

這種迭代風格有時叫做「內部迭代」，因為它的代碼完全執行在可迭代對象的上下文（context）之內（它控制迭代的所有方面），而編程者只提供在每個步驟要執行的運算操作（使用匿名函數）。

支持列表推導式或類似構造的語言，還可以在結果列表的構造期間使用隱式迭代器，比如在Python中：

```Python
names = [person.name for person in roster if person.male]
```

有時隱式迭代只能做到部份的隱藏實質。C++語言有一些用於隱式迭代的函數模板，比如`for_each()`。這些函數仍要求顯式的迭代器對象作為它們的初始輸入，但是後續的迭代不將迭代器對象暴露給使用者。

### 串流

迭代器是對輸入串流的一種有用的抽象，串流提供了潛在的無限可迭代的（但不必然可索引）的對象。一些語言，比如Perl和Python，將串流實現為迭代器。串流的可替代的實現包括數據驅動語言，比如AWK和sed。

## 迭代器分類

### 迭代器範疇

迭代器可以依據功能而歸類，下面是迭代器範疇的一個（不完全）列表:

範疇｜語言

雙向迭代器｜C++

前向迭代器｜C++

輸入迭代器｜C++

輸出迭代器｜C++

隨機訪問迭代器｜C++

Trivial迭代器｜C++ (舊STL)

### 迭代器類型

不同的語言或它們所具有的函數庫定義了自己的迭代器的類型，下面是一個（不完全）列表：

類型｜語言

陣列迭代器｜PHP, R

緩存迭代器｜PHP

常量迭代器｜C++, PHP

目錄迭代器｜PHP, Python

過濾器迭代器｜PHP, R

Limit迭代器｜PHP

列表迭代器｜Java, R

遞歸陣列迭代器｜PHP

XML迭代器｜PHP

## 語言範例

### C#

在C#中，一種新形式的迭代器提供了函數語言程式設計中的生成器，使用`yield return`

類似於Python中使用的`yield`

```csharp
// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers)
{
    foreach(int i in numbers)
    {
        if (i % 2 == 0) yield return i;
    }
}
```

### C++

C++的STL可支持迭代器。

```c++
 template<typename InputIterator>
 void printall(InputIterator first, InputIterator last)
 {
     for(; first != last; ++first)
     {
         std::cout << *first << std::endl;
     }
 }
```

### Java

Java JDK 1.2 版開始支持迭代器。每一個迭代器提供`next()`以及`hasNext()`方法，同時也支持remove。

```java
Iterator iter = list.iterator();
//Iterator<MyType> iter = list.iterator();    in J2SE 5.0
while (iter.hasNext())
    System.out.println(iter.next());
```

### Python

在Python中，迭代器是語言的基礎部份，而在很多情況下是不可見的，因為它們隱含的用在了`for`（foreach）語句、列表推導式和生成器表達式之中。Python標準內建的所有搜集 (抽象數據類型)類型都支持迭代，還有很多支持它的類也是標準庫的一部分。下面的例子展示典型的在序列（如列表、元組、字典、集合等）上的隱式迭代：

```Python
for value in sequence:
    print(value)
```

Python字典（某種形式的關聯數組），在字典返回了鍵（key）的時候，可以直接在其上進行迭代：

```Python
for key in dictionary:
    value = dictionary[key]
    print(key, value)
```

或者在字典`items`方法產生元組形式的對應鍵-值對的時候，在其上進行迭代：

```Python
for key, value in dictionary.items():
    print(key, value)
```

但是迭代器也可以被顯式的使用和定義。對於一個可迭代的序列類型或類，內建的函數`iter()`可用來建立一個迭代對象。接著可以通過`next()`函數對這個迭代對象進行迭代；這個函數在內部使用`__next__()`方法，它返回這個容器中的下一個元素。（前面的敘述適用於Python 3.x，在Python 2.x中要使用等價的`next()`方法。）當沒有元素剩餘的時候，引發`StopIteration`異常。下面的例子展示與前例等價的使用顯式迭代器的在序列上的迭代：

```Python
it = iter(sequence)
while True:
    try:
        #value = it.next()
        value = next(it)
    except StopIteration:
        break
    print(value)
```

任何使用者定義的類都可以通過定義返回迭代器對象的`__iter__()`方法，支持標準迭代（無論隱式還是顯式）。接著迭代器對象需要定義返回下一個元素的`__next__()`方法。

Python生成器實現了這個迭代協議。

### Ruby

Ruby程序員可以用yield關鍵字定義迭代器，又將迭代器和生成器分開。

```ruby
0..42.each do |n|
 puts n
end
```

...以及...

```ruby
for n in 0..42
 puts n
end
```

### Rust

使用Rust可以對向量的元素進行迭代，或者創建自己的迭代器。每個迭代器都有適配器(map，filter，skip，take……)。

```rust
for n in 0..42 {
    println!("{}", n);
}
```

fibonacci下面是一個自定義迭代器。

```rust
for i in fibonacci().skip(4).take(4) {
    println!("{}", i);
}
```

## 外部連結

- Article " Understanding and Using Iterators " by Joshua Gatcomb
- Article " A Technique for Generic Iteration and Its Optimization " (217 KB) by Stephen M. Watt
- Overview of the Standard Template Library
- STL Iterators
- What are iterators? - Reference description
- Java interface
- Template reference
- Boost C++ Iterator Library
- PHP: Object Iteration