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


当前回答

这里没有真正充分提到的显著差异:

map keeps iterators to all elements stable, in C++17 you can even move elements from one map to the other without invalidating iterators to them (and if properly implemented without any potential allocation). map timings for single operations are typically more consistent since they never need large allocations. unordered_map using std::hash as implemented in the libstdc++ is vulnerable to DoS if fed with untrusted input (it uses MurmurHash2 with a constant seed - not that seeding would really help, see https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/). Being ordered enables efficient range searches, e.g. iterate over all elements with key ≥ 42.

其他回答

原因已在其他答案中给出;这是另一个。

std::map(平衡二叉树)操作平摊O(log n)和最坏情况O(log n)。 std::unordered_map(哈希表)操作平摊O(1)和最坏情况O(n)。

在实践中,哈希表每隔一段时间就会出现O(n)操作的“打嗝”,这可能是应用程序所能容忍的,也可能不是。如果它不能容忍,你更喜欢std::map而不是std::unordered_map。

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

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

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

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

哈希表具有比普通map实现更高的常量,这对于小型容器非常重要。最大尺寸是10个,100个,甚至1000个或更多?常数和以前一样,但是O(log n)接近O(k)。(记住,对数复杂度仍然很好。)

一个好的哈希函数取决于你的数据的特征;所以如果我不打算看一个自定义哈希函数(但肯定可以改变我的想法,而且很容易,因为我typedef几乎所有的东西),即使默认选择执行体面的许多数据源,我发现map的有序性质是足够的帮助,最初我仍然默认映射而不是哈希表在这种情况下。

另外,这样您甚至不必考虑为其他类型(通常是UDT)编写哈希函数,只需编写op<(无论如何您都想要)。

如果你想比较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)