查看原文
其他

当谈论迭代器时,我谈些什么?

樱雨楼 Python猫 2019-10-30

点击上方“Python猫”,选择“设为星标

花下猫语:之前说过,我对于编程语言跟其它学科的融合非常感兴趣,但我还说漏了一点,就是我对于 Python 跟其它编程语言的对比学习,也很感兴趣。所以,我一直希望能聚集一些有其它语言基础的同学,一起讨论共通的语言特性间的话题。不同语言的碰撞,常常能带给人更高维的视角,也能触及到语言的根基,这个过程是极有益的。

这篇文章是群内 樱雨楼 小姐姐的投稿,她是我们学习群里的真·大佬,说到对 Python 的研究以及高阶知识的水平,无人能出其右(群里很多同学都被她实力圈粉啦)。除了 Python,她对 C++、Perl、Go 与 Fortran 等语言都有涉猎,本文主要是对比了 Python 与 C++,来深入谈谈迭代器。话不多说,请看正文。

樱雨楼 | 原创作者

豌豆花下猫 | 编辑润色

0 前言

迭代器(Iterator)是 Python 以及其他各种编程语言中的一个非常常见且重要,但又充满着神秘感的概念。无论是 Python 的基础内置函数,还是各类高级话题,都处处可见迭代器的身影。

那么,迭代器究竟是怎样的一个概念?其又为什么会广泛存在于各种编程语言中?本文将基于 C++ 与 Python,深入讨论这一系列问题。

1 什么是迭代器?我们为什么要使用迭代器?

什么是迭代器?当我初学 Python 的时候,我将迭代器理解为一种能够放在“for xxx in …”的“…”位置的东西;后来随着学习的深入,我了解到迭代器就是一种实现了迭代器协议的对象;学习 C++ 时,我了解到迭代器是一种行为和指针类似的对象…

事实上,迭代器是一个伴随着迭代器模式(Iterator Pattern)而生的抽象概念,其目的是分离并统一不同的数据结构访问其中数据的方式,从而使得各种需要访问数据结构的函数,对于不同的数据结构可以保持相同的接口。

在很多讨论 Python 迭代器的书籍与文章中,我看到这样两种观点:1. 迭代器是为了节约数据结构所产生的内存;2. 遍历迭代器效率更高。

这两点论断都是很不准确的:首先,除了某些不定义在数据结构上的迭代器(如文件句柄,itertools 模块的 count、cycle 等无限迭代器等),其他迭代器都定义在某种数据结构上,所以不存在节约内存的优势;其次,由于迭代器是一种高度泛化的实现,其需要在每一次迭代器移动时都做一些额外工作(如 Python 需要不断检测迭代器是否耗尽,并进行异常监测;C++ 的 deque 容器需要对其在堆上用于存储的多段不连续内存进行衔接等),故遍历迭代器的效率一定低于或几乎接近于直接遍历容器,而不太可能高于直接遍历原容器。

综上所述,迭代器存在的意义,不是为了空间换时间,也不是为了时间换空间,而是一种适配器(Adapter)。迭代器的存在,使得我们可以使用同样的 for 语句去遍历各种容器,或是像 C++ 的 algorithm 模块所示的那样,使用同样的接口去处理各种容器。

这些容器可以是一个连续内存的数组或列表,或是一个多段连续内存的 deque,甚至是一个完全不连续内存的链表或是哈希表等等,我们完全不需要关注迭代器对于不同的容器究竟是怎么取得数据的。

2 C++中的迭代器

2.1 泛化指针

在 C++ 中,迭代器通过泛化指针(Generalized Pointer)的形式呈现。泛化指针与仿函数(Functor)的定义类似,其包含以下两种情况:

  1. 是一个真正的指针

  2. 不是指针,但重载了某些指针运算符(如“*,++,--,!=” 等),使得其行为和指针相似

根据泛化指针为了将其“伪装”成一个真正的指针从而重载的运算符的数量,迭代器被分为五种,如下文所示。

2.2 C++的迭代器分类

C++ 的迭代器按其所支持的行为被分为五类:

  1. 输入迭代器(Input Iterator):仅可作为右值(rvalue),不可作为左值(lvalue)。可以进行比较(“== 与 !=”)

  2. 输出迭代器(Output Iterator):仅可作为左值,不可作为右值

  3. 前向迭代器(Forward Iterator):支持一切输入迭代器的操作,以及单步前进操作(++)

  4. 双向迭代器(Bidirectional Iterator):支持一切前向迭代器的操作,以及单步后退操作(--)

  5. 随机访问迭代器(Random Access Iterator):支持一切双向迭代器操作,以及非单步双向移动操作

