Python中的iterator、iterable、generator

剛接觸Python的時候著實為iterator、iterable、generator所困擾
且一開始從官網下載安裝的就是Python3，但在摸索的過程中又看到了許多Python2的文章
剛開始哪搞得清楚Python2與Python3的差別，試了許多Python2的範例常常都行不通
從C++轉過來的我又對Python的duck typing非常地不能理解與適應
讓我不禁納悶想問：是誰說Python簡單的呀？

以下先總結我對這些名詞的認知(本篇文章內容都是針對Python3)：
iterable：中文翻作可迭代物，通常是一個容器、iterable實作__iter__方法回傳一個參考到此容器內部的iterator

iterator：中文翻作迭代器、iterator pattern在Python中的實作，為序列或容器型態提供一相同的介面讓客戶端可遍歷(iterate over)容器內的元素，iterator實作了__next__與__iter__方法，方別供next與iter函式呼叫，每個iterator同時也是一個iterable

generator：中文翻作產生器，是由包含yield敘述的函式或產生器表達式(簡稱genexp)所產生，支援所有iterator的操作以及額外的send方法，客戶端可透過send方法與generator溝通、影響其內部狀態

先舉個簡單的例子，請看以下的程式碼：

>>>a=[1,2]
>>>b=iter(a)
>>>c=iter(b)
>>>c is b
True
>>>next(b)
1
>>>next(b)
2
>>>next(b)
Traceback (most recent call last):
  File "", line 1, in 
    next(b)
StopIteration

從上面的例子我們就可以弄懂iterable與iterator的分別了
iterable指的就是容器本身，將iterable傳進iter函式可以得到一個iterator
iterator的操作非常簡單，透過next函式可以不斷取出下一個元素，抵達尾端時會丟出StopIteration意外
在Python中iterator是個一次性的物件，不能回頭，若想要重新遍歷容器就必須再藉由iter函式產生新的iterator

另外從第三行程式碼可以發現：iterator本身也是一個iterable，這是為了方便和一致性，把iterator丟進iter函式會回傳iterator本身，這樣可以讓iterator也能用在for迴圈以及接受iterable的函式中

我們可以模擬一下簡單的iterator大概是長這樣：

class IteratorSim:
    def __init__(self,container):
        self.index=-1
        self.container=container

    def __iter__(self):
        print('invoke iter')
        return self

    def __next__(self):
        print('invoke next')
        self.index+=1
        if self.index>len(self.container)-1:
            raise StopIteration
        return self.container[self.index]

IteratorSim由建構式接收並保存一個容器的參考
每次__next__方法被調用時就回傳容器中的元素，並將代表目前索引值的index加1
在__next__與__iter__中都加入了print來紀錄這兩個方法的呼叫，我們可以此來觀察一下for迴圈的運作：

a=[1,2,3]
it=IteratorSim(a)

for i in it:
    print(a)

輸出：

invoke iter
invoke next
1
invoke next
2
invoke next
3
invoke next

觀察上面的結果可知對一個iterator或iterable做for迴圈時，會先呼叫iter函式取得iterator，然後用next函式取出其值，直到StopIteration被丟出
上面這個類別只是為了展示用，實際上我們很少需要實作自己的iterator，在製作自己的容器類別時通常也會以Python內建的容器類別當底層的資料結構，只要借用這些容器內建的iterator或配合genexp在大部分情況下就夠用了
以上就是iterator與iterable的基本行為

行為解釋完了，接下來稍微談一下對應這兩者的ABC(Abstract Class抽象類別)
在collections.abc中定義了許多ABC，iterator與iterable也包含其中(i要改為大寫I)
雖然Python是動態語言，並不像其他編譯式語言有著嚴謹的型別規定，在Python只關心物件有沒有支援特定的操作，並不關心其真正的型別是什麼或繼承了什麼
但繼承一個ABC並實作其要求的純虛擬方法可以讓你的類別立即享用到ABC中的其他方法，以及代表對其型別的強烈保證
任何類別只要有__iter__方法皆會被視為Iterable的子類別，即使沒有顯式地繼承它，這是因為在Iterable中實作了__subclasshook__，會自動地把有__iter__方法的類別納入為子類別

許多函式都要求引數為iterable，最直覺的方法是不是用isinstance(obj,Iterable)或hasattr(obj,'__iter__')來檢查呢？
這樣做有一個問題，有一種情況是類別沒有__iter__方法但卻是iterable，可以丟進for迴圈，那就是：有實作__getitem__的類別實例
__getitem__方法讓物件支援索引取值，索引超過範圍時會丟出IndexError，理論上來說這樣就足以遍歷整個物件了，Python會很聰明地幫你把這個類別擴充，讓他可以當成iter的引數並產生一個iterator
所以確認引數是否為iterable的正確方式應為把它傳進iter函式，若不是，則TypeError例外會被擲出

