为什么我的unordered_map自行排序？

Question

所以我正在玩unordered_mapSTL 的新标准化.我的代码有点像这样,我只是创建一个unordered_map,填充并打印出来:

    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;

但是,我获得的输出因此被订购:

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

但是我不想为我的地图订购付出代价!这就是我使用unordered_map的原因......这里发生了什么？

附加说明:我正在使用gcc version 4.3.4 20090804 (release) 1 (GCC)并正在编译这样的g++ -std=c++0X maptest.cpp

Answer 1

"无序"并不意味着它会随机存储项目或维护您将它们放在地图中的顺序.它只是意味着你不能依赖任何特定的订购.您没有为订购付出代价,恰恰相反 - 实现并未明确地对项目进行排序,它是一个散列图并以其喜欢的方式存储其元素,这通常是一种非常高效的方式.事实上,当在地图上使用这些密钥和这个数字和操作顺序时,散列算法和地图的其他内部工作最终会按照看起来有序的顺序存储项目.例如,字符串可能会导致明显的随机布局.

另一方面,这可能是由于地图使用散列映射(至少一些)整数到自身并使用散列的低位(与地图大小要求一样多)来确定底层的索引数组(例如,CPython这样做 - 有一些非常聪明的补充来相对简单有效地处理冲突;出于同样的原因,CPython字符串和元组的散列是非常可预测的).