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


当前回答

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

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

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

其他回答

我只是想指出……有很多种unordered_map。

在哈希图上查找维基百科文章。根据所使用的实现的不同,查找、插入和删除方面的特征可能有很大差异。

这是我最担心的添加unordered_map到STL:他们将不得不选择一个特定的实现,因为我怀疑他们会走政策的道路,所以我们将被困在一个实现的平均使用,而没有其他情况…

例如,一些哈希映射具有线性重新哈希,其中不是一次重新哈希整个哈希映射,而是在每次插入时重新哈希一部分,这有助于分摊成本。

另一个例子:一些哈希映射使用一个简单的节点列表作为bucket,其他使用map,其他不使用节点,但找到最近的槽,最后一些将使用节点列表,但重新排序,以便最后访问的元素位于前面(像缓存一样)。

因此,目前我倾向于std::map或loki::AssocVector(用于冻结数据集)。

不要误解我的意思,我希望使用std::unordered_map,将来也可能会使用,但是当您想到实现它的所有方法和由此产生的各种性能时,很难“信任”这样一个容器的可移植性。

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

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

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

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

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

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

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

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

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

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

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

我认为这个问题已经部分回答了,因为没有提供关于以“int”类型作为键的性能的信息。我做了我自己的分析,我发现std::map在许多实际情况下使用整数作为键时可以胜过std::unordered_map(在速度上)。

整数测试

测试场景包括使用顺序键和随机键填充映射,以及长度为17的倍数[17:119]的字符串值。执行测试时,元素计数范围为[10:10000000],以10为幂。

Labels:

Map64: std::map<uint64_t,std::string>
Map32: std::map<uint32_t,std::string>
uMap64: std::unordered_map<uint64_t,std::string>
uMap32: std::unordered_map<uint32_t,std::string>

插入

Labels:

Sequencial Key Insert: maps were constructed with keys in the range [0-ElementCount]
Random Key Insert: maps were constructed with random keys in the full range of the type

关于插入的结论:

当映射大小小于10000个元素时,在std::map中插入展开键往往优于std::unordered_map。 在std::map中插入密集键在1000个元素下与std::unordered_map没有性能差异。 在所有其他情况下,std::unordered_map往往执行得更快。

查找

Labels:

Sequential Key - Seq. Search: Search is performed in the dense map (keys are sequential). All searched keys exists in the map.
Random Key - Rand. Search: Search is performed in the sparse map (keys are random). All searched keys exists in the map.

(label names can be miss leading, sorry about that)

关于查阅的结论:

当地图大小小于1000000个元素时,在std::map上的搜索往往略优于std::unordered_map。 密集std::map的搜索性能优于std::unordered_map

查询失败

Labels:

Sequential Key - Rand. Search: Search is performed in the dense map. Most keys do not exists in the map.
Random Key - Seq. Search: Search is performed in the sparse map. Most keys do not exists in the map.

(label names can be miss leading, sorry about that)

关于查找失败的结论:

在std::map中搜索缺失是一个很大的影响。

一般的结论

即使在需要速度时,std::map用于整数键在许多情况下仍然是更好的选择。举个实际的例子,我有一本字典 在这里查找从未失败,尽管键具有稀疏分布,但它将在与std::unordered_map相同的速度下执行得更差,因为我的元素计数低于1K。内存占用显著降低。

字符串的测试

为了供参考,我在这里给出了字符串[string]映射的计时。键字符串是由一个随机的uint64_t值形成的,值字符串是在其他测试中使用的相同。

Labels:

MapString: std::map<std::string,std::string>
uMapString: std::unordered_map<std::string,std::string>

评价平台

操作系统:Linux - OpenSuse风滚草

编译器:g++ (SUSE Linux) 11.2.1 20210816

CPU: Intel(R) Core(TM) i9-9900 CPU @ 3.10GHz

内存:64 gb