在 std::map 和 std::unordered_map 之间进行选择 [英] Choosing between std::map and 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.]

同样适用于最坏情况 删除复杂性.

这篇关于在 std::map 和 std::unordered_map 之间进行选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！