迭代器

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

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

## 描述

### 內部迭代器

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

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

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

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

迴圈計數器有時也被稱為迴圈迭代器。但是迴圈計數器只提供遍歷功能而不提供存取功能。

#### 生成器

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

### 隱式迭代器

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

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

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

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

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

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

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

### 串流

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

## 迭代器分類

### 迭代器範疇

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

### 迭代器類型

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

## 語言範例

### C♯

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

類似於 Python 中使用的 `yield`

### C++

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

### Java

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

### Python

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

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

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

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

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

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

### Ruby

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

... 以及...

### Rust

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

fibonacci () 下面是一個自訂迭代器。

## 參見

* Iteratee
* 設計模式
* 迭代
* 迭代器模式
* 範圍
* 存取者模式
* 指標 (電腦編程)

## 參照

## 外部連結

* 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 （頁面存檔備份，存於網際網路檔案館）