Python 中的迭代器實現原理

在數學中，集合表示由一個或多個確定的元素所構成的整體。在 Python 中，列表、元組、集合可以用于表示數學中的集合。

例如，分別使用列表、元組、集合表示了一個包含 3 個字符串的集合：

• 列表 [‘www’, ‘imooc’, ‘com’]
• 元組 (‘www’, ‘imooc’, ‘com’)
• 集合 {‘www’, ‘imooc’, ‘com’}

1. 可迭代對象 iterable

1.1 什么是可迭代對象

Python 提供了 for … in 循環，用于對列表、元組、集合中的元素進行遍歷。能夠被 for … in 循環遍歷的對象被稱為可迭代對象 iterable，列表、元組、集合均屬于可迭代對象。使用 for … in 循環遍歷可迭代對象的例子如下：

• 遍歷列表的代碼

list = ['www', 'imooc', 'com']
for item in list:
    print(item)

• 遍歷元組的代碼

tuple = ('www', 'imooc', 'com')
for item in tuple:
    print(item)

• 遍歷集合的代碼

set = {'www', 'imooc', 'com'}
for item in set:
    print(item)

1.2 盡可能使用 for … in 循環進行遍歷

如果需要遍歷的對象是列表，可以通過訪問索引的方式進行遍歷，代碼如下：

strings = ['www', 'imooc', 'com']
i = 0
while i < len(strings):
    string = strings[i]
    print(string)
    i = i + 1

• 在第 1 行，使用列表表示 strings
• 在第 3 行，通過 len(strings) 獲取列表 strings 中字符串的數量
• 在第 4 行，通過 strings[i] 訪問第 i 個元素

以上的遍歷方式中，要求 strings 是一個列表，如果 strings 的數據結構發生變化：使用集合而不是列表表示 strings，那么通過訪問索引的方式進行遍歷的代碼就會失效。

strings = {'www', 'imooc', 'com'}
i = 0
while i < len(strings):
    string = strings[i]
    print(string)
    i = i + 1

• 在第 1 行，使用集合表示 strings
• 在第 3 行，通過 len(strings) 獲取集合 strings 中字符串的數量
• 在第 4 行，通過 strings[i] 訪問第 i 個元素

因為 strings 是一個集合，不支持索引操作，會導致運行錯誤：

Traceback (most recent call last):
  File "strings.py", line 5, in <module>
    string = strings[i]
TypeError: 'set' object does not support indexing

應盡可能使用 for … in 循環遍歷可迭代對象，如果可迭代對象的數據類型發生變化，從列表變成集合，使用for … in 循環遍歷的代碼則無需改變。

2. 迭代器 iterator

1.1 什么是迭代器

迭代器 iterator 是一個特殊的對象，用于遍歷訪問可迭代對象 iterable。Python 通過迭代器 iterator 實現 for … in 循環語句，用戶編寫的 for … in 循環代碼如下：

for item in iterable:
    print(item)

這段 for … in 循環代碼會被翻譯為如下：

iterator = iter(iterable)
while True:
    try:
        item = next(iterator)
        print(item)
    except StopIteration:
        break

• 在第 1 行，內置函數 iter 獲取可迭代對象 iterable 的迭代器 iterator
• 在第 4 行，內置函數 next 獲取迭代器 iterator 返回的下一個元素
• 在第 6 行，當迭代器遍歷完全部元素后，拋出一個特殊的異常 StopIteration，表示迭代結束

1.2 列表的迭代器

下面通過一個具體的例子，了解如何通過迭代器實現 for … in 循環，使用 for … in 循環遍歷列表的代碼如下：

list = ['www', 'imooc', 'com']
for item in list:
    print(item)

Python 把以上 for … in 循環轉換為如下功能等價的代碼：

list = ['www', 'imooc', 'com']
listIterator = iter(list)
while True:
    try:
        item = next(listIterator)
        print(item)
    except StopIteration:
        break

以上兩段代碼均輸出相同的結果，如下所示：

www
imooc
com

3. 迭代協議

使用迭代器遍歷訪問可迭代對象，要求迭代器和可迭代對象遵循迭代協議，迭代協議如下：

1. 可迭代對象 iterable 提供成員方法 __iter__，該方法返回用于遍歷的迭代器 iterator

class Iterable:
    def __iter__(self):

