A recent talk about unordered_map in C++ made me realize that I should use unordered_map for most cases where I used map before, because of the efficiency of lookup ( amortized O(1) vs. O(log n) ). Most times I use a map, I use either int or std::string as the key type; hence, I've got no problems with the definition of the hash function. The more I thought about it, the more I came to realize that I can't find any reason of using a std::map over a std::unordered_map in the case of keys with simple types -- I took a look at the interfaces, and didn't find any significant differences that would impact my code.

因此,问题是:是否有任何真正的理由使用std::map而不是std::unordered_map在简单类型的情况下,如int和std::string?

我是从严格的编程角度提出这个问题的——我知道它并不是完全标准的,而且它可能会给移植带来问题。

另外,我认为正确答案之一可能是“对于较小的数据集更有效”,因为开销更小(是真的吗?)——因此,我希望将这个问题限制在键数量非普通的情况下(>1 024)。

编辑:哦,我忘记了显而易见的(感谢GMan!)——是的,地图当然是有序的——我知道,我正在寻找其他原因。


当前回答

我最近做了一个测试,做了50000个归并排序。这意味着如果字符串键是相同的,合并字节字符串。最终的输出应该是排序的。这包括查找每一个插入。

对于地图实现,完成这项工作需要200毫秒。对于unordered_map + map,插入unordered_map需要70 ms,插入map需要80 ms。所以混合实现快了50毫秒。

我们在使用地图之前应该三思。如果您只需要在程序的最终结果中对数据进行排序,那么混合解决方案可能会更好。

其他回答

如果你想比较std::map和std::unordered_map实现的速度,你可以使用谷歌的sparsehash项目,它有一个time_hash_map程序来计时。例如,在x86_64 Linux系统上使用gcc 4.4.2

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)

我最近做了一个测试,做了50000个归并排序。这意味着如果字符串键是相同的,合并字节字符串。最终的输出应该是排序的。这包括查找每一个插入。

对于地图实现,完成这项工作需要200毫秒。对于unordered_map + map,插入unordered_map需要70 ms,插入map需要80 ms。所以混合实现快了50毫秒。

我们在使用地图之前应该三思。如果您只需要在程序的最终结果中对数据进行排序,那么混合解决方案可能会更好。

以上所有的小补充:

当你需要按范围获取元素时,最好使用map,因为它们是排序的,你可以从一个边界迭代到另一个边界。

I was intrigued by the answer from @Jerry Coffin, which suggested that the ordered map would exhibit performance increases on long strings, after some experimentation (which can be downloaded from pastebin), I've found that this seems to hold true only for collections of random strings, when the map is initialised with a sorted dictionary (which contain words with considerable amounts of prefix-overlap), this rule breaks down, presumably because of the increased tree depth necessary to retrieve value. The results are shown below, the 1st number column is insert time, 2nd is fetch time.

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298

通过使用std::unordered_map,您可以声明在代码中任何地方都不依赖于被排序的映射。在某些情况下,这些附加的上下文信息可能有助于理解这个映射在程序中是如何实际使用的。随着性能作为一个副作用的到来,清晰度可能更加重要。

当然,当您需要使用有序映射时,没有编译器会阻止您使用无序映射,但这不大可能工作得很好,因此读者可能会认为这不是一个错误。