为什么我的 unordered_map 会自行排序？
所以我正在使用 STL 中新标准化的 unordered_map。我的代码有点像这样，我只是创建一个 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
So I was playing with the newly standardized unordered_map from the STL. The code I have is kinda like this, I just create an unordered_map, fill it up, 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 thusly:
1 mary
2 had
3 a
4 little
5 lamb
6 whose
7 fleece
8 was
9 all
10 fleecey
But I don't want to pay the price to have my map ordered! That is why I am using an unordered_map... What is going on here?
additional note: I am using gcc version 4.3.4 20090804 (release) 1 (GCC) and am compiling like this g++ -std=c++0X maptest.cpp
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
“无序”并不意味着它将随机存储物品或保持您在地图中放置物品的顺序。这只是意味着您不能依赖任何特定的顺序。您不需要为排序付出代价，恰恰相反 - 实现并没有显式地对项目进行排序，它是一个哈希图，并以任何它喜欢的方式存储其元素，这通常是一种非常高效的方式。碰巧的是，当哈希算法和映射的其他内部工作原理恰好使用这些键以及映射上的操作数量和顺序时，最终会以看起来有序的顺序存储项目。例如，字符串可能会导致明显随机的布局。
顺便说一句，这可能是由于映射使用将（至少一些）整数映射到自身的哈希并使用哈希的较低位（与映射大小要求一样多）来确定基础索引的索引造成的数组（例如，CPython 就是这样做的 - 通过一些非常的巧妙添加来相对简单有效地处理冲突；出于同样的原因，CPython 字符串和元组的哈希值非常可预测）。
"Unordered" doesn't mean it will store the items randomly or maintain the order you put them in the map. It just means you can't rely on any particular ordering. You don't pay a price for ordering, quite the contrary - the implementation isn't explicitly ordering the items, it's a hashmap and stores its elements in whatever way it pleases, which usually is a pretty performant way. It just so happens that the the hashing algorithm and other internal workings of the map, when using exactly these keys and this number and order of operations on the map, end up storing the items in a order that looks ordered. Strings, for example, may lead to an apparently randomized layout.
On a side note, this is probably caused by the map using a hash that maps (at least some) integers to itself and using the lower bits (as many as the map size mandates) of the hash the to determine the index for the underlying array (for instance, CPython does this - with some very clever additions to handle collisions relatively simply and efficiently; for the same reason the hashes of CPython strings and tuples are very predictable).
为了您的娱乐，这里是 libc++ 的输出，它还有一个 std::hash的标识函数。
有多种方法可以实现哈希容器，每种方法都有自己的权衡。
For your amusement, here's the output from libc++, which also has an identity function for
std::hash<int>.There are several ways to implement a hash container, each with its own tradeoffs.