C ++ - Liste mit schneller Suche

Question

Ich arbeite mit einem std::list.

Elemente werden in der Reihenfolge des Einfügens in die Liste angezeigt, nicht entsprechend dem Wert eines Elements.

Wenn Sie std::find()ein Element verwenden, muss die gesamte Liste durchsucht werden.

Um das "Finden" von O (n) nach O (log (n)) zu beschleunigen, könnte ich selbst eine Hash-Map implementieren, um die std::listPositionen der Elemente zu speichern , oder ich könnte Boost-Multi-Indizes verwenden.https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup.

Frage: Gibt es heute in C ++ 17 eine Standard- / Common- oder Best-Practice-Methode zum Implementieren eines Containers, der alle Eigenschaften einer Liste PLUS schnell find(und z. B. remove) aufweist? Oder gibt es einen solchen Containertyp bereits? C ++ 20 vielleicht?

Edit / Nb: Die Reihenfolge der Elemente in der Liste ist relevant und daher kann eine std :: map nicht direkt verwendet werden.

Answer 1

Da Iteratoren für a std::listüber Einfügungen und Löschungen hinweg gültig bleiben (mit Ausnahme des von Ihnen gelöschten Elements natürlich), können Sie eine Secondaray-Datenstruktur vom Typ beibehalten std::map <my_key, my_list_iterator>(oder eine, std::unordered_mapwenn dies besser geeignet ist).

Wenn Sie dann einen Listeneintrag hinzufügen oder löschen, tun Sie dasselbe mit Ihrem std::map / unordered_mapund Sie sind fertig. Sie können dies natürlich mit der Komplexität O (log (n)) (oder O (1)) suchen.

Answer 2

Sehr kurze und verständliche Anleitung (basierend auf einem einzelnen Beispiel) zur Implementierung eines Containers mit den gewünschten Funktionen mithilfe von Boost MultiIndex https://stackoverflow.com/a/39510606/11608725

Für mich ist es praktischer, leichter zu verstehen als das formellere https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookupdas deckt jede mögliche Verwendung ab (obwohl es auch Beispiele verwendet).

Answer 3

Eine teilweise und SEHR primitive (Prototyp) Implementierung der vorliegenden Antwort https://stackoverflow.com/a/64539693/11608725 (von 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

In diesem Prototyp fehlen unter anderem Iteratormethoden zum Implementieren eines benutzerdefinierten Containers. Informationen dazu finden Sie hier: Wie implementiere ich einen Iterator im STL-Stil und vermeide häufige Fallstricke? .

(Bearbeiten: Ted Lyngmo in seinem Kommentar unten bietet eine bessere Version hier: https://godbolt.org/z/6xfbq7).

Es wäre wirklich ordentlich, wenn diese Art von Behälter sofort zur Verfügung gestellt würde. Ebenso wie andere Container, die grundlegenderen Vorbildern nachempfunden sind, aber spezifische Leistungsvorteile bieten, die bestimmte Nutzungssituationen widerspiegeln. Wenn jemand eine Bibliothek kennt, die diese Art von Spezialcontainern anbietet, sagen Sie es bitte ;-)