在普通键的情况下使用map over unordered_map有什么好处吗？

Question

最近关于C ++中的unordered_map的讨论使我意识到我应该在之前使用unordered_map的大多数情况下使用map，因为查找效率（摊销的O（1）与O（log n））。大多数时候我使用地图，我使用int或std::string作为关键类型;因此，我对哈希函数的定义没有任何问题。我越是想到它，我就越发现，在简单类型的键的情况下，我找不到任何使用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
• 如果您要构建小表（可能不到100个元素）并进行大量查询，请使用O(log n)。这是因为读取它是std::map。
• 如果你要更换表，那么可能是std::unordered_map是不错的选择。
• 如果您有疑问，请使用believed。

历史背景

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

广泛的just got along，C ++最终将有序映射作为默认值，因为没有太多参数可以实现它们。另一方面，基于散列的实现有很多东西需要讨论。因此，为了避免标准化中的僵局，他们std::unordered_map与有序地图。大约在2005年，许多语言已经有很好的基于哈希的实现实现，因此委员会更容易接受新的std::map。在一个完美的世界中，std::ordered_map将是无序的，我们将source作为单独的类型。

性能

下面两张图应该说明一点（）：

map

Answer 3

以上所有内容的小增加：

当你需要按范围获取元素时，更好地使用http://www.cplusplus.com/reference/map/map/，因为它们是有序的，你可以从一个边界迭代到另一个边界。

Answer 4

来自：qazxswpoi

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

map容器通常比unordered_map容器慢，可以通过键来访问各个元素，但是它们允许根据子集的顺序直接迭代子集。“

Answer 5

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

Answer 6

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

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

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

Answer 7

我对@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

Answer 8

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

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

通过向STL添加unordered_map，最让我担心的是：他们将不得不选择一个特定的实现，因为我怀疑它们会沿着Policy路走下去，所以我们将坚持使用平均使用的实现和没有其他案件......

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

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

所以目前我倾向于选择std::map或者更喜欢loki::AssocVector（用于冻结数据集）。

不要误会我的意思，我想将来使用std::unordered_map，但是当你想到实现它的所有方法以及各种各样的性能时，很难“信任”这种容器的可移植性。结果。

Answer 9

Significant differences that have not really been adequately mentioned here:

• map使所有元素的迭代器保持稳定，在C ++ 17中，您甚至可以将元素从一个map移动到另一个map，而不会使迭代器失效（如果没有任何可能的分配，则正确实现）。
• 单个操作的unordered_map时序通常更加一致，因为它们从不需要大量分配。
• std::hash使用https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/在libstdc ++中实现，如果使用不受信任的输入，它很容易受到DoS的影响（它使用具有常量种子的MurmurHash2 - 不是播种真的有帮助，请参阅map）。
• 被订购可实现有效的范围搜索，例如用密钥≥42迭代所有元素。

Answer 10

散列表具有比常见映射实现更高的常量，这对于小容器来说变得很重要。最大尺寸是10,100，甚至可能是1,000或更多？常量与以前相同，但O（log n）接近O（k）。 （记住对数复杂性仍然非常好。）

良好散列函数的作用取决于数据的特征;因此，如果我不打算查看自定义哈希函数（但后来肯定会改变我的想法，而且很容易因为我在所有内容附近输入），即使默认选择对许多数据源执行得体，我发现有序地图的本质是足够的帮助最初我仍然默认映射而不是在这种情况下的哈希表。

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

Answer 11

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

对于unordered_map实现，完成工作需要200毫秒。对于map + unordered_map，map插入需要70 ms，map插入需要80 ms。因此混合实现速度提高了50毫秒。

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

Answer 12

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

std :: map（平衡二叉树）操作分摊为O（log n），最差情况为O（log n）。 std :: unordered_map（哈希表）操作分摊为O（1），最差情况为O（n）。

这在实践中如何发挥作用是哈希表每隔一段时间用一次O（n）操作“打嗝”，这可能是你的应用程序可以容忍的东西，也可能不是。如果它不能容忍它，你更喜欢std :: map over std :: unordered_map。