Unordered map sortiert doch die Elemente?

goldenBoy

Hallo,

ich dachte, bei tr1::unordered_map werden die Keys nicht sortiert, aber das scheint nicht zu stimmen.

Ich habe in der folgenden Reihenfolge Elemente in einem unordered_map hinzugefügt:

std:tr1::unordered_map<int, string> test;

test.insert<1, "montag">
test.insert<3, "dienstag">
test.insert<2, "mittwoch">

Ergebnis:
1 montag
2 mittwoch
3 dienstag

Ich möchte aber die Elemente genau in der Reihenfolge haben, in der sie hinzugefügt wurden.

Bitte um Hilfe.

Shade Of Mine

Eine map muss immer sortieren. Wie soll er sonst den Schlüssel effizient wieder finden? unordered_map heisst nur, die map hat keine natürliche Ordnung, zB weil es eine hash Map ist -> also hashes der Keys zum sortieren verwendet.

Wenn du die Reihenfolge beibehalten willst, brauchst du vector oder list.

SeppJ

unordered_map ist ganz was anderes, als du denkst. Bitte Dokumentation lesen, nicht vom Namen falsch auf den Inhalt schließen. Der Unterschied zwischen map und unordered_map ist in erster Linie ein technischer bezüglich der Laufzeitkomplexität, das Verhalten der Schnittstelle ist in beiden Fällen gleich^*.

Du suchst irgendeine andere Art von Container. Welchen genau, das hängt von deinen Anforderungen ab. Einfügereihenfolge beibehalten und Zugriff über Schlüssel bietet jedenfalls keine Standarddatenstruktur, da wird wohl eine eigene Kombi, z.B. aus vector und map nötig sein. Details hängen wie gesagt von deinen Anforderungen, d.h. wieso und wofür du das überhaupt brauchst.

^*: Dabei ist aber undefiniert, in welcher Reihenfolge die Elemente beim Durchiterieren gefunden werden. Dies kann sich durchaus bei einer map und unordered_map mit ansonstem gleichem Inhalt unterscheiden. Es wird jedenfalls nicht die Einfügereihenfolge sein, denn es ist nicht festgelegt, dass es diese sein muss und es wäre bei der Implementierung unnötig umständlich, diese noch irgendwo zu speichern.

goldenBoy

Ich werde ein Vector verwendet, das als Inhalt "pair" annimmt.
Ich muss halt meinen Code viel umschreiben.

Danke für die Hilfe!

Nexus

SeppJ schrieb:

unordered_map ist ganz was anderes, als du denkst. Bitte Dokumentation lesen, nicht vom Namen falsch auf den Inhalt schließen.

Ist auch etwas schade, dass das Standardisierungskommitee für C++ wieder mal ganz originell sein musste und Hash-Maps nicht wie normale Menschen einfach hash_map nennen konnte, sondern einen unintuitiven und längeren Namen kreierte. Die Namenkollisionsproblematik scheint mir etwas aufgebauscht, für irgendwas haben wir ja Namespaces.

Shade Of Mine

Nexus schrieb:

SeppJ schrieb:

unordered_map ist ganz was anderes, als du denkst. Bitte Dokumentation lesen, nicht vom Namen falsch auf den Inhalt schließen.

Ist auch etwas schade, dass das Standardisierungskommitee für C++ wieder mal ganz originell sein musste und Hash-Maps nicht wie normale Menschen einfach hash_map nennen konnte, sondern einen unintuitiven und längeren Namen kreierte. Die Namenkollisionsproblematik scheint mir etwas aufgebauscht, für irgendwas haben wir ja Namespaces.

Ohne jetzt die Hintergründe zu kennen - ich habe angenommen dass der Name nicht hash_map lautet weil man theoretisch ja auch die map als skiplist oder ähnliches implementieren könnte.

camper

Shade Of Mine schrieb:

Nexus schrieb:

SeppJ schrieb:

unordered_map ist ganz was anderes, als du denkst. Bitte Dokumentation lesen, nicht vom Namen falsch auf den Inhalt schließen.

Ist auch etwas schade, dass das Standardisierungskommitee für C++ wieder mal ganz originell sein musste und Hash-Maps nicht wie normale Menschen einfach hash_map nennen konnte, sondern einen unintuitiven und längeren Namen kreierte. Die Namenkollisionsproblematik scheint mir etwas aufgebauscht, für irgendwas haben wir ja Namespaces.

Ohne jetzt die Hintergründe zu kennen - ich habe angenommen dass der Name nicht hash_map lautet weil man theoretisch ja auch die map als skiplist oder ähnliches implementieren könnte.

Der Grund war schon, dass einige Hersteller schon bisher (inkompatibel) std::hash_map angeboten haben.

knivil

Der Grund war schon, dass einige Hersteller schon bisher (inkompatibel) std::hash_map angeboten haben.

Keine Ahnung aber C++ hatte einfach keine Hashmap in der STL bis 2006. Jedes "Framework" hat sein eigenes Sueppchen bis dahin gekocht. Das gleiche ist bei String oder Threads zu beobachten. Jeder scheut den Aufwand seine Bibliotheken anzupassen, da es erstmal keinen Mehrwert bietet.

Und nein unordered_set sortiert die Elemente nicht. Was du willst, ist bei (fast) jedem Container verfuegbar, der push_back anbietet.