webentwicklung-frage-antwort-db.com.de

was ist der Unterschied zwischen set und unordered_set in C++?

Kam durch diese gute Frage, die ähnlich, aber überhaupt nicht gleich ist, da sie von Java spricht, das eine unterschiedliche Implementierung von Hashtabellen hat, weil Accessor /mutators synchronisiert wurde Unterschiede zwischen HashMap und Hashtable?

Was ist also der Unterschied in der C++ - Implementierung von set und unordered_set? Diese Frage kann natürlich erweitert werden, um für andere C++ - Container eine Zuordnung zu unordered_map usw. zu erstellen.

Hier ist meine erste Einschätzung

set: Während standard nicht ausdrücklich verlangt, dass es als Bäume implementiert wird, bedeutet die Zeit - Komplexitäts - Einschränkung, die nach Operationen für find/insert gefragt wird, dass es immer als Baum implementiert wird. Normalerweise als RB - Baum (wie gesehen in GCC 4.8), das höhenausgeglichen ist ..__ Da sie höhenausgeglichen sind, haben sie vorhersagbare zeitliche Komplexität für find ().

Vorteile: Kompakt (im Vergleich zu anderen DS im Vergleich)

Con: Zugriffszeitkomplexität ist O (lg n)

unordered_set: Während standard nicht explizit von ihm verlangt, als Bäume implementiert zu werden, bedeutet die zeitliche Komplexität, die nach Operationen für find/insert gefragt wird, dass es immer als Hash-Tabelle implementiert wird.

Pros:

  1. Schneller (verspricht amortisiert O(1) für die Suche)
  2. Im Vergleich zu Tree-DS können einfache Grundelemente einfach in threadsicher konvertiert werden

Nachteile:

  1. Es kann nicht garantiert werden, dass O(1) der schlimmste Fall O (n) ist.
  2. Nicht so kompakt wie ein Baum. (aus praktischen Gründen ist der Lastfaktor niemals 1)

Hinweis: Das O (1) für Hashtabelle geht von der Annahme aus, dass keine Kollision vorliegt. Selbst bei einem Ladefaktor von 0,5 führt jede zweite Variableneinfügung zu einer Kollision. Es konnte festgestellt werden, dass der Ladefaktor der Hash-Tabelle umgekehrt proportional zu der Anzahl von Operationen ist, die für den Zugriff auf ein Element darin erforderlich sind. Mehr reduzieren wir #operationen, sparser Hashtabellen. Wenn das gespeicherte Element eine mit dem Zeiger vergleichbare Größe hat, ist der Overhead sehr wichtig.

Edit: Da die meisten sagen, dass die Frage eine ausreichende Antwort enthält, ändere ich die Frage in "Habe ich irgendeinen Unterschied zwischen der Karte/dem Set zur Leistungsanalyse verpasst, das man wissen sollte?"

51
Ajeet Ganga

Ich denke, Sie haben im Allgemeinen Ihre eigene Frage beantwortet, jedoch Folgendes:

Nicht so kompakt wie ein Baum. (aus praktischen Gründen ist der Lastfaktor niemals 1)

ist nicht unbedingt wahr. Jeder Knoten eines Baums (wir nehmen an, es handelt sich um einen rot-schwarzen Baum) für einen Typ T verwendet Speicherplatz, der mindestens 2 * pointer_size + sizeof(T) + sizeof(bool) entspricht. Dies kann 3 * pointer size sein, abhängig davon, ob der Baum einen parent-Zeiger für jeden Baumknoten enthält.

Vergleichen Sie dies mit einer Hash-Map: Es wird für jede Hash-Map Platz verschwendet, da load factor < 1, wie Sie gesagt haben. Unter der Annahme, dass die Hash-Map einfach verknüpfte Listen für die Verkettung verwendet (und es gibt keinen wirklichen Grund, dies nicht zu tun), wird für jedes eingefügte Element nur sizeof(T) + pointer size verwendet. 

Beachten Sie, dass bei dieser Analyse der Overhead ignoriert wird, der durch zusätzlichen Platz für die Ausrichtung entstehen kann.

Für jedes Element T, das eine kleine Größe hat (also einen beliebigen Basistyp), dominiert die Größe der Zeiger und anderer Overhead. Bei einem Ladefaktor von > 0.5 (zum Beispiel) kann der std::unordered_set tatsächlich weniger Speicher verbrauchen als der entsprechende std::set.

Der andere große fehlende Punkt ist die Tatsache, dass die Iteration durch einen std::set garantiert eine Reihenfolge vom kleinsten zum größten ergibt, basierend auf der angegebenen Vergleichsfunktion, während das Iterieren durch einen std::unordered_set die Werte in einer "zufälligen" Reihenfolge liefert. 

26
Yuushi

Ein weiterer Unterschied (wenn auch nicht auf die Leistung bezogen) besteht darin, dass die set-Einfügung die Iteratoren nicht ungültig macht, während die unordered_set-Einfügung kann, wenn sie eine Wiederholung auslöst. In der Praxis ist dies ein eher unbedeutendes Anliegen, da Verweise auf die tatsächlichen Elemente gültig bleiben.

11
dhaffey

Yuushi spricht die räumliche Effizienz und andere Punkte bereits gut an; Nur ein paar andere Teile der Frage, die ich kommentieren werde ...

Das O (1) für Hashtabelle geht von der Annahme aus, dass keine Kollision vorliegt.

Das ist nicht wahr. Was O(1) bedeutet, ist nicht, dass der erste Suchversuch immer erfolgreich sein wird. Es ist im Durchschnitt eine konstante Anzahl von erforderlichen Versuchen erforderlich, und nicht etwas, das mit der Anzahl der Werte wächst. Bei einem unordered_set oder ..._map ist der max_load_factor bei der Konstruktion beispielsweise 1,0, und wenn der Ladefaktor bei einer guten Hash-Funktion an den Wert heranreicht, ist die Anzahl der average - Elemente, die ein beliebiges Element betreffen Bucket wird um 2 herum liegen, unabhängig davon, wie viele Werte in der Tabelle enthalten sind.

Selbst bei einem Lastfaktor von 0,5 führt jede zweite variable Einfügung zu einer Kollision.

Richtig, aber es ist nicht so schlimm, wie man es intuitiv erwarten könnte: Die durchschnittliche Kettenlänge von 2 bei 1,0 Lastfaktor ist nicht schlecht.

Es konnte beobachtet werden, dass der Lastfaktor der Hash-Tabelle umgekehrt ist proportional zu der Anzahl von Operationen, die für den Zugriff auf ein .__ erforderlich sind. Element darin. Mehr reduzieren wir #operationen, sparser Hashtabellen.

Es gibt definitiv eine Korrelation (es ist nicht invers).

2
Tony Delroy

In einigen Fällen ist set günstiger.

Zum Beispiel mit vector als 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> in set sein kann, weil vectoroperator< überschreibt.

Wenn Sie jedoch unordered_set<vector<int>> verwenden, müssen Sie eine Hashfunktion für vector<int> erstellen, da vector keine Hashfunktion hat. Daher müssen Sie eine solche 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 sehen, dass unordered_set in manchen Fällen komplizierter ist.

Hauptsächlich zitiert aus: https://stackoverflow.com/a/29855973/6329006

Weitere Unterschiede zwischen unordered_set und set finden Sie hier: https://stackoverflow.com/a/52203931/6329006

0
Jayhello