導語：之前說過，我對于編程語言跟其它學科的融合非常感興趣，但我還說漏了一點，就是我對于 Python 跟其它編程語言的對比學習，也很感興趣。所以，我一直希望能聚集一些有其它語言基礎的同學，一起討論共通的語言特性間的話題。不同語言的碰撞，常常能帶給人更高維的視角，也能觸及到語言的根基，這個過程是極有益的。

0 前言

迭代器（Iterator）是 Python 以及其他各種編程語言中的一個非常常見且重要，但又充滿著神秘感的概念。無論是 Python 的基礎內置函數，還是各類高級話題，都處處可見迭代器的身影。

那么，迭代器究竟是怎樣的一個概念？其又為什么會廣泛存在于各種編程語言中？本文將基于 C++ 與 Python，深入討論這一系列問題。

1 什么是迭代器？我們為什么要使用迭代器？

什么是迭代器？當我初學 Python 的時候，我將迭代器理解為一種能夠放在“for xxx in …”的“…”位置的東西；后來隨著學習的深入，我了解到迭代器就是一種實現了迭代器協議的對象；學習 C++ 時，我了解到迭代器是一種行為和指針類似的對象…

事實上，迭代器是一個伴隨著迭代器模式（Iterator Pattern）而生的抽象概念，其目的是分離并統一不同的數據結構訪問其中數據的方式，從而使得各種需要訪問數據結構的函數，對于不同的數據結構可以保持相同的接口。

在很多討論 Python 迭代器的書籍與文章中，我看到這樣兩種觀點：1. 迭代器是為了節約數據結構所產生的內存；2. 遍歷迭代器效率更高。

這兩點論斷都是很不準確的：首先，除了某些不定義在數據結構上的迭代器（如文件句柄，itertools 模塊的 count、cycle 等無限迭代器等），其他迭代器都定義在某種數據結構上，所以不存在節約內存的優勢；其次，由于迭代器是一種高度泛化的實現，其需要在每一次迭代器移動時都做一些額外工作（如 Python 需要不斷檢測迭代器是否耗盡，并進行異常監測；C++ 的 deque 容器需要對其在堆上用于存儲的多段不連續內存進行銜接等），故遍歷迭代器的效率一定低于或幾乎接近于直接遍歷容器，而不太可能高于直接遍歷原容器。

綜上所述，迭代器存在的意義，不是為了空間換時間，也不是為了時間換空間，而是一種適配器（Adapter）。迭代器的存在，使得我們可以使用同樣的 for 語句去遍歷各種容器，或是像 C++ 的 algorithm 模塊所示的那樣，使用同樣的接口去處理各種容器。

這些容器可以是一個連續內存的數組或列表，或是一個多段連續內存的 deque，甚至是一個完全不連續內存的鏈表或是哈希表等等，我們完全不需要關注迭代器對于不同的容器究竟是怎么取得數據的。

2 C++中的迭代器

2.1 泛化指針

在 C++ 中，迭代器通過泛化指針（Generalized Pointer）的形式呈現。泛化指針與仿函數（Functor）的定義類似，其包含以下兩種情況：

是一個真正的指針

不是指針，但重載了某些指針運算符（如“*，++，--，!=” 等），使得其行為和指針相似

根據泛化指針為了將其“偽裝”成一個真正的指針從而重載的運算符的數量，迭代器被分為五種，如下文所示。

2.2 C++的迭代器分類

C++ 的迭代器按其所支持的行為被分為五類：

輸入迭代器（Input Iterator）：僅可作為右值（rvalue），不可作為左值（lvalue）。可以進行比較（“== 與 !=”）

輸出迭代器（Output Iterator）：僅可作為左值，不可作為右值

前向迭代器（Forward Iterator）：支持一切輸入迭代器的操作，以及單步前進操作（++）

雙向迭代器（Bidirectional Iterator）：支持一切前向迭代器的操作，以及單步后退操作（--）

隨機訪問迭代器（Random Access Iterator）：支持一切雙向迭代器操作，以及非單步雙向移動操作

對于前向迭代器，雙向迭代器，以及隨機訪問迭代器，如果其不存在底層 const（Low-Level Const）限定，則同時也支持一切輸出迭代器操作。

2.3 迭代器適配器

C++ 中還存在一系列迭代器適配器，用于使得一些非迭代器對象的行為類似于迭代器，或修改迭代器的一些默認行為，大致包含如下幾個類別：

插入迭代器（Insert Iterator）：使得對迭代器左值的寫入操作變為向容器中插入數據的操作，按插入位置的不同，可分為 front_insert_iterator，back_insert_iterator 和 insert_iterator

反向迭代器（Reverse Iterator）：對調迭代器的移動方向。使得“+”操作變為向左移動，同時“-”操作變為向右移動（類似于 Python 的 reversed 函數）

移動迭代器（Move Iterator）：使得對迭代器的取值變為右值引用（Rvalue Reference）

流迭代器（Stream Iterator）：使流對象的行為適配迭代器（類似于 Python 的文件句柄）

3 Python中的迭代器

3.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):returniter(...)

self 實現了__next__：如果__iter__方法返回 self，則說明 self 本身將作為迭代器，此時 self 本身需要繼續實現__next__方法，以實現完整的迭代器協議。示例代碼如下：

classSampleIterator:def__iter__(self):returnselfdef__next__(self):#NotTheEndif...:return...#ReachTheEndelse:raiseStopIteration

此例可以看出，當迭代器終止時，通過拋出 StopIteration 異常告知 Python 迭代器已耗盡。

3.2 生成器

