在键不重要的情况下，使用 map 比 unordered_map 有什么优势吗？

Question

最近的一个话题是关于 unordered_map 在 C++ 中让我意识到我应该使用 unordered_map 对于我使用的大多数情况 map 之前，由于查找的效率（ 摊销 O(1) 与 O(logn) ）。大多数时候我使用地图，我使用 int 或者 std::string 作为密钥类型；因此，我对哈希函数的定义没有任何问题。我想得越多，我就越意识到我找不到任何使用a的理由 std::map 在...之上 std::unordered_map 对于简单类型的键——我查看了接口，没有发现任何会影响我的代码的显着差异。

因此问题是：有什么真正的理由要使用 std::map 超过 std::unordered map 对于简单类型，例如 int 和 std::string?

我是从严格的编程角度来问的——我知道它没有完全被视为标准，并且它可能会带来移植问题。

另外，我希望正确的答案之一可能是 “对于较小的数据集更有效” 因为开销较小（这是真的吗？）——因此我想将问题限制在密钥数量不小的情况（> 1 024）。

编辑： 呃，我忘记了显而易见的事情（感谢 GMan！）——是的，地图当然是有序的——我知道这一点，并且正在寻找其他原因。

Answer 1

不要忘了map保持它的元素进行排序。如果你不能给说了，显然你不能使用unordered_map。

另外需要记住的是，unordered_map一般使用更多的内存。 map只是有几个看家指针，内存为每个对象。相反，unordered_map有一个大阵列（这些可以得到一些实现比较大的），然后额外的内存为每个对象。如果你需要记忆感知，map应更好地证明，因为它缺乏大阵。

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

只需从个人的经验，我在主实体查找表使用unordered_map代替map当发现在性能（测得的，当然）一个巨大的改进。

在另一方面，我发现这是慢得多在反复插入和删除元素。它为元素的相对静态的收集是伟大的，但如果你正在做吨插入和删除的哈希+桶装似乎积少成多。 （注意，这是在许多迭代。）

Answer 2

如果您想要对比std::map和std::unordered_map实现的速度，你可以使用谷歌的的具有time_hash_map程序时间他们sparsehash 项目。例如，与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)

Answer 3

我回声大致相同的点GMAN制成：根据使用的类型，std::map可以是（并且通常是）比std::tr1::unordered_map更快（使用包括在VS 2008 SP1执行）

。

有一些复杂的因素要牢记。例如，在std::map，你比较键，这意味着你永远只能看一个关键的权利和树的左子分支之间区分的开始就够了。根据我的经验，几乎你看一下整个键唯一的一次是，如果你正在使用的东西如int，你可以在一个单一的指令进行比较。有了一个比较典型的密钥类型一样的std :: string，你往往只比较几个字符左右。

一个体面散列函数，相比之下，总是着眼于整个键。 IOW，即使表查找是恒定的复杂性，所述散列本身具有大致线性的复杂性（虽然在键，而不是物品的数量的长度）。随着长串钥匙，一个std::map可能完成搜索之前unordered_map甚至会的启动的其搜索。

其次，虽然有调整哈希表的几种方法，其中大部分是相当缓慢的 - 到如此地步，除非是查找的相当的比插入和缺失更频繁，性病::地图将通常比std::unordered_map更快。

当然，正如我在以前的问题的评论中提及了，你也可以使用的树表。这有优点也有缺点。一方面，它限制了最坏的情况下，一个树。它还允许快速的插入和删除，因为（至少当我已经做到了），我用表的固定大小。消除的所有的表大小调整可以让你保持你的哈希表非常简单并且通常更快。

另一点：用于散列和基于树的地图的要求是不同的。显然散列需要一个散列函数和相等比较，其中责令地图需要小于比较。当然，我所提到的混合动力车既需要。当然，对于使用字符串作为关键的常见的情况，这是不是一个真正的问题，但有些类型的键套装订货比散列（反之亦然）更好。

Answer 4

我对 @Jerry Coffin 的答案很感兴趣，它表明经过一些实验（可以从 帕斯特宾），我发现这似乎只适用于随机字符串的集合，当使用排序字典（其中包含具有大量前缀重叠的单词）初始化映射时，此规则会失效，大概是因为增加检索价值所需的树深度。结果如下所示，第一个数字列是插入时间，第二个数字列是提取时间。

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

