如何从std :: list中实现O(1)擦除

Question

问题是std::list用于实现O(1)清除列表项的推荐方法是什么？

通常,当我选择双向链表时,我希望能够在O(1)时间内从列表中删除元素,然后在O(1)时间内将其移动到不同的列表中.如果元素有自己的prev和next指针,那么完成工作就没有真正的诀窍.如果列表是双向链接循环列表,则删除不一定需要知道包含该项目的列表.

根据迭代器失效规则,std::list迭代器非常耐用.因此,std::list在我自己的项目上使用时,我似乎得到了我想要的行为,就是在我的类中隐藏一个迭代器,以及包含列表.

class Item {
    typedef std::shared_ptr<Item> Ptr;
    struct Ref {
        std::list<Ptr>::iterator iter_;
        std::list<Ptr> *list_;
    };
    Ref ref_;
    //...
};

这有一个缺点,我需要创建自己的装饰版本std::list,知道ref_每当项目添加到列表时更新.我想不出一种不需要嵌入式迭代器的方法,因为没有一种方法意味着擦除会首先引发O(n)查找操作.

使用O(1)擦除的推荐方法是什么std::list？或者,是否有更好的方法来实现目标？

---

在过去,我通过实现自己的列表数据结构来实现这一点,其中放置在列表中的项目具有其自己的next和prev指针.管理这些指针很自然,因为它们是列表操作本身固有的(我的列表实现的API调整指针).如果我想使用STL,那么最好的方法是什么？我提出了嵌入迭代器的稻草人提议.有更好的方法吗？

如果需要具体的用例,请考虑使用计时器.创建计时器时,会将其放入适当的列表中.如果取消,则希望有效地将其除去.(此特定示例可以通过标记而不是删除来解决,但它是实现取消的有效方法.)可根据请求提供其他用例.

---

我探索的另一个选择是将a std::list与a 融合std::unordered_map以创建指针类型的专用列表.这是更重量级的(因为哈希表),但提供了一个非常接近接口级标准容器的容器,并给我O(1)删除列表元素.稻草人提案中缺少的唯一特征是指向当前包含该项目的列表的指针.我已在CodeReview上提出当前的实现以征求意见.

Answer 1

无法从 std::list 中进行 O(1) 擦除。

您可能需要考虑使用 an intrusive list，其中列表节点直接嵌入到结构中，就像您已经完成的那样。

你可以使用boost::intrusive或自己推出，也可以看看这个