Python 迭代器和 C++ 迭代器，最大的不同竟然是......

作者 | 樱雨楼
责编 | 胡巍巍

[h1]前言[/h1]
迭代器（Iterator）是 Python 以及其他各种编程语言中的一个非常常见且重要，但又充满着神秘感的概念。无论是 Python 的基础内置函数，还是各类高级话题，都处处可见迭代器的身影。
那么，迭代器究竟是怎样的一个概念？其又为什么会广泛存在于各种编程语言中？本文将基于 C++ 与 Python，深入讨论这一系列问题。

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

什么是迭代器？当我初学 Python 的时候，我将迭代器理解为一种能够放在“for xxx in …”的“…”位置的东西；后来随着学习的深入，我了解到迭代器就是一种实现了迭代器协议的对象；学习 C++ 时，我了解到迭代器是一种行为和指针类似的对象…
事实上，迭代器是一个伴随着迭代器模式（Iterator Pattern）而生的抽象概念，其目的是分离并统一不同的数据结构访问其中数据的方式，从而使得各种需要访问数据结构的函数，对于不同的数据结构可以保持相同的接口。
在很多讨论 Python 迭代器的书籍与文章中，我看到这样两种观点：1. 迭代器是为了节约数据结构所产生的内存；2. 遍历迭代器效率更高。
这两点论断都是很不准确的：首先，除了某些不定义在数据结构上的迭代器（如文件句柄，itertools 模块的 count、cycle 等无限迭代器等），其他迭代器都定义在某种数据结构上，所以不存在节约内存的优势；其次，由于迭代器是一种高度泛化的实现，其需要在每一次迭代器移动时都做一些额外工作（如 Python 需要不断检测迭代器是否耗尽，并进行异常监测；C++ 的 deque 容器需要对其在堆上用于存储的多段不连续内存进行衔接等），故遍历迭代器的效率一定低于或几乎接近于直接遍历容器，而不太可能高于直接遍历原容器。
综上所述，迭代器存在的意义，不是为了空间换时间，也不是为了时间换空间，而是一种适配器（Adapter）。迭代器的存在，使得我们可以使用同样的 for 语句去遍历各种容器，或是像 C++ 的 algorithm 模块所示的那样，使用同样的接口去处理各种容器。
这些容器可以是一个连续内存的数组或列表，或是一个多段连续内存的 deque，甚至是一个完全不连续内存的链表或是哈希表等等，我们完全不需要关注迭代器对于不同的容器究竟是怎么取得数据的。

[h1]C++中的迭代器[/h1]
[h2]3.1 泛化指针[/h2]在 C++ 中，迭代器通过泛化指针（Generalized Pointer）的形式呈现。泛化指针与仿函数（Functor）的定义类似，其包含以下两种情况：

是一个真正的指针
不是指针，但重载了某些指针运算符（如“*，++，--，!=” 等），使得其行为和指针相似

根据泛化指针为了将其“伪装”成一个真正的指针从而重载的运算符的数量，迭代器被分为五种，如下文所示。
[h2]3.2 C++的迭代器分类[/h2]C++ 的迭代器按其所支持的行为被分为五类：

输入迭代器（Input Iterator）：仅可作为右值（rvalue），不可作为左值（lvalue）。可以进行比较（“== 与 !=”）
输出迭代器（Output Iterator）：仅可作为左值，不可作为右值
前向迭代器（Forward Iterator）：支持一切输入迭代器的操作，以及单步前进操作（++）
双向迭代器（Bidirectional Iterator）：支持一切前向迭代器的操作，以及单步后退操作（--）
随机访问迭代器（Random Access Iterator）：支持一切双向迭代器操作，以及非单步双向移动操作

对于前向迭代器，双向迭代器，以及随机访问迭代器，如果其不存在底层 const（Low-Level Const）限定，则同时也支持一切输出迭代器操作。
[h2]3.3 迭代器适配器[/h2]C++ 中还存在一系列迭代器适配器，用于使得一些非迭代器对象的行为类似于迭代器，或修改迭代器的一些默认行为，大致包含如下几个类别：