生成器（Generator）是 Python 特有的一組特殊語法，其主要目的為提供一個基于函數而不是類的迭代器定義方式。同時，Python 也具有生成器推導式，其基于推導式語法快速建立迭代器。生成器一般適用于需要創建簡單邏輯的迭代器的場合。

只要一個函數的定義中出現了 yield 關鍵詞，則此函數將不再是一個函數，而成為一個“生成器構造函數”，調用此構造函數即可產生一個生成器對象。

由此可見，如果僅討論該語法本身，而不關心實現的話：生成器只是“借用”了函數定義的語法，實際上與函數并無關系（并不代表生成器的底層實現也與函數無關）。示例代碼如下：

defSampleGenerator():yield...yield...yield...

生成器推導式則更為簡單，只需要將列表推導式的中括號換為小括號即可：

(...for...in...)

綜上所述，生成器是 Python 獨有的一類迭代器的特殊構造方式。生成器一旦被構造，其會自動實現完整的迭代器協議。

3.3 無限迭代器

itertools 模塊中實現了三個特殊的無限迭代器（Infinite Iterator）：count，cycle 以及 repeat，其有別于普通的表示范圍的迭代器。如果對無限迭代器進行迭代將導致無限循環，故無限迭代器通常只可使用 next 函數進行取值。

3.4 與C++迭代器的比較

經過上文的討論可以發現，Python 只有一種迭代器，此種迭代器只能進行單向，單步前進操作，且不可作為左值。故 Python 的迭代器在 C++ 中應屬于單向只讀迭代器，這是一種很低級的迭代器。

此外，由于迭代器只支持單向移動，故一旦向前移動便不可回頭，如果遍歷一個已耗盡迭代器，則 for 循環將直接退出，且無任何錯誤產生，此種行為往往會產生一些難以察覺的 bug，實際使用時請務必注意。

綜上所述，Python 對于迭代器的實現其實是高度匱乏的，應謹慎使用。

4 迭代器有效性

4.1 什么是迭代器有效性？

由于迭代器本身并不是獨立的數據結構，而是指向其他數據結構中的值的泛化指針，故和普通指針一樣，一旦指針指向的內存發生變動，則迭代器也將隨之失效。

如果迭代器指向的數據結構是只讀的，則顯然，直到析構函數被調用，迭代器都不會失效。但如果迭代器所指向的數據結構在其存在時發生了插入或刪除操作，則迭代器將可能失效。故討論某個操作是否會導致指向容器的迭代器失效，是一個很重要的話題。

4.2 C++的迭代器有效性

由于 Python 中沒有 C++ 的 list、deque 等數據結構實現，故本文只簡單地討論 vector 與 unordered_map 這兩種數據結構的迭代器有效性。

對于 vector，由于其存在內存擴容與轉移操作，故任何會潛在導致內存擴容的方法都將損壞迭代器，包括 push_back、emplace_back、insert、emplace 等。

unordered_map 與 vector 的情形類似，對 unordered_map 進行任何插入操作也將損壞迭代器。

4.3 Python的迭代器有效性

注：本節所討論全部內容均基于實際行為進行猜想和推論，并沒有經過對 Python 源代碼的考察和驗證，僅供讀者參考。

4.3.1 尾插入操作不會損壞指向當前元素的List迭代器

考察如下代碼：

numList=[1,2,3]numListIter=iter(numList)next(numListIter)foriinrange(1000000):numList.append(i)#print2print(next(numListIter))

如果在 C++ 中對一個 vector 執行這么多次的 push_back，則指向第二個元素的迭代器一定早已失效。但在 Python 中可以看到，指向 List 的迭代器并未失效，其仍然返回了 2。

故可猜想：Python 對于 List 所產生的迭代器并不跟蹤指向 List 元素的指針，而僅僅跟蹤的是容器的索引值。

4.3.2 尾插入操作會損壞List尾迭代器

numList=[1,2]numListIter=iter(numList)#1next(numList)numList.append(3)#2next(numListIter)#3print(next(numListIter))

首先，Python 不存在尾迭代器這一概念。但由上述代碼可知，當迭代器所指向的 List 變長后，迭代器的終止點也隨之變化，即：原先的尾迭代器將不再適用。

按照“迭代器僅跟蹤元素索引值”這一推斷，也能解釋這一行為。

4.3.3 迭代器一旦耗盡，則將永久損壞

考察如下代碼：

numList=[1,2]numListIter=iter(numList)for_innumListIter:passnumList.append(3)#StopIterationprint(next(numListIter))

當 for 一個迭代器后，迭代器將耗盡，在 C++ 中，這將導致頭尾迭代器相等，但由上述代碼可知， Python 的迭代器一旦耗盡，便不再可以使用，即使繼續往容器中增加元素也不行。

由此可見， Python 的迭代器中可能存在某種用于指示迭代器是否被耗盡的標記，一旦迭代器被標記為耗盡狀態，便永遠不可繼續使用了。

4.3.4 任何插入操作都將損壞Dict迭代器

考察如下代碼：

numDict={1:2}numDictIter=iter(numDict)numDict[3]=4#RuntimeErrornext(numDictIter)

當對一個 Dict 進行插入操作后，原 Dict 迭代器將立即失效，并拋出 RuntimeError。這與 C++ 中的行為是一致的，且更為安全。

Set 與 Dict 具有相同的迭代器失效性質，不再重復討論。

5 后記

迭代器的故事到這里就結束了。總的看來，Python 中的迭代器雖應用廣泛，但并不是一種高級的，靈活的實現，且存在著一些黑魔法。故唯有深入的去理解，才能真正的用好迭代器。祝編程愉快~