如何从std :: list中实现O（1）擦除 [英] How to achieve O(1) erasure from a std::list

问题描述

问题是使用 std :: list 以实现O（1）清除列表项的推荐方法是什么？

The question is what is the recommended way to use std::list to achieve O(1) erasure of list items?

通常，当我选择一个双向链表时，我想要能够在O（1）时间内从列表中删除一个元素，然后在O（1）的时间内将它移动到不同的列表。如果元素有自己的 prev 和下一个指针，没有真正的窍门，完成工作。如果列表是双重链接的循环列表，则删除不一定需要知道包含该项目的列表。

Usually, when I choose a doubly linked list, I want to be able to remove an element from a list in O(1) time, and then move it to a different list in O(1) time. If the element has its own prev and next pointers, there is no real trick to getting the job done. If the list is a doubly linked circular list, then removal doesn't necessarily require knowing the list that contains the item.

根据迭代器无效规则， std :: list 迭代器非常耐用。所以，在我自己的项目上使用 std :: list 时，我希望得到我想要的行为是在我的类和包含列表中隐藏一个迭代器。 / p>

As per Iterator invalidation rules, std::list iterators are very durable. So, it seems to me to get the behavior I desire when using std::list on my own item is to stash an iterator within my class, and the containing 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）查找操作。

This has the downside that I will need to create my own decorated version of std::list that knows to update the ref_ whenever the item is added to a list. I can't think of a way that doesn't require the embedded iterator, since not having one would mean erasure would incur a O(n) find operation first.

使用 std :: list 来擦除O（1）的建议方法是什么？

What is the recommended way to get O(1) erasure with std::list? Or, is there a better approach to achieving the objective?

在过去，我已经实现了这个目标，列表数据结构，其中放置在列表中的项目具有其自己的next和prev指针。管理这些指针是很自然的，因为它们是列表操作本身固有的（我的列表实现的API调整指针）。如果我想使用STL代替，什么是最好的方法来完成这个？我提供了嵌入迭代器的草人建议。有更好的方法吗？

In the past, I have accomplished this by implementing my own list data structure, where the item placed in the list has its own next and prev pointers. Managing these pointers is natural, since they are inherent to the list operations themselves (the API to my list implementation adjusts the pointers). If I want to use the STL instead, what would be the best way to accomplish this? I offer the straw-man proposal of embedding the iterator. Are there better approaches?

如果需要一个具体的用例，考虑一个定时器实现。创建计时器时，将其放置到适当的列表中。如果它被取消，则期望有效地去除它。 （此特定示例可以通过标记而不是删除来解决，但它是实现取消的有效方式。）可以根据请求提供其他用例。

If a concrete use-case is desired, consider a timer implementation. When a timer is created, it is placed into an appropriate list. If it is canceled, it is desirable to efficiently remove it. (This particular example can be solved via marking instead of removal, but it is a valid way to implement cancellation.) Additional use-cases are available upon request.

我探索的另一个选择是将 std :: list 与 std :: unordered_map 为指针类型创建一个专门的列表。这是更重的（因为哈希表），但提供了一个非常接近标准容器在接口级别的容器，并给我O（1）列表元素擦除。草稿人提案缺少的唯一功能是指向当前包含该项目的列表的指针。我已在 CodeReview 提出当前实施以征求意见。

Another alternative I explored was to fuse a std::list with a std::unordered_map to create a specialized list for pointer types. This is more heavyweight (because of the hash table), but provides a container that is pretty close to the standard containers at the interface level, and gives me O(1) erasure of list elements. The only feature missing from the straw-man proposal is a pointer to the list which currently contains the item. I have put up the current implementation at CodeReview to solicit comment.

推荐答案

也许你可以重新设计你的接口来提出迭代器而不是原始对象？在计时器示例的情况下：

Maybe you could redesign your interface to hand out iterators instead of raw objects? In the case of your timers example:

class Timer {
  // ...
};

typedef std::list<Timer>::iterator TimerRef;

class Timers {

  public:

    TimerRef createTimer(long time);
    void cancelTimer(TimerRef ref);

  private:

    std::list<Timer> timers;
};

当然，而不是

timer.cancel();

该类的用户现在必须说

timers.cancelTimer(timerRef);

但根据您的使用情况，这可能不是问题。

but depending on your use case, that might not be a problem.

更新：在列表之间移动计时器：

Update: moving timers between lists:

class Timers {

  public:

    Timer removeTimer(TimerRef ref);
    void addTimer(Timer const &timer);

    // ...

};

用法：

timers2.addTimer(timers1.removeTimer(timerRef));

不可否认，这有点麻烦，但也是如此。

Admittedly it's a bit cumbersome, but so are the alternatives.

这篇关于如何从std :: list中实现O（1）擦除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！