在微不足道的键的情况下，使用 map 而不是 unordered_map 有什么优势吗？

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

还有一点需要记住的是，unordered_map 通常会使用更多内存。 map 只有几个管理指针和每个对象的内存。相反，unordered_map 有一个大数组（在某些实现中这些数组可能会变得很大），然后为每个对象提供额外的内存。如果您需要了解内存，map 应该会更好，因为它缺少大数组。

因此，如果您需要纯粹的查找检索，我会说 unordered_map 是要走的路。但是总是有取舍的，如果你买不起，那么你就不能使用它。

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

另一方面，我发现重复插入和删除元素要慢得多。这对于相对静态的元素集合来说非常有用，但是如果您要进行大量的插入和删除，那么散列 + 分桶似乎会加起来。 （注意，这是经过多次迭代。）

---

如果您想比较 std::map 和 std::unordered_map 实现的速度，可以使用 Google 的 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)

---

我会回应 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。

当然，正如我在上一个问题的评论中提到的，您也可以使用树表。这既有优点也有缺点。一方面，它将最坏的情况限制在树上。它还允许快速插入和删除，因为（至少在我完成后）我使用了固定大小的表。消除所有表大小调整可以让您的哈希表更简单，通常更快。

还有一点：散列和基于树的映射的要求是不同的。散列显然需要散列函数和相等比较，其中有序映射需要小于比较。当然，我提到的混合动力车两者都需要。当然，对于使用字符串作为键的常见情况，这并不是真正的问题，但某些类型的键比散列更适合排序（反之亦然）。

---

我对@Jerry Coffin 的回答很感兴趣，这表明经过一些实验（可以从 pastebin 下载），有序映射会在长字符串上表现出性能提升，我发现这似乎只适用对于随机字符串的集合，当使用排序字典（包含具有大量前缀重叠的单词）初始化映射时，此规则会失效，可能是因为检索值所需的树深度增加。结果如下图，第 1 列是插入时间，第 2 列是获取时间。

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

---

这里没有真正充分提及的重大差异：

map 使所有元素的迭代器保持稳定，在 C++17 中，您甚至可以将元素从一个映射移动到另一个映射，而不会使迭代器失效（并且如果在没有任何潜在分配的情况下正确实现）。

单个操作的映射时间通常更一致，因为它们从不需要大量分配。

使用在 libstdc++ 中实现的 std::hash 的 unordered_map 如果输入不受信任的输入，则容易受到 DoS 的攻击（它使用带有恒定种子的 MurmurHash2 - 并不是说种子真的有帮助，请参阅 https://emboss.github.io/blog/2012 /12/14/break-murmur-hash-flooding-dos-reloaded/)。

排序可以实现有效的范围搜索，例如迭代所有 key ≥ 42 的元素。

---

我只想指出...有很多种unordered_map。

在哈希图上查找 Wikipedia Article。根据使用的实现，查找、插入和删除方面的特征可能会有很大差异。

这就是在 STL 中添加 unordered_map 时我最担心的问题：他们将不得不选择一个特定的实现，因为我怀疑他们会走 Policy 的道路，所以我们将被困在一个实现平均使用量，其他情况没有...

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

另一个例子：一些哈希映射使用简单的节点列表作为存储桶，其他使用映射，其他不使用节点但找到最近的槽，最后一些将使用节点列表但重新排序以便最后访问的元素在前面（就像一个缓存的东西）。

所以目前我倾向于使用 std::map 或者可能是 loki::AssocVector（用于冻结数据集）。

不要误会我的意思，我想使用 std::unordered_map 并且将来可能会使用，但是当您想到实现它的所有方式以及各种表演的结果。

---

概括

假设顺序不重要：

如果您要构建一次大表并进行大量查询，请使用 std::unordered_map

如果您要构建小表（可能少于 100 个元素）并进行大量查询，请使用 std::map。这是因为读取它是 O(log n)。

如果您要经常更改表格，那么 std::map 可能是不错的选择。

如果您有疑问，只需使用 std::unordered_map。

历史背景

