不要忘记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快。

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

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

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

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

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

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

另一个例子:一些哈希映射使用一个简单的节点列表作为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)

I was intrigued by the answer from @Jerry Coffin, which suggested that the ordered map would exhibit performance increases on long strings, after some experimentation (which can be downloaded from pastebin), I've found that this seems to hold true only for collections of random strings, when the map is initialised with a sorted dictionary (which contain words with considerable amounts of prefix-overlap), this rule breaks down, presumably because of the increased tree depth necessary to retrieve value. The results are shown below, the 1st number column is insert time, 2nd is fetch time.

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个归并排序。这意味着如果字符串键是相同的，合并字节字符串。最终的输出应该是排序的。这包括查找每一个插入。

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

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

来自: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 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.

总结

假设顺序不重要:

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

历史背景

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

It is widely believed that C++ ended up with ordered map as default because there are not too many parameters on how they can be implemented. On the other hand, hash based implementations has tons of things to talk about. So to avoid gridlocks in standardization they just got along with ordered map. Around 2005, many languages already had good implementations of hash based implementation and so it was more easier for the committee to accept new std::unordered_map. In a perfect world, std::map would have been unordered and we would have std::ordered_map as separate type.

性能

下面两张图不言自明:

以上所有的小补充:

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

关于插入的结论:

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

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

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