Gibt es einen Vorteil der Verwendung von map gegenüber unordered_map im Falle von trivialen Schlüsseln?

Question

Ein kürzlich gehaltener Vortrag über unordered_map in C++ machte mir klar, dass ich die unordered_map für die meisten Fälle, in denen ich map zuvor wegen der Effizienz der Nachschlagefunktion ( amortisiert O(1) vs. O(log n) ). Meistens verwende ich eine Karte, entweder int o std::string als Schlüsseltyp; daher habe ich keine Probleme mit der Definition der Hash-Funktion. Je mehr ich darüber nachdachte, desto mehr wurde mir klar, dass ich keinen Grund für die Verwendung einer std::map über eine std::unordered_map im Falle von Schlüsseln mit einfachen Typen - ich habe mir die Schnittstellen angesehen und keine signifikanten Unterschiede gefunden, die sich auf meinen Code auswirken würden.

Daher die Frage: Gibt es einen wirklichen Grund für die Verwendung von std::map sur std::unordered_map im Fall von einfachen Typen wie int y std::string ?

Ich frage aus rein programmiertechnischer Sicht - ich weiß, dass es nicht ganz als Standard gilt und dass es Probleme bei der Portierung geben kann.

Außerdem erwarte ich, dass eine der richtigen Antworten lauten könnte "Es ist effizienter für kleinere Datenmengen". wegen eines geringeren Overheads (stimmt das?) - daher möchte ich die Frage auf Fälle beschränken, in denen die Anzahl der Schlüssel nicht trivial ist (>1 024).

Edit : Puh, ich habe das Offensichtliche vergessen (danke GMan!) - ja, Karten sind natürlich geordnet - das weiß ich, und ich suche nach anderen Gründen.

Answer 1

Ich habe vor kurzem einen Test gemacht, der 50000 Merge&Sort macht. Das heißt, wenn die String-Schlüssel gleich sind, wird der Byte-String zusammengeführt. Und die endgültige Ausgabe sollte sortiert sein. Dies beinhaltet also ein Nachschlagen bei jeder Einfügung.

Für die map Implementierung dauert es 200 ms, um die Arbeit zu beenden. Für die unordered_map + map dauert es 70 ms für unordered_map Einfügung und 80 ms für map Einfügung. Die hybride Implementierung ist also 50 ms schneller.

Wir sollten zweimal nachdenken, bevor wir die map . Wenn Sie nur die Daten benötigen, die im Endergebnis Ihres Programms sortiert werden sollen, ist eine Hybridlösung möglicherweise besser.

Answer 2

Kleine Ergänzung zu all dem oben Gesagten:

Bessere Nutzung map wenn Sie Elemente nach Bereichen abrufen müssen, da sie sortiert sind und Sie sie einfach von einer Grenze zur anderen durchlaufen können.

Answer 3

Wenn Sie Projekt mit Visual Studio 2010 kompilieren - vergessen Sie unordered_map für Strings. Wenn Sie modernere Studio wie 2017 verwenden - dann unordered_map viel schneller als bestellt Karte.

Answer 4

Durch die Verwendung einer ungeordneten Karte erklären Sie, dass Sie sich nirgendwo in Ihrem Code darauf verlassen, dass die Karte geordnet ist. Diese zusätzliche Kontextinformation kann in manchen Fällen helfen zu verstehen, wie diese Karte im Programm tatsächlich verwendet wird. Die Klarheit kann wichtiger sein als die Leistung, die als Nebeneffekt entsteht.

Natürlich wird kein Compiler Sie davon abhalten, eine ungeordnete Map zu verwenden, wenn Sie die geordnete benötigen, aber es ist so unwahrscheinlich, dass dies gut funktioniert, dass der Leser sich wahrscheinlich darauf verlassen kann, dass es nicht nur ein Fehler ist.

Answer 5

Von: http://www.cplusplus.com/reference/map/map/

"Intern werden die Elemente in einer Map immer nach ihrem Schlüssel sortiert, und zwar nach einem bestimmten strengen schwachen Ordnungskriterium, das durch das interne Vergleichsobjekt (vom Typ Compare) angegeben wird.

map-Container sind im Allgemeinen langsamer als unordered_map-Container, wenn es darum geht, auf einzelne Elemente nach ihrem Schlüssel zuzugreifen, aber sie ermöglichen die direkte Iteration von Teilmengen auf der Grundlage ihrer Reihenfolge."