Also habe ich mit dem neu standardisierten unordered_map von der STL gespielt. Der Code, den ich habe, ist irgendwie so, ich erstelle nur eine unordered_map, fülle sie aus und drucke sie aus:
Allerdings ist die Ausgabe, die ich bekomme, so geordnet:
%Vor%Aber ich will den Preis nicht bezahlen, um meine Karte bestellen zu lassen! Deshalb verwende ich eine unordered_map ... Was geht hier vor?
zusätzlicher Hinweis: Ich verwende gcc version 4.3.4 20090804 (release) 1 (GCC) und kompiliere wie diese g++ -std=c++0X maptest.cpp
"Ungeordnet" bedeutet nicht, dass die Elemente zufällig gespeichert werden oder die Reihenfolge beibehalten wird, die Sie in die Karte eingefügt haben. Es bedeutet nur, dass Sie sich nicht auf eine bestimmte Reihenfolge verlassen können. Sie zahlen keinen Preis für die Bestellung, im Gegenteil - die Implementierung ist nicht ausdrücklich die Reihenfolge der Artikel, es ist eine Hashmaps und speichert seine Elemente in welcher Weise es auch immer, was in der Regel eine ziemlich performante Art und Weise ist. Es kommt einfach vor, dass der Hashalgorithmus und andere interne Funktionen der Karte, wenn genau diese Schlüssel und diese Anzahl und Reihenfolge der Operationen auf der Karte verwendet werden, die Artikel in einer Reihenfolge ablegen, die geordnet aussieht. Strings zum Beispiel können zu einem scheinbar zufälligen Layout führen.
Nebenbei bemerkt, dies wird wahrscheinlich dadurch verursacht, dass die Karte einen Hash verwendet, der (mindestens einige) Ganzzahlen mit sich selbst abbildet und die unteren Bits (so viele wie die Kartengrößenmandate) des Hashs verwendet, um den Index zu bestimmen für das zugrunde liegende Array (zum Beispiel macht CPython dies - mit einigen sehr cleveren Zusätzen, um Kollisionen relativ einfach und effizient zu behandeln; aus demselben Grund sind die Hashes von CPython Strings und Tupeln sehr vorhersehbar).
Zu Ihrer Belustigung, hier ist die Ausgabe von libc ++, die auch eine Identitätsfunktion für std::hash<int> hat.
Es gibt mehrere Möglichkeiten, einen Hash-Container zu implementieren, von denen jeder seine eigenen Kompromisse hat.
Tags und Links c++11 map unordered-map