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

Zusammenfassung

Die Annahme, dass die Reihenfolge nicht wichtig ist:

• Wenn Sie eine große Tabelle einmal erstellen und viele Abfragen machen wollen, verwenden Sie std::unordered_map
• Wenn Sie eine kleine Tabelle erstellen (vielleicht unter 100 Elementen) und viele Abfragen machen, verwenden Sie std::map . Der Grund dafür ist, dass die Lektüre des Dokuments O(log n) .
• Wenn Sie den Tisch häufig wechseln, sollten Sie können sein std::map ist eine gute Option.
• Im Zweifelsfall verwenden Sie einfach std::unordered_map .

Historischer Kontext

In den meisten Sprachen, ungeordnete Karte (aka Hash-basierte Dictionaries) sind die Standard-Map jedoch in C++ erhalten Sie geordnete Karte als Standard-Map. Wie konnte das passieren? Einige Leute nehmen fälschlicherweise an, dass das C++-Komitee diese Entscheidung in seiner einzigartigen Weisheit getroffen hat, aber die Wahrheit ist leider hässlicher als das.

Sie ist weit verbreitet glaubte dass C++ die geordnete Karte als Standard verwendet, weil es nicht allzu viele Parameter gibt, wie sie implementiert werden können. Auf der anderen Seite gibt es bei hashbasierten Implementierungen eine Menge zu besprechen. Um also Blockaden bei der Standardisierung zu vermeiden, haben sie kam gerade so zurecht mit geordneter Karte. Um 2005 hatten viele Sprachen bereits gute Implementierungen von Hash-basierten Implementierungen und so war es für den Ausschuss einfacher, neue std::unordered_map . In einer perfekten Welt, std::map wäre ungeordnet gewesen und wir hätten std::ordered_map als separater Typ.

Leistung

Die beiden folgenden Grafiken sprechen für sich ( Quelle ):

Answer 2

Ich denke, die Frage ist teilweise beantwortet, da keine Informationen über die Leistung mit "int"-Typen als Schlüssel bereitgestellt wurden. Ich habe meine eigene Analyse durchgeführt und herausgefunden, dass std::map in vielen praktischen Situationen (in Bezug auf die Geschwindigkeit) std::unordered_map übertreffen kann, wenn Ganzzahlen als Schlüssel verwendet werden.

Integer-Test

Das Testszenario bestand darin, Karten mit sequentiellen und zufälligen Schlüsseln und mit String-Werten mit Längen im Bereich [17:119] in Vielfachen von 17 zu füllen. Die Tests wurden mit einer Elementanzahl im Bereich [10:100000000] in Potenzen von 10 durchgeführt.

Labels:

Map64: std::map<uint64_t,std::string>
Map32: std::map<uint32_t,std::string>
uMap64: std::unordered_map<uint64_t,std::string>
uMap32: std::unordered_map<uint32_t,std::string>

Einfügung

Labels:

Sequencial Key Insert: maps were constructed with keys in the range [0-ElementCount]
Random Key Insert: maps were constructed with random keys in the full range of the type

Schlussfolgerung zu Einfügung :

• Das Einfügen von verteilten Schlüsseln in std::map ist tendenziell besser als std::unordered_map, wenn die Größe der Karte unter 10000 Elementen liegt.
• Das Einfügen von dichten Schlüsseln in std::map zeigt unter 1000 Elementen keinen Leistungsunterschied zu std::unordered_map.
• In allen anderen Situationen ist std::unordered_map tendenziell schneller.

Nachschlagen

Labels:

Sequential Key - Seq. Search: Search is performed in the dense map (keys are sequential). All searched keys exists in the map.
Random Key - Rand. Search: Search is performed in the sparse map (keys are random). All searched keys exists in the map.

(label names can be miss leading, sorry about that)

Schlussfolgerung zu nachschlagen :

• Die Suche auf der gespreizten std::map ist tendenziell etwas besser als die std::unordered_map, wenn die Größe der Map unter 1000000 Elementen liegt.
• Suche auf dichter std::map übertrifft std::unordered_map

Fehlgeschlagene Suche

Labels:

Sequential Key - Rand. Search: Search is performed in the dense map. Most keys do not exists in the map.
Random Key - Seq. Search: Search is performed in the sparse map. Most keys do not exists in the map.

(label names can be miss leading, sorry about that)

Schlussfolgerung zu Fehlgeschlagener Nachschlag :

• Suche vermissen ist eine große Auswirkung in std::map.

Allgemeine Schlussfolgerung

