Python 迭代器和 C++ 迭代器，最大的不同竟然是......

作者 | 櫻雨樓

責編 | 胡巍巍

迭代器（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）的定義類似，其包含以下兩種情況：

1. 是一個真正的指針

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在 Python 中，迭代器基於鴨子類型（Duck Type）下的迭代器協議（Iterator Protocol）實現。迭代器協議規定：如果一個類想要成為可迭代對象（Iterable Object），則其必須實現__iter__方法，且其返回值需要是一個實現了__next__方法的對象。

即：實現了__iter__方法的類將成為可迭代對象，而實現了__next__方法的類將成為迭代器。

顯然，__iter__方法是 iter 函數所對應的魔法方法，__next__方法是 next 函數所對應的魔法方法。

對於一個可迭代對象，針對「誰實現了__next__方法？」這一問題進行討論，可將可迭代對象的實現分為兩種情況：

1. self 未實現__next__：如果__iter__方法的返回值就是一個 Iterator，則此時 self 即為一個可迭代對象。此時，self 將迭代操作「委託」到了另一個數據結構上。示例代碼如下：

class SampleIterator:

def __iter__(self):

return iter(...)

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

class SampleIterator:

def __iter__(self):

return self

def __next__(self):

# Not The End

if ...:

return ...

# Reach The End

else:

raise StopIteration

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

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

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

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

def SampleGenerator:

yield ...

yield ...

yield ...

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

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

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

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

4.4 與C++迭代器的比較

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

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

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

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

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

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

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

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

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

考察如下代碼：

numList = [1, 2, 3]

numListIter = iter(numList)

next(numListIter)

for i in range(1000000):

numList.append(i)

# print 2

print(next(numListIter))

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

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

numList = [1,2]

numListIter = iter(numList)

# 1

next(numList)

numList.append(3)

# 2

next(numListIter)

# 3

print(next(numListIter))

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

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

考察如下代碼：

numList = [1,2]

numListIter = iter(numList)

for _ in numListIter:

pass

numList.append(3)

# StopIteration

print(next(numListIter))

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

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

考察如下代碼：

numDict = {1:2}

numDictIter = iter(numDict)

numDict[3] = 4

# RuntimeError

next(numDictIter)

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

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

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

作者：豌豆花下貓，某985高校畢業生， 兼具極客思維與人文情懷。公眾號Python貓，專註Python技術、數據科學和深度學習，力圖創造一個有趣又有用的學習分享平台。

聲明：本文為作者投稿，版權歸作者所有。

【End】

下面給大家推薦 CSDN 的好朋友——程序人生。

為什麼推薦程序人生？

程序人生聚集百萬程序員，在這裡你可以笑談開發軼事，吐槽百味的程序人生。

無論是從行業熱點到經驗解析，從職場困惑到風口趨勢，還有程序員不為人知的秘密，我們將為你一一揭曉。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！