Python中哪些类deque容器在结构变更时可保留有效迭代器？

Python 标准库没有原生提供和 C++ std::deque 行为完全一致、修改头尾元素时原有迭代器仍然有效的数据结构。 #

原因说明 #

标准库自带的 collections.deque 迭代器采用快照逻辑实现，只要迭代过程中 deque 的长度发生变化（无论是头部弹出还是尾部追加），所有已创建的迭代器都会立即失效，抛出 RuntimeError: deque mutated during iteration，和你了解的特性一致。 #

符合需求的实现方案 #

你可以基于标准库现有能力快速实现符合要求的结构，两种方案都能满足均摊O(1)的append/popleft要求，同时保证迭代器有效：

推荐实现：带引用计数的单链表 #

逻辑简单直接，完全贴合你的场景，性能最优：

• 每个链表节点存储元素值、下一个节点的引用，以及已被消费的次数
• 队列本身仅持有头节点、尾节点指针，以及总消费者迭代器数量（因为你限定了所有__iter__调用都发生在__next__之前，可以提前拿到这个数值）
• append 操作直接在尾节点后追加新节点，更新尾指针即可，O(1)
• 每个迭代器仅持有当前指向的节点引用，调用__next__时将当前节点的消费计数+1，再返回节点值、把迭代器指针移到下一个节点
• 每次消费后检查头节点的消费计数是否等于总消费者数，相等就执行popleft：把原头节点废弃，头指针移到下一个节点即可，O(1)
  这种实现下迭代器持有节点的直接引用，无论队列头部弹出多少旧元素、尾部追加多少新元素，迭代器的访问都不会失效。

替代封装方案（仅适合小数据量场景） #

如果不想自己实现链表逻辑，也可以基于collections.deque加偏移量封装，但是要注意内部deque的随机访问时间复杂度为O(n)，对性能敏感的场景不推荐：

• 队列内部维护一个base_offset变量，记录已经被popleft的元素总数量，用deque存储还未被所有消费者消费的元素
• 每个迭代器仅维护自己的current_offset变量，记录下一个要读取的元素全局偏移量
• append 操作直接往内部deque尾部追加元素，O(1)
• 迭代器调用__next__时，计算deque_index = current_offset - base_offset，直接取内部deque对应索引的元素返回，再把current_offset加1即可
• 每次消费后检查所有迭代器的最小current_offset，如果大于base_offset，就执行popleft弹出内部deque的头部元素，base_offset加1，O(1)
  因为迭代器没有直接迭代内部的deque实例，所以deque的长度变化不会导致迭代器失效，只要你保证不会让迭代器读取已经被弹出的元素（你的场景里所有元素被所有迭代器消费后才会弹出，天然满足这个要求），逻辑完全安全。

内容的提问来源于stack exchange，提问作者OneRaynyDay