插入迭代器（Insert Iterator）：使得对迭代器左值的写入操作变为向容器中插入数据的操作，按插入位置的不同，可分为 front_insert_iterator，back_insert_iterator 和 insert_iterator
反向迭代器（Reverse Iterator）：对调迭代器的移动方向。使得“+”操作变为向左移动，同时“-”操作变为向右移动（类似于 Python 的 reversed 函数）
移动迭代器（Move Iterator）：使得对迭代器的取值变为右值引用（Rvalue Reference）
流迭代器（Stream Iterator）：使流对象的行为适配迭代器（类似于 Python 的文件句柄）

[h1] Python中的迭代器[/h1]
[h2]4.1 迭代器协议[/h2]在 Python 中，迭代器基于鸭子类型（Duck Type）下的迭代器协议（Iterator Protocol）实现。迭代器协议规定：如果一个类想要成为可迭代对象（Iterable Object），则其必须实现__iter__方法，且其返回值需要是一个实现了__next__方法的对象。
即：实现了__iter__方法的类将成为可迭代对象，而实现了__next__方法的类将成为迭代器。
显然，__iter__方法是 iter 函数所对应的魔法方法，__next__方法是 next 函数所对应的魔法方法。
对于一个可迭代对象，针对“谁实现了__next__方法？”这一问题进行讨论，可将可迭代对象的实现分为两种情况：

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

class SampleIterator: def __iter__(self): return iter(...)

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 迭代器已耗尽。
[h2]4.2 生成器[/h2]生成器（Generator）是 Python 特有的一组特殊语法，其主要目的为提供一个基于函数而不是类的迭代器定义方式。同时，Python 也具有生成器推导式，其基于推导式语法快速建立迭代器。生成器一般适用于需要创建简单逻辑的迭代器的场合。
只要一个函数的定义中出现了 yield 关键词，则此函数将不再是一个函数，而成为一个“生成器构造函数”，调用此构造函数即可产生一个生成器对象。
由此可见，如果仅讨论该语法本身，而不关心实现的话：生成器只是“借用”了函数定义的语法，实际上与函数并无关系（并不代表生成器的底层实现也与函数无关）。示例代码如下：
def SampleGenerator(): yield ... yield ... yield ...
生成器推导式则更为简单，只需要将列表推导式的中括号换为小括号即可：
(... for ... in ...)
综上所述，生成器是 Python 独有的一类迭代器的特殊构造方式。生成器一旦被构造，其会自动实现完整的迭代器协议。
[h2]4.3 无限迭代器[/h2]itertools 模块中实现了三个特殊的无限迭代器（Infinite Iterator）：count，cycle 以及 repeat，其有别于普通的表示范围的迭代器。如果对无限迭代器进行迭代将导致无限循环，故无限迭代器通常只可使用 next 函数进行取值。
4.4 与C++迭代器的比较
[h2][/h2]经过上文的讨论可以发现，Python 只有一种迭代器，此种迭代器只能进行单向，单步前进操作，且不可作为左值。故 Python 的迭代器在 C++ 中应属于单向只读迭代器，这是一种很低级的迭代器。
此外，由于迭代器只支持单向移动，故一旦向前移动便不可回头，如果遍历一个已耗尽迭代器，则 for 循环将直接退出，且无任何错误产生，此种行为往往会产生一些难以察觉的 bug，实际使用时请务必注意。
综上所述，Python 对于迭代器的实现其实是高度匮乏的，应谨慎使用。

