2015年3月27日 星期五

C++ 學習小筆記-std::map vs std::unodered_map

顧名思義map 跟 unordered_map的差別在於"ordered"
也就是 map是有order unordered_map則沒有,
差別(應該是)在於底下的實作方式
map 是用類似 Binary tree 之類的方式來實作,所以也支援從 find()的結果開始繼續iterate
還有lower_bound() 之類的功能
而 unordered_map推測應該是用 hash_table 來實作
因此:
unordered_map所花費的記憶體空間比較大,但一般情況下會比較快
然而worst case底下 map 會有O(logN)的時間複查度 unordered_map 卻有可能用到 O(N)
所以 ... 自己看個伴吧 :P

Related Articles

0 comments:

張貼留言

技術提供:Blogger.