Ich verstehe nicht std :: tr1 :: unordered_map

Question

Ich brauche einen assoziativen Container, der mich ein bestimmtes Objekt durch eine Zeichenfolge indexiert, aber das auch die Reihenfolge der Insertion behält, so dass ich nach einem bestimmten Objekt suchen kann Name oder nur darauf iterieren und Objekte in der gleichen Reihenfolge abrufen, die ich sie eingefügt habe.

Ich denke, dass hybrid of linked list and hash map sollte die Arbeit tun, aber bevor ich versuchte, std::tr1::unordered_map zu verwenden, denke, dass es auf diese Weise arbeitete ich beschrieben, aber es war nicht. Könnte mir jemand die Bedeutung und das Verhalten von unordered_map erklären?

---

@wesc: Ich bin sicher, dass std :: map von STL implementiert ist, während ich sicher, dass std :: bin hash_map ist nicht in der STL (denke ich ältere Version von Visual Studio in einem Namespace setzen genannt stdext).

@cristopher: Also, wenn ich es richtig verstehe, ist der Unterschied in der Umsetzung (und damit Leistungen), nicht in der Art, wie es sich äußerlich verhält.

Answer 1

Boost documentation of unordered containers

Der Unterschied liegt in der Methode, wie Sie den Look erzeugen.

In den Map/Set-Containern wird operator< verwendet, um einen geordneten Baum zu generieren. In den ungeordneten Behältern wird ein operator(key) => index verwendet.

Siehe Hashing für eine Beschreibung, wie das funktioniert.

Answer 2

I denke,, dass eine unordered_map und hash_map mehr oder weniger die gleiche Sache sind. Der Unterschied ist, dass die STL nicht offiziell eine hash_map hat (was Sie verwenden, ist wahrscheinlich eine Compiler-spezifische Sache), also ist unordered_map der Fix für diese Unterlassung.

unordered_map ist nur das ... ungeordnet. Sie können sich nicht darauf verlassen, dass bei der Iteration eine Reihenfolge beibehalten wird.

Answer 3

@wesc: STL hat std :: map ... also was ist der Unterschied mit unordered_map? Ich glaube nicht, dass STL das Gleiche umsetzen und es anders nennen würde.

Answer 4

Sie sicher, dass std :: hash_map existiert in alle STL-Implementierungen? SGI STL implementiert es, aber GNU g ++ hat es nicht (es befindet sich im Namensraum __gnu_cxx) wie in 4.3.1. Soweit ich weiß, war hash_map schon immer nicht standardisiert, und jetzt löst tr1 das aus.

Answer 5

Entschuldigung, lies deinen letzten Kommentar falsch. Ja, hash_map ist nicht in STL, map is. Aber unordered_map und hash_map sind die gleichen, die ich gelesen habe.

Karte -> log (n) Insertion, Retrieval, Iteration ist effizient (und durch Schlüsselvergleich bestellt)

hash_map/unordered_map -> konstante Zeit Einfügen und Abrufen, Iterationszeit werden nicht effizient ist, garantieren

Keine von beiden wird für Sie alleine funktionieren, da die Map die Dinge basierend auf dem Schlüsselinhalt und nicht der Einfügesequenz ordnet (außer Ihr Schlüssel enthält Informationen über die Einfügesequenz darin).

Sie müssen entweder das, was Sie beschrieben haben (list + hash_map), oder einen Schlüsseltyp erstellen, der die Einfügematrix und eine entsprechende Vergleichsfunktion enthält.

Answer 6

Sie benötigen einen assoziativen Container zwei Möglichkeiten, um Index:

• Anzeigenauftrag
• String Vergleich

Versuchen Boost.MultiIndex oder Boost.Intrusive. Ich habe es nicht so benutzt, aber ich denke es ist möglich.

Answer 7

Sie haben nach dem kanonischen Grund gefragt, warum Boost :: MultiIndex erstellt wurde: Listeneinfügereihenfolge mit schneller Suche nach Schlüssel. Boost MultiIndex tutorial: list fast lookup