Wie wähle ich zwischen map und unordered_map?

Question

Angenommen, ich möchte Daten mit einer Zeichenfolge als Schlüssel zuordnen. Welchen Behälter sollte ich gewählt haben, map oder unordered_map? unordered_map nimmt mehr Speicher auf, also nehmen wir an, Speicher ist kein Problem, und die Sorge ist Geschwindigkeit.

unordered_map sollte im Allgemeinen die durchschnittliche Komplexität von O (1) mit dem schlechtesten Fall von O (n) angeben. In welchen Fällen würde es zu O (n) kommen? Wann wird ein map effizienter als unordered_map? Kommt es vor, wenn n klein ist?

Angenommen, ich würde STL unordered_map mit dem Standard Haser Vs. Karte. String ist der Schlüssel.

Wenn ich über die Elemente iteriere anstatt auf ein einzelnes Element jedes Mal zuzugreifen, sollte ich map bevorzugen?

Answer 1

In der Praxis, wenn der Speicher nicht ist Problem, unordered_map ist immer schneller, wenn Sie Einzelelementzugriff wünschen.

Der schlimmste Fall ist theoretisch und gebunden an einen einzelnen Hash für alle Elemente. Dies ist nicht von praktischer Relevanz. Die unordered_map wird langsamer, sobald Sie zumindest Log-N-Elemente haben, die zum selben Hash gehören. Dies ist auch nicht von praktischer Relevanz. In einigen speziellen Szenarien könnten Sie einen speziellen Hash-Algorithmus verwenden, der eine gleichmäßigere Verteilung gewährleistet. Für gewöhnliche Zeichenfolgen, die kein spezifisches Muster teilen, sind die generischen Hash-Funktionen, die mit unordered_map kommen, genauso gut.

Wenn Sie die Karte (mit Iteratoren) sortiert durchqueren möchten, können Sie unordered_map nicht verwenden.Im Gegensatz dazu ermöglicht map nicht nur das, sondern kann Ihnen auch das nächste Element in einer Karte basierend auf einer Annäherung des Schlüssels bereitstellen (siehe lower_bound und upper_bound Methoden).

Answer 2

In welchen Fällen würde es zu O (n) kommen?

wenn Sie eine solche schlecht Hash-Funktion haben, die den gleichen Hash-Wert für alle Eingangs stirngs erzeugt (dh produzieren Kollisionen) ...

Welche Behälter sollte ich gewählt habe, Karte oder unordered_map ?

Es ist immer die Fragen der Anforderungen und Art/Menge der Daten, die Sie haben.

Wann wird eine Karte effizienter als unordered_map?

Es ist nur andere Strukturen. Du solltest besser auf eine Chiose macht einen von ihnen zu verwenden, je nach typischen Anwendungsfällen (takeing in Rechnung, welche Art von Daten haben Sie und ihre Menge)

Ist es hppaen wenn n klein ist?

Bei kleinen Datenmenge hängt alles von bestimmten STL-Implementierung ... Also manchmal sogar ein einfacher Vektor/Array könnte schneller sein als assoziative Container ...

Answer 3

Welchen Container soll ich gewählt haben, map or unordered_map? unordered_map nimmt mehr Speicher in Anspruch, also nehmen wir an, Speicher ist kein Problem, und das Problem ist die Geschwindigkeit.

Profil und dann entscheiden. unordered_map ist in der Regel schneller, aber es variiert je nach Fall.

In welchen Fällen würde es zu O (n) kommen?

Wenn das Hashing nicht gut ist und eine Reihe von Elementen den gleichen Bins zugewiesen werden.

Wann wird eine Karte effizienter als unordered_map? Hört es sich, wenn n klein ist?

Wahrscheinlich nicht, aber profilieren Sie es, wenn Sie wirklich interessiert sind. Einen Behälter mit einer kleinen Größe zu haben, ist der Flaschenhals Ihres Programms äußerst unwahrscheinlich. Wie auch immer, ein einfacher vector mit linearer Suche kann in solchen Fällen schneller sein.

---

Die wichtigste Sache bei der Entscheidung ist die Anforderungen der Bestellung und fehlende Iterator-Invalidierung. Wenn Sie beide benötigen, müssen Sie ziemlich viel map verwenden. Ansonsten unordered_map.

Answer 4

     | map    | unordered_map 
--------------------------------------------------------- 
element ordering  | strict weak  | n/a 
         |     | 
common implementation | balanced tree | hash table 
         | or red-black tree| 
         |     | 
search time   | log(n)   | O(1) if there are no hash collisions 
         |     | Up to O(n) if there are hash collisions 
         |     | O(n) when hash is the same for any key 
         |     |  
Insertion time   | log(n)+rebalance | Same as search 
         |     | 
Deletion time   | log(n)+rebalance | Same as search 
         |     | 
needs comparators  | only operator < | only operator == 
         |     | 
needs hash function | no    | yes 
         |     | 
common use case  | when good hash is| In most other cases. 
         | not possible or | 
         | too slow. Or when| 
         | order is required|