在std::map和std::unorder_map之间进行选择?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (456)

现在std中有一个真正的散列映射。unordered_map,为什么(或者什么时候)我还想用好的旧的?map过关unordered_map在它真正存在的系统上?有什么明显的情况我无法立即看到?

提问于
用户回答回答于

map允许以排序方式遍历元素,但是unordered_map不会的。在许多情况下,这是非常重要的,例如显示一个集合(例如通讯录)。这还以其他间接方式体现出来,例如:(1)从find(),或者(2)成员函数的存在lower_bound()

另外,我认为在最坏情况搜索复杂。

  • map,是O(LG N)
  • unordered_map,是O(N)这五月当哈希函数不好导致过多的哈希冲突时发生。

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

用户回答回答于

除了上面的答案,还应该注意到,仅仅是因为unordered_map是恒速(O(1))并不意味着它比map(指秩序)log(N))。常数可能大于log(N)尤其是因为N限制为232(或264)。

因此,除了其他答案(map维护顺序和散列函数可能很困难)map更有表现力。

例如,在我运行的一个程序中,我看到了VS 10std::unordered_mapstd::map(虽然boost::unordered_map比两者都快)。

注3至5小节。

所属标签

可能回答问题的人

  • Hanzo

    6 粉丝0 提问7 回答
  • Richel

    9 粉丝0 提问3 回答
  • mariolu

    31 粉丝0 提问2 回答
  • 上云小秘书

    15 粉丝0 提问2 回答

扫码关注云+社区

领取腾讯云代金券