6

问题是推荐的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，那么最好的方法是什么？我提供了嵌入迭代器的稻草人建议。有更好的方法吗？

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

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

4

5 回答 5

3

std::list::erase保证为 O(1)。

没有太多其他方法可以从标准列表中删除元素。（std::list::remove和朋友不做完全相同的事情，所以他们不算数）。

如果要从标准列表中删除，则需要一个迭代器和列表本身。这就是你似乎已经拥有的。做不同的事情并没有太多的自由。与您所做的不同，我会将列表包含与对象分开，因为为什么要制作一个一次只能在一个列表中的对象？对我来说似乎是一种不必要的人为限制。但是，无论您的设计如何提供动力。

于 2013-04-18T03:36:42.167 回答
2

也许你可以重新设计你的界面来分发迭代器而不是原始对象？对于您的计时器示例：

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);

但根据您的用例，这可能不是问题。

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

class Timers {

  public:

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

    // ...

};

用法：

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

诚然，这有点麻烦，但替代方案也是如此。

于 2013-04-21T08:48:07.890 回答
1

没有办法从 std::list 中擦除 O(1)。

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

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

于 2013-04-18T00:35:24.700 回答
1

这是使用嵌入式iterator. 一些私有特征用于帮助减少类中的混乱：

template <typename T> class List;

template <typename T>
class ListTraits {
protected:
    typedef std::list<std::shared_ptr<T>> Impl;
    typedef typename Impl::iterator Iterator;
    typedef typename Impl::const_iterator ConstIterator;
    typedef typename Impl::reverse_iterator Rotareti;
    typedef typename Impl::const_reverse_iterator ConstRotareti;
    typedef std::map<const List<T> *, typename Impl::iterator> Ref;
};

如图所示，列表实现将使用std::list，但基础值类型将是 a std::shared_ptr。我所追求的是允许一个实例T有效地导出它自己的iterator，以实现 O(1) 擦除。这是通过Ref在将项目插入列表后使用 a 来记忆项目的迭代器来完成的。

template <typename T>
class List : public ListTraits<T> {
    template <typename ITER> class IteratorT;
    typedef ListTraits<T> Traits;
    typename Traits::Impl impl_;
public:
    typedef typename Traits::Impl::size_type size_type;
    typedef typename Traits::Impl::value_type pointer;
    typedef pointer value_type;
    typedef IteratorT<typename Traits::Iterator> iterator;
    typedef IteratorT<typename Traits::ConstIterator> const_iterator;
    typedef IteratorT<typename Traits::Rotareti> reverse_iterator;
    typedef IteratorT<typename Traits::ConstRotareti> const_reverse_iterator;
    class Item;
    ~List () { while (!empty()) pop_front(); }
    size_type size () const { return impl_.size(); }
    bool empty () const { return impl_.empty(); }
    iterator begin () { return impl_.begin(); }
    iterator end () { return impl_.end(); }
    const_iterator begin () const { return impl_.begin(); }
    const_iterator end () const { return impl_.end(); }
    reverse_iterator rbegin () { return impl_.rbegin(); }
    reverse_iterator rend () { return impl_.rend(); }
    const_reverse_iterator rbegin () const { return impl_.rbegin(); }
    const_reverse_iterator rend () const { return impl_.rend(); }
    pointer front () const { return !empty() ? impl_.front() : pointer(); }
    pointer back () const { return !empty() ? impl_.back() : pointer(); }
    void push_front (const pointer &e);
    void pop_front ();
    void push_back (const pointer &e);
    void pop_back ();
    void erase (const pointer &e);
    bool contains (const pointer &e) const;
};

这List主要遵循类似队列的界面。但是，可以从列表中的任何位置删除项目。简单的函数大多只是委托给底层的std::list. 但是push_*()andpop_*()方法也记住了iterator.

template <typename T>
template <typename ITER>
class List<T>::IteratorT : public ITER {
    friend class List<T>;
    ITER iter_;
    IteratorT (ITER i) : iter_(i) {}
public:
    IteratorT () : iter_() {}
    IteratorT & operator ++ () { ++iter_; return *this; }
    IteratorT & operator -- () { --iter_; return *this; }
    IteratorT operator ++ (int) { return iter_++; }
    IteratorT operator -- (int) { return iter_--; }
    bool operator == (const IteratorT &x) const { return iter_ == x.iter_; }
    bool operator != (const IteratorT &x) const { return iter_ != x.iter_; }
    T & operator * () const { return **iter_; }
    pointer operator -> () const { return *iter_; }
};

