迭代器

迭代是什么

迭代指的是一个重复的过程，每次重复都必须基于上一次的结果而继续，单纯的重复并不是迭代，如Python中的for循环就是一个非常好的迭代例子。

for item in range(10):
    print(item)

迭代必须向前推进，不能后退，如下所示：

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# ------------------------------>

下面这种方式就不属于迭代：

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# -------->
#     <----
#          --------------------->

迭代器协议

在学习迭代器的整个知识点中，迭代器协议占据了非常重要的位置。

迭代器协议中包含了2个最基本的概念，分别是可迭代对象和迭代器对象。

• 可迭代对象（Iterable）：内部实现了__iter__()方法的对象则被称为可迭代对象
• 迭代器对象（Iterator）：内部实现了__next__()方法的对象则被称之为迭代器对象

两者之间的关系：

• 在Python中，迭代器对象一定属于可迭代对象范畴，也就说迭代器对象必须具有__iter__()方法以及__next__()方法
• 在Python中，可迭代对象不一定属于迭代器对象范畴，也就是说可迭代对象只需要实现__iter__()方法即可

介绍2个函数：

• iter(Object)函数，它底层会执行Object.__iter__()方法
• next(Object)函数，它底层会执行Object.__next__()方法

内置类型

通过collections.abc下的Iterable类和Iterator类进行判定，可快速的判定出所有内置类型是否是一个可迭代对象或者迭代器对象：

>>> from collections.abc import Iterable
>>> from collections.abc import Iterator

>>> isinstance(list(), Iterable)
True
>>> isinstance(list(), Iterator)
False

经过测试，所有的容器类型（list、tuple、str、dict、set、frozenset）均属于可迭代对象，但不属于迭代器对象

原子类型（bool、int、float、None）等均不属于可迭代对象，更不属于迭代器对象。

也可以通过另一种方式进行验证，通过hasattr()函数，检查类中是否定义了某一个方法：

>>> hasattr(list,"__iter__")
True
>>> hasattr(list,"__next__")
False

迭代原理

当可迭代对象被for循环进行调用后，底层执行流程如下所示：

1. 将自动的执行iter()方法，该方法内部会查找可迭代对象的__iter__()方法，如果具有该方法，则返回一个该可迭代对象的专属迭代器对象，如果没有该方法，则抛出TypeError object is not iterable的异常。

   Ps：每次的for循环都会返回一个全新的迭代器对象

2. 不断的调用迭代器对象的__next__()方法，并且返回迭代器对象中下一个数据项，当遍历完成整个迭代器后，引发Stopiteration异常终止迭代

   Ps：迭代器本身并不存储任何数据项，存储的只是一个指针，该指针指向可迭代对象中真正存储的数据项，它指向当前被遍历到的数据项索引位置，下一次遍历则向后推进这个位置

3. for循环自动的捕捉Stopiteration异常，并且停止迭代

   Ps:for循环底层就是while循环实现的，只不过多加了3个步骤：

   第一步：执行可迭代对象的__iter()__方法并保存返回的专属迭代器

   第二步：不断的执行迭代器的__next()__方法

   第三步：捕获Stopiteration异常

我们手动的实现一个for循环：

li1 = list(range(10))

iteratorObject = iter(li1)  # ❶
while 1:
    try:
        print(next(iteratorObject))  # ❷
    except StopIteration as e:  # ❸
        break

❶：执行可迭代对象的__iter__()方法并保存返回的专属迭代器

❷：不断的执行迭代器的__next__()方法

❸：捕获Stopiteration异常

线性可迭代对象与迭代器的实现

如果是一个线性容器的可迭代对象，那么它一定具有索引值，我们可以让它的__iter__()方法返回一个专属的迭代器对象。

然后专属迭代器对象中记录本次迭代遍历的索引值，根据这个索引值返回可迭代对象中的数据项，当索引值达到可迭代对象中数据项总个数-1的时候，抛出异常，本次迭代结束：

class LinearTypeContainer:
    def __init__(self, array):
        if isinstance(array, list) or isinstance(array, tuple):
            self.array = array
        else:
            raise TypeError("argument array must is linear container")

    def __iter__(self):
        return LinearContainer_iterator(self.array)  # ❶


