Liste C ++ avec recherche rapide

Question

Je travaille avec un std::list.

Les éléments apparaissent dans "l'ordre d'insertion" dans la liste, et non selon la valeur d'un élément.

Lors de la std::find()saisie d'un élément, la liste entière doit être recherchée.

Afin d'accélérer la "recherche" de O (n) à O (log (n)), je pourrais moi-même implémenter un hash-map pour stocker les std::listpositions des éléments, ou je pourrais utiliser boost Multi Indexes,https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup.

Question: Aujourd'hui, avec C ++ 17, existe-t-il un moyen standard / courant ou des meilleures pratiques d'implémenter un conteneur qui a toutes les propriétés d'une liste PLUS rapide find(et, par exemple remove)? Ou un tel type de conteneur existe-t-il déjà? C ++ 20 peut-être?

Edit / Nb: L'ordre des éléments dans la liste est pertinent et donc un std :: map ne peut pas être utilisé directement.

Answer 1

Étant donné que les itérateurs pour a std::listrestent valides entre les insertions et les suppressions (sauf pour l'élément que vous avez supprimé, bien sûr), vous pouvez conserver une structure de données secondaire de type std::map <my_key, my_list_iterator>(ou std::unordered_mapsi cela est plus approprié).

Ensuite, chaque fois que vous ajoutez ou supprimez une entrée de liste, faites la même chose pour vous std::map / unordered_mapet vous avez terminé. Vous pouvez, bien sûr, rechercher cela avec une complexité O (log (n)) (ou O (1)).

Answer 2

Guide très court et compréhensible (basé sur un seul exemple) sur la façon d'implémenter un conteneur avec les capacités souhaitées à l'aide de Boost MultiIndex https://stackoverflow.com/a/39510606/11608725

C'est plus pratique, pour moi, plus facile à comprendre, que le style plus formel https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookupqui couvre toutes les utilisations possibles (bien qu'il utilise également des exemples).

Answer 3

Une implémentation partielle et TRÈS primitive (prototype) de la présente réponse https://stackoverflow.com/a/64539693/11608725 (par 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);
}

démo: https://godbolt.org/z/jdnvdM

Entre autres choses, il manque à ce prototype des méthodes d'itération pour implémenter un conteneur personnalisé, des informations à ce sujet ici: Comment implémenter un itérateur de style STL et éviter les pièges courants? .

(Edit: Ted Lyngmo dans son commentaire ci-dessous fournit une meilleure version ici: https://godbolt.org/z/6xfbq7).

Ce serait vraiment bien si ce type de conteneur était fourni prêt à l'emploi. Ainsi que d'autres conteneurs inspirés / dérivés de conteneurs plus fondamentaux, mais qui ajoutent des avantages de performances spécifiques reflétant des situations d'utilisation spécifiques. Si quelqu'un connaît une bibliothèque qui fournit ce type de conteneurs spécialisés, veuillez le dire ;-)