对于前向迭代器,双向迭代器,以及随机访问迭代器,如果其不存在底层 const(Low-Level Const)限定,则同时也支持一切输出迭代器操作。

2.3 迭代器适配器

C++ 中还存在一系列迭代器适配器,用于使得一些非迭代器对象的行为类似于迭代器,或修改迭代器的一些默认行为,大致包含如下几个类别:

  1. 插入迭代器(Insert Iterator):使得对迭代器左值的写入操作变为向容器中插入数据的操作,按插入位置的不同,可分为 front_insert_iterator,back_insert_iterator 和 insert_iterator

  2. 反向迭代器(Reverse Iterator):对调迭代器的移动方向。使得“+”操作变为向左移动,同时“-”操作变为向右移动(类似于 Python 的 reversed 函数)

  3. 移动迭代器(Move Iterator):使得对迭代器的取值变为右值引用(Rvalue Reference)

  4. 流迭代器(Stream Iterator):使流对象的行为适配迭代器(类似于 Python 的文件句柄)

3 Python中的迭代器

3.1 迭代器协议

在 Python 中,迭代器基于鸭子类型(Duck Type)下的迭代器协议(Iterator Protocol)实现。迭代器协议规定:如果一个类想要成为可迭代对象(Iterable Object),则其必须实现__iter__方法,且其返回值需要是一个实现了__next__方法的对象。

即:实现了__iter__方法的类将成为可迭代对象,而实现了__next__方法的类将成为迭代器。

显然,__iter__方法是 iter 函数所对应的魔法方法,__next__方法是 next 函数所对应的魔法方法。

对于一个可迭代对象,针对“谁实现了__next__方法?”这一问题进行讨论,可将可迭代对象的实现分为两种情况:

  1. self 未实现__next__:如果__iter__方法的返回值就是一个 Iterator,则此时 self 即为一个可迭代对象。此时,self 将迭代操作“委托”到了另一个数据结构上。示例代码如下:

class SampleIterator:
    def __iter__(self):
        return iter(...)
  1. self 实现了__next__:如果__iter__方法返回 self,则说明 self 本身将作为迭代器,此时 self 本身需要继续实现__next__方法,以实现完整的迭代器协议。示例代码如下:

class SampleIterator:
    def __iter__(self):
        return self

    def __next__(self):
        # Not The End
        if ...:
            return ...
        # Reach The End
        else:
            raise StopIteration

此例可以看出,当迭代器终止时,通过抛出 StopIteration 异常告知 Python 迭代器已耗尽。

3.2 生成器

生成器(Generator)是 Python 特有的一组特殊语法,其主要目的为提供一个基于函数而不是类的迭代器定义方式。同时,Python 也具有生成器推导式,其基于推导式语法快速建立迭代器。生成器一般适用于需要创建简单逻辑的迭代器的场合。

只要一个函数的定义中出现了 yield 关键词,则此函数将不再是一个函数,而成为一个“生成器构造函数”,调用此构造函数即可产生一个生成器对象。

由此可见,如果仅讨论该语法本身,而不关心实现的话:生成器只是“借用”了函数定义的语法,实际上与函数并无关系(并不代表生成器的底层实现也与函数无关)。示例代码如下:

def SampleGenerator():
    yield ...
    yield ...
    yield ...

生成器推导式则更为简单,只需要将列表推导式的中括号换为小括号即可:

(... for ... in ...)

综上所述,生成器是 Python 独有的一类迭代器的特殊构造方式。生成器一旦被构造,其会自动实现完整的迭代器协议。

3.3 无限迭代器

itertools 模块中实现了三个特殊的无限迭代器(Infinite Iterator):count,cycle 以及 repeat,其有别于普通的表示范围的迭代器。如果对无限迭代器进行迭代将导致无限循环,故无限迭代器通常只可使用 next 函数进行取值。

关于无限迭代器的详细内容,可参阅 Python 文档。(注:我在 Python进阶:设计模式之迭代器模式 写过)

3.4 与C++迭代器的比较

经过上文的讨论可以发现,Python 只有一种迭代器,此种迭代器只能进行单向,单步前进操作,且不可作为左值。故 Python 的迭代器在 C++ 中应属于单向只读迭代器,这是一种很低级的迭代器。

