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!)——是的,地图当然是有序的——我知道,我正在寻找其他原因。


当前回答

通过使用std::unordered_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::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)

来自:http://www.cplusplus.com/reference/map/map/

在内部,map中的元素总是按照其内部比较对象(类型为Compare)指示的特定严格弱排序标准的键进行排序。

Map容器通过键访问单个元素通常比unordered_map容器慢,但它们允许基于它们的顺序对子集进行直接迭代。”

以上所有的小补充:

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

如果你用Visual Studio 2010编译项目-忘记字符串的unordered_map。 如果你使用更现代的Studio,比如2017 -那么unordered_map比ordered map快得多。