迭代器(选修)

迭代器

迭代是Python最强大的功能之一，是访问集合元素的一种方式。

迭代器是一个可以记住遍历的位置的对象。

迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束。迭代器只能往前不会后退。

迭代器有两个基本的方法：iter() 和 next()。

字符串，列表或元组对象都可用于创建迭代器：

list=[1,2,3,4]
it = iter(list)    # 创建迭代器对象

next(it) # 输出迭代器的下一个元素

next(it) # 再输出下一个元素

enumerate

列表好处是不需要对下标进行迭代，直接输出列表的值：

x = [2, 4, 6]

for i in x:
    print(i)

但是有些情况下，我们既希望获得下标， 也希望获得对应的值，那么：

可以将迭代器传给 enumerate 函数， 这样每次迭代都会返回一组 (index, value) 组成的元组：

x = [2, 4, 6]
for i, n in enumerate(x):
    print(i, 'is', n)

自定义迭代器

一个迭代器都有 __iter__() 与 __next__()

__iter__() 方法返回一个特殊的迭代器对象， 这个迭代器对象实现了 __next__() 方法并通过 StopIteration 异常标识迭代的完成。

__next__() 方法（Python 2 里是 next()）会返回下一个迭代器对象。

自定义一个 list 的取反迭代器：

class ReverseListIterator(object):
    def __init__(self, lst):
        self.list = lst
        self.index = len(lst)

    def __iter__(self):
        return self

    def __next__(self):
        self.index -= 1
        if self.index >= 0:
            return self.list[self.index]
        else:
            raise StopIteration

x = range(10)
for i in ReverseListIterator(x):
    print(i)

只要我们定义了这三个方法(__init__, __iter__, __next__)，我们可以返回任意迭代值：

实现Collatz 猜想

这里我们实现 Collatz 猜想：

• 奇数 n：返回 3n + 1
• 偶数 n：返回 n / 2
• 直到 n 为 1 为止：

class Collatz(object):
    def __init__(self, start):
        self.value = start

    def __iter__(self):
        return self

    def __next__(self):
        if self.value == 1:
            raise StopIteration
        elif self.value % 2 == 0:
            self.value = self.value / 2
        else:
            self.value = 3 * self.value + 1
        return self.value


for x in Collatz(5):
    print(x)

不过迭代器对象存在状态，有问题：

i = Collatz(5)
# zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的迭代器。
for x, y in zip(i, i):
    print(x, y)

# 下方代码等价于上方代码
i = Collatz(5)
# *zipped 可理解为解压，返回二维矩阵式
zipped = zip(i, i)
#<zip object at 0x00000200CFC1F400> #返回的是一个对象
x, y = zip(*zipped)
print(x, y)

解决方法是将迭代器和可迭代对象分开处理。

迭代器和可迭代对象分开处理

这里提供了一个二分树的中序遍历实现：

class BinaryTree(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __iter__(self):
        return InorderIterator(self)

class InorderIterator(object):
    def __init__(self, node):
        self.node = node
        self.stack = []

    def __next__(self):
        if len(self.stack) > 0 or self.node is not None:
            while self.node is not None:
                self.stack.append(self.node)
                self.node = self.node.left
            node = self.stack.pop()
            self.node = node.right
            return node.value
        else:
            raise StopIteration()

测试：

tree = BinaryTree(
    left=BinaryTree(
        left=BinaryTree(1),
        value=2,
        right=BinaryTree(
            left=BinaryTree(3),
            value=4,
            right=BinaryTree(5)
        ),
    ),
    value=6,
    right=BinaryTree(
        value=7,
        right=BinaryTree(8)
    )
)

for value in tree:
    print(value)

不会出现之前的问题：

for x, y in zip(tree, tree):
    print(x, y)