接下來談談generator，generator是一種特殊的iterator，使用它的方法跟iterator一模一樣
最簡單產生generator的方式是使用genexp，用串列生成式(list comprehension)不同處在於genexp不會一次生成一整個串列，而是產生一個generator，每次進行迭代才會產出一個元素，這樣可以節省不必要開記憶體開支，例如以下範例：

>>>sum(i for i in range(100))#引數只有一個時genexp的括號可省略
4950
>>>sum([i for i in range(100)])
4950

sum函式是接收一個iterable並計算所有元素的總和，對sum函式來說無可避免地需要迭代出每一個元素，所以一次傳一個很大的list跟傳一個generator是沒有分別的，這就是使用generator節省記憶體的時機之一

另一種會產生generator的情況是呼叫有包含yield關鍵字的函式，如下：

def foo():
    print('generator start')
    a=yield 1
    print('first yield')
    a=yield a
    print('second yield')
    a=yield a
    print('last yield')
>>> a=foo()
>>> a
<generator object foo at 0x039CF8D0>
>>> next(a)
generator start
1
>>> a.send(5)
first yield
5
>>> a.send(2)
second yield
2
>>> next(a)
last yield
Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    next(a)
StopIteration

上面簡單示範了yield的行為，foo被呼叫後會回傳一個generator，在第一次的next或send之前，函式內容不會執行
每次呼叫next或send方法後，呼叫方會得到下一次yield的值且函式會停留在該處
send方法所傳進去的值會成為該次yield陳述的運算結果，若是呼叫next而不是send則相當於send(None)，這就是為什麼最後一次的next不會得到任何值
yield敘述跟generator還有很多細節可以討論，有興趣的讀者可以直接上Python官網查詢相關文件
(補充：通常yield會放在一個while回圈裡，但這裡為了方便示範直接寫了三次yield)
講到這不知道大家有沒有發現，透過genexp得到的generator它的send是無用武之地的，因為並沒有存在yield陳述可以抓到send的值！
這麼設計應該是另有原因，可能設計者者不想讓genexp又產出一種新的iterator的所以直接復用generator了

最後補充一些C++與Python的iterator分別
C++中的iterator是除了讓眾多不同的STL容器能有相同的存取介面之外，也讓STL容器能與原生陣列(C-style array)有很好的相容性，原生陣列可透過[]運算子以及指標加上*運算子取值，iterator讓STL容器可以用類似指標的方式存取它們，並且可以簡單地使用++運算子讓iterator指向容器的下一個位置，儘管在不同的容器中下一個位置的移動方式可能是天差地遠

C++中並沒有一個抽象子類別讓所有的iterator繼承，而是定義了一些共同的介面讓template函式所使用
在C++中template函式的特性就是它可以根據不同的參數型態在產生多個不同的函式實體，而這些型態只要能支援函式內部的操作即可，在C++中這稱為隱式介面(implicit interface)
這其實與Python的動態型別有一點像，但差別在於C++中這些事情都是在編譯期進行
所以要是用不適當的型別去實體化一個template函式，程式碼會直接無法通過編譯

而iterable應該算對應到STL容器，STL容器可以透過begin方法得到指向容器第一個元素的iterator，這就類似iter函式的作用，在C++中用到iterator的API都是要求傳入兩個iterator，分別指向容器的第一個元素，與最後一個元素的之後的某個位置，也就是end方法所回傳的iterator
這剛開始聽起來好像很奇怪，但在C++中iterator有一個重要的任務：那就是盡可能地跟原生指標相容
指標中可以用NULL或nullptr代表不指向任何合法位置的指標，而在iterator中就是用最後一個元素的下一個位置來當作NULL，代表不指向任何一個容器內已存在的元素
當然，你可也可以傳入container.begin()+2和container.end()-3這種iterator來讓函式只作用到一部分的容器元素

C++中的iterator分為幾個層級，由功能最少到功能最多分別為：
input_iterator與output_iterator、forward_iterator、bidirectional_iterator與功能最強random_access_iterator
這個資訊記錄在每個iterator class中一個叫做iterator_category的typedef裡，使用iterator的演算法可根據不同層級所支援的操作來實現最佳化
Python的iterator等級對應到C++中的forward_iterator，這類型的iterator只能往前不能回頭
但在Python這種動態語言中這些iterator種類的規範就顯得囉嗦而不必要了，Python中給容器用的函式是接收iterable而不一定要從iterable中產生iterator再傳入，若此容器確實支援random access，那直接用整數下標取值即可，要判斷容器是否能支援這個操作在Python裡也相當容易