Как добиться стирания O(1) из std::list

std::list::erase гарантированно будет O(1).

Существует не так много других способов стереть элементы из стандартного списка. (std::list::remove и друзья не делают одно и то же, поэтому не учитываются).

Если вы хотите удалить из стандартного списка, вам нужен итератор и сам список. Это то, что у вас, кажется, уже есть. Существует не очень много свободы делать это по-другому. Я бы сохранил включение списка отдельно от объектов, в отличие от того, что вы сделали, потому что зачем создавать объект, который может быть только в одном списке за раз? Мне кажется ненужным искусственным ограничением. Но что бы ни приводило в действие ваш дизайн.

Может быть, вы могли бы изменить свой интерфейс, чтобы выдавать итераторы вместо необработанных объектов? В случае вашего примера таймеров:

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

По общему признанию, это немного громоздко, но альтернативы тоже.

Невозможно стереть O(1) из std::list.

вы можете рассмотреть возможность использования intrusive list, где узлы списка непосредственно встроены в структуры, как вы уже сделали.

вы можете использовать ускорение: :intrusive или создайте свой собственный, также ознакомьтесь с это

Вот «полное» решение с использованием встроенного файла 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, но базовым типом значения будет std::shared_ptr. Что мне нужно, так это позволить экземпляру T эффективно получить свой собственный iterator, чтобы добиться стирания O (1). Это делается с помощью Ref для запоминания итератора элемента после его вставки в список.

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_*() и pop_*() также запоминают 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. Отличие заключается в том, что операторы * и -> определены таким образом, что итератор ведет себя так, как будто он T *, а не 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();
}

Поскольку элемент во многих отношениях является своим собственным итератором, в этой версии List метод find() не нужен. Но вместо этого есть метод contains(), который используется для проверки того, является ли элемент членом списка.

Теперь представленное решение использует std::map для связывания экземпляров списка с итераторами. Это поддерживает дух O(1), если количество списков, членом которых одновременно является элемент, относительно невелико.

В следующий раз я попробую свои силы в версии boost::intrusive.

Ужасная правда: хотя связанный список является мощной структурой, std::list не может полностью использовать его возможности.

Вы не можете стереть объект из std::list, используя только итераторы, потому что список должен освободить узел, и вы должны знать, где находится распределитель, который выделил память (подсказка: он находится в списке).

Навязчивые контейнеры имеют много преимуществ по сравнению со стандартным связанным списком, например самосознание ;-), способность хранить полиморфные объекты по значению и они делают возможными трюки со списками (например, наличие отдельных объектов в нескольких списках). Поскольку вы все равно не используете std::list напрямую, вы можете вообще отказаться от использования std::list и использовать сторонний контейнер или создать свой собственный.

(Кроме того, ваше решение также навязчиво, поскольку ваш тип должен быть получен из List<T>::Item, что налагает определенные требования на тип, которого нет в std::list)