轉(zhuǎn)自:http://www./art/1543058
list支持快速的插入和刪除,但是查找費(fèi)時; vector支持快速的查找,但是插入費(fèi)時。 map查找的時間復(fù)雜度是對數(shù)的,這幾乎是最快的,hash也是對數(shù)的。 STL 中的 map 內(nèi)部是平衡二叉樹,所以平衡二叉樹的性質(zhì)都具備。查找數(shù)據(jù)的時間也是對數(shù)時間。 vector,在分配內(nèi)存上一般要比 new 高效的多。 為什么說 hash_map 是對數(shù)級的?在不碰撞的情況下,hash_map是所有數(shù)據(jù)結(jié)構(gòu)中查找最快的,它是常數(shù)級的。
我想沒必要懷疑stl::map的查找效率,影響效率最主要的因素是什么?算法,在查找問題上,有什么算法比RB_tree更好嗎?至少現(xiàn)在還沒有。不否 認(rèn)你可以通過自己寫代碼,設(shè)計一個符合你需要的BR—TREE,比stl::map簡捷那么一點(diǎn),但最多也就每次迭代中少一行指令而已,處理十萬個數(shù)據(jù)多 執(zhí)行十萬行指令,這對你重要嗎?如果你不是在設(shè)計OS像LINUX,沒人會關(guān)注這十萬行指令花的時間。
大多數(shù)程序員寫不出比std::map更好的map,這是當(dāng)然的。然而并不是std::map的所有特性都出現(xiàn)在我們的程序中,自己編寫的可以更適合自己的程序,的確會比std::map更快一些。
關(guān)于hash_map,它與map的實(shí)現(xiàn)機(jī)制是不一樣的,map內(nèi)部一般用樹來實(shí)現(xiàn),其查找操作是O(logN)的,這個沒有爭議,我就不多說了。 ----------------------------------------- BS: "對于大型容器而言,hash_map能夠提供比map快5至10倍的元素查找速度是很常見的,尤其是在查找速度特別重要的地方.另一方面,如果hash_map選擇了病態(tài)的散列函數(shù),他也可能比map慢得多. " ANSIC++在1998年之后就沒再有重大改變,并且決定不再向C++標(biāo)準(zhǔn)庫中做任何重大的變更,正是這個原因,hash table(包括hash_map)并沒有被列入標(biāo)準(zhǔn)之中,雖然它理應(yīng)在C++標(biāo)準(zhǔn)之中占有一席之地。
hehe俺也來湊湊熱鬧。
你的百萬級的數(shù)據(jù)放到vector不大合適。因?yàn)関ector需要連續(xù)的內(nèi)存空間,顯然在初始化這個容器的時候會花費(fèi)很大的容量。
如果內(nèi)存不是考慮的問題。用vector比map好。map每插入一個數(shù)據(jù),都要排序一次。所以速度反不及先安插所有元素,再進(jìn)行排序。 用 binary_search對已序區(qū)間搜索,如果是隨機(jī)存取iterator,則是對數(shù)復(fù)雜度??梢姡诓豢紤]內(nèi)存問題的情況下,vector比map 好。
如果你需要在數(shù)據(jù)中間進(jìn)行插入,list 是最好的選擇,vector 的插入效率會讓你痛苦得想死。
涉及到查找的話用map比較好,因?yàn)閙ap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)用rb-tree實(shí)現(xiàn),而用vector你只能用線性查找,效率很低。 stl還提供了 hash容器,理論上查找是飛快~~~。做有序插入的話vector是噩夢,map則保證肯定是按key排序的,list要自己做些事情。
HASH類型的查找肯定快,是映射關(guān)系嘛,但是插入和刪除卻慢,要做移動操作, LIST類型的使鏈?zhǔn)疥P(guān)系,插入非???,但是查找卻費(fèi)時,需要遍歷~~ , 還是用LIST類型的吧,雖然查找慢點(diǎn), 先快速排序,然后二分查找,效率也不低 |
|
來自: 看風(fēng)景D人 > 《STL》