Gegeben 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. Wie teuer ist a == b für std::unordered_set ?
Komplexität von operator== und operator!= :
Lineare Komplexität im Durchschnitt. N 2 im schlimmsten Fall, wobei N die Größe des Behälters ist.
Weitere Details im Standard §23.2.5, Punkt 11:
Für unordered_set und unordered_map die Komplexität von operator== (d. h. die Anzahl der Aufrufe des == -Operators von value_type an das Prädikat von
key_equal() , und der von hash_function() zurückgegebene Hasher ist im Mittelfall proportional zu N und im ungünstigsten Fall zu N <2>, wobei N ist a.size() .
Der schlimmste Fall ist O (n²).
Aber ungeordnete Mengen werden tatsächlich durch Hash angeordnet. So ist es möglich, die Hashes zu vergleichen (wenn dies nicht gelingt, können die Mengen nicht gleich sein) und dann zu überprüfen, dass dieselben Hashwerte (linear) gleiche Werte (O (n²) für verschiedene Werte mit demselben 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 - & gt; immer anderer Hash) und zu O (n²), wenn die Hash-Funktion "schlecht" ist (alles hat immer die gleiche) Hash-Wert)
Tags und Links c++ set complexity-theory equality unordered-set