Elenco C ++ con ricerca rapida

Question

Sto lavorando con a std::list.

Gli elementi vengono visualizzati in "ordine di inserimento" nell'elenco, non in base al valore di un elemento.

Quando si std::find()inserisce un elemento, è necessario cercare l'intero elenco.

Per velocizzare la "ricerca" da O (n) a O (log (n)) potrei implementare io stesso una hash-map per memorizzare le std::listposizioni degli elementi, oppure potrei usare boost Multi Indexes,https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup.

Domanda: Oggi, con C ++ 17, esiste un modo standard / comune o best practice per implementare un contenitore che abbia tutte le proprietà di un elenco PIÙ veloce find(e, ad esempio remove)? Oppure esiste già un tale tipo di contenitore? C ++ 20 forse?

Modifica / Nb: l'ordine degli elementi nell'elenco è rilevante e quindi una std :: map non può essere utilizzata direttamente.

Answer 1

Poiché gli iteratori per a std::listrimangono validi tra gli inserimenti e le eliminazioni (ad eccezione dell'elemento che hai eliminato, ovviamente), potresti mantenere una struttura dati secondaria di tipo std::map <my_key, my_list_iterator>(o a std::unordered_mapse è più adatta).

Quindi, ogni volta che aggiungi o elimini una voce dell'elenco, fai la stessa cosa con il tuo std::map / unordered_mape il gioco è fatto. Ovviamente puoi cercarlo con complessità O (log (n)) (o O (1)).

Answer 2

Guida molto breve e comprensibile (basata su un singolo esempio) su come implementare un container con le capacità desiderate utilizzando Boost MultiIndex https://stackoverflow.com/a/39510606/11608725

È più pratico, per me, più facile da capire, rispetto allo stile più formale https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookupche copre ogni possibile utilizzo (anche se utilizza anche esempi).

Answer 3

Un'implementazione (prototipo) parziale e MOLTO primitiva della presente risposta https://stackoverflow.com/a/64539693/11608725 (di Paul Sanders):

 #include <unordered_map>
 #include <list>
 #include <iterator>
 #include <iostream>

 using std::unordered_map;
 using std::list;
 using std::make_pair;
 using std::begin;
 using std::end;
 using std::prev;
 using std::cout;

 template <typename T>
 struct fastlist {
    list<T> l;
    unordered_map<T, typename list<T>::iterator> m;
     
    void push_front(T e) {
        l.push_front(e);
        m.insert(make_pair(e, begin(l)));
    }

    void push_back(T e) {
        l.push_back(e);
        m.insert(make_pair(e, prev(end(l))));
    }

    auto find(T e) {
        return m[e];
    }

    void remove(T e) {
        auto it = m[e];
        m.erase(*it);
        l.erase(it);
    }
};

int main() {          // Giving it a spin
    fastlist<int> f;

    f.push_back(3);
    f.push_back(4);
    f.push_back(5);
    f.push_front(2);
    f.push_front(1);
    f.remove(3);
    f.remove(5);
    f.remove(1); 
    f.push_back(200); 
    f.push_front(-100);
    cout << *f.find(4);
}

demo: https://godbolt.org/z/jdnvdM

Tra le molte altre cose, a questo prototipo mancano metodi iteratori per implementare un contenitore personalizzato, informazioni su questo qui: Come implementare un iteratore in stile STL ed evitare insidie ​​comuni? .

(Modifica: Ted Lyngmo nel suo commento qui sotto fornisce una versione migliore qui: https://godbolt.org/z/6xfbq7).

Sarebbe davvero bello se questo tipo di contenitore venisse fornito fuori dagli schemi. Così come altri contenitori che sono modellati / derivati ​​da quelli più fondamentali, ma aggiungono vantaggi prestazionali specifici che riflettono situazioni di utilizzo specifiche. Se qualcuno conosce una libreria che fornisce quel tipo di contenitori specializzati, per favore dillo ;-)