迭代器
迭代器（英語：iterator），是使用戶可在容器物件（container，例如鏈表或陣列）上遍訪的物件[1][2][3]，設計人員使用此介面無需關心容器物件的內存分配的實現細節。其行為很像數據庫技術中的游標（cursor），迭代器最早出現在1974年設計的CLU編程語言中。
在各種語言實作迭代器的方式皆不盡同，有些物件導向語言像Java、C#、Ruby、Python、Delphi都已將迭代器的特性內建語言當中，完美的跟語言整合，我們稱之隱式迭代器。但像是C++語言本身就沒有迭代器的特色，但STL仍利用模板實作了功能強大的迭代器。STL容器的數據的內存地址可能會重新分配（reallocate），與容器綁定的迭代器仍然可以定位到重新分配後的正確的內存地址。
描述
編輯內部迭代器
編輯內部的迭代器是高階函數（通常接受匿名函數），比如map、 reduce等，它實現跨經一個容器的遍歷，依次將給定函數應用到每個元素。
外部迭代器和迭代器模式
編輯外部的迭代器可以被認為是某種類型的指針，它有兩個主要操作：引用在一個對象搜集（collection）中的一個特定元素（稱為元素訪問），和修改自身使其指向下一個元素（稱為元素遍歷）[4]。還必須有一種方式建立迭代器並指向容器的第一個元素，還要有某種方式確定何時迭代器已經窮盡了容器中所有的元素。依據語言和意向用途，迭代器還可以提供額外的操作或展示不同的行為。
迭代器的主要用途是允許用戶處理一個容器的所有元素，而將用戶隔離於容器的內部結構[2]。這允許容器以任何它希望的方式存儲元素，而允許用戶把它們看作就是簡單的序列或列表。迭代器類通常設計為緊密協作於對應的容器類。容器類通常提供建立迭代器的方法。
循環計數器有時也被稱為循環迭代器。但是循環計數器只提供遍歷功能而不提供訪問功能。
生成器
編輯實現迭代器的一種方式是使用受限形式的協程，也叫做生成器。不同於子例程，生成器協程可以向它的調用者多次產生返回值，而非只是返回一次。多數迭代器可自然的表達為生成器，但是因為生成器在被多次啟用之間保存了自己的局部狀態，它們特別適合於複雜的、有狀態的迭代器，比如樹遍歷器。在不同的作者和語言之間，術語「生成器」和「迭代器」的用法上有微妙的差異和區別[5]。有些語言將二者視為同一介面，有些語言如JavaScript[6]則將之獨立化。在Python中，生成器是一個迭代器構造器，即返回一個迭代器的函數。下面的Python生成器返回一個斐波那契數列的迭代器，使用到了Python的yield語句：
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，提供了迭代一個容器對象的元素的內置方式，而不用介入一個顯式的迭代器對象。實際的迭代器對象可以在現實中存在，即便如此，它也不被暴露在這個語言的源代碼中[4][7]。
隱式迭代器經常通過foreach語句（或等價者）來顯現出來，比如下面的Python例子：
for value in iterable:
print(value)
在Python中，可迭代者（iterable）是可以被轉換成迭代器的一個對象，接着在這個for循環期間從頭至尾迭代它，這是隱含完成的。
在Smalltalk家族語言和受其啟發的語言中，它們可以由搜集（collection）對象自身建立。比如下面Ruby例子：
iterable.each do |value|
puts value
end
這種迭代風格有時叫做「內部迭代」，因為它的代碼完全執行在可迭代對象的上下文（context）之內（它控制迭代的所有方面），而編程者只提供在每個步驟要執行的運算操作（使用匿名函數）。
支持列表推導式或類似構造的語言，還可以在結果列表的構造期間使用隱式迭代器，比如在Python中：
names = [person.name for person in roster if person.male]
有時隱式迭代只能做到部份的隱藏實質。C++語言有一些用於隱式迭代的函數模板，比如for_each()。這些函數仍要求顯式的迭代器對象作為它們的初始輸入，但是後續的迭代不將迭代器對象暴露給用戶。
串流
編輯迭代器是對輸入串流的一種有用的抽象，串流提供了潛在的無限可迭代的（但不必然可索引）的對象。一些語言，比如Perl和Python，將串流實現為迭代器。串流的可替代的實現包括數據驅動語言，比如AWK和sed。
迭代器分類
編輯迭代器範疇
編輯迭代器可以依據功能而歸類，下面是迭代器範疇的一個（不完全）列表[8][9]:
| 範疇 | 語言 |
|---|---|
| 雙向迭代器 | C++ |
| 前向迭代器 | C++ |
| 輸入迭代器 | C++ |
| 輸出迭代器 | C++ |
| 隨機訪問迭代器 | C++ |
| Trivial迭代器 | C++ (舊STL)[10] |
迭代器類型
編輯不同的語言或它們所具有的函數庫定義了自己的迭代器的類型，下面是一個（不完全）列表[11]：
| 類型 | 語言 |
|---|---|
| 數組迭代器 | PHP, R[12] |
| 緩存迭代器 | PHP |
| 常量迭代器 | C++,[13] PHP |
| 目錄迭代器 | PHP, Python |
| 過濾器迭代器 | PHP, R |
| Limit迭代器 | PHP |
| 列表迭代器 | Java,[7] R |
| 遞歸數組迭代器 | PHP |
| XML迭代器 | PHP |
語言範例
編輯C#
編輯在C#中，一種新形式的迭代器提供了函數語言程式設計中的生成器，使用yield return
類似於Python中使用的yield
// 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++
編輯 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()。
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標準內建的所有搜集類型都支持迭代，還有很多支持它的類也是標準庫的一部分。下面的例子展示典型的在序列（如列表、元組、字典、集合等）上的隱式迭代：
for value in sequence:
print(value)
Python字典（某種形式的關聯數組），在字典返回了鍵（key）的時候，可以直接在其上進行迭代：
for key in dictionary:
value = dictionary[key]
print(key, value)
或者在字典items方法產生元組形式的對應鍵-值對的時候，在其上進行迭代：
for key, value in dictionary.items():
print(key, value)
但是迭代器也可以被顯式的使用和定義。對於一個可迭代的序列類型或類，內建的函數iter()可用來建立一個迭代對象。接着可以通過next()函數對這個迭代對象進行迭代；這個函數在內部使用__next__()方法，它返回這個容器中的下一個元素。（前面的敘述適用於Python 3.x，在Python 2.x中要使用等價的next()方法。）當沒有元素剩餘的時候，引發StopIteration異常。下面的例子展示與前例等價的使用顯式迭代器的在序列上的迭代：
it = iter(sequence)
while True:
try:
#value = it.next() # in Python 2.x
value = next(it) # in Python 3.x
except StopIteration:
break
print(value)
任何用戶定義的類都可以通過定義返回迭代器對象的__iter__()方法，支持標準迭代（無論隱式還是顯式）。接着迭代器對象需要定義返回下一個元素的__next__()方法。
Ruby
編輯Ruby程序員可以用yield關鍵字定義迭代器，又將迭代器和生成器分開。
0..42.each do |n|
puts n
end
...以及...
for n in 0..42
puts n
end
Rust
編輯使用Rust可以對向量的元素進行迭代，或者創建自己的迭代器。 每個迭代器都有適配器(map，filter，skip，take……)。
for n in 0..42 {
println!("{}", n);
}
fibonacci()下面是一個自定義迭代器。
for i in fibonacci().skip(4).take(4) {
println!("{}", i);
}
參見
編輯引用
編輯- ^ Gatcomb, Joshua. Understanding and Using Iterators. Perl.com. [2012-08-08]. （原始內容存檔於2005-06-30）.
A user-defined iterator usually takes the form of a code reference that, when executed, calculates the next item in a list and returns it. When the iterator reaches the end of the list, it returns an agreed-upon value.
- ^ 2.0 2.1 Watt, Stephen M. A Technique for Generic Iteration and Its Optimization (PDF). The University of Western Ontario, Department of Computer Science. [2012-08-08]. （原始內容存檔於2012-08-06）.
Iterators were introduced as constructs to allow looping over abstract data structures without revealing their internal representation.
- ^ Alex Allain. STL Iterators. Cprogramming.com - Your resource for C and C++. [2012-08-08]. （原始內容存檔於2021-02-13）.
You can think of an iterator as pointing to an item that is part of a larger container of items.
- ^ 4.0 4.1 Difference between an external iterator and an internal iterator. CareerRide.COM. 2009-04-03 [2012-08-08]. （原始內容存檔於2021-04-18）.
An internal iterator is implemented by the member functions of the class which has the iteration logic. An external iterator is implemented by a separate class which can be attached to the object which has iteration logic. The advantage of external iterator is that, many iterators can be made active simultaneously on the existing or same object.
- ^ Watt, Stephen M. A Technique for Generic Iteration and Its Optimization (PDF). The University of Western Ontario, Department of Computer Science. [2012-08-08]. （原始內容存檔 (PDF)於2022-05-26）.
Some authors use the term iterator, and others the term generator. Some make subtle distinctions between the two.
- ^ Iterators and generators. MDN Web Docs. [2018-10-16]. （原始內容存檔於2021-05-18） （美國英語）.
- ^ 7.0 7.1 Freeman, Eric; Freeman, Elisabeth; Kathy, Sierra; Bert, Bates. Hendrickson, Mike; Loukides, Mike , 編. Head First Design Patterns 1. O'REILLY: 338. 2004 [2012-08-09]. ISBN 978-0-596-00712-6. （原始內容 (paperback)存檔於2020-04-30）.
- ^ Kevin Waterson. C++ Iteratoren: Iterator-Kategorien. cppreference.com. [2012-08-09]. （原始內容存檔於2016-01-10） （德語）.
- ^ Kevin Waterson. Iterators: Concepts. sgi. [2012-08-09]. （原始內容存檔於2017-12-03）.
- ^ larsmans. Types of iterator: Output vs. input vs. forward vs. random access iterator. stackoverflow. 2011-03-06 [2012-08-09]. （原始內容存檔於2015-11-28）.
- ^ Kevin Waterson. Introduction to SPL: Introduction to Standard PHP Library (SPL). PHPRO.ORG. [2012-08-09]. （原始內容存檔於2016-01-10）.
- ^ Collier, Andrew. Iterators in R. [16 November 2013]. （原始內容存檔於2018-10-18）.
- ^ concurrent_unordered_set Template Class. Intel Threading Building Blocks for Open Source. [2012-08-09]. （原始內容存檔於2015-05-01）.
•The iterator types iterator and const_iterator are of the forward iterator category
外部連結
編輯
- 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 （頁面存檔備份，存於網際網路檔案館）