Why is my order unordered_map itself?

Question

So, I played with the recently standardized unordered_map from STL. The code that I have, sort of like, I just create an unordered_map, populate it and print it out:

  unordered_map<int,string> m1; m1[5]="lamb"; m1[2]="had"; m1[3]="a"; m1[1]="mary"; m1[4]="little"; m1[7]="fleece"; m1[6]="whose"; m1[10]="fleecey"; m1[8]="was"; m1[9]="all"; for(unordered_map<int,string>::const_iterator i = m1.begin(); i != m1.end(); ++i) cout<<i->first<<" "<<i->second<<endl; 

However, the output I get is ordered:

 1 mary 2 had 3 a 4 little 5 lamb 6 whose 7 fleece 8 was 9 all 10 fleecey 

But I do not want to pay the price for my card to be ordered! That is why I use unordered_map ... What is happening here?

additional note: I am using gcc version 4.3.4 20090804 (release) 1 (GCC) and compiling, like this, g++ -std=c++0X maptest.cpp

Answer 1

"Unordered" does not mean that it will store items randomly or maintain order you place on the map. It just means that you cannot rely on any particular order. You do not pay the price for the order, quite the opposite - the implementation does not explicitly order the elements, it is a hash map and saves its elements in any way, which is usually quite spectacular. It so happened that the hashing algorithm and other internal actions of the card, when using exactly these keys and this number and the order of operations on the card, ultimately save the elements in an order that looks ordered. Lines, for example, can lead to a clearly randomized arrangement.

On the side of the note, this is probably related to a map using a hash that maps (at least some) integers to itself and uses the least significant bits (as many as size credentials) of the hash to determine the index for the underlying array (e.g. CPython does this is with some very smart additions for handling conflicts, relatively simple and efficient, for the same reason, the hashes of strings and tuples of CPython are very predictable).

Answer 2

For your pleasure, here is the output of libC ++, which also has an authentication function for std::hash<int> .

 9 all 8 was 10 fleecey 6 whose 7 fleece 4 little 1 mary 3 a 2 had 5 lamb 

There are several ways to implement a hash container, each of which has its own trade-offs.