Answer 5

我只想指出，......有许多种unordered_maps的。

中查找维基百科文章哈希地图。根据该实施使用，以查找的长期特征，插入和删除可能相当显著变化。

这就是我担心的最有加unordered_map的STL的：他们将不得不选择一个特定的实现，我怀疑他们会去的Policy道路，所以我们将被固定在了一个实现平均使用并没有对其他情况下...

例如一些散列映射具有线性重散列，其中，代替在一次重散列整个散列映射，一个部分是在翻版每个插入，这有助于分摊成本。

另一个例子：一些哈希映射使用节点的简单列表的桶，其他人使用的地图，别人不使用节点，但找到最近的槽，最后有些人会使用的节点列表，但重新排序，以便最后访问的元素是在前面（如高速缓存的东西）。

因此，在此刻我倾向于选择std::map或者一个loki::AssocVector（用于冷冻的数据集）。

不要误会我的意思，我想用std::unordered_map，我可能在未来，但是当你想实现它所有的方法和它很难“信任”这样一个容器的便携性各种性能即这种结果。

Answer 6

此处尚未充分提及的显着差异：

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

Answer 7

哈希表具有比普通的映射实现，这成为小容器显著更高常数。最大尺寸为10，100，或者甚至1000以上？常量是和以前一样，但O（log n）的接近O（K）。 （记住对数复杂度仍然确实好。）

什么是好的哈希函数取决于数据的特性;所以，如果我不打算寻找一个自定义的散列函数（但以后肯定可以改变我的想法，并且很容易，因为我的typedef差点儿一切）和即使默认设置被选择为许多数据源进行体面，我觉得有序地图的性质是足够的帮助下开始，我仍然默认映射，而不是在这种情况下，哈希表。

另外这样你就不必别想写其他（通常UDT）类型，只是写运<（您想反正）的哈希函数。

Answer 8

我做了一个测试最近这使得50000归并排序及。这意味着，如果该字符串密钥是相同的，合并的字节串。而最终的输出应进行排序。因此，这包括一个查找每插入。

有关的map实施方式中，它需要200毫秒来完成这项工作。对于unordered_map + map，需要花费70毫秒unordered_map插入和80毫秒map插入。因此，混合实现为50ms更快。

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

Answer 9

原因已经在其他的答案被给予;这里是另一个

的std ::地图（平衡二进制树）操作是摊销O（log n）的和最坏情况下的O（log n）的。 的std :: unordered_map（哈希表）操作是摊销O（1）和最坏情况下为O（n）。

这怎么发挥出来的做法是，哈希表“打嗝”每一次与O（n）的操作，可能会或可能不会有事您的应用程序可以容忍一段时间。如果无法忍受，你更喜欢的std ::地图上的std :: unordered_map。

Answer 10

概括

假设顺序并不重要：

• 如果您要构建一次大型表并执行大量查询，请使用 std::unordered_map
• 如果您要构建小表（可能少于 100 个元素）并执行大量查询，请使用 std::map. 。这是因为它的读取是 O(log n).
• 如果你要经常换桌子的话 或许 std::map 是不错的选择。
• 如果您有疑问，请使用 std::unordered_map.

历史背景

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

它被广泛 相信 C++ 最终以有序映射作为默认值，因为关于如何实现它们没有太多参数。另一方面，基于哈希的实现有很多值得讨论的事情。因此，为了避免标准化方面的僵局，他们 刚刚相处 与有序的地图。2005年左右，许多语言已经有了基于哈希的良好实现，因此委员会更容易接受新的 std::unordered_map. 。在一个完美的世界里， std::map 会是无序的，我们会 std::ordered_map 作为单独的类型。

表现

下面两张图应该能说明问题（来源):

Answer 11

小除了上述所有：

更好地利用map，当你需要获得通过一系列的元素，因为它们排序，你可以在它们之间迭代从一个边界到另一个。

Answer 12

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

“在内部，在图中的元素通常由它的密钥的特定严格弱排序准则表示由其内部比较对象（的类型比较）以下来分类的。

地图容器通常比unordered_map容器可以通过键访问各个元件慢，但它们允许基于它们的顺序上的子集的直接迭代。“