Как добиться удаления O (1) из списка std :: list
Вопрос в том, что является рекомендуемым способом использования 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, каков будет лучший способ сделать это? Я предлагаю соломенное предложение о встраивании итератора. Есть ли лучшие подходы?
Если требуется конкретный вариант использования, рассмотрите реализацию таймера. Когда таймер создан, он помещается в соответствующий список. Если он отменен, желательно эффективно его удалить. (Этот конкретный пример может быть решен с помощью маркировки вместо удаления, но это является допустимым способом осуществления отмены.) Дополнительные варианты использования доступны по запросу.
Еще одна альтернатива, которую я исследовал, заключалась в std::list с std::unordered_map создать специализированный список типов указателей. Это более тяжелый (из-за хеш-таблицы), но предоставляет контейнер, который довольно близок к стандартным контейнерам на уровне интерфейса, и дает мне O (1) стирание элементов списка. Единственная особенность, отсутствующая в предложении соломенного человека, — это указатель на список, который в настоящее время содержит элемент. Я поднял текущую реализацию в Просмотр Кода запросить комментарий.
Решение
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где узлы списка непосредственно встроены в структуры, как вы уже сделали.
ты можешь использовать повышение :: навязчивым или сверните свое, также проверьте этот
Вот «полное» решение с использованием встроенного 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();
}
Так как элемент во многих отношениях является собственным итератором, find() метод не должен быть необходим в этой версии List, Но вместо этого это contains() метод, который используется, чтобы увидеть, является ли элемент членом списка.
Теперь представленное решение использует std::map связать экземпляры списка с итераторами. Это поддерживает дух O (1), если число списков, в которые одновременно входит элемент, относительно мало.
Я попробую свои силы в boost::intrusive версия следующая.
Ужасная правда: хотя связанный список является мощной структурой, std::list не может полностью использовать свои возможности.
Вы не можете стереть объект с std::list используя только итераторы, потому что list должен освободить узел, и вы должны знать, где находится распределитель, который выделил память (подсказка: он находится в списке).
У навязчивых контейнеров есть много преимуществ по сравнению со стандартным связанным списком, например, самосознание ;-), возможность хранить полиморфные объекты по значению, и они делают возможным приемы со списком (например, наличие отдельных объектов в нескольких списках). Так как вы не используете std::list в любом случае, вы можете отказаться от использования std::list В общем и используйте сторонний контейнер, или сверните свой.
(Кроме того, ваше решение также навязчиво, так как ваш тип должен быть получен из List<T>::Item, который устанавливает определенные требования к типу, который std::list не делает)
Не может быть сделано В списке используются прямые и / или обратные указатели, указывающие на «смежные» элементы списка. Следовательно, вам нужно будет повторять каждый раз, когда вы что-то делаете.
Если вы хотите O (1) для какой-либо коллекции, заставьте ваш контент работать с массивом.
Тем не менее, для сканирования, хотя список из менее чем 100 элементов занимает незаметный период времени, если вы не делаете это тысячу раз в секунду.
Редактировать:
Если вы знаете, какой узел вы хотите удалить, это легко. Я не уверен, как именно работает список STD, но в теоретическом смысле узел должен быть в состоянии удалить себя, установив 1 или 2 указателя вперед и назад соседних узлов так, чтобы они указывали друг на друга.