在普通键的情况下，使用map比unordered_map有什么优势吗?

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

另一件需要记住的事情是unordered_map通常使用更多的内存。map只有几个内部指针和每个对象的内存。相反，unordered_map有一个很大的数组(在某些实现中会变得相当大)，然后每个对象都有额外的内存。如果你需要内存感知，map应该被证明更好，因为它缺少大数组。

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

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

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

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

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

另外，这样你甚至不必考虑为其他类型(通常是UDT)编写哈希函数，只需编写op<(这是你想要的)。

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

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

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

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

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

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

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

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

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

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

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

我对@Jerry Coffin的回答很感兴趣，这表明有序映射将在长字符串上表现出性能的提高，经过一些实验(可以从pastebin下载)，我发现这似乎只适用于随机字符串的集合，当映射被一个排序字典初始化时(其中包含有相当多前缀重叠的单词)，这条规则就失效了，大概是因为检索值所需的树深度增加了。结果如下所示，第一列数字是插入时间，第二列是取回时间。

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
** Integer Keys **
unordered:      137      15
ordered:      168      81
** Random String Keys **
unordered:       55      50
ordered:       33      31
** Real Words Keys **
unordered:      278      76
ordered:      516     298

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

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

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

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

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

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

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

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

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

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

• map使指向所有元素的迭代器保持稳定，在c++ 17中，你甚至可以将元素从一个map移动到另一个map，而不使指向它们的迭代器失效(如果正确实现，没有任何潜在的分配)。
• 单个操作的map计时通常更一致，因为它们从不需要大的分配。
• unordered_map使用libstdc++中实现的std::hash，如果提供不受信任的输入，则容易受到DoS的攻击(它使用带有常量种子的MurmurHash2 -种子并不是真正有帮助，请参阅https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/)。
• 排序可以实现高效的范围搜索，例如遍历键≥42的所有元素。

总结

假设顺序不重要:

• 如果你打算一次构建一个大表，并进行大量查询，请使用std::unordered_map
• 如果你要构建一个小表(可能少于100个元素)并进行大量查询，请使用std::map。这是因为对它的读取是O(log n)。
• 如果你要改变表很多，那么可能是 std::map是一个不错的选择。
• 如果你有疑问，就使用std::unordered_map。

历史背景

在大多数语言中，无序映射(又名基于哈希的字典)是默认映射，但在c++中，你得到的是有序映射作为默认映射。这是怎么发生的?有些人错误地认为c++委员会用他们独特的智慧做出了这个决定，但不幸的是，事实比这更丑陋。

c++最终将ordered map作为默认值，这是普遍的相信，因为没有太多参数来决定如何实现它们。另一方面，基于哈希的实现有很多东西需要讨论。因此，为了避免标准化的僵局，他们只是相处得不错与有序的地图。大约在2005年，许多语言已经有了很好的基于哈希的实现，因此委员会更容易接受新的std::unordered_map。在完美的情况下，std::map应该是无序的，我们将std::ordered_map作为单独的类型。

性能

下面两个图表应该说明自己(源):

以上所有的小补充:

当你需要按范围获取元素时，最好使用map，因为它们是排序的，你可以从一个边界迭代到另一个边界。

如果你用Visual Studio 2010编译项目-忘记字符串的unordered_map。 如果你使用更现代的Studio，比如2017 -那么unordered_map比ordered 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

< / p >

关于插入的结论:

• 当映射大小小于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)

< / p >

关于查找的结论:

• 当地图大小小于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)

< / p >

关于查找失败的结论:

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

一般的结论

字符串的测试

作为参考，我在这里给出了字符串(字符串)映射的计时。键字符串是由一个随机的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

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

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