在琐碎的键的情况下，使用map over unordered_map有什么好处吗？
最近在C ++中讨论unordered_map使我意识到，由于查找的效率（ 分段O（1）与O（log n） ），我应该使用unordered_map来处理以前使用map大多数情况。 大多数时候我使用一个映射，我使用int或std::strings作为键，因此我没有问题的散列函数的定义。 我想到的越多，就越意识到我找不到在unordered_map上使用简单types的情况下使用std::map任何原因 – 我查看了接口，并没有发现任何会影响我的代码的重大差异。
因此，这个问题是否有任何真正的理由使用简单的types如int和std::string情况下unordered map使用std::map ？
我从严格的编程观点来问 – 我知道这不是完全被认为是标准的，它可能会带来移植的问题。
另外，我希望正确答案之一可能是“对于较小的数据集更有效”，因为开销较小（这是真的吗？） – 因此，我想限制问题的情况下，密钥的数量是非平凡的（> 1 024）。
编辑： 呃，我忘了明显的（谢谢GMan！） – 是的，地图的顺序是当然的 – 我知道，我正在寻找其他原因。
不要忘记map保持他们的元素sorting。 如果你不能放弃，显然你不能使用unordered_map 。
还有一点要记住的是， unordered_map通常使用更多的内存。 一个map只有几个pipe家指针，然后每个对象的内存。 相反， unordered_map有一个很大的数组（在某些实现中可能会变得很大），然后为每个对象增加内存。 如果你需要内存感知， map应该certificate更好，因为它缺乏大arrays。
所以，如果你需要纯粹的查找检索，我会说一个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大致相同的点：根据使用的types， std::map可以（通常是）比std::tr1::unordered_map （使用VS 2008 SP1中包含的实现）更快。
记住一些复杂的因素。 例如，在std::map ，你是比较键的，这意味着你只能看到一个键的开始，以便区分树的右侧和左侧子分支。 根据我的经验，几乎你唯一一次看到整个关键是如果你使用像int这样的东西，你可以在一个单一的指令进行比较。 使用像std :: string这样更典型的键types，通常只比较几个字符。
一个体面的哈希函数，相反，总是看着整个关键。 IOW，即使表查找是不变的复杂性，散列本身也具有大致线性的复杂性（尽pipe在密钥的长度上，而不是在项的数量上）。 以长string作为键， std::map可能会在unordered_map甚至开始search之前完成search。
其次，有几种方法调整哈希表的大小，其中大部分都非常慢 – 除非查找比插入和删除更频繁，否则std :: map通常比std::unordered_map要快。
当然，正如我在上一个问题的评论中提到的那样，你也可以使用树形表格。 这既有优点也有缺点。 一方面，它把最坏的情况限制在一棵树上。 它也允许快速插入和删除，因为（至less当我做完了）我已经使用了一个固定大小的表。 消除所有表格大小调整允许你保持你的哈希表更简单，通常更快。
编辑：哎呀，我差点忘了提及另一点：哈希和基于树的地图的要求是不同的。 散列显然需要一个散列函数和一个等式比较，其中有序地图需要比较less的比较。 当然，我提到的混合体需要两个。 当然，对于使用string作为键的常见情况，这不是一个真正的问题，但是某些types的键适合比散列更好（反之亦然）。
我对@Jerry Coffin的回答很感兴趣，它build议有序地图在经过一些实验（可以从pastebin下载）之后会在长string上performance出性能的提高，我发现这似乎只适用于集合随机string，当映射被初始化为一个已sorting的字典（其中包含具有相当数量的前缀重叠的字）时，这个规则崩溃了，大概是因为增加了检索值所需的树深度。 结果如下所示，第一个数字列是插入时间，第二个是取时间。
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
我只想指出…有很多种unordered_map 。
在散列图上查找维基百科文章 。 取决于使用哪种实现方式，查找，插入和删除方面的特性可能差异很大。
最令我担心的是在STL中增加了unordered_map ：他们将不得不select一个特定的实现，因为我怀疑他们会走下Policy道路，所以我们将坚持一个平均使用的实现没有其他情况下…
例如，一些哈希映射具有线性重新哈希，而不是一次重新哈希整个哈希映射，而是在每次插入时重新哈希一个部分，这有助于分摊成本。
另一个例子：一些哈希映射为一个桶使用了一个简单的节点列表，另一些哈希映射使用了一个映射，另外一些不使用节点，但是find最近的时隙，最后一些将使用节点列表，但是重新sorting它们，以便最后访问的元素在前面（就像caching的东西）。
所以目前我倾向于selectstd::map或者一个loki::AssocVector （用于冻结数据集）。
不要误解我的意思，我想使用std::unordered_map ，我可能会在将来，但是当你想到实现它的所有方法时，很难“信任”这个容器的可移植性，各种各样的表演。
哈希表比普通的映射实现具有更高的常量，这对于小型容器来说是非常重要的。 最大尺寸是10,100，甚至可能是1000或更多？ 常数与以往相同，但O（log n）接近于O（k）。 （记住对数复杂性还是非常好的。）
什么使得一个好的散列函数取决于你的数据的特性; 所以如果我不打算查看一个自定义的散列函数（但是以后肯定会改变我的想法，并且很容易，因为我键入的是该死的附近的所有内容），即使默认select了适合许多数据源的体面，我发现这个命令在这种情况下，映射的本质是足够的帮助，我仍然默认映射，而不是哈希表。
另外，您甚至不必为其他（通常是UDT）types编写散列函数，而只需写op <（无论如何）。
我最近做了一个testing，使得50000合并和sorting。 这意味着如果string键是相同的，合并字节string。 最后的输出应该被sorting。 所以这包括查找每个插入。
对于map实现，完成作业需要200毫秒。 对于unordered_map + map ， unordered_map插入花费70毫秒， map插入花费80毫秒。 所以混合实现速度要快50ms。
在使用map之前，我们应该三思。 如果您只需要在程序的最终结果中对数据进行sorting，那么混合解决scheme可能会更好。
这里没有充分提到的重大差异：
-
map保持所有元素的迭代器稳定，在C ++ 17中，甚至可以将元素从一个map移动到另一个map，而不会使向它们无效的迭代器失效（如果在没有任何潜在分配的情况下正确实施）。 - 单个操作的
map时间通常更一致，因为他们从不需要大的分配。 - 在libstdc ++中使用
std::hashunordered_map使用不可信input的情况下容易受到DoS的攻击（它使用MurmurHash2和一个常量种子 – 这种种子不会真正起作用，请参阅https://emboss.github.io/blog/2012 / 12/14 / break-murmur-hash-flooding-dos-reloaded / ）。 - 经过sorting可以进行有效的范围search，例如使用键> = 42迭代所有元素。
其他答案已经给出了原因。 这是另一个。
std :: map（平衡二叉树）操作分摊到O（log n）和最坏情况O（log n）。 std :: unordered_map（散列表）操作是摊销O（1）和最坏情况O（n）。
这在实践中是如何实现的，就是散列表每隔一段时间就用一个O（n）操作“打嗝”，这个操作可能是或者可能不是你的应用程序可以容忍的。 如果它不能容忍它，你更喜欢std :: map over std :: unordered_map。
来自： http : //www.cplusplus.com/reference/map/map/
“在内部，映射中的元素总是按照由其内部比较对象（比较types）指示的特定的严格弱sorting标准按键sorting。
map容器通常比unordered_map容器慢，通过它们的键来访问各个元素，但是它们允许基于它们的顺序对子集进行直接迭代。
