Come ottenere la cancellazione O (1) da una lista std ::

Question

La domanda è qual è il modo consigliato di utilizzare std::list per ottenere la cancellazione O (1) delle voci dell'elenco?

Di solito, quando scelgo una lista doppiamente collegata, voglio essere in grado di rimuovere un elemento da una lista in O (1) volta, e quindi spostarlo in una lista diversa in O (1). Se l'elemento ha i propri puntatori prev e next, non c'è un vero trucco per portare a termine il lavoro. Se l'elenco è un elenco circolare doppiamente collegato, la rimozione non richiede necessariamente la conoscenza dell'elenco che contiene l'elemento.

Come da Iterator invalidation rules, std::list gli iteratori sono molto resistenti. Quindi, mi sembra di ottenere il comportamento che desidero quando uso std::list sul mio oggetto è quello di mettere a posto un iteratore all'interno della mia classe, e l'elenco dei contenuti.

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

Questo ha l'aspetto negativo che ho bisogno di creare la mia versione decorata di std::list che conosce per aggiornare il ref_ ogni volta che l'elemento viene aggiunto a un elenco. Non riesco a pensare a un modo che non richieda l'iteratore incorporato, poiché non esserne uno significherebbe che la cancellazione comporterebbe prima un'operazione di ricerca O (n).

Qual è il metodo consigliato per cancellare O (1) con std::list? O c'è un approccio migliore per raggiungere l'obiettivo?

---

In passato, ho compiuto questo implementando la mia struttura della lista di dati, in cui l'elemento inserito nella lista ha i suoi puntatori Next e Prev. Gestire questi puntatori è naturale, dal momento che sono inerenti alle operazioni stesse dell'elenco (l'implementazione dell'API nella mia lista regola i puntatori). Se invece voglio usare lo STL, quale sarebbe il modo migliore per farlo? Offro la proposta da uomo di paglia di incorporare l'iteratore. Ci sono approcci migliori?

Se si desidera utilizzare un caso di utilizzo concreto, considerare un'implementazione del timer. Quando viene creato un timer, viene inserito in un elenco appropriato. Se viene cancellato, è consigliabile rimuoverlo in modo efficiente. (Questo particolare esempio può essere risolto tramite marcatura anziché rimozione, ma è un modo valido per implementare la cancellazione.) Ulteriori casi d'uso sono disponibili su richiesta.

---

Un'altra alternativa ho esplorato era di fondere un std::list con un std::unordered_map per creare una lista specializzata per i tipi di puntatore. Questo è più pesante (a causa della tabella hash), ma fornisce un contenitore che è abbastanza vicino ai contenitori standard a livello di interfaccia e mi dà la cancellatura O (1) degli elementi della lista. L'unica caratteristica mancante nella proposta di straw-man è un puntatore all'elenco che attualmente contiene l'elemento. Ho presentato l'attuale implementazione al CodeReview per sollecitare il commento.

Answer 1

Non c'è modo di cancellare O (1) da std :: list.

Si consiglia di prendere in considerazione l'utilizzo di intrusive list, in cui i nodi di elenco sono direttamente incorporati nelle strutture, come già fatto.

è possibile utilizzare boost::intrusive o rotolare il proprio, anche verificare this

Answer 2

non può essere fatto. Un elenco utilizza i puntatori avanti e/o indietro che puntano agli elementi dell'elenco "adiacenti". Quindi dovrai ripetere ogni volta che fai qualcosa.

Se si desidera O (1) per una sorta di raccolta, far funzionare il contenuto con un array.

Per la registrazione, tuttavia, la scansione di un elenco di meno di 100 elementi richiede un periodo di tempo trascurabile, a meno che non lo facciate migliaia di volte al secondo.

Edit:

Se sai quello nodo che si desidera rimuovere, è facile. Non sono sicuro di come funzioni esattamente la lista STD, ma in senso teorico, un nodo dovrebbe essere in grado di rimuovere se stesso impostando i suoi 1 o 2 puntatori avanti e indietro dei nodi adiacenti l'uno verso l'altro.

Answer 3

std::list::erase è garantito come O (1).

Non c'è un sacco di altri modi per cancellare elementi da una lista standard. (std::list::remove e gli amici non fanno esattamente la stessa cosa, quindi non contano).

Se si desidera cancellare da un elenco standard, è necessario un iteratore e l'elenco stesso. Questo è quello che sembra aver già. Non c'è molta libertà di farlo diversamente. Manterrei il contenuto della lista separato dagli oggetti, a differenza di ciò che hai fatto, perché creare un oggetto che può essere in una sola lista alla volta? Sembra una restrizione artificiale inutile per me. Ma qualunque sia il tuo progetto.

