跳至內容

疊代器

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書

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

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

描述

[編輯]

內部疊代器

[編輯]

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

外部疊代器和疊代器模式

[編輯]
主條目：疊代器模式

外部的疊代器可以被認為是某種類型的指標，它有兩個主要操作：參照在一個對象搜集（英語：Collection (abstract data type)）（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++

[編輯]

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

 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標準內建的所有搜集（英語：Collection (abstract data type)）類型都支援迭代，還有很多支援它的類也是標準庫的一部分。下面的例子展示典型的在序列（如列表、元組、字典、集合等）上的隱式迭代： 

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__()方法。

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

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);
}

參見

[編輯]

參照

[編輯]
  1. ^ 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. ^ 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. 
  3. ^ 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. ^ 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. 
  5. ^ 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. 
  6. ^ Iterators and generators. MDN Web Docs. [2018-10-16]. （原始內容存檔於2021-05-18） （美國英語）. 
  7. ^ 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）. 
  8. ^ Kevin Waterson. C++ Iteratoren: Iterator-Kategorien. cppreference.com. [2012-08-09]. （原始內容存檔於2016-01-10） （德語）. 
  9. ^ Kevin Waterson. Iterators: Concepts. sgi. [2012-08-09]. （原始內容存檔於2017-12-03）. 
  10. ^ larsmans. Types of iterator: Output vs. input vs. forward vs. random access iterator. stackoverflow. 2011-03-06 [2012-08-09]. （原始內容存檔於2015-11-28）. 
  11. ^ Kevin Waterson. Introduction to SPL: Introduction to Standard PHP Library (SPL). PHPRO.ORG. [2012-08-09]. （原始內容存檔於2016-01-10）. 
  12. ^ Collier, Andrew. Iterators in R. [16 November 2013]. （原始內容存檔於2018-10-18）. 
  13. ^ 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 

外部連結

[編輯]
查看維基詞典中的詞條「迭代器」。
取自 "https://zh.wikipedia.org/w/index.php?title=迭代器&oldid=83137902"