class LinearContainer_iterator:
    def __init__(self, array):
        self.index = 0
        self.array = array
        self.len = len(self.array)

    def __next__(self):
        if self.index < self.len:
            retDataItem = self.array[self.index]
            self.index += 1
            return retDataItem
        else:
            raise StopIteration

    def __iter__(self):  # ❷
        return self


container = LinearTypeContainer([i for i in range(10)])


for i in container:
    print(i)
print(list(container))

❶：Python中的一切传参均为引用传递

故LinearTypeContainer中的self.array和LinearContainer_iterator的self.array都是一个对象，并不会额外开辟内存空间

这也就是为什么可迭代对象创建的专属迭代器不会消耗太多的内存空间原因了。

❷：迭代器对象一定属于可迭代对象范畴，所以在这里我们为迭代器对象LinearContainer_iterator类也新增了__iter__()方法

这样做的好处在于如果单独的拎出了这个迭代器对象，则它也会支持for循环的遍历：

    def __iter__(self):
        return self


containerIterator = LinearTypeContainer([i for i in range(10)]).__iter__()


for item in containerIterator:
    print(item)
    
# 0
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# 9

如果取消了linearContainer_iterator类的这个__iter__()方法，则不支持for循环的遍历：

    # def __iter__(self):
    #     return self


containerIterator = LinearTypeContainer([i for i in range(10)]).__iter__()


for item in containerIterator:
    print(item)
    
# TypeError: 'LinearContainer_iterator' object is not iterable

非线性可迭代对象与迭代器实现

如果是一个非线性容器的可迭代对象，可以先判断它的类型，如果传入的容器是一个字典，则将迭代的数据项集合转换为元组，里面存储的全部是字典的key即可。

如果传入的容器是一个集合，则将迭代的数据项集合转换为元组，再参照线性可迭代对象与迭代器的实现。

具体实现：

class MappingTypeContainer:
    def __init__(self, mapping):
        self.mapping = mapping
        if not (
            isinstance(self.mapping, dict) or
            isinstance(self.mapping, set) or
            isinstance(self.mapping, frozenset)
        ):
            raise TypeError("argument mapping must is mapping container")

    def __getattr__(self, name: str):
        try:
            return dict.__getattribute__(self.mapping, name)
        except AttributeError:
            return set.__getattribute__(self.mapping, name)

    def __str__(self):
        return str(self.mapping)

    def __iter__(self):
        return MappingContainer_iterator(tuple(self.mapping))


class MappingContainer_iterator:
    def __init__(self, array):
        self.index = 0
        self.array = array
        self.len = len(self.array)

    def __next__(self):
        if self.index < self.len:
            retDataItem = self.array[self.index]
            self.index += 1
            return retDataItem
        else:
            raise StopIteration

    def __iter__(self):
        return self


container = MappingTypeContainer(
    {str("k") + str(i): str("v") + str(i) for i in range(3)}
)

for item in container.items():
    print(item)

print(container)

# ('k0', 'v0')
# ('k1', 'v1')
# ('k2', 'v2')
# {'k0': 'v0', 'k1': 'v1', 'k2': 'v2'}


container = MappingTypeContainer({i for i in range(3)})

for item in container:
    print(item)

print(container)

# 0
# 1
# 2
# {0, 1, 2}

迭代器对象的特性

每一次for循环创建出的可迭代对象的专属迭代器都是一次性的，用完后就没用了：

...

# ❶
containerIterator = LinearTypeContainer([i for i in range(3)]).__iter__()

for item in containerIterator:
    print(item)

# 0
# 1
# 2

for item in containerIterator:
    print(item)  # ❷
    print("?")

❶：直接拿出一个迭代器对象

❷：在第2次循环中，迭代器对象中存储的索引值已经最大了，每次调用iter()都会抛出异常返回出来再被for处理，所以print()函数根本不会运行

迭代器对象并不存储可迭代对象中的真正迭代数据，而是仅存储长度和索引，所以内存的占用并不多：

