在std :: map和std :: unordered_map之间进行选择
Joh*_*ell 130 c++ hash unordered-map map c++11
现在std有一个真正的哈希映射unordered_map,为什么(或何时)我还想在它实际存在的系统上使用旧的mapover unordered_map？是否有任何我无法立即看到的明显情况？
Aru*_*run 109
正如已经提到的,map允许迭代的排序方式的元素,但unordered_map没有.这在许多情况下非常重要,例如显示集合(例如地址簿).这也体现在其他间接方式中:(1)从返回的迭代器开始迭代find(),或者(2)成员函数的存在,如:lower_bound().
此外,我认为在最坏情况 搜索复杂性方面存在一些差异.
因为
map,它是O(lg N)因为
unordered_map,它是O(N)[ 当哈希函数不好导致太多哈希冲突时,可能会发生这种情况.
这同样适用于最坏情况 删除复杂性.
- 你最坏的情况是正确的,但是这篇文章有点误导 - 因为平均来说std :: unordered_map对于搜索复杂度是O(1),这比std :: map要好得多 (69认同)
- 理解对于某些应用来说,最坏情况下的性能对于了解并且是决定性因素非常重要.对于某些硬实时系统,具有像哈希表这样的线性最坏情况是不可接受的.std :: map总是O(lg N),这是一个非常好的属性. (7认同)
Mot*_*tti 86
除了上面的答案,你还应该注意,仅仅因为unordered_map恒定速度(O(1))并不意味着它比map(顺序log(N))更快.常数可能大于log(N)特别是因为N受限于2 32(或2 64).
因此,除了其他答案(map维护顺序和哈希函数可能很困难)之外,它可能map更具性能.
例如,在我为一篇博客文章运行的程序中,我看到VS10的std::unordered_map速度慢于std::map(虽然boost::unordered_map比两者都快).
注意第3到第5栏.
- VS10,这就是你的问题. (9认同)
- @nm可悲的是我的时间机器在2010年10月11日没有工作. (6认同)
- 博客链接已经走上了这条路，如果没有那个上下文，这里显示的结果几乎没有价值，因为散列与比较所需的时间因确切的散列函数、数据类型、长度和值而异。这对于 VC++ 标准库尤其重要，因为散列函数速度快但容易发生冲突：数字未经改变地传递，任何长度的字符串中只有 10 个字符间隔组合在散列值中，桶计数不是素数。（GNU 处于频谱的另一端）。 (2认同)
ein*_*ica 25
这是由于谷歌的Chandler Carruth在他的CppCon 2014讲座中
std::map是(许多人认为)对于面向性能的工作没有用处:如果你想要O(1)-amortized访问,使用适当的关联数组(或缺少一个,std::unorderded_map); 如果您想要排序顺序访问,请使用基于向量的内容.
还有,std::map是一棵平衡的树; 你不得不经常穿越它,或者重新平衡它.这些分别是cache-killer和cache-apocalypse操作......所以只说拒绝std::map.
您可能对有效哈希映射实现的SO问题感兴趣.
(PS - std::unordered_map缓存不友好,因为它使用链表作为存储桶.)
假设您有非常大的键,也许是大字符串.要为大字符串创建哈希值,您需要从头到尾遍历整个字符串.至少需要线性时间到密钥的长度.但是,当您仅使用>键的运算符搜索二叉树时,每个字符串比较都可以在找到第一个不匹配时返回.对于大字符串,这通常很早.
这种推理可以应用到find的功能std::unordered_map和std::map.如果密钥的性质使得生成散列(在这种情况下std::unordered_map)花费的时间比使用二进制搜索(在这种情况下std::map)查找元素的位置花费的时间长,则查找密钥应该更快在std::map.很容易想到会出现这种情况的情况,但我认为它们在实践中很少见.
| 归档时间： |
|
| 查看次数： |
85061 次 |
| 最近记录： |