花猫语：之前说过，我对编程语言与其他学科的融合很感兴趣，但是我也漏掉了一点，就是我对比较研究也很感兴趣Python和其他编程语言。因此，我一直希望聚集一些有其他语言基础的同学，共同探讨语言特点之间的话题。不同语言的碰撞往往能给人带来更高维的视角，也能触及语言的根基。这个过程非常有益。本文由群内樱玉楼小姐姐投稿。她是我们学习小组的真正老大。说到对Python的研究和进阶知识的水平，没有人能比得上她（群里很多同学都是她的实力粉）。除了Python，她还涉猎过C++、Perl、Go和Fortran等语言。本文主要通过Python和C++的对比，深入浅谈迭代器。话不多说，请看正文。樱玉楼|原作者猫下豌豆花|编辑润色原文地址：https://mp.weixin.qq.com/s/Be...0前言迭代器（Iterator）是Python和其他各种编程语言中一个非常常见和重要，但又充满神秘色彩的概念的。无论是Python的基础内置函数，还是各种进阶话题，迭代器随处可见。那么，迭代器是一个什么样的概念呢？为什么它广泛存在于各种编程语言中？本文将基于C++和Python深入探讨这一系列问题。1什么是迭代器？我们为什么要使用迭代器？什么是迭代器？刚学Python的时候，我把迭代器理解为一个可以放在“forxxxin...”的“...”位置的东西；后来，随着了解的深入，我了解到迭代器是一个实现了迭代器协议的对象；在学习C++的时候，我了解到迭代器是一个对象，它的行为类似于指针……实际上，迭代器是一个伴随迭代器模式而来的抽象概念，其目的是分离和统一不同数据结构访问对象的方式数据，使得需要访问数据结构的各种功能可以为不同的数据结构维护相同的接口。在许多讨论Python迭代器的书籍和文章中，我看到了两种观点：1.迭代器用于保存数据结构产生的内存；2.遍历迭代器更高效。这两个结论是很不准确的：第一，除了一些迭代器没有定义在数据结构上（比如文件句柄，itertools模块的count和cycle等无限迭代器等），其他的迭代器都定义在一些中就数据结构而言，没有节省内存的优势；其次，由于迭代器是一个高度泛化的实现，每次迭代器移动时都需要做一些额外的工作（例如Python需要不断检查迭代器是否消耗Exhaustion，异常监控；C++deque容器需要连接多个segmentofdiscontinuousmemoryusedforstorageontheheap等），所以遍历迭代器的效率肯定低于或几乎接近于直接遍历容器，而不可能比直接遍历原始容器高。总结一下，迭代器存在的意义不是用空间换时间，也不是用时间换空间，而是一种适配器（Adapter）。迭代器的存在使得我们可以使用相同的for语句来遍历各种容器，或者像C++的算法模块那样使用相同的接口来处理各种容器。这些容器可以是连续内存的数组或列表，也可以是多段连续内存的双端队列，甚至是完全不连续内存的链表或哈希表等。我们不需要关注迭代器是什么针对不同的容器。如何获取数据。2C++中的迭代器2.1广义指针在C++中，迭代器以广义指针的形式出现。广义指针类似于函子的定义，包括以下两种情况：是一个真正的指针但不是指针，而是一些指针运算符（如“*、++、--、!=”等）为了使它表现得像一个指针，迭代器根据重载运算符的数量分为五种类型，这些重载运算符泛化了一个指针，以便将其“伪装”为真正的指针，如下所示。2.2C++迭代器分类在C++中，迭代器是根据支持的行为分为五类：InputIterator：只能作为右值使用，不能作为左值使用。可以比较（"==and!="）输出迭代器（OutputIterator）：只能作为左值，不能作为右值前向迭代器（ForwardIterator）：支持输入迭代器的所有操作，以及单步前向操作(++)双向迭代器（BidirectionalIterator）：支持所有前向迭代器操作，以及单步向后操作(--)随机访问迭代器（RandomAccessIterator）：支持所有双向迭代器操作，以及非单步二步-waymoveoperations对于正向迭代器、双向迭代器和随机访问迭代器，如果没有底层const（Low-LevelConst）限制，也支持所有的输出迭代器操作。2.3迭代器适配器C++中也有一系列的迭代器适配器，用于使一些非迭代器对象表现得像迭代器，或者修改迭代器的一些默认行为，大致包括以下几类：插入迭代器（InsertIterator）：将迭代器左值的写入操作变成了向容器中插入数据的操作。根据插入位置不同，可分为front_insert_iterator、back_insert_iterator和insert_iterator反向迭代器（ReverseIterator）：反转迭代器的移动方向。使“+”操作向左移动，“-”操作变为向右移动（类似于Python的逆向函数）MoveIterator：使迭代器的值成为右值引用（RvalueReference）StreamIterator（Stream迭代器：使流对象的行为适应迭代器（类似于Python文件句柄）3Python中的迭代器3.1迭代器协议在Python中，迭代器是基于迭代器协议（IteratorProtocol）下的鸭子类型（DuckType）实现的。迭代器协议规定，如果一个类要成为可迭代对象（IterableObject），则必须实现__iter__方法，其返回值必须是实现了__next__方法的对象。即：实现了__iter__方法的类将成为可迭代对象，实现了__next__方法的类将成为迭代器。显然，__iter__方法是iter函数对应的magic方法，__next__方法是next函数对应的magic方法。对于可迭代对象，讨论“谁实现了__next__方法？”的问题。可迭代对象的实现分为两种情况：self没有实现__next__：如果__iter__方法的返回值是一个Iterator，那么此时self就是一个可迭代对象。此时，self将迭代操作“委托”给另一个数据结构。示例代码如下：classSampleIterator:def__iter__(self):returniter(...)selfimplements__next__:如果__iter__方法返回self，说明self本身会被用作迭代器，self本身需要继续实现__next__方法来实现完整的迭代器协议。示例代码如下：classSampleIterator:def__iter__(self):returnselfdef__next__(self):#NotTheEndif...:return...#ReachTheEndelse:raiseStopIteration从中可以看出这个例子，当迭代器终止时，通过抛出StopIteration异常通知Python迭代器已耗尽。3.2生成器生成器（Generator）是Python独有的一套特殊语法，其主要目的是提供一种基于函数而非类的迭代器定义方法。同时，Python还有一个生成器理解，可以根据理解语法快速构建迭代器。当您需要创建具有简单逻辑的迭代器时，生成器通常适用。只要yield关键字出现在函数的定义中，该函数就不再是函数，而是“生成器构造函数”。调用这个构造函数可以生成一个生成器对象。可以看出，如果只讨论语法本身，而不关心实现：生成器只是“借用”了函数定义的语法，实际上与函数无关（并不意味着底层生成器的实现与函数无关）。示例代码如下：defSampleGenerator():yield...yield...yield...generatorcomprehension更简单，只需将listcomprehension的方括号改为圆括号即可：(...for...in...)综上所述，生成器就是Python特有的一种迭代器的特殊构造方法。一旦构建了生成器，它就会自动实现完整的迭代器协议。3.3无限迭代器itertools模块实现了三种特殊的无限迭代器（InfiniteIterator）：count、cycle和repeat，它们有别于普通的代表范围的迭代器。如果对无限迭代器进行迭代，会造成无限循环，所以无限迭代器通常只能使用next函数取值。有关无限迭代器的详细信息，请参阅Python文档。（注：旧文章PythonAdvanced:TheIteratorPatternofDesignPatterns也有介绍）3.4与C++迭代器的比较经过上面的讨论可以发现Python只有一种迭代器，这种迭代器只能执行一种——way，单步向前操作，不能用作左值。所以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.3Python的迭代器有效性注：本节讨论的所有内容都是基于实际行为的猜想和推论，并没有经过Python源码的检验和验证。仅供读者参考。4.3.1尾部插入操作不会破坏指向当前元素的List迭代器。考虑以下代码：numList=[1,2,3]numListIter=iter(numList)next(numListIter)foriinrange(1000000):numList.append(i)#print2print(next(numListIter))如果push_back是在C++中对一个向量执行了这么多次，指向第二个元素的迭代器一定已经过期了。但是在Python中可以看到，指向List的迭代器并没有失效，它仍然返回2。因此，可以猜测Python为List生成的迭代器不会跟踪指向List元素的指针，而只会跟踪索引容器的价值。4.3.2尾部插入操作会破坏List尾部迭代器numList=[1,2]numListIter=iter(numList)#1next(numList)numList.append(3)#2next(numListIter)#3print(next(numListIter))First,Python没有尾迭代器的概念。但是从上面的代码可以看出，当迭代器指向的List变长的时候，迭代器的终止点也随之发生变化，即原来的尾迭代器将不再适用。这种行为也可以通过迭代器只跟踪元素索引值的推论来解释。4.3.3迭代器一旦耗尽，将永久损坏。考虑以下代码：numList=[1,2]numListIter=iter(numList)for_innumListIter:passnumList.append(3)#StopIterationprint(next(numListIter))when完成一个迭代器后，迭代器将被耗尽。在C++中，这会导致头尾迭代器相等，但是从上面的代码来看，一旦Python迭代器用完，就不能再使用了，即使继续向容器中添加元素也没有用.可以看出，在Python的迭代器中可能有某种标记来表示迭代器是否已经耗尽。一旦迭代器被标记为耗尽，它就再也不能使用了。4.3.4任何插入操作都会损坏Dict迭代器。考虑以下代码：numDict={1:2}numDictIter=iter(numDict)numDict[3]=4#RuntimeErrornext(numDictIter)插入一个Dict后，原始Dict迭代器将立即失效并抛出一个RuntimeError。这与C++中的行为一致并且更安全。Set和Dict具有相同的迭代器失效属性，因此我们不再重复讨论。5后记迭代器的故事到此结束。总的来说，Python中的迭代器虽然被广泛使用，但并不是一个高级灵活的实现，并且存在一些黑魔法。因此，只有深入了解，才能真正用好迭代器。祝大家编程愉快~（花猫注：鉴于部分同学可能看完这篇文章后想加入群交流，补充两句。虽然我们群是免费群，但总想走高质量技术交流路线，所以限制人数，审核严格。公众号菜单栏有我的联系方式，有兴趣的同学可以看看。）公众号【蟒猫】，本号连载优质系列文章，包括喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐与翻译等，欢迎关注。
