我认为这个问题已经部分回答了，因为没有提供关于以“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

来自: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时，性能有了巨大的改进(当然是度量的)。

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

通过使用std::unordered_map，您可以声明在代码中任何地方都不依赖于被排序的映射。在某些情况下，这些附加的上下文信息可能有助于理解这个映射在程序中是如何实际使用的。随着性能作为一个副作用的到来，清晰度可能更加重要。

当然，当您需要使用有序映射时，没有编译器会阻止您使用无序映射，但这不大可能工作得很好，因此读者可能会认为这不是一个错误。

我大致同意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快。

当然，就像我在对你上一个问题的评论中提到的，你也可以使用树表。这既有优点也有缺点。一方面，它将最坏的情况限制在一棵树上。它还允许快速插入和删除，因为(至少当我这样做时)我使用了固定大小的表。消除所有的表大小调整可以让你的哈希表更简单，通常更快。

另一点:哈希和基于树的映射的需求是不同的。哈希显然需要一个哈希函数和一个相等比较，其中有序映射需要一个小于比较。当然，我提到的混合型需要两者兼备。当然，对于使用字符串作为键的常见情况，这并不是真正的问题，但某些类型的键比哈希更适合排序(反之亦然)。

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

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

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