2. 迭代器 iterator 提供成員方法 __next__，該方法返回下一個被遍歷的元素

class Iterator:
    def __next__(self):

3. 異常 StopIteration，當遍歷完全部的元素后，成員方法 __next__ 拋出一個特殊的異常 Stop Iteration 表示遍歷結束

4. 內置函數 iter，用于獲取可迭代對象對應的迭代器

def iter(iterable):
    iterator = iterable.__iter__()
    return iterator

• 在第 1 行，iter 的輸入參數是可迭代對象 iterable
• 在第 2 行，調用成員方法 __iter__
• 在第 3 行，返回迭代器 iterator

5. 內置函數 next，用于獲取下一個被遍歷的元素

def next(iterator):
    item = iterator.__next__()
    return item

• 在第 1 行，next 的輸入參數是迭代器 iterator
• 在第 2 行，調用成員方法 __next__
• 在第 3 行，返回被遍歷的元素

根據以上的迭代協議，即可將 for … in 循環翻譯為如下等價代碼：

iterator = iter(iterable)
while True:
    try:
        item = next(iterator)
        print(item)
    except StopIteration:
        break

4. 實現一個自定義的迭代器

4.1 通過單鏈表實現堆棧

通過單鏈表實現堆棧，圖示如下：

在上圖中，每個節點有兩個字段: item 和 next，item 用于存儲數據，next 指向下一個節點，head 指針指向堆棧的頂部。描述堆棧的 Python 代碼如下：

class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    def push(self, item):
        node = Node(item)
        node.next = self.head
        self.head = node

stack = Stack()
stack.push('a')
stack.push('b')
stack.push('c')

• 在第 1 行，定義了類 Node 用于描述鏈表中的節點
• 在第 6 行，定義了類 Stack 描述堆棧
  • 在第 8 行，定義了頭指針 head，指向鏈表中的首個節點
  • 在第 10 行，定義了成員方法 push，將元素壓如到堆棧中
    • 在第 11 行，創建一個新節點 node
    • 在第 12 行，新節點 node 的 next 指向頭結點
    • 在第 13 行，頭結點指向新節點
• 在第 15 行，創建一個對象 stack
• 在第 16 行到第 18 行，依次壓入 3 個元素 ‘a’、‘b’、‘c’

4.2 實現迭代協議

class StackIterator:
    def __init__(self, stack):
        self.stack = stack
        self.cursor = self.stack.head

    def __next__(self):
        if self.cursor == None:
            raise StopIteration
        else:
            item = self.cursor.item
            self.cursor = self.cursor.next
            return item

• 在第 1 行，定義類 StackIterator
  • 類 Stack 是可迭代對象
  • 類 StackIterator 是迭代器
• 在第 2 行，定義構造函數，參數 stack 是被遍歷的對象
  • 在第 4 行，成員變量 cursor 指向了當前正在遍歷的元素，初始化被設置為鏈表的頭結點
• 在第 6 行，定義方法 __next__
  • 在第 7 行，如果變量 cursor 等于 None，表示已經到達鏈表的尾部，即遍歷完全部的元素了
    • 在第 8 行，拋出異常 StopIteration 表示遍歷結束
  • 在第 9 行，如果變量 cursor 不等于 None
    • 在第 10 行，記錄下當前正在遍歷的元素
    • 在第 11 行，將 cursor 指向下一個元素

在定義了 StackIterator 后，在 Stack 中增加一個新的成員方法 __iter__，返回 Stack 對應的迭代器，代碼如下：

class Stack:
    def __iter__(self):
        return StackIterator(self)   

4.3 通過 while 循環遍歷堆棧

在實現了迭代協議后，使用 while 循環顯示的使用 iter、next、StopIteration 完成對 stack 的遍歷，代碼如下：

stackIterator = iter(stack)
while True:
    try:
        item = next(stackIterator)
        print(item)
    except StopIteration:
        break

程序依次壓入 ‘a’、‘b’、‘c’，遍歷時以壓入相反的順序輸出，結果如下：

c
b
a

4.4 通過 for … in 循環遍歷堆棧

在實現了迭代協議后，可以通過 for … in 循環進行遍歷，代碼如下：

for item in stack:
    print(item)

與上一節的代碼相比，代碼要簡潔很多，程序輸出相同的結果如下：

c
b
a