Wie vergleicht man Vektor mit Array?

Das ist eine Variante dessen, was bald vorgeschlagen wird:

Es gibt viele verschiedene Möglichkeiten, dieses Problem zu lösen, jedes hat Vor- und Nachteile.

Einige Vortests

1. Offensichtlich können zwei Bereiche nicht gleich sein, wenn sie unterschiedliche Größe haben.
2. Sie könnten eine Reihenfolge unabhängige Hash-Funktion für Elemente in den Bereichen (Danke, @ Michael Anderson) berechnen. Es könnte eine Summe von Elementen sein, oder Sie könnten nur xor sie alle. Arrays mit unterschiedlichem Hash-Wert können nicht gleich sein.

std::unordered_multiset

Sie könnten ein unordered_multiset erstellen, das die Häufigkeit von Elementen im Bereich enthält. Obwohl es im Durchschnitt eine lineare Komplexität aufweist, kann es aufgrund von Hash-Kollisionen O (n ^ 2) sein. Zitat aus dem Standard (N3337, § 23.5.7.2):

  

Komplexität: Durchschnittlicher Fall linear, worst case quadratisch.

Sie sollten jedoch auch an die Komplexität von std::unordered_set::operator== denken:

  

Für unordered_set und unordered_map ist die Komplexität von    operator== (d. h. die Anzahl der Aufrufe an den == - Operator von    value_type , zu dem Prädikat, das von key_equal() zurückgegeben wird, und zum   hasher zurückgegeben von hash_function() ) ist proportional zu N in der   Durchschnittswert und im schlimmsten Fall N^2 , wobei N a.size() ist.

     

Für unordered_multiset und unordered_multimap ist die Komplexität von    operator== ist proportional zu sum of Ei^2 im durchschnittlichen Fall und   im schlimmsten Fall zu N^2 , wobei N ist a.size() und Ei ist   Größe der i th Äquivalent-Schlüsselgruppe in a .

     

Allerdings, wenn die   jeweilige Elemente von jedem entsprechenden Paar von äquivalenten Schlüsseln   Die Gruppen Eai und Ebi sind in der gleichen Reihenfolge angeordnet (wie es üblich ist)   B. wenn a und b unmodifizierte Kopien derselben sind   Container), dann die durchschnittliche Komplexität für unordered_multiset   und unordered_multimap wird proportional zu N (aber worst-case)   Die Komplexität bleibt O(N2) , z. B. für einen pathologisch schlechten Hash   Funktion).

Beispiel:

std::sort

Sie können sortierte Kopien Ihrer Reichweite vergleichen. Gemäß dem Standard (N3337, § 25.4.1.1) hat es O(n * log(n)) complexity:

  

Komplexität: O (N log (N)) (wobei N == last - first) Vergleiche.

Beispiel:

Konvertieren Sie zuerst das Array in den Vektor v1.

v = {1,1,2,3,4}; Vektor und

v1 = {1,1,2,3,4}; konvertiert von Array