在 std::map 和 std::unordered_map 之间进行选择
既然 std 在 unordered_map 中有一个真正的哈希映射，为什么(或何时)我还想使用旧的 mapunordered_map 在它实际存在的系统上?是否有任何我无法立即看到的明显情况?
Now that std has a real hash map in unordered_map, why (or when) would I still want to use the good old map over unordered_map on systems where it actually exists? Are there any obvious situations that I cannot immediately see?
推荐答案
As 已经提到，map 允许以排序的方式迭代元素，但unordered_map 不允许.这在许多情况下非常重要，例如显示集合(例如地址簿).这也体现在其他间接方式上，例如:(1) 从 find() 返回的迭代器开始迭代，或 (2) 存在像 lower_bound() 这样的成员函数.
As already mentioned, map allows to iterate over the elements in a sorted way, but unordered_map does not. This is very important in many situations, for example displaying a collection (e.g. address book). This also manifests in other indirect ways like: (1) Start iterating from the iterator returned by find(), or (2) existence of member functions like lower_bound().
此外，我认为在最坏情况 搜索复杂性方面存在一些差异.
Also, I think there is some difference in the worst case search complexity.
对于
map，是O(lg N)
对于unordered_map，它是O( N ) [当哈希函数不好导致太多哈希冲突时，可能发生这种情况.]
For unordered_map, it is O( N ) [This may happen when the hash function is not good leading to too many hash collisions.]
同样适用于最坏情况 删除复杂性.
相关文章