在C ++中使用map和hash_map
我有一个hash_map和C + +的map的问题。 我明白， map是在STL，但hash_map不是一个标准。 两者有什么区别？
它们以非常不同的方式实施。
hash_map （TR1和Boost中的unordered_map ;使用它们）使用散列表，其中密钥被散列到表中的一个槽中，并且该值存储在与该密钥相关的列表中。
map被实现为平衡二叉search树（通常是红/黑树）。
一个unordered_map应该给访问集合的已知元素提供稍微好一点的性能，但是一个map还会有其他有用的特性（例如它按照sorting顺序存储，这样就可以从头到尾遍历）。 unordered_map插入和删除的速度比map快。
hash_map是许多库实现提供的常见扩展。 这就是为什么当它作为TR1的一部分被添加到C ++标准中时它被重命名为unordered_map 。 地图通常用红黑树等平衡二叉树来实现（实现方式各不相同）。 hash_map和unordered_map通常使用哈希表来实现。 因此订单不被维护。 unordered_map插入/删除/查询将是O（1）（常量时间）其中映射将是O（log n）其中n是数据结构中的项目数。 所以unordered_map更快，如果你不关心项目的顺序应该优先于map 。 有时你想保持秩序（按键sorting），并为该map将是select。
一些关键的区别在于复杂性要求。
映射需要O（log（N））时间来插入和查找。
unordered_map需要O（1）的“平均”时间来插入和查找，但是允许其最坏情况时间为O（N）。
所以，通常，unordered_map会更快，但取决于您存储的密钥和哈希函数，可能会变得更糟糕。
C ++规范并没有说明你必须使用什么algorithm来为STL容器。 但是，它确实对性能施加了一定的限制，这就排除了对map和其他关联容器使用散列表的限制。 （它们通常用红色/黑色树来实现）。这些约束要求这些容器比散列表可以提供更好的最差情况下的性能。
许多人确实需要散列表，但是，基于散列的STL关联容器已经是多年来的常见扩展。 因此，他们将unordered_map等添加到C ++标准的更高版本中。
我不知道给出了什么，但是，hash_map需要超过20秒来清除（）150K无符号整数键和浮点值。 我只是在跑步，阅读别人的代码。
这是它如何包含hash_map。
#include "StdAfx.h" #include <hash_map>
我在这里读到https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap
说clear（）是O（N）的顺序。 对我来说，这是非常奇怪的，但是，就是这样。
