如何selectmap和unordered_map？
假设我想用一个string作为关键字映射数据。 我应该select什么容器， map或unordered_map ？ unordered_map占用更多的内存，所以我们假设内存不是问题，关心的是速度。
unordered_map应该通常给O（1）的平均复杂度O（n）的最坏情况。 在什么情况下会到达O（n）？ 什么时候map比unordered_map更省时？ 当n很小时会发生吗？
假设我将使用STL unordered_map与默认haser Vs. 地图。 string是关键。
如果我要迭代元素而不是每次访问单个元素，我应该更喜欢map吗？
在实践中，如果内存没有问题，如果你想要单个元素的访问， unordered_map总是更快。
最坏的情况是理论上的，并且对于所有元素的单个散列计算是必然的。 这不具有实际意义。 一旦至less有N个属于同一个散列的元素， unordered_map会变慢。 这也是没有实际意义的。 在一些特殊情况下，您可以使用特定的哈希algorithm来确保更均匀的分布。 对于不共享特定模式的普通string，与unordered_map一起使用的通用哈希函数同样好。
如果你想以一种sorting的方式遍历地图（使用迭代器），你不能使用unordered_map 。 相反， map不仅可以实现这一function，还可以根据键的近似值为您提供地图中的下一个元素（请参阅lower_bound和upper_bound方法）。
| map | unordered_map --------------------------------------------------------- element ordering | strict weak | n/a | | common implementation | balanced tree | hash table | or red-black tree| | | search time | log(n) | O(1) if there are no hash collisions | | Up to O(n) if there are hash collisions | | O(n) when hash is the same for any key | | Insertion time | log(n)+rebalance | Same as search | | Deletion time | log(n)+rebalance | Same as search | | needs comparators | only operator < | only operator == | | needs hash function | no | yes | | common use case | when good hash is| In most other cases. | not possible or | | too slow. Or when| | order is required|
我应该select什么容器，map或unordered_map？ unordered_map占用更多的内存，所以我们假设内存不是问题，关心的是速度。
configuration文件，然后决定。 unordered_map通常比较快，但是每个案例都有所不同。
在什么情况下会到达O（n）？
当哈希不好，一堆元素被分配到相同的箱子。
什么时候地图比unordered_map更省时？ 当n很小的时候，它会发生吗？
可能不会，但是如果你真的在乎的话。 有一个小尺寸的容器是你的程序的瓶颈似乎极不可能。 无论如何，对于这种情况，使用线性search的简单vector可能会更快。
决定时最重要的是要求sorting和缺乏迭代器失效。 如果你需要，你几乎必须使用map 。 否则， unordered_map 。
在什么情况下会到达O（n）？
如果你有这样一个不好的散列函数，它会为所有的input结果产生相同的散列值（即产生冲突）。
我应该select什么容器，map或unordered_map？
你有什么要求和种类/数量总是问题。
什么时候地图比unordered_map更省时？
这只是不同的结构。 根据您的典型用例，您最好select其中一种（考虑您拥有的数据types和数量）
当n很小的时候会发生什么？
在小数据量的情况下，一切都取决于特定的STL实现…因此，有时甚至是简单的向量/数组可能比关联容器更快…
