Python中可常数时间追踪删除元素的集合及std::list::iterator替代方案

针对你需要的「能常数时间删除任意元素、无需有序/索引、支持后续枚举」的需求，以下是几种实用方案，覆盖不同场景：

方案1：直接使用内置set（优先选择，元素可哈希且唯一） #

如果你的元素是可哈希类型（如整数、字符串、元组）且不需要存储重复值，Python内置的set完全满足需求：

• set.add(item)：平均O(1)时间添加元素
• set.remove(item)：平均O(1)时间删除指定元素
• 枚举元素直接通过for item in my_set:完成，遍历复杂度O(n)

这是最轻量化的方案，基于Python底层C实现，性能最优，无需额外代码。

方案2：使用第三方库llist（模拟C++ std::list，支持重复/不可哈希元素） #

如果需要支持重复元素、不可哈希元素，或者需要类似C迭代器的「元素句柄」来直接删除，llist是最佳选择——这是一个基于C扩展的双向链表库，API和C std::list高度一致，核心操作均为O(1)时间。

示例代码：

from llist import dllist, dllistnode

# 创建双向链表
my_list = dllist()
# 添加元素并保存对应节点（等价于C++的迭代器）
node_a = my_list.append("apple")
node_b = my_list.append("banana")
node_c = my_list.append("cherry")

# 通过节点直接删除元素，O(1)时间
my_list.remove(node_b)

# 枚举所有剩余元素
for fruit in my_list:
    print(fruit)  # 输出 apple、cherry

方案3：自定义哈希+交换删除（元素唯一可哈希，无依赖） #

如果不想引入第三方库，且元素唯一可哈希，可以自己实现基于动态数组和字典的集合，通过「交换到末尾再删除」的技巧实现O(1)删除：

class FastUniqueCollection:
    def __init__(self):
        self._items = []
        self._item_map = {}
    
    def add(self, item):
        if item not in self._item_map:
            self._item_map[item] = len(self._items)
            self._items.append(item)
    
    def remove(self, item):
        idx = self._item_map.pop(item)
        # 若不是最后一个元素，和末尾元素交换
        if idx != len(self._items) - 1:
            last_item = self._items[-1]
            self._items[idx] = last_item
            self._item_map[last_item] = idx
        self._items.pop()
    
    def __iter__(self):
        return iter(self._items)
    
    def __contains__(self, item):
        return item in self._item_map

该实现所有核心操作均为平均O(1)时间，基于Python内置容器，性能接近标准库。

方案4：自定义双向链表（支持重复/不可哈希元素，纯Python） #

如果元素不可哈希或需要重复存储，且无法使用第三方库，可以手动实现双向链表，搭配字典记录元素对应的节点：

class ListNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class FastCollection:
    def __init__(self):
        # 哨兵节点简化边界处理
        self.head = ListNode(None)
        self.tail = ListNode(None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self._value_nodes = {}
    
    def add(self, value):
        node = ListNode(value)
        # 插入到链表尾部
        prev_node = self.tail.prev
        prev_node.next = node
        node.prev = prev_node
        node.next = self.tail
        self.tail.prev = node
        # 记录节点映射
        if value not in self._value_nodes:
            self._value_nodes[value] = []
        self._value_nodes[value].append(node)
    
    def remove(self, value):
        nodes = self._value_nodes.get(value, [])
        if not nodes:
            raise ValueError(f"{value} not in collection")
        # 弹出最后一个节点删除（列表末尾操作O(1)）
        node = nodes.pop()
        if not nodes:
            del self._value_nodes[value]
        # 从链表移除节点
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def __iter__(self):
        current = self.head.next
        while current != self.tail:
            yield current.value
            current = current.next

注意：纯Python实现的链表性能会比C扩展库差，适合数据量不大的场景。

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