在大多数语言中，无序映射（又名基于哈希的字典）是默认映射，但是在 C++ 中，您将有序映射作为默认映射。那是怎么发生的？有些人错误地认为 C++ 委员会以他们独特的智慧做出了这个决定，但不幸的是，事实比这更丑陋。

广泛believed C++ 最终以有序映射为默认值，因为没有太多关于如何实现它们的参数。另一方面，基于散列的实现有很多事情要谈。因此，为了避免标准化中的僵局，他们just got along使用有序地图。在 2005 年左右，许多语言已经有了很好的基于散列的实现，因此委员会更容易接受新的 std::unordered_map。在一个完美的世界中，std::map 将是无序的，我们会将 std::ordered_map 作为单独的类型。

表现

下面的两个图表应该不言自明（source）：

https://i.stack.imgur.com/zN3lx.png

https://i.stack.imgur.com/U8qDO.png

---

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

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

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

---

哈希表具有比普通映射实现更高的常量，这对于小型容器来说非常重要。最大尺寸是 10、100，甚至可能是 1,000 或更多？常数和以往一样，但 O(log n) 接近 O(k)。 （记住对数复杂度仍然非常好。）

什么是好的散列函数取决于数据的特征；因此，如果我不打算查看自定义哈希函数（但以后肯定会改变主意，而且很容易，因为我在所有东西附近都键入了该死的），即使选择默认值以对许多数据源执行得体，我发现有序map 的性质最初足以提供帮助，在这种情况下，我仍然默认使用 map 而不是哈希表。

另外，您甚至不必考虑为其他（通常是 UDT）类型编写散列函数，只需编写 op< （无论如何您都想要）。

---

我最近做了一个测试，可以进行 50000 次合并和排序。这意味着如果字符串键相同，则合并字节字符串。最后的输出应该是排序的。所以这包括对每个插入的查找。

对于 map 实施，完成作业需要 200 毫秒。对于 unordered_map + map，unordered_map 插入需要 70 毫秒，map 插入需要 80 毫秒。所以混合实现要快 50 毫秒。

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

---

我认为这个问题得到了部分回答，因为没有提供有关“int”类型作为键的性能的信息。我进行了自己的分析，发现在使用整数作为键的许多实际情况下，std::map 的性能（在速度上）优于 std::unordered_map。

整数测试

测试场景包括使用顺序和随机键填充映射，并使用长度在 [17:119] 范围内的字符串值（以 17 的倍数）。使用元素计数在 [10:100000000] 范围内以 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

https://i.stack.imgur.com/LSLE4.png

插入结论：

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

https://i.stack.imgur.com/UwxBQ.png

查找结论：

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

https://i.stack.imgur.com/rxouP.png

查找失败的结论：

搜索未命中对 std::map 有很大影响。

一般结论

即使在需要速度的情况下，整数键的 std::map 在许多情况下仍然是更好的选择。作为一个实际的例子，我有一个字典，其中查找永远不会失败，虽然键的分布很稀疏，但它的执行速度与 std::unordered_map 相同，因为我的元素计数低于 1K。并且内存占用显着降低。

字符串测试

作为参考，我在这里介绍了 string[string] 映射的时间安排。密钥字符串由随机 uint64_t 值形成，值字符串与其他测试中使用的相同。

Labels:

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

https://i.stack.imgur.com/HK8d7.png

评估平台

操作系统：Linux - OpenSuse Tumbleweed

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

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

内存：64Gb

---

以上所有内容的小补充：

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

---

如果您使用 Visual Studio 2010 编译项目 - 忘记字符串的 unordered_map。如果您使用更现代的 Studio，例如 2017 - 那么 unordered_map 比有序地图快得多。

---

通过使用无序映射，您可以声明代码中没有任何地方依赖被排序的映射。在某些情况下，此附加上下文信息可能有助于了解此映射在程序中的实际使用方式。清晰度可能更重要，因为性能是副作用。

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

---

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

“在内部，地图中的元素始终按照其内部比较对象（比较类型）指示的特定严格弱排序标准按其键排序。

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

---