00前言

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

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

01 什么是迭代器？我們?yōu)槭裁匆褂玫鳎?/span>

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

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

在很多討論 Python 迭代器的書籍與文章中，我看到這樣兩種觀點(diǎn)：1. 迭代器是為了節(jié)約數(shù)據(jù)結(jié)構(gòu)所產(chǎn)生的內(nèi)存；2. 遍歷迭代器效率更高。

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

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

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

02 C++中的迭代器

2.1 泛化指針

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

1. 是一個真正的指針

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

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

2.2 C++的迭代器分類

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

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

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

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

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

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

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

2.3 迭代器適配器

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

1. 插入迭代器（Insert Iterator）：使得對迭代器左值的寫入操作變?yōu)橄蛉萜髦胁迦霐?shù)據(jù)的操作，按插入位置的不同，可分為 front_insert_iterator，back_insert_iterator 和 insert_iterator

2. 反向迭代器（Reverse Iterator）：對調(diào)迭代器的移動方向。使得“+”操作變?yōu)橄蜃笠苿樱瑫r“-”操作變?yōu)橄蛴乙苿樱愃朴?Python 的 reversed 函數(shù)）

3. 移動迭代器（Move Iterator）：使得對迭代器的取值變?yōu)橛抑狄茫≧value Reference）

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

03 Python中的迭代器

3.1 迭代器協(xié)議

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

即：實(shí)現(xiàn)了__iter__方法的類將成為可迭代對象，而實(shí)現(xiàn)了__next__方法的類將成為迭代器。

顯然，__iter__方法是 iter 函數(shù)所對應(yīng)的魔法方法，__next__方法是 next 函數(shù)所對應(yīng)的魔法方法。

對于一個可迭代對象，針對“誰實(shí)現(xiàn)了__next__方法？”這一問題進(jìn)行討論，可將可迭代對象的實(shí)現(xiàn)分為兩種情況：

1. self 未實(shí)現(xiàn)__next__：如果__iter__方法的返回值就是一個 Iterator，則此時 self 即為一個可迭代對象。此時，self 將迭代操作“委托”到了另一個數(shù)據(jù)結(jié)構(gòu)上。示例代碼如下：

class SampleIterator:
    def __iter__(self):
        return iter(...)

2. self 實(shí)現(xiàn)了__next__：如果__iter__方法返回 self，則說明 self 本身將作為迭代器，此時 self 本身需要繼續(xù)實(shí)現(xiàn)__next__方法，以實(shí)現(xiàn)完整的迭代器協(xié)議。示例代碼如下：

class SampleIterator:
    def __iter__(self):
        return self

    def __next__(self):
        # Not The End
        if ...:
            return ...
        # Reach The End
        else:
            raise StopIteration

此例可以看出，當(dāng)?shù)鹘K止時，通過拋出 StopIteration 異常告知 Python 迭代器已耗盡。

3.2 生成器

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

只要一個函數(shù)的定義中出現(xiàn)了 yield 關(guān)鍵詞，則此函數(shù)將不再是一個函數(shù)，而成為一個“生成器構(gòu)造函數(shù)”，調(diào)用此構(gòu)造函數(shù)即可產(chǎn)生一個生成器對象。

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

def SampleGenerator():
    yield ...
    yield ...
    yield ...

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

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

綜上所述，生成器是 Python 獨(dú)有的一類迭代器的特殊構(gòu)造方式。生成器一旦被構(gòu)造，其會自動實(shí)現(xiàn)完整的迭代器協(xié)議。

3.3 無限迭代器

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

關(guān)于無限迭代器的詳細(xì)內(nèi)容，可參閱 Python 文檔。(注：我在 Python進(jìn)階：設(shè)計(jì)模式之迭代器模式 寫過)

3.4 與C++迭代器的比較

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

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

綜上所述，Python 對于迭代器的實(shí)現(xiàn)其實(shí)是高度匱乏的，應(yīng)謹(jǐn)慎使用。

04 迭代器有效性

4.1 什么是迭代器有效性？

由于迭代器本身并不是獨(dú)立的數(shù)據(jù)結(jié)構(gòu)，而是指向其他數(shù)據(jù)結(jié)構(gòu)中的值的泛化指針，故和普通指針一樣，一旦指針指向的內(nèi)存發(fā)生變動，則迭代器也將隨之失效。

如果迭代器指向的數(shù)據(jù)結(jié)構(gòu)是只讀的，則顯然，直到析構(gòu)函數(shù)被調(diào)用，迭代器都不會失效。但如果迭代器所指向的數(shù)據(jù)結(jié)構(gòu)在其存在時發(fā)生了插入或刪除操作，則迭代器將可能失效。故討論某個操作是否會導(dǎo)致指向容器的迭代器失效，是一個很重要的話題。

4.2 C++的迭代器有效性

由于 Python 中沒有 C++ 的 list、deque 等數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，故本文只簡單地討論 vector 與 unordered_map 這兩種數(shù)據(jù)結(jié)構(gòu)的迭代器有效性。

對于 vector，由于其存在內(nèi)存擴(kuò)容與轉(zhuǎn)移操作，故任何會潛在導(dǎo)致內(nèi)存擴(kuò)容的方法都將損壞迭代器，包括 push_back、emplace_back、insert、emplace 等。

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

4.3 Python的迭代器有效性

注：本節(jié)所討論全部內(nèi)容均基于實(shí)際行為進(jìn)行猜想和推論，并沒有經(jīng)過對 Python 源代碼的考察和驗(yàn)證，僅供讀者參考。

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

考察如下代碼：

numList = [1, 2, 3]
numListIter = iter(numList)
next(numListIter)

for i in range(1000000):
    numList.append(i)

# print 2
print(next(numListIter))

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

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

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

numList = [1,2]
numListIter = iter(numList)

# 1
next(numList)
numList.append(3)

# 2 
next(numListIter)

# 3
print(next(numListIter))

首先，Python 不存在尾迭代器這一概念。但由上述代碼可知，當(dāng)?shù)魉赶虻?List 變長后，迭代器的終止點(diǎn)也隨之變化，即：原先的尾迭代器將不再適用。

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

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

考察如下代碼：

numList = [1,2]
numListIter = iter(numList)
for _ in numListIter:
    pass

numList.append(3)

# StopIteration
print(next(numListIter))

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

由此可見， Python 的迭代器中可能存在某種用于指示迭代器是否被耗盡的標(biāo)記，一旦迭代器被標(biāo)記為耗盡狀態(tài)，便永遠(yuǎn)不可繼續(xù)使用了。

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

考察如下代碼：

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

# RuntimeError
next(numDictIter)

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

Set 與 Dict 具有相同的迭代器失效性質(zhì)，不再重復(fù)討論。

05 后記

迭代器的故事到這里就結(jié)束了?？偟目磥?，Python 中的迭代器雖應(yīng)用廣泛，但并不是一種高級的，靈活的實(shí)現(xiàn)，且存在著一些黑魔法。故唯有深入的去理解，才能真正的用好迭代器。祝編程愉快~