Selbst wenn Geschwindigkeit gefragt ist, kann std::map für Integer-Schlüssel in vielen Situationen die bessere Wahl sein. Ein praktisches Beispiel: Ich habe ein Wörterbuch in dem Nachschlagevorgänge nie fehlschlagen, und obwohl die Schlüssel spärlich verteilt sind, wird es mit der gleichen Geschwindigkeit wie std::unordered_map ausgeführt, da die Anzahl der Elemente unter 1K liegt. Und der Speicherplatzbedarf ist deutlich geringer.

String-Test

Als Referenz finden Sie hier die Zeitangaben für string[string] Karten. Key-Strings werden aus einem zufälligen uint64_t-Wert gebildet, Value-Strings sind die gleichen, die auch in den anderen Tests verwendet werden.

Labels:

MapString: std::map<std::string,std::string>
uMapString: std::unordered_map<std::string,std::string>

Bewertungsplattform

OS: Linux - OpenSuse Tumbleweed

Compiler: g++ (SUSE Linux) 11.2.1 20210816

CPU: Intel(R) Core(TM) i9-9900 CPU @ 3,10GHz

RAM: 64Gb

Answer 3

Ich möchte nur darauf hinweisen, dass... es gibt viele Arten von unordered_map s.

Schauen Sie sich die Wikipedia-Artikel auf der Hash-Karte. Je nachdem, welche Implementierung verwendet wurde, können sich die Eigenschaften in Bezug auf das Nachschlagen, Einfügen und Löschen erheblich unterscheiden.

Und das ist es, was mich am meisten beunruhigt bei der Hinzufügung von unordered_map an die STL: Sie werden eine bestimmte Implementierung wählen müssen, da ich bezweifle, dass sie sich für die Policy und so werden wir mit einer Implementierung für den durchschnittlichen Gebrauch feststecken und nichts für die anderen Fälle...

Einige Hash-Maps verfügen beispielsweise über ein lineares Rehashing, bei dem nicht die gesamte Hash-Map auf einmal, sondern nur ein Teil davon bei jeder Einfügung rehasht wird, wodurch die Kosten amortisiert werden können.

Ein weiteres Beispiel: Einige Hash-Maps verwenden eine einfache Liste von Knoten für einen Bucket, andere verwenden eine Karte, wieder andere verwenden keine Knoten, sondern suchen den nächstgelegenen Slot, und wieder andere verwenden eine Liste von Knoten, ordnen sie aber so an, dass das zuletzt aufgerufene Element ganz vorne steht (wie bei einem Caching).

Daher bevorzuge ich im Moment eher die std::map oder vielleicht eine loki::AssocVector (für eingefrorene Datensätze).

Verstehen Sie mich nicht falsch, ich würde gerne die std::unordered_map aber es ist schwierig, der Portabilität eines solchen Containers zu "vertrauen", wenn man an die vielen Implementierungsmöglichkeiten und die verschiedenen Leistungen denkt, die sich daraus ergeben.

Answer 4

Die Gründe dafür wurden in anderen Antworten genannt; hier ist ein weiterer.

std::map (balanced binary tree) Operationen amortisieren sich O(log n) und im schlimmsten Fall O(log n). std::unordered_map (Hashtabelle) Operationen amortisieren sich O(1) und im schlimmsten Fall O(n).

In der Praxis bedeutet dies, dass die Hash-Tabelle hin und wieder mit einer O(n)-Operation "Schluckauf" hat, was Ihre Anwendung tolerieren kann oder auch nicht. Wenn sie dies nicht tolerieren kann, sollten Sie std::map gegenüber std::unordered_map vorziehen.

Answer 5

Hash-Tabellen haben höhere Konstanten als herkömmliche Map-Implementierungen, was für kleine Container von Bedeutung ist. Die maximale Größe beträgt 10, 100 oder vielleicht sogar 1.000 oder mehr? Die Konstanten sind dieselben wie immer, aber O(log n) ist nahe an O(k). (Denken Sie daran, dass logarithmische Komplexität immer noch wirklich gut.)

Was eine gute Hash-Funktion macht, hängt von den Eigenschaften Ihrer Daten ab. Wenn ich also nicht vorhabe, mir eine benutzerdefinierte Hash-Funktion anzuschauen (aber ich kann meine Meinung sicherlich später ändern, und zwar ganz einfach, da ich fast alles typisiert habe), und obwohl die Standardwerte so gewählt sind, dass sie für viele Datenquellen anständig funktionieren, finde ich die geordnete Natur von map anfangs so hilfreich, dass ich in diesem Fall immer noch map statt einer Hash-Tabelle verwende.

Außerdem muss man so nicht einmal darüber nachdenken, eine Hash-Funktion für andere (normalerweise UDT-) Typen zu schreiben, sondern kann einfach op< schreiben (was man sowieso will).