在普通鍵的情況下使用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::map和std::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)
添加回答
舉報
0/150
提交
取消