[h1]迭代器有效性[/h1]
[h2]5.1 什么是迭代器有效性？[/h2]由于迭代器本身并不是独立的数据结构，而是指向其他数据结构中的值的泛化指针，故和普通指针一样，一旦指针指向的内存发生变动，则迭代器也将随之失效。
如果迭代器指向的数据结构是只读的，则显然，直到析构函数被调用，迭代器都不会失效。但如果迭代器所指向的数据结构在其存在时发生了插入或删除操作，则迭代器将可能失效。故讨论某个操作是否会导致指向容器的迭代器失效，是一个很重要的话题。
[h2]5.2 C++的迭代器有效性[/h2]由于 Python 中没有 C++ 的 list、deque 等数据结构实现，故本文只简单地讨论 vector 与 unordered_map 这两种数据结构的迭代器有效性。
对于 vector，由于其存在内存扩容与转移操作，故任何会潜在导致内存扩容的方法都将损坏迭代器，包括 push_back、emplace_back、insert、emplace 等。
unordered_map 与 vector 的情形类似，对 unordered_map 进行任何插入操作也将损坏迭代器。
[h2]5.3 Python的迭代器有效性[/h2]注：本节所讨论全部内容均基于实际行为进行猜想和推论，并没有经过对 Python 源代码的考察和验证，仅供读者参考。
[h3]5.3.1 尾插入操作不会损坏指向当前元素的List迭代器[/h3]考察如下代码：
numList = [1, 2, 3]numListIter = iter(numList)next(numListIter)for i in range(1000000): numList.append(i)# print 2print(next(numListIter))
如果在 C++ 中对一个 vector 执行这么多次的 push_back，则指向第二个元素的迭代器一定早已失效。但在 Python 中可以看到，指向 List 的迭代器并未失效，其仍然返回了 2。
故可猜想：Python 对于 List 所产生的迭代器并不跟踪指向 List 元素的指针，而仅仅跟踪的是容器的索引值。
[h3]5.3.2 尾插入操作会损坏List尾迭代器[/h3]numList = [1,2]numListIter = iter(numList)# 1next(numList)numList.append(3)# 2 next(numListIter)# 3print(next(numListIter))
首先，Python 不存在尾迭代器这一概念。但由上述代码可知，当迭代器所指向的 List 变长后，迭代器的终止点也随之变化，即：原先的尾迭代器将不再适用。
按照“迭代器仅跟踪元素索引值”这一推断，也能解释这一行为。
[h3]5.3.3 迭代器一旦耗尽，则将永久损坏[/h3]考察如下代码：
numList = [1,2]numListIter = iter(numList)for _ in numListIter: passnumList.append(3)# StopIterationprint(next(numListIter))
当 for 一个迭代器后，迭代器将耗尽，在 C++ 中，这将导致头尾迭代器相等，但由上述代码可知， Python 的迭代器一旦耗尽，便不再可以使用，即使继续往容器中增加元素也不行。
由此可见， Python 的迭代器中可能存在某种用于指示迭代器是否被耗尽的标记，一旦迭代器被标记为耗尽状态，便永远不可继续使用了。
[h3]5.3.4 任何插入操作都将损坏Dict迭代器[/h3]考察如下代码：
numDict = {1:2}numDictIter = iter(numDict)numDict[3] = 4# RuntimeErrornext(numDictIter)
当对一个 Dict 进行插入操作后，原 Dict 迭代器将立即失效，并抛出 RuntimeError。这与 C++ 中的行为是一致的，且更为安全。
Set 与 Dict 具有相同的迭代器失效性质，不再重复讨论。

[h1]后记[/h1]
迭代器的故事到这里就结束了。总的看来，Python 中的迭代器虽应用广泛，但并不是一种高级的，灵活的实现，且存在着一些黑魔法。故唯有深入的去理解，才能真正的用好迭代器。祝编程愉快~
作者：豌豆花下猫，某985高校毕业生，兼具极客思维与人文情怀。公众号Python猫，专注Python技术、数据科学和深度学习，力图创造一个有趣又有用的学习分享平台。
声明：本文为作者投稿，版权归作者所有。
【End】
下面给大家推荐 CSDN 的好朋友——程序人生。
为什么推荐程序人生？
程序人生聚集百万程序员，在这里你可以笑谈开发轶事，吐槽百味的程序人生。
无论是从行业热点到经验解析，从职场困惑到风口趋势，还有程序员不为人知的秘密，我们将为你一一揭晓。
长按下方二维码关注程序人生，可了解更多程序员的开发趣事、热点资讯：

龙泉寺的IT高僧是用哪种编程语言呢？Java ? Python？这篇10W+文章告诉你↓↓↓

程序员下班时，为啥电脑不关只揣了手机就走啦？？这篇9W+文章过于真相了↓↓↓

调查上万名程序员，竟然发现女程序员比男程序员更懂 Java？怎么回事啊？？↓↓↓

点击阅读原文，输入关键词，即可搜索您想要的 CSDN 文章。
你点的每个“在看”，我都认真当成了喜欢