Bei zwei std::set s kann man einfach beide Sätze gleichzeitig durchlaufen und die Elemente vergleichen, was zu linearer Komplexität führt. Dies funktioniert nicht für std::unordered_set s, da die Elemente in beliebiger Reihenfolge gespeichert werden können. Also, wie teuer ist a == b für std::unordered_set?Wie teuer ist der Vergleich zweier ungeordneter Sätze für die Gleichheit?
Komplexität von operator== und operator!=:
Lineare Komplexität im durchschnittlichen Fall. N im schlimmsten Fall, wobei N die Größe des Containers ist.
Weitere Details im Standard §23.2.5, Punkt 11:
Für unordered_set und unordered_map, die Komplexität des operator== (dh die Anzahl der Anrufe an die == Betreiber der value_type, zum Prädikat zurück durch key_equal() und zu dem Hasher durch hash_function() zurückgekehrt ist) in dem Durchschnittsfall proportional zu N und zu N 2 im schlimmsten Fall, wo Na.size() ist.
Der schlimmste Fall ist O (n²).
Aber ungeordnete Sätze sind tatsächlich von Hash angeordnet. So ist es möglich, die Hashes zu vergleichen (wenn dies fehlschlägt, können die Sets nicht gleich sein) und dann überprüfen, dass dieselben Hashes (linear) echte gleiche Werte (O (n²) für verschiedene Werte mit dem gleichen Hash) haben.
Im besten Fall ist das O (n).
Normalerweise tendiert die Komplexität zu O (n) wenn die Hash-Funktion "gut" ist (verschiedene Objekte -> immer unterschiedliche Hash) und zu O (n²) wenn die Hash-Funktion "schlecht" ist (alles hat immer die gleiche) Hash-Wert)
"Hash-Funktion ist gut (verschiedene Objekte -> immer unterschiedliche Hash)" -> verschiedene Hashes können auch für einen schrecklichen Hash-Algorithmus wahr sein (z. B. Hash-Strings von bis zu 128 Zeichen durch Rücksendung eines 8 * 128-Bit-Hash-Wertes geklont) der String), aber mod in die Anzahl der Eimer und das Ergebnis ist hässlich. Wenn es keinen speziellen Einblick in Eingaben gibt, die die Kollisionsvermeidung erleichtern, hat eine gute Hash-Funktion Post-Modding im Allgemeinen Kollisionen im Verhältnis von verwendeten zu unbenutzten Buckets ... was immer noch zu O (n) -Mittelwerten führt. –
@TonyDelroy: Danke für das Aufzeigen! Ein "guter Hash" muss nicht nur "verschiedene Werte" zurückgeben, sondern auch "gut verteilt" in Bezug auf die Buckets (Der Hash-Raum sollte einheitlich und primitiv zu den Buckets sein, um den von Ihnen erwähnten Effekt zu minimieren) –
Haben Sie eine effiziente Möglichkeit, die festgelegte Mitgliedschaft zu überprüfen (zum Beispiel werden sie von Hashtabellen unterstützt)? – Thilo
In den klaren, einfachen, leicht verständlichen und verständlichen Worten des C++ Standards: "Zwei ungeordnete Container' a' und 'b' vergleichen sich gleich, wenn' a.size() == b.size() 'und für jeden Äquivalent-Schlüssel-Gruppe '[Ea1, Ea2)' erhalten aus 'a.Equal_range (Ea1)' existiert eine äquivalente Schlüsselgruppe '[Eb1, Eb2)', die aus 'b.Equal_range (Ea1)' erhalten wird, so dass ' Abstand (Ea1, Ea2) == Abstand (Eb1, Eb2) 'und' is_permutation (Ea1, Ea2, Eb1) 'gibt 'wahr' zurück. Für 'ungeordneter_satz' ... ist die Komplexität von 'operator ==' ... proportional zu "N" im durchschnittlichen Fall und zu "N^2" im schlimmsten Fall, wobei "N" "a.größe()" ist. " –