class LinearContainer_iterator:
    def __init__(self, array):
        self.index = 0  # ❶
        self.array = array  # ❷
        self.len = len(self.array) # ❸
        
    ...

❶：占用额外的内存空间

❷：引用对象，并不开辟内存

❸：占用额外的内存空间

惰性求值与及早求值

迭代器对象中对于返回的数据项，是进行实时演算的，这种实时演算的特性求值方式被称为惰性求值，即你需要的时候我算出来后再给你：

    def __next__(self):
        if self.index < self.len:
            retDataItem = self.array[self.index]
            self.index += 1
            return retDataItem
        else:
            raise StopIteration

除开惰性求值，还有一种及早求值的方案，即使你要1个，我也把所有的都给你。

如Python2中的range()、map()、filter()、dict.items()、dict.keys()、dict.values()，它们均返回的是一个纯粹的列表，这样的设计是不合理的，参见要命的问题③。

因为返回的列表会占用很大的内存空间，而Python3中则统一优化为惰性求值方案，即返回一个可迭代对象。

要命的问题

一个非常有趣的问题：

• Python中的所有自带容器类型为何不自己设置成迭代器？

  而是在for循环时实例出一个专属的迭代器？

  直接在这些自带类型的底层实现__next__()方法不好吗？

  这样岂不是更加减少了内存的消耗，少定义了类和实例化了类吗？

答：这真是一个要命的问题，这个问题我也想过很久，最后是在stackoverflow提问并且获得了满意的答案才记录下来的。

因为它确实是可以实现的，如下所示，只需要在加上❶处代码即可：

class LinearTypeContainer:
    def __init__(self, array):
        if isinstance(array, list) or isinstance(array, tuple):
            self.array = array
        else:
            raise TypeError("argument array must is Linear container")

        self.index = 0
        self.len = len(self.array)

    def __iter__(self):
        return self

    def __next__(self):
        if self.index < self.len:
            retDataItem = self.array[self.index]
            self.index += 1
            return retDataItem
        else:
            self.index = 0  # ❶
            raise StopIteration

container = LinearTypeContainer(list(range(5)))

for item in container:
    print(item)

for item in container:
    print(item)

for item in container:
    print(item)

但是这样做在某种特殊情况下会出现问题：

container = LinearTypeContainer(list(range(5)))

for item in container:
    print(item)
    if container.index == 3:
        break

print("*"*20)

for item in container: 
    print(item)

# 0
# 1
# 2
# ********************
# 3
# 4

你会发现如果第一次for循环到了1半的时候退出，第二次for循环会接着根据第一次for循环进行继续。

能够解决一下吗？只需要加上一个标志位即可：

class LinearTypeContainer:
    def __init__(self, array):
        if isinstance(array, list) or isinstance(array, tuple):
            self.array = array
        else:
            raise TypeError("argument array must is Linear container")

        self.index = 0
        self.len = len(self.array)
        self.iter = False # ❶

    def __iter__(self):
        if self.iter: # ❷
            self.index = 0
        self.iter = True
        return self

    def __next__(self):
        if self.index < self.len:
            retDataItem = self.array[self.index]
            self.index += 1
            return retDataItem
        else:
            self.index = 0
            raise StopIteration


container = LinearTypeContainer(list(range(5)))

for item in container:
    print(item)
    if container.index == 3:
        break

print("*" * 20)

for item in container:
    print(item)

# 0
# 1
# 2
# ********************
# 0
# 1
# 2
# 3
# 4

❶：判断是不是一次新的调用

❷：如果是新的调用，则将index重新置为0即可

那么为何Python不这样设计呢？我们应该更多的考虑多线程的情况下，多个for循环使用同一个迭代器它是否是线程安全的，上面的示例中这个共享迭代器并不是线程安全的，此外它也不支持嵌套循环，如下所示，这样会造成无限循环：

container = LinearTypeContainer(list(range(5)))

for item in container:
    print(item)
    for j in container:
        print(j)

综上各个方面的考虑，Python将内置的数据类型，都设置了在for循环时返回专属迭代器的做法，这是非常好的设计，但是对于有些内置的对象，则是将它本身做成了迭代器，如文件对象。