为了账号安全,请及时绑定邮箱和手机立即绑定

在普通键的情况下使用map over unordered_map有什么好处吗?

在普通键的情况下使用map over unordered_map有什么好处吗?

喵喵时光机 2019-08-14 16:52:09
在普通键的情况下使用map over unordered_map有什么好处吗?最近unordered_map在C ++中的讨论使我意识到我应该使用之前使用unordered_map的大多数情况map,因为查找的效率(摊销的O(1)与O(log n))。大多数时候我使用地图,我使用int或std::string作为密钥类型; 因此,我对哈希函数的定义没有任何问题。我想过这个问题越多,我越才明白,我找不到任何理由使用的std::map在std::unordered_map与简单类型的键的情况下-我看了一下界面,并没有发现任何影响我的代码的重大差异。因此,问题:是否有使用任何真正的原因std::map在std::unordered map简单类型等的情况下int和std::string?我从一个严格的编程角度问我 - 我知道它没有被完全认为是标准的,并且它可能会带来移植问题。另外,我希望其中一个正确的答案可能是“它对于较小的数据集更有效”,因为开销较小(是真的吗?) - 因此我想将问题限制在数量较多的情况下键是非平凡的(> 1 024)。编辑: 呃,我忘记了显而易见的(感谢GMan!) - 是的,地图是当然有序的 - 我知道,我正在寻找其他原因。
查看完整描述

3 回答

?
Cats萌萌

TA贡献1805条经验 获得超9个赞

如果你想比较你的实现std::mapstd::unordered_map实现的速度,你可以使用谷歌的sparsehash项目,它有一个time_hash_map程序来计时。例如,在x86_64 Linux系统上使用gcc 4.4.2


$ ./time_hash_map

TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):

map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB

map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB

map_replace            22.3 ns  (37427396 hashes, 40000000 copies)

map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)

map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)

map_remove             49.1 ns  (37427396 hashes, 40000000 copies)

map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)


STANDARD MAP (4 byte objects, 10000000 iterations):

map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB

map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB

map_replace           151.2 ns  (       0 hashes, 20000000 copies)

map_fetch             156.0 ns  (       0 hashes, 20000000 copies)

map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)

map_remove            141.0 ns  (       0 hashes, 20000000 copies)

map_toggle             67.3 ns  (       0 hashes, 20000000 copies)


查看完整回答
反对 回复 2019-08-14
  • 3 回答
  • 0 关注
  • 913 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信