这是用于定义迭代器类型的帮助模板的实现List。它的不同之处在于*and->运算符的定义方式使迭代器表现得像 aT *而不是 a std::shared_ptr<T> *（这是底层迭代器通常会做的）。

template <typename T>
class List<T>::Item {
    friend class List<T>;
    mutable typename Traits::Ref ref_;
};

T可以将派生自的类型List<T>::Item添加到List<T>. 此基类包含Ref用于在将项目添加到列表时记忆迭代器的实例。

template <typename T>
inline void List<T>::push_front (const pointer &e) {
    const Item &item = *e;
    typename Traits::Ref::iterator i = item.ref_.find(this);
    if (i == item.ref_.end()) {
        item.ref_[this] = impl_.insert(impl_.begin(), e);
    } else if (front() != e) {
        impl_.erase(i->second);
        i->second = impl_.insert(impl_.begin(), e);
    }
}

template <typename T>
inline void List<T>::pop_front () {
    if (!empty()) {
        const Item &item = *front();
        item.ref_.erase(this);
        impl_.pop_front();
    }
}

此代码说明了如何执行记忆。执行时push_front()，首先检查项目以查看它是否已包含。如果不是，则将其插入，并将生成的迭代器添加到ref_对象中。否则，如果它还不是最前面，则删除该项目并重新插入最前面，并更新记忆的迭代器。pop_front()删除记忆的迭代器，然后调用pop_front().std::list

template <typename T>
inline void List<T>::push_back (const pointer &e) {
    const Item &item = *e;
    typename Traits::Ref::iterator i = item.ref_.find(this);
    if (i == item.ref_.end()) {
        item.ref_[this] = impl_.insert(impl_.end(), e);
    } else if (back() != e) {
        impl_.erase(i->second);
        i->second = impl_.insert(impl_.end(), e);
    }
}

template <typename T>
inline void List<T>::pop_back () {
    if (!empty()) {
        const Item &item = *back();
        item.ref_.erase(this);
        impl_.pop_back();
    }
}

push_back()和pop_back()类似于push_front()和pop_front()。

template <typename T>
inline void List<T>::erase (const pointer &e) {
    const Item &item = *e;
    typename Traits::Ref::iterator i = item.ref_.find(this);
    if (i != item.ref_.end()) {
        item.ref_.erase(i);
        impl_.erase(i->second);
    }
}

该erase()例程检索记忆的迭代器，并使用它来执行擦除。

template <typename T>
inline bool List<T>::contains (const pointer &e) const {
    const Item &item = *e;
    typename Traits::Ref::iterator i = item.ref_.find(this);
    return i != item.ref_.end();
}

由于项目在许多方面都是它自己的迭代器，find()因此在这个版本的List. 但是，取而代之的是这个contains()方法，它用于查看元素是否是列表的成员。

现在，提出的解决方案使用 astd::map将列表实例与迭代器相关联。如果一个项目同时属于的列表数量相对较少，这将保持 O(1) 的精神。

我将尝试boost::intrusive下一个版本。

于 2013-04-21T08:22:55.027 回答
0

可怕的事实：虽然链表是强大的结构，但std::list不能充分利用它的功能。

您不能std::list仅使用迭代器来擦除对象，因为 list 必须释放节点，并且您必须知道分配内存的分配器在哪里（提示：它在列表中）。

与标准链表相比，侵入式容器具有许多优点，例如自我意识；-)、按值存储多态对象的能力以及它们使列表技巧（例如在多个列表中具有单个对象）可行。由于您不std::list直接使用，您可以完全放弃使用std::list并使用第三方容器，或者滚动您自己的容器。

（此外，您的解决方案也是侵入性的，因为您的类型必须派生自List<T>::Item，这对没有的类型提出了某些要求std::list）

于 2013-04-21T14:12:00.177 回答