Die Wahl zwischen std::map und std::unordered_map
Nun, dass std
hat eine echte hash-map in unordered_map
warum (oder Wann) würde ich immer noch wollen, um die gute alte map
über unordered_map
auf Systemen, auf denen es tatsächlich existiert? Gibt es offensichtliche Situationen, die ich nicht sofort sehen?
InformationsquelleAutor der Frage Johann Gerell | 2010-10-10
Du musst angemeldet sein, um einen Kommentar abzugeben.
Als bereits erwähnt
map
erlaubt das iterieren über die Elemente in einer sortierten Weise, aberunordered_map
nicht. Dies ist sehr wichtig, in vielen Situationen, wie zum Beispiel die Anzeige einer Sammlung (z.B. Adressbuch). Dies äußert sich auch in anderen indirekten Möglichkeiten, wie: (1) Starten Sie die Iteration vom iterator zurückgegebenfind()
oder (2) die Existenz der member-Funktionen wielower_bound()
.Außerdem denke ich, dass es da einen Unterschied gibt in der schlimmsten Fall Suche Komplexität.
Für
map
es ist O( lg N )Für
unordered_map
es ist O( N ) [kann passieren, wenn die hash-Funktion ist nicht gut, führt zu zu viele hash-Kollisionen.]Gleiches gilt für die schlimmsten Fall Löschung Komplexität.
InformationsquelleAutor der Antwort Arun
Zusätzlich zu den oben genannten Antworten, sollten Sie auch beachten Sie, dass, nur weil
unordered_map
ist Konstante Geschwindigkeit (O(1)
) bedeutet nicht, dass es schneller alsmap
(umlog(N)
). Die Konstante kann größer sein, alslog(N)
zumalN
ist begrenzt durch 232 oder 264).Also zusätzlich zu den anderen Antworten (
map
Ordnung wahrt und hash-Funktionen, die schwierig sein kann) kann es sein, dassmap
ist schneller.Beispielsweise in einem Programm ich lief für eine blog-post ich sah, dass für VS10
std::unordered_map
war langsamer alsstd::map
(obwohlboost::unordered_map
schneller war als die beiden).Note 3. durch 5 bars.
InformationsquelleAutor der Antwort Motti
Dies ist aufgrund der Google-Chandler Carruth in seinem CppCon 2014 Vortrag
std::map
ist betrachtet durch viele zu sein) nicht sinnvoll für performance-orientierte Arbeit: Wenn Sie möchten, O(1)-fortgeführten Zugriff, verwenden Sie eine angemessene assoziatives array (oder für deren fehlen,std::unorderded_map
); wenn Sie möchten, sortiert sequentieller Zugriff, etwas basierend auf einem Vektor.Auch
std::map
ist ein ausgewogener Baum, und Sie haben zu Durchlaufen, oder re-balance es, unglaublich oft. Dies sind die cache-killer und cache-Apokalypse Operationen bzw.... so einfach NEIN sagen zustd::map
.Die Sie interessieren könnten diese Frage ALSO auf effiziente hash-map-Implementierungen.
(PS -
std::unordered_map
ist cache-unfreundlich, weil es verwendet, verknüpfte Listen, als Eimer.)InformationsquelleAutor der Antwort einpoklum
Ich denke, es ist offensichtlich, dass Sie verwenden würden, die
std::map
müssen Sie zur Iteration über die Elemente in der map sortiert werden.Könnten Sie es auch verwenden, wenn Sie möchten, schreiben Sie einen Vergleichsoperator (intuitiv) anstelle einer hash-Funktion (die ist in der Regel sehr unintuitiv).
InformationsquelleAutor der Antwort Ken Bloom
Sagen, Sie haben sehr große Tasten, vielleicht auch große Zeichenfolgen. Erstellen Sie ein hash-Wert für eine große Zeichenfolge, die Sie brauchen durch zu gehen die ganze Kette vom Anfang bis zum Ende. Es dauert mindestens lineare Zeit, um die Länge des Schlüssels. Allerdings, wenn Sie auf der Suche nach einem binären Baum mit der
>
Betreiber der Schlüssel jedes string-Vergleich können Sie zurück, wenn der erste mismatch gefunden wird. Dies ist in der Regel sehr früh für große Zeichenfolgen.Diese überlegung kann angewandt werden, um die
find
Funktionstd::unordered_map
undstd::map
. Wenn die Natur der Schlüssel ist so, dass es länger dauert, um zu produzieren ein hash (im Fall vonstd::unordered_map
), als es dauert, um die Position eines Elements mithilfe von binärer Suche (im Fall vonstd::map
), sollte es schneller nachschlagen eines Schlüssels in derstd::map
. Es ist ganz einfach, denken Sie an Szenarien, in denen dies der Fall sein würde, aber Sie wäre durchaus in der Praxis selten, glaube ich.InformationsquelleAutor der Antwort Martin G