前文已经介绍了许多特殊方法，通过重写或实现这些特殊方法，自定义的类越来越融入 Python 的语法，成为一个合格的 Python 对象了。本节重点介绍容器和迭代相关的特殊方法。
Python中的容器
编程语言中的数据类型大多都可以分为简单类型和复杂类型，复杂类型一般是处理多个值的。Python 中的容器(container)表示一类存储一系列值的数据类型，例如序列（如元组、列表）以及映射（如字典）。
容器类型这个概念在 Python 中非常重要，因为 Python 的许多语法都是针对容器设置的，相应地也有一些关于容器的特殊方法。本节以两种典型数据结构链表和二叉树为例介绍容器相关的特殊方法。不过本文并不是为了介绍这些数据结构，而是通过这些示例介绍如何在 Python 中使用特殊方法为容器提供一致的接口。
首先给出这些数据类型最基本的定义：
class LinkedListNode:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self._length = 0
class BinaryTreeNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
self._length = 0
处理索引
在 Python 中，可以使用方括号的形式从容器中取值：对于序列，方括号根据索引值从序列中获取元素；对于映射，方括号根据键从映射中获取值：
>>> l = [50, 100, 200, 300]
>>> d = {'this': 50, 'that': 100, 'those': [1, 2, 3]}
>>> l[1]
100
>>> d['this']
50
.__getitem__() 特殊方法提供了对方括号语法的支持。该方法需要一个额外的参数 key ，代表向方括号内传入的值。
对于 LinkedList 类，它的 .__getitem__() 需要根据索引获得值，那么这个方法就可以这样编写：
class LinkedList:
def __getitem__(self, index):
if not 0 <= index < self._length:
raise IndexError('index out of range')
current = self.head
for _ in range(index):
current = current.next
return current
接下来先编写一个辅助方法，批量为链表添加值：
class LinkedList:
def append(self, value):
new_node = LinkedListNode(value)
self._length += 1
if self.tail is None:
self.head = new_node
self.tail = new_node
return
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
ls = LinkedList()
for _ in range(10):
ls.append(random.randint(0, 100))
可以看到，现在的链表实例便支持使用方括号的索引了，并且对于不合适的索引值会自动抛出错误：
>>> ls[0]
LinkedListNode(72)
>>> ls[9]
LinkedListNode(9)
>>> ls[10]
Traceback (most recent call last):
File ".../container.py", line 169, in __getitem__
IndexError: index out of range
但目前的 .__getitem__() 方法还远不够完善。例如，在 Python 中，索引可能是负值，代表从尾部倒数的位置：
>>> l[-1]
300
所以序列的 .__getitem__() 方法最好添加对负数索引的支持：
class LinkedList:
def __getitem__(self, index):
if not -self._length <= index < self._length:
raise IndexError('index out of range')
if index < 0:
index = self._length + index
# ...
映射的 .__getitem__() 方法处理起来则简单得多，它是根据键获取值，并且在键不存在时应该抛出 KeyError 异常：
class BinarySearchTree:
def _get(self, node, key):
if node is None:
return None
if key < node.key:
return self._get(node.left, key)
elif key > node.key:
return self._get(node.right, key)
else:
return node
def __getitem__(self, key):
node = self._get(self.root, key)
if node is None:
raise KeyError(f'{key!r} not found.')
return node.value
内置类型slice
方括号除了需要处理索引外，别忘了 Python 中还有一种特殊的语法切片。切片是专门针对序列的；回顾一下，Python 切片的语法为：
container[start:stop:step]
其中 start 表示起始位置的索引，stop 表示结束位置的索引，step 表示步长。切片的结果会包含起始位置的元素，但不会包含结束位置的元素：
>>> ls = list(range(10))
>>> ls
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> ls[1:-1:2]
[1, 3, 5, 7]
内置类型 slice 提供了对切片的支持。在平时使用切片时，Python 会自动将冒号表示的切片转换为 slice 对象，list 等序列也会自动处理 slice 对象，所以不会直接接触 slice 。但在自定义的类中，就需要处理 slice 对象了。
slice 对象有 3 个属性：start 、stop 和 step ，它们和切片语法的记号一一对应。不过拿到了这几个属性之后不要直接通过这几个值计算每个元素的位置，因为 Python 的切片规则比想象中的要复杂。例如，当步长为负的时候，切片会从后往前获取元素：
>>> ls[3:9:-1]
[]
>>> ls[9:3:-1]
[9, 8, 7, 6, 5, 4]
这个时候可以借助内置的 range 处理实际位置的元素。别忘了 range 函数同样接收 start 、stop 和 step 这三个参数，而且它的生成结果就可以作为索引值。因此代码可以这样编写：
class LinkedList:
def __getitem__(self, index):
if isinstance(index, slice):
return tuple(self[i] for i in
range(index.start, index.stop, index.step))
# ...
不过直接使用 range 还有一些问题：首先是切片的起止可能是负数，但 range 处理完后还是负数，这点可以通过处理前将起止转化为相对长度的正数解决；其次，切片语法的每个元素都可以省略，省略它们会使得 slice 对象的对应属性被转换为 None ：
>>> ls[::-1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> ls[:]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> class DemoType:
... def __getitem__(self, index):
... print(index, type(index))
>>> demo = DemoType()
>>> demo[:3:]
slice(None, 3, None) <class 'slice'>
>>> demo[:]
slice(None, None, None) <class 'slice'>
所以，程序中还需要对 None 值加以检测，并恢复为合理的默认值：
- 如果省略
start ，则默认为序列的开头
- 如果省略
stop ，则默认为序列的结尾
- 如果省略
step ，则默认为 1 ，表示单步切片
既要处理负值，还要处理缺失值，这使得切片的处理非常麻烦。不过好在 slice 类提供了一个 .indices() 方法，它专门用于处理序列切片时的索引问题：.indices() 方法接收一个数值，代表序列的长度，它会根据这个长度自动处理切片对象的负值和空值；它的返回结果是一个三元素元组，可以直接解包作为 range 的参数，从而极大简化了索引的问题：
class LinkedList:
def __getitem__(self, index):
if isinstance(index, slice):
return tuple(self[i] for i in range(*index.indices(self._length)))
# ...
实际上，Python 方括号的功能非常强大，甚至平时使用的索引和切片远没有发挥方括号的功能。例如，方括号实际上可以接收多个值：
>>> demo[2, 3, 4]
(2, 3, 4) <class 'tuple'>
可以看出，Python 会将任意以逗号分隔的值转换为一个元组。不仅如此，这个元组内的每个元素都可以是一个切片字面量：
>>> demo[:, 2, 3:3:2, 2]
(slice(None, None, None), 2, slice(3, 3, 2), 2) <class 'tuple'>
这样索引和切片便可以处理更复杂的数据。Python 专门处理多维数组的第三方库 numpy 和它在数据处理方面的增强版本 pandas 几乎将 Python 的索引和切片用到了极致，它们不仅使用元组处理多维数组的索引，还在多维数组中引入了 None 和 Ellipsis 的作用，分别表示单个坐标轴的升维和多个连续维度的切片：
import numpy as np
arr = np.arange(10 ** 5).reshape((10,) * 5)
arr[0, :, None, ...]
pandas 更是提供了非数值形式的索引和层级索引，可以表示并处理任意复杂的表格数据：
import pandas as pd
df = pd.DataFrame(rand.randint(50, 95, size=(4, 6)),
index=pd.MultiIndex.from_product([[2020, 2021], [1, 2]],
names=['year', 'term']),
columns=pd.MultiIndex.from_product([['Tim', 'Mary', 'John'],
['math', 'physics']],
names=['name', 'subject']))
df.loc[pd.IndexSlice[:, 1], pd.IndexSlice[:, 'math']]
其它容器方法
以上只介绍了针对获取元素的 __getitem__ ，显然有 get 就有对应的 set 和 delete ，它们分别用于以 object[key] = value 与 del object[key] 的方式添加值和删除值，例如：
class BinarySearchTree:
def __delitem__(self, key):
self.root = self._delete(self.root, key)
def __setitem__(self, key, value):
self.root = self._insert(self.root, key, value)
def _insert(self, node, key, value):
if node is None:
self._length += 1
return BinaryTreeNode(key, value)
if key < node.key:
node.left = self._insert(node.left, key, value)
...
def _delete(self, node, key):
if node is None:
raise KeyError(f'Key {key} not found.')
if key < node.key:
node.left = self._delete(node.left, key)
...
那么 BinarySearchTree 对象就可以使用这两种语法添加或删除键值对了：
tree[50] = 'Added'
del tree[50]
除此之外，还有一些方法也是针对序列的：
Python 中为容器提供了一个操作符 in ，用于检查特定元素或键是否存在于容器中。该操作符将返回一个布尔值：如果元素或键存在于容器中，返回 True ，否则返回 False ：
>>> 100 in l
True
>>> 150 in l
False
>>> 'that' in d
True
.__contains__(self, key) 提供了对自定义容器类型使用 in 操作符的支持。如果想让自定义的容器支持 in 操作符，就需要编写自己的 .__contains__() 方法：
class LinkedList:
def __contains__(self, key):
for node in self:
if node.value == key:
return True
return False
现在 LinkedList 就可以使用 in 操作符检查元素的存在性了：
>>> ls
LinkedList[19, 21, 96, 75, 50, 56, 91, 100, 46, 8]
>>> 21 in ls
True
>>> 24 in ls
False
最后，Python 还为容器提供了一个 .__len__() 特殊方法，它会被内置函数 len() 调用以获取容器内元素的个数。之前还说过，如果容器实现了 .__len__() 特殊方法，那么它不用实现 .__bool__() 方法就可以正确转换为布尔值了。
class LinkedList:
def __len__(self):
return self._length
序列协议
在 Python 中，序列是一种很特殊的容器类型：它可以看作是索引到元素的一种映射，但索引只能是小于 .__len__() 的整数。这时类的定义可以简化。
在 Python 中，如果想要让一个对象模拟容器类型（如列表或元组），只需要实现以下两个方法：
.__len__(self) ：这个方法应该返回序列中元素的数量__getitem__(self, key) ：这个方法应该通过索引或切片获取序列中的元素
只要实现了这两个方法，该类的实例就可以作为 for 循环的循环对象，Python 会尝试使用 0 到 .__len__() 的整数作为索引，尝试应用 .__getitem__() 方法从对象中取值。并且在使用 in 运算符时，Python 可以通过这种行为检查序列的所有元素，从而判断是否包含了指定的元素，而不需要实现 .__contains__() 方法。
这种特殊的行为在 Python 中称为“序列协议”。“协议(protocol)”通常是指非正式的接口，这些接口不是由正式的接口或抽象基类定义的，而是由类实现的方法和属性集合，使得实例能够按照一定的方式工作。上一节介绍的鸭子类型是协议的一个典型表现：如果一个对象执行了所需要的方法，它就可以被用在任何期望这些方法的地方，不必严格继承某个特定的类或实现一个特定的接口。如果一个类实现了序列协议的特殊方法，它的实例就能表现得像一个序列，可以实现索引、切片、迭代等序列操作。
不仅如此，Python 的协议甚至可以用于 issubclass() 和 isinstance() 。例如，在 collections.abc 中提供了一些容器的抽象基类，只要实现了这些抽象基类支持的协议方法，就可以用作子类的判据，例如：
>>> from collections.abc import Container
>>> help(Container)
Help on class Container in module collections.abc:
class Container(builtins.object)
| Methods defined here:
|
| __contains__(self, x)
...
这说明，任何实现了 .__contains__() 方法的类，都可以视为 Container 的子类，而无需显式继承它，哪怕这个子类并不打算作为容器使用：
class Interval:
def __init__(self, low, high, low_inc=True, high_inc=True):
self.low, self.high = low, high
self.low_inc, self.high_inc = low_inc, high_inc
def __contains__(self, value):
if self.low_inc and self.high_inc:
return self.low <= value <= self.high
elif self.low_inc and not self.high_inc:
return self.low <= value < self.high
# ...
print(issubclass(Interval, Container)) # True
不过，显式继承这些抽象基类的好处在于，这些抽象基类通常会对子类的方法做检查，以确保它们实现了关键的特殊方法：
>>> from collections.abc import Sequence
>>> class LinkedList(Sequence): pass
>>> from collections.abc import MutableMapping
>>> class BinarySearchTree(MutableMapping): pass
>>> LinkedList()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: Can't instantiate abstract class LinkedList with abstract methods __getitem__, __len__
>>> BinarySearchTree()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: Can't instantiate abstract class BinarySearchTree with abstract methods __delitem__, __getitem__, __iter__, __len__, __setitem__
可迭代对象
迭代的概念
Python 中的 for 语句比较特殊，它是一种“遍历”类型的循环而不是计数循环，类似其它语言提供的 foreach 形式的循环，它的语法为：
for var in list:
...
for 循环从 list 中逐个取值，并赋值给循环变量 var 。
使用 for 循环获取一个对象所有元素的过程称为迭代(iteration)。迭代过程可以是隐式的，在没有直接使用 for 时也发生了对一系列成员的遍历，例如 list 类的构造函数：
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> list(d)
['a', 'b', 'c']
这就涉及到 Python 的可迭代对象与迭代器的概念，它们规定一个对象应该如何迭代、每次迭代返回什么结果，并在什么时候停止迭代。
可迭代对象
可以显式或隐式地应用 for 循环，遍历每个成员的对象称为可迭代对象，迭代器和生成器都是可迭代对象。生成器的讨论见函数式编程的相关章节，本节重点讨论迭代器。
可迭代对象的特点和生成器的特点是一样的，它们都通过提供过程而不是结果消除重复计算的开销，具体表现在以下方面：
- 可迭代对象通过惰性生成数据的方式，在一次循环内就可以同时生产值和使用值，因此可以节约时间
- 相对于一般的序列，可迭代对象仅在当前迭代时产生数据，一旦离开当前迭代，本次迭代产生的数据就被销毁，因此可以节约空间
在 Python 中，实现了 __iter__() 特殊方法的对象是可迭代对象。collections.abc 模块中定义了抽象基类 Iterable ，配合内置的 isinstance() 函数可以快速判断一个对象是否是可迭代对象。内置的序列对象都是可迭代对象，生成器函数和生成器表达式也都是可迭代对象：
>>> from collections.abc import Iterable
>>> isinstance(123, Iterable)
False
>>> isinstance('123', Iterable)
True
>>> def gen(): yield 1
>>> isinstance(gen, Iterable)
False
>>> isinstance(gen(), Iterable)
True
>>> class Gen:
... def __iter__(self): pass
>>> isinstance(Gen(), Iterable)
True
如果要想自己实现的类也是可迭代对象，需要在类内实现 __iter__() 特殊方法。该方法是一个实例方法，除了 self 不需要任何参数。该方法需要返回一个可以被 for 循环使用的对象，例如列表或生成器。由于树的遍历使用递归实现比较简单，因此这里采用递归形式的生成器实现迭代：
class BinarySearchTree:
def _inorder_traversal(self, node):
if node is not None:
yield from self._inorder_traversal(node.left)
yield node
yield from self._inorder_traversal(node.right)
def __iter__(self):
return self._inorder_traversal(self.root)
这样 BinarySearchTree 类就可以被 for 循环使用，从而实现迭代：
>>> from random import randint
>>> tree = BinarySearchTree()
>>> for _ in range(5):
... tree[randint(0, 100)] = f'item {randint(1, 1000)}'
>>> for node in tree:
... print(node)
5: item 646
51: item 867
64: item 199
95: item 795
98: item 405
虽然 BinarySearchTree 类已经是可迭代对象，但它还不是迭代器，因为它只是返回了一个生成器对象，这个类本身并没有给出每次产出值的具体步骤。接下来介绍迭代器的概念。
迭代器和迭代器协议
迭代器对象必须要实现两个方法：.__iter__() 和 .__next__() ，二者合称迭代器协议。collections.abc 模块中同样定义了抽象基类 Iterator 。可以用其判断一个实例是不是迭代器：
>>> from collections.abc import Iterator
>>> genexp = (i ** 2 for i in range(10) if i % 2)
>>> isinstance(genexp, Iterator)
True
通过 help() 函数检查 Iterator ，就可以知道迭代器的实现细节：
>>> help(collections.abc.Iterator)
...
| Methods defined here:
|
| __iter__(self)
|
| __next__(self)
| Return the next item from the iterator. When exhausted, raise StopIteration
...
特殊方法 .__next__() 是一个实例方法，在每次循环迭代时，该方法依次返回下一个项目值，类型生成器的 yield 语句。如果没有新项目，该函数应该抛出 StopIteration 异常，以作为迭代结束的依据。
如果一个对象实现了 .__next__() 方法，那么它就可以在 for 循环中产出值，这时它的 .__iter__() 可以简单地返回 self ，告诉 for 语句自身就支持迭代。
实现了迭代器协议的对象，既是可迭代对象，又是迭代器。以下实现了一个迭代器示例，使用迭代器来输出斐波那契数列的项：
class Fibonacci:
def __init__(self, max_value):
self._max = max_value
self._n, self._a = 0, 1
def __iter__(self):
return self
def __next__(self):
self._n, self._a = self._a, self._n + self._a
if self._n < self._max:
return self._n
else:
raise StopIteration
在理解了生成器的原理后，应该就很容易理解 .__next__() 方法的用途了。以下是一个使用示例：
>>> series = Fibonacci(200)
>>> for i in series:
... print(i, end=' ')
1 1 2 3 5 8 13 21 34 55 89 144
在该例中，.__iter__() 和 .__next__() 缺一不可，因为 .__iter__() 告诉 for 循环从哪个迭代器取值，并不是所有对象自身都是迭代器；而 .__next__() 是如何迭代的依据，迭代循环根据 .__next__() 来逐一获得每次迭代产生的值。
.__next__() 方法的 raise StopIteration 异常用作结束迭代的标志，它会使 for 循环停止迭代而不是抛出错误。可以认为 StopIteration 异常相当于执行了一个循环的 break 。
虽然以上示例的 .__iter__() 方法只是简单返回了自身，但是对于复杂一些的迭代器，.__iter__() 方法在迭代前可能还需要做一些必要的初始化工作，例如链表的迭代可以这样处理：
class LinkedList:
def __iter__(self):
self._iter_node = self.head
return self
def __next__(self):
if self._iter_node is None:
raise StopIteration
current = self._iter_node
self._iter_node = self._iter_node.next
return current
除此之外，有些容器对象可能还需要提供对逆序迭代的支持。如果一个类实现了 .__reversed__(self) 方法，那么它可以被内置函数 reversed() 调用，以实现逆序的迭代。因此，该方法应该返回一个新的迭代器，例如：
class LinkedList:
def __reversed__(self):
return self._reversed_iter()
def _reversed_iter(self):
current = self.tail
while current is not None:
yield current
current = current.prev
使用迭代器可以实现对象的迭代循环，迭代器让程序更加通用、高效。对于大量项目的迭代，使用迭代器可以避免列表等占用太多内存的问题。Python 内置了一些可迭代对象如 map 、filter，在标准库 itertools 中提供了各种迭代器，这些迭代器非常高效，且内存消耗也很少。
可迭代对象与迭代
可迭代对象最简单的迭代方法就是使用 for 循环遍历这个对象，它会自动处理 .__iter__() 和 .__next__() 。这里的 for 也可以是列表解析、生成器表达式等用到的 for 。
如果不使用 for 循环，也可以通过以下方式模拟迭代的过程：
series = Fibonacci(200)
iter_obj = series.__iter__()
while True:
try:
i = iter_obj.__next__()
print(i, end=' ')
except StopIteration:
break
但一般情况下，不要直接调用私有的特殊方法。Python 内置了两个函数 iter() 和 next() ，是迭代器协议相关的两个特殊方法的相关函数。前者用于获取实例代表的可迭代对象，后者用于手动迭代对象。
iter(object) 函数需要传入一个对象，其实质就是调用对象的 .__iter__() 方法，从而返回一个迭代器用于迭代：
>>> ls = [1, 2, 3]
>>> iter(ls)
<list_iterator object at 0x000002037B3E9A20>
>>> isinstance(ls, Iterator)
False
>>> iter(series) is series
True
可以看到列表本身并不是迭代器，不过它会被 iter() 调用而返回一个特殊的列表迭代器。而由于之前实现的 Fibonacci 类其 .__iter__() 方法返回的就算实例本身，因此其对应的可迭代对象就是本身，本身便作为迭代器使用。
该函数还可以传入第二个参数 sentinel ，这种情况下，object 必须是一个可调用对象（例如函数或方法，有关可调用对象的内容将在下节介绍），这时调用 iter() 会返回一个特殊的 callable iterator 对象，这个对象在每次迭代时，都会调用 object 一次，直到其返回值与 sentinel 相等时就停止迭代。
Python 官方文档演示了 sentinel 参数的一个用法，它将文件变成一个特别的二进制块迭代器，每次读取 64 字节，直到读到文件末尾（不再读出任何内容）为止：
from functools import partial
with open('mydata.db', 'rb') as f:
read_block = partial(f.read, 64)
for block in iter(read_block, b''):
process_block(block)
在有第二个参数时，自动调用 object 并不会传入任何参数，所以需要使用 partial 将其变成一个偏函数；并且 object 本身并不需要实现迭代器协议中的任意一个方法，相当于 iter() 为不断调用函数的行为创建了一个迭代器。
另一个内置函数 next(iterator) 需要传入一个迭代器，它等价于调用迭代器的 .__next__() 方法。next() 还可以传入第二个参数 default ，表示迭代器触发 StopIteration 时，返回的默认值。
在 Python 中，使用 open() 打开的文件对象是可迭代对象，每次迭代它都会从文件中读取一行，这样就可以避免文件过大在内存中无法存放的情况。如果只是想读取文件的第一行获取一些元信息，那么就可以使用 next() 函数：
with open('demo.csv', 'r') as f:
head = next(f)
fields = head[:-1].split(',')
参考资料/延伸阅读
https://docs.python.org/3/reference/datamodel.html#emulating-container-types
Python3 官方文档对容器类型的描述
https://docs.python.org/3/library/stdtypes.html#iterator-types
Python3 官方文档对迭代器类型的描述