此外,由于迭代器只支持单向移动,故一旦向前移动便不可回头,如果遍历一个已耗尽迭代器,则 for 循环将直接退出,且无任何错误产生,此种行为往往会产生一些难以察觉的 bug,实际使用时请务必注意。

综上所述,Python 对于迭代器的实现其实是高度匮乏的,应谨慎使用。

4 迭代器有效性

4.1 什么是迭代器有效性?

由于迭代器本身并不是独立的数据结构,而是指向其他数据结构中的值的泛化指针,故和普通指针一样,一旦指针指向的内存发生变动,则迭代器也将随之失效。

如果迭代器指向的数据结构是只读的,则显然,直到析构函数被调用,迭代器都不会失效。但如果迭代器所指向的数据结构在其存在时发生了插入或删除操作,则迭代器将可能失效。故讨论某个操作是否会导致指向容器的迭代器失效,是一个很重要的话题。

4.2 C++的迭代器有效性

由于 Python 中没有 C++ 的 list、deque 等数据结构实现,故本文只简单地讨论 vector 与 unordered_map 这两种数据结构的迭代器有效性。

对于 vector,由于其存在内存扩容与转移操作,故任何会潜在导致内存扩容的方法都将损坏迭代器,包括 push_back、emplace_back、insert、emplace 等。

unordered_map 与 vector 的情形类似,对 unordered_map 进行任何插入操作也将损坏迭代器。

4.3 Python的迭代器有效性

注:本节所讨论全部内容均基于实际行为进行猜想和推论,并没有经过对 Python 源代码的考察和验证,仅供读者参考。

4.3.1 尾插入操作不会损坏指向当前元素的List迭代器

考察如下代码:

numList = [123]
numListIter = iter(numList)
next(numListIter)

for i in range(1000000):
    numList.append(i)

# print 2
print(next(numListIter))

如果在 C++ 中对一个 vector 执行这么多次的 push_back,则指向第二个元素的迭代器一定早已失效。但在 Python 中可以看到,指向 List 的迭代器并未失效,其仍然返回了 2。

故可猜想:Python 对于 List 所产生的迭代器并不跟踪指向 List 元素的指针,而仅仅跟踪的是容器的索引值。

4.3.2 尾插入操作会损坏List尾迭代器

numList = [1,2]
numListIter = iter(numList)

# 1
next(numList)
numList.append(3)

# 2 
next(numListIter)

# 3
print(next(numListIter))

首先,Python 不存在尾迭代器这一概念。但由上述代码可知,当迭代器所指向的 List 变长后,迭代器的终止点也随之变化,即:原先的尾迭代器将不再适用。

按照“迭代器仅跟踪元素索引值”这一推断,也能解释这一行为。

4.3.3 迭代器一旦耗尽,则将永久损坏

考察如下代码:

numList = [1,2]
numListIter = iter(numList)
for _ in numListIter:
    pass

numList.append(3)

# StopIteration
print(next(numListIter))

当 for 一个迭代器后,迭代器将耗尽,在 C++ 中,这将导致头尾迭代器相等,但由上述代码可知, Python 的迭代器一旦耗尽,便不再可以使用,即使继续往容器中增加元素也不行。

由此可见, Python 的迭代器中可能存在某种用于指示迭代器是否被耗尽的标记,一旦迭代器被标记为耗尽状态,便永远不可继续使用了。

4.3.4 任何插入操作都将损坏Dict迭代器

考察如下代码:

numDict = {1:2}
numDictIter = iter(numDict)
numDict[3] = 4

# RuntimeError
next(numDictIter)

当对一个 Dict 进行插入操作后,原 Dict 迭代器将立即失效,并抛出 RuntimeError。这与 C++ 中的行为是一致的,且更为安全。

Set 与 Dict 具有相同的迭代器失效性质,不再重复讨论。

5 后记

迭代器的故事到这里就结束了。总的看来,Python 中的迭代器虽应用广泛,但并不是一种高级的,灵活的实现,且存在着一些黑魔法。故唯有深入的去理解,才能真正的用好迭代器。祝编程愉快~

(花下猫注:鉴于有同学看完本文,可能想要加群交流,我补充两句。我们群虽然是免费群,但一直想走高质量的技术交流路线,因此既限制人数,也严审核。公众号菜单栏有我联系方式,感兴趣的同学欢迎查看了解。

看看历史文章,一起学 Python

1

聊聊 print 的前世今生

2

聊聊 Python 的内置电池

3

聊聊技术写作的个人体会

4

如何给列表降维?sum()函数的妙用

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存