我大致同意GMan的观点:根据使用类型的不同，std::map可以(而且通常)比std::tr1::unordered_map快(使用VS 2008 SP1中包含的实现)。

有几个复杂的因素需要记住。例如，在std::map中，您正在比较键，这意味着您只查看足够多的键的开头，以区分树的左右子分支。根据我的经验，几乎只有当你使用int这样可以在单个指令中进行比较的时候，你才会查看整个键。对于更典型的键类型，如std::string，通常只比较几个字符。

相比之下，一个像样的哈希函数总是查看整个键。IOW，即使查找表的复杂度是恒定的，哈希本身也具有大致的线性复杂度(尽管是键的长度，而不是项的数量)。使用长字符串作为键，std::map可能会在unordered_map开始搜索之前完成搜索。

其次，虽然有几种方法可以调整哈希表的大小，但大多数方法都非常慢——除非查找比插入和删除频繁得多，否则std::map通常会比std::unordered_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

以上所有的小补充:

当你需要按范围获取元素时，最好使用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快得多。