作者 | 櫻雨樓
責編 | 胡巍巍
前言
迭代器（Iterator）是 Python 以及其他各種程式語言中的一個非常常見且重要，但又充滿著神秘感的概念。無論是 Python 的基礎內置函數，還是各類高級話題，都處處可見迭代器的身影。
那麼，迭代器究竟是怎樣的一個概念？其又為什麼會廣泛存在於各種程式語言中？本文將基於 C++ 與 Python，深入討論這一系列問題。
什麼是迭代器？我們為什麼要使用迭代器？
什麼是迭代器？當我初學 Python 的時候，我將迭代器理解為一種能夠放在「for xxx in …」的「…」位置的東西；後來隨著學習的深入，我了解到迭代器就是一種實現了迭代器協議的對象；學習 C++ 時，我了解到迭代器是一種行為和指針類似的對象…
事實上，迭代器是一個伴隨著迭代器模式（Iterator Pattern）而生的抽象概念，其目的是分離並統一不同的數據結構訪問其中數據的方式，從而使得各種需要訪問數據結構的函數，對於不同的數據結構可以保持相同的接口。
在很多討論 Python 迭代器的書籍與文章中，我看到這樣兩種觀點：1. 迭代器是為了節約數據結構所產生的內存；2. 遍歷迭代器效率更高。
這兩點論斷都是很不準確的：首先，除了某些不定義在數據結構上的迭代器（如文件句柄，itertools 模塊的 count、cycle 等無限迭代器等），其他迭代器都定義在某種數據結構上，所以不存在節約內存的優勢；其次，由於迭代器是一種高度泛化的實現，其需要在每一次迭代器移動時都做一些額外工作（如 Python 需要不斷檢測迭代器是否耗盡，並進行異常監測；C++ 的 deque 容器需要對其在堆上用於存儲的多段不連續內存進行銜接等），故遍歷迭代器的效率一定低於或幾乎接近於直接遍歷容器，而不太可能高於直接遍歷原容器。
綜上所述，迭代器存在的意義，不是為了空間換時間，也不是為了時間換空間，而是一種適配器（Adapter）。迭代器的存在，使得我們可以使用同樣的 for 語句去遍歷各種容器，或是像 C++ 的 algorithm 模塊所示的那樣，使用同樣的接口去處理各種容器。
這些容器可以是一個連續內存的數組或列表，或是一個多段連續內存的 deque，甚至是一個完全不連續內存的鍊表或是哈希表等等，我們完全不需要關注迭代器對於不同的容器究竟是怎麼取得數據的。
C++中的迭代器
3.1 泛化指針
在 C++ 中，迭代器通過泛化指針（Generalized Pointer）的形式呈現。泛化指針與仿函數（Functor）的定義類似，其包含以下兩種情況：
是一個真正的指針不是指針，但重載了某些指針運算符（如「*，++，--，!=」 等），使得其行為和指針相似根據泛化指針為了將其「偽裝」成一個真正的指針從而重載的運算符的數量，迭代器被分為五種，如下文所示。
3.2 C++的迭代器分類
C++ 的迭代器按其所支持的行為被分為五類：
輸入迭代器（Input Iterator）：僅可作為右值（rvalue），不可作為左值（lvalue）。可以進行比較（「== 與 !=」）輸出迭代器（Output Iterator）：僅可作為左值，不可作為右值前向迭代器（Forward Iterator）：支持一切輸入迭代器的操作，以及單步前進操作（++）雙向迭代器（Bidirectional Iterator）：支持一切前向迭代器的操作，以及單步後退操作（--）隨機訪問迭代器（Random Access Iterator）：支持一切雙向迭代器操作，以及非單步雙向移動操作對於前向迭代器，雙向迭代器，以及隨機訪問迭代器，如果其不存在底層 const（Low-Level Const）限定，則同時也支持一切輸出迭代器操作。
3.3 迭代器適配器
C++ 中還存在一系列迭代器適配器，用於使得一些非迭代器對象的行為類似於迭代器，或修改迭代器的一些默認行為，大致包含如下幾個類別：
插入迭代器（Insert Iterator）：使得對迭代器左值的寫入操作變為向容器中插入數據的操作，按插入位置的不同，可分為 front_insert_iterator，back_insert_iterator 和 insert_iterator反向迭代器（Reverse Iterator）：對調迭代器的移動方向。使得「+」操作變為向左移動，同時「-」操作變為向右移動（類似於 Python 的 reversed 函數）移動迭代器（Move Iterator）：使得對迭代器的取值變為右值引用（Rvalue Reference）流迭代器（Stream Iterator）：使流對象的行為適配迭代器（類似於 Python 的文件句柄）
Python中的迭代器
4.1 迭代器協議
在 Python 中，迭代器基於鴨子類型（Duck Type）下的迭代器協議（Iterator Protocol）實現。迭代器協議規定：如果一個類想要成為可迭代對象（Iterable Object），則其必須實現__iter__方法，且其返回值需要是一個實現了__next__方法的對象。
即：實現了__iter__方法的類將成為可迭代對象，而實現了__next__方法的類將成為迭代器。
顯然，__iter__方法是 iter 函數所對應的魔法方法，__next__方法是 next 函數所對應的魔法方法。
對於一個可迭代對象，針對「誰實現了__next__方法？」這一問題進行討論，可將可迭代對象的實現分為兩種情況：
self 未實現__next__：如果__iter__方法的返回值就是一個 Iterator，則此時 self 即為一個可迭代對象。此時，self 將迭代操作「委託」到了另一個數據結構上。示例代碼如下：classSampleIterator:def__iter__(self):return iter(...)
self 實現了__next__：如果__iter__方法返回 self，則說明 self 本身將作為迭代器，此時 self 本身需要繼續實現__next__方法，以實現完整的迭代器協議。示例代碼如下：classSampleIterator:def__iter__(self):return selfdef__next__(self):# Not The Endif ...:return ...# Reach The Endelse:raise StopIteration
此例可以看出，當迭代器終止時，通過拋出 StopIteration 異常告知 Python 迭代器已耗盡。
4.2 生成器
生成器（Generator）是 Python 特有的一組特殊語法，其主要目的為提供一個基於函數而不是類的迭代器定義方式。同時，Python 也具有生成器推導式，其基於推導式語法快速建立迭代器。生成器一般適用於需要創建簡單邏輯的迭代器的場合。
只要一個函數的定義中出現了 yield 關鍵詞，則此函數將不再是一個函數，而成為一個「生成器構造函數」，調用此構造函數即可產生一個生成器對象。
由此可見，如果僅討論該語法本身，而不關心實現的話：生成器只是「借用」了函數定義的語法，實際上與函數並無關係（並不代表生成器的底層實現也與函數無關）。示例代碼如下：
def SampleGenerator():yield ...yield ...yield ...
生成器推導式則更為簡單，只需要將列表推導式的中括號換為小括號即可：
(... for ... in ...)
綜上所述，生成器是 Python 獨有的一類迭代器的特殊構造方式。生成器一旦被構造，其會自動實現完整的迭代器協議。
4.3 無限迭代器
itertools 模塊中實現了三個特殊的無限迭代器（Infinite Iterator）：count，cycle 以及 repeat，其有別於普通的表示範圍的迭代器。如果對無限迭代器進行迭代將導致無限循環，故無限迭代器通常只可使用 next 函數進行取值。
4.4 與C++迭代器的比較
經過上文的討論可以發現，Python 只有一種迭代器，此種迭代器只能進行單向，單步前進操作，且不可作為左值。故 Python 的迭代器在 C++ 中應屬於單向只讀迭代器，這是一種很低級的迭代器。
此外，由於迭代器只支持單向移動，故一旦向前移動便不可回頭，如果遍歷一個已耗盡迭代器，則 for 循環將直接退出，且無任何錯誤產生，此種行為往往會產生一些難以察覺的 bug，實際使用時請務必注意。
綜上所述，Python 對於迭代器的實現其實是高度匱乏的，應謹慎使用。
迭代器有效性
5.1 什麼是迭代器有效性？
由於迭代器本身並不是獨立的數據結構，而是指向其他數據結構中的值的泛化指針，故和普通指針一樣，一旦指針指向的內存發生變動，則迭代器也將隨之失效。
如果迭代器指向的數據結構是只讀的，則顯然，直到析構函數被調用，迭代器都不會失效。但如果迭代器所指向的數據結構在其存在時發生了插入或刪除操作，則迭代器將可能失效。故討論某個操作是否會導致指向容器的迭代器失效，是一個很重要的話題。
5.2 C++的迭代器有效性
由於 Python 中沒有 C++ 的 list、deque 等數據結構實現，故本文只簡單地討論 vector 與 unordered_map 這兩種數據結構的迭代器有效性。
對於 vector，由於其存在內存擴容與轉移操作，故任何會潛在導致內存擴容的方法都將損壞迭代器，包括 push_back、emplace_back、insert、emplace 等。
unordered_map 與 vector 的情形類似，對 unordered_map 進行任何插入操作也將損壞迭代器。
5.3 Python的迭代器有效性
註：本節所討論全部內容均基於實際行為進行猜想和推論，並沒有經過對 Python 原始碼的考察和驗證，僅供讀者參考。
5.3.1 尾插入操作不會損壞指向當前元素的List迭代器
考察如下代碼：
numList = [1, 2, 3]numListIter = iter(numList)next(numListIter)for i in range(1000000):numList.append(i)# print 2print(next(numListIter))
如果在 C++ 中對一個 vector 執行這麼多次的 push_back，則指向第二個元素的迭代器一定早已失效。但在 Python 中可以看到，指向 List 的迭代器並未失效，其仍然返回了 2。
故可猜想：Python 對於 List 所產生的迭代器並不跟蹤指向 List 元素的指針，而僅僅跟蹤的是容器的索引值。
5.3.2 尾插入操作會損壞List尾迭代器
numList = [1,2]numListIter = iter(numList)# 1next(numList)numList.append(3)# 2 next(numListIter)# 3print(next(numListIter))
首先，Python 不存在尾迭代器這一概念。但由上述代碼可知，當迭代器所指向的 List 變長後，迭代器的終止點也隨之變化，即：原先的尾迭代器將不再適用。
按照「迭代器僅跟蹤元素索引值」這一推斷，也能解釋這一行為。
5.3.3 迭代器一旦耗盡，則將永久損壞
考察如下代碼：
numList = [1,2]numListIter = iter(numList)for _ in numListIter:passnumList.append(3)# StopIterationprint(next(numListIter))
當 for 一個迭代器後，迭代器將耗盡，在 C++ 中，這將導致頭尾迭代器相等，但由上述代碼可知， Python 的迭代器一旦耗盡，便不再可以使用，即使繼續往容器中增加元素也不行。
由此可見， Python 的迭代器中可能存在某種用於指示迭代器是否被耗盡的標記，一旦迭代器被標記為耗盡狀態，便永遠不可繼續使用了。
5.3.4 任何插入操作都將損壞Dict迭代器
考察如下代碼：
numDict = {1:2}numDictIter = iter(numDict)numDict[3] = 4# RuntimeErrornext(numDictIter)
當對一個 Dict 進行插入操作後，原 Dict 迭代器將立即失效，並拋出 RuntimeError。這與 C++ 中的行為是一致的，且更為安全。
Set 與 Dict 具有相同的迭代器失效性質，不再重複討論。
後記
迭代器的故事到這裡就結束了。總的看來，Python 中的迭代器雖應用廣泛，但並不是一種高級的，靈活的實現，且存在著一些黑魔法。故唯有深入的去理解，才能真正的用好迭代器。祝編程愉快~
作者：豌豆花下貓，某985高校畢業生， 兼具極客思維與人文情懷。公眾號Python貓，專注Python技術、數據科學和深度學習，力圖創造一個有趣又有用的學習分享平臺。
聲明：本文為作者投稿，版權歸作者所有。
【End】
下面給大家推薦 CSDN 的好朋友——程序人生。
為什麼推薦程序人生？
程序人生聚集百萬程式設計師，在這裡你可以笑談開發軼事，吐槽百味的程序人生。
無論是從行業熱點到經驗解析，從職場困惑到風口趨勢，還有程式設計師不為人知的秘密，我們將為你一一揭曉。