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,因为它们是排序的,你可以从一个边界迭代到另一个边界。

其他回答

不要忘记map保持其元素的顺序。如果你不能放弃它,显然你不能使用unordered_map。

另外需要记住的一点是,unordered_map通常会使用更多的内存。Map只有一些内部指针和每个对象的内存。相反,unordered_map有一个大数组(在某些实现中会变得相当大),然后为每个对象提供额外的内存。如果需要内存感知,map应该会更好,因为它缺少大数组。

所以,如果你需要纯粹的查找-检索,我认为unordered_map是最好的方法。但总会有权衡,如果你负担不起,那你就不能使用它。

仅凭个人经验,我发现在主实体查找表中使用unordered_map而不是map时,性能有了巨大的改进(当然是度量的)。

另一方面,我发现它在重复插入和删除元素时要慢得多。它非常适合相对静态的元素集合,但如果您正在进行大量的插入和删除,那么哈希+桶似乎就会累加起来。(注意,这需要经过多次迭代。)

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

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.

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

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

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

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

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

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

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