Answer 4

Ecco una soluzione "completa" che utilizza uno iterator incorporato. Alcuni tratti privati ​​vengono utilizzati per contribuire a ridurre il disordine nella classe:

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

Come mostrato, l'attuazione lista sarà utilizzando std::list, ma il tipo di valore sottostante sarà un std::shared_ptr. Quello che sto cercando è che un'istanza di T ricava in modo efficiente il proprio iterator, per ottenere la cancellazione di O (1). Questo viene fatto usando un Ref per memoizzare l'iteratore dell'elemento dopo che è stato inserito nell'elenco.

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

Questo List segue per lo più una coda come l'interfaccia. Ma un oggetto può essere rimosso da qualsiasi posizione nell'elenco. Le funzioni semplici per lo più solo delegano al sottostante std::list. Ma i metodi push_*() e pop_*() memoize anche il 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_; } 
}; 

Questa è l'implementazione del modello di supporto utilizzato per definire i tipi iteratori per List. Quello che fa in modo diverso è che gli operatori * e -> sono definiti in modo tale che l'iteratore si comporti come se fosse un T * piuttosto che uno std::shared_ptr<T> * (che è ciò che l'iteratore sottostante farebbe normalmente).

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

Un tipo T derivato da List<T>::Item possibile aggiungere a un List<T>. Questa classe base contiene l'istanza Ref utilizzata per memoizzare l'iteratore quando l'elemento viene aggiunto a un elenco.

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

Questo codice illustra come viene eseguita la memoizzazione. Quando si esegue push_front(), l'elemento viene prima controllato per vedere se è già contenuto.In caso contrario, viene inserito e l'iteratore risultante viene aggiunto all'oggetto ref_. Altrimenti, se non è già anteriore, l'elemento viene rimosso e reinserito nella parte anteriore e l'iteratore memoizzato viene aggiornato. pop_front() rimuove l'iteratore memoized e quindi chiama pop_front() sullo 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() e pop_back() sono simili a push_front() e 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); 
    } 
} 

Il erase() di routine recupera l'iteratore memoized, e lo utilizza per eseguire la cancellazione.

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

Dal momento che un oggetto è il suo iteratore per molti aspetti, un metodo find() non dovrebbe essere necessario in questa versione di List. Ma, al posto di questo è questo metodo che viene utilizzato per vedere se l'elemento è un membro della lista.

Ora, la soluzione presentata utilizza un std::map per associare le istanze dell'elenco agli iteratori. Ciò mantiene lo spirito di O (1) se il numero di elenchi di un elemento è un membro di simultaneamente è relativamente piccolo.

Proverò la mia versione successiva alla versione boost::intrusive.

Answer 5

Forse potresti ridisegnare l'interfaccia per distribuire gli iteratori anziché gli oggetti grezzi? Nel caso del vostro timer esempio:

class Timer { 
    // ... 
}; 

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

class Timers { 

    public: 

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

    private: 

    std::list<Timer> timers; 
}; 

Naturalmente, invece di

timer.cancel(); 

utenti della classe ora hanno da dire

timers.cancelTimer(timerRef); 

ma a seconda del caso d'uso, che potrebbe non essere un problema

---

Aggiornamento: movimento timer tra liste:

class Timers { 

    public: 

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

    // ... 

}; 

utilizzo:

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

Certo è un po 'ingombrante, ma lo sono anche le alternative.

Answer 6

Terribile verità: mentre l'elenco collegato è una struttura potente, lo std::list non può sfruttare appieno le sue capacità.

Non è possibile cancellare l'oggetto da std::list utilizzando solo iteratori, poiché l'elenco deve deallocare il nodo e si deve sapere dove si trova l'allocatore che ha allocato la memoria (suggerimento: è in una lista).

I contenitori intrusivi presentano molti vantaggi rispetto all'elenco standard collegato, come l'autoconsapevolezza ;-), la possibilità di archiviare oggetti polimorfici in base al valore e rendono possibili trucchi di elenco (come avere singoli oggetti in più elenchi) fattibili. Dato che non si utilizza direttamente lo std::list direttamente, è possibile abbandonare del tutto l'utilizzo di std::list e utilizzare il contenitore di terze parti oppure eseguire il rollover.

(Inoltre, la soluzione è anche invadente, dal momento che il tipo deve essere derivato da List<T>::Item, che pone alcuni requisiti del tipo che std::list non lo fa)