Warum sollte jemand set anstelle von unordered_set verwenden?

C ++ 0x wird eingeführt, unordered_setdas an boostund an vielen anderen Orten verfügbar ist . Was ich verstehe ist, dass unordered_setes sich um eine Hash-Tabelle mit O(1)Nachschlagekomplexität handelt. Auf der anderen Seite setist nichts als ein Baum mit log(n)Nachschlagekomplexität. Warum um alles in der Welt sollte jemand setanstelle von verwenden unordered_set? dh besteht ein Bedarf setmehr?

Wenn für jemanden, der die Elemente des Sets durchlaufen möchte, die Reihenfolge von Bedeutung ist.

Ungeordnete Sets müssen ihre O (1) durchschnittliche Zugriffszeit auf verschiedene Arten bezahlen:

• setverbraucht weniger Speicher als unordered_setzum Speichern der gleichen Anzahl von Elementen.
• Für eine kleine Anzahl von Elementen sind Suchvorgänge in a setmöglicherweise schneller als Suchvorgänge in a unordered_set.
• Auch wenn viele Operationen schneller im sind durchschnittlicher Fall für unordered_set, werden sie oft garantiert haben , besser worst case Komplexität für set(zum Beispiel insert).
• Das set Sortieren der Elemente ist nützlich, wenn Sie der Reihe nach darauf zugreifen möchten.
• Sie können lexikographisch vergleichen verschiedene sets mit <, <=, >und >=. unordered_sets sind nicht erforderlich, um diese Vorgänge zu unterstützen.

Wann immer Sie einen Baum einer Hash-Tabelle vorziehen.

Beispielsweise sind Hash-Tabellen im schlimmsten Fall "O (n)". O (1) ist der Durchschnittsfall. Bäume sind im schlimmsten Fall "O ( log n)".

Verwenden Sie set, wenn:

1. Wir benötigen geordnete Daten (verschiedene Elemente).
2. Wir müssten die Daten drucken / darauf zugreifen (in sortierter Reihenfolge).
3. Wir brauchen Vorgänger / Nachfolger von Elementen.

Verwenden Sie unordered_set, wenn:

1. Wir müssen eine Reihe unterschiedlicher Elemente beibehalten, und es ist keine Bestellung erforderlich.
2. Wir brauchen Einzelelementzugriff, dh keine Durchquerung.

Beispiele:

einstellen:

Eingabe: 1, 8, 2, 5, 3, 9

Ausgabe: 1, 2, 3, 5, 8, 9

Unordered_set:

Eingabe: 1, 8, 2, 5, 3, 9

Ausgabe: 9 3 1 8 2 5 (möglicherweise diese Reihenfolge, beeinflusst durch die Hash-Funktion)

Hauptunterschied:

Hinweis: (in einigen Fällen setist dies bequemer) Verwenden Sie beispielsweise vectorals Schlüssel

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3 

Der Grund , warum vector<int>kann als Schlüssel in setda vectorÜberschreibungoperator< .

Wenn Sie jedoch verwenden unordered_set<vector<int>>, müssen Sie eine Hash-Funktion für erstellen vector<int>, da der Vektor keine Hash-Funktion hat. Daher müssen Sie eine wie folgt definieren:

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};

vector<vector<int>> two(){
    //unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
    unordered_set<vector<int>, VectorHash> s;
    s.insert({1, 2});
    s.insert({1, 3});
    s.insert({1, 2});

    for(const auto& vec:s)
        cout<<vec<<endl;
    // 1 2
    // 1 3
}

Sie können das in einigen Fällen sehen unordered_set komplizierter ist.

Hauptsächlich zitiert von: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006

Weil std :: set Teil von Standard C ++ ist und unordered_set nicht. C ++ 0x ist KEIN Standard und Boost auch nicht. Für viele von uns ist Portabilität unerlässlich, und das bedeutet, sich an den Standard zu halten.

Betrachten Sie Sweepline-Algorithmen. Diese Algorithmen würden mit Hash-Tabellen völlig versagen, funktionieren aber hervorragend mit ausgeglichenen Bäumen. Um Ihnen ein konkretes Beispiel für einen Sweepline-Algorithmus zu geben, betrachten Sie den Fortune-Algorithmus. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Eine weitere Sache, zusätzlich zu dem, was andere bereits erwähnt haben. Während die erwartete amortisierte Komplexität für das Einfügen eines Elements in eine ungeordnete Menge O (1) ist, wird dies von Zeit zu Zeit der Fall sein nehmen O (n) , weil die Hash-Tabelle Bedürfnisse umstrukturiert werden (die Anzahl der Schaufeln Bedürfnisse zu ändern) - auch mit eine 'gute' Hash-Funktion. Genau wie beim Einfügen eines Elements in einen Vektor wird ab und zu O (n) benötigt, da das zugrunde liegende Array neu zugewiesen werden muss.

Das Einfügen in einen Satz dauert immer höchstens O (log n). Dies kann in einigen Anwendungen vorzuziehen sein.

Verzeihen Sie mir noch eine bemerkenswerte Sache über die sortierte Eigenschaft:

Wenn Sie einen Datenbereich im Container haben möchten , zum Beispiel: Sie haben die Zeit im Set gespeichert und möchten die Zeit vom 01.01.2013 bis zum 01.01.2014.

Für unordered_set ist das unmöglich.

Natürlich wäre dieses Beispiel für Anwendungsfälle zwischen map und unordered_map überzeugender .

g++ 6.4 stdlibc ++ geordnet gegen ungeordneten gesetzten Benchmark

Ich habe diese dominante Linux C ++ - Implementierung verglichen, um den Unterschied zu erkennen:

Die vollständigen Benchmark-Details und -Analysen finden Sie unter: Was ist die zugrunde liegende Datenstruktur eines STL-Satzes in C ++?und ich werde sie hier nicht wiederholen.

"BST" bedeutet "getestet mit std::setund" Hash Map "bedeutet" getestet mit std::unordered_set. "Heap" ist, für std::priority_queuedas ich analysiert habe: Heap vs Binary Search Tree (BST)

Als kurze Zusammenfassung:

• Die Grafik zeigt deutlich, dass unter diesen Bedingungen das Einfügen von Hashmaps bei mehr als 100.000 Elementen immer viel schneller war und der Unterschied mit zunehmender Anzahl von Elementen zunimmt

  Die Kosten für diesen Geschwindigkeitsschub sind, dass Sie nicht in der Lage sind, effizient in der richtigen Reihenfolge zu fahren.

• Die Kurven deuten eindeutig darauf hin, dass die std::setReihenfolge BST-basiert und std::unordered_setHashmap-basiert ist. In der Referenzantwort bestätigte ich weiter, dass durch GDB-Schritt das Debuggen des Codes.

Ähnliche Frage für mapvs unordered_map: Gibt es einen Vorteil der Verwendung von map gegenüber unordered_map bei trivialen Schlüsseln?

Auf der anderen Seite würde ich sagen, dass es praktisch ist, Dinge in einer Beziehung zu haben, wenn Sie sie in ein anderes Format konvertieren möchten.

Es ist auch möglich, dass der Zugriff schneller ist, während die Zeit zum Erstellen des Index oder des Speichers, der beim Erstellen und / oder Zugreifen verwendet wird, größer ist.

Wenn Sie die Dinge sortieren möchten, verwenden Sie set anstelle von unordered_set. unordered_set wird over set verwendet, wenn die Reihenfolge der gespeicherten Daten keine Rolle spielt.

Obwohl diese Antwort 10 Jahre zu spät sein könnte, sollte darauf hingewiesen werden, dass sie std::unordered_setauch Sicherheitsnachteile hat.

Wenn die Hash-Funktion vorhersehbar ist (dies ist normalerweise der Fall, wenn keine Gegenmaßnahmen wie ein zufälliges Salz angewendet werden), können Angreifer Daten von Hand erstellen, die Hash-Kollisionen verursachen und dazu führen, dass alle Einfügungen und Suchvorgänge O (n) Zeit in Anspruch nehmen .

Dies kann für sehr effiziente und elegante Denial-of-Service-Angriffe verwendet werden.

Viele (die meisten?) Implementierungen von Sprachen, die intern Hash-Maps verwenden, sind auf Folgendes gestoßen:

• Javascript
• PHP
• Java