10

所以我在玩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

4

2 回答 2

10

“无序”并不意味着它会随机存储物品或保持您在地图中放置它们的顺序。这只是意味着您不能依赖任何特定的顺序。您无需为订购付出代价，恰恰相反 - 实现并没有明确订购项目，它是一个 hashmap 并以它喜欢的任何方式存储其元素，这通常是一种非常高效的方式。碰巧的是，哈希算法和映射的其他内部工作，当恰好使用这些键以及映射上的这个数量和操作顺序时，最终以看起来有序的顺序存储项目。例如，字符串可能会导致明显的随机布局。

附带说明一下，这可能是由于映射使用将（至少一些）整数映射到自身的哈希并使用哈希的低位（与映射大小要求一样多）来确定底层的索引数组（例如，CPython 做到了这一点——添加了一些非常聪明的附加功能来相对简单有效地处理冲突；出于同样的原因，CPython 字符串和元组的哈希值非常可预测）。

于 2011-07-29T23:49:14.193 回答
2

为了您的娱乐，这是 libc++ 的输出，它还具有用于std::hash<int>.

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

有几种方法可以实现散列容器，每种方法都有自己的权衡。

于 2011-07-30T02:13:20.427 回答