轉(zhuǎn)自：http://www./art/1543058

list支持快速的插入和刪除，但是查找費(fèi)時(shí);

vector支持快速的查找，但是插入費(fèi)時(shí)。

map查找的時(shí)間復(fù)雜度是對(duì)數(shù)的，這幾乎是最快的，hash也是對(duì)數(shù)的。
如果我自己寫，我也會(huì)用二叉檢索樹，它在大部分情況下可以保證對(duì)數(shù)復(fù)雜度，最壞情況是常數(shù)復(fù)雜度，而std::map在任何情況下都可以保證對(duì)數(shù)復(fù)雜度，原因是它保證存諸結(jié)構(gòu)是完全二叉檢索樹，但這會(huì)在存諸上犧牲一些時(shí)間。

STL   中的   map   內(nèi)部是平衡二叉樹，所以平衡二叉樹的性質(zhì)都具備。查找數(shù)據(jù)的時(shí)間也是對(duì)數(shù)時(shí)間。 vector，在分配內(nèi)存上一般要比   new   高效的多。

為什么說(shuō)   hash_map   是對(duì)數(shù)級(jí)的？在不碰撞的情況下，hash_map是所有數(shù)據(jù)結(jié)構(gòu)中查找最快的，它是常數(shù)級(jí)的。
如果對(duì)問(wèn)題設(shè)計(jì)了足夠好的hash算法，保證碰撞率很低，hash_map的查找效率無(wú)可置疑。
另外，STL的map，它的查找是對(duì)數(shù)級(jí)的，是除hash_map外最高的了，你可以說(shuō)“也許還有改進(jìn)余地”，但對(duì)于99.9999%的程序員，設(shè)計(jì)一個(gè)比STL   map好的map，我執(zhí)悲觀態(tài)度。
STL的map有平衡策略（比如紅黑樹什么的），所以不會(huì)退化，不需要考慮數(shù)據(jù)本身的分布問(wèn)題。只不過(guò)，如果數(shù)據(jù)本身是排好序的，用vector或heap會(huì)明顯的快些，因?yàn)樗鼈兊脑L問(wèn)比較簡(jiǎn)單。

我想沒(méi)必要懷疑stl::map的查找效率,影響效率最主要的因素是什么?算法,在查找問(wèn)題上,有什么算法比RB_tree更好嗎？至少現(xiàn)在還沒(méi)有。不否 認(rèn)你可以通過(guò)自己寫代碼，設(shè)計(jì)一個(gè)符合你需要的BR—TREE，比stl：：map簡(jiǎn)捷那么一點(diǎn)，但最多也就每次迭代中少一行指令而已，處理十萬(wàn)個(gè)數(shù)據(jù)多 執(zhí)行十萬(wàn)行指令，這對(duì)你重要嗎？如果你不是在設(shè)計(jì)OS像LINUX，沒(méi)人會(huì)關(guān)注這十萬(wàn)行指令花的時(shí)間。
rb-tree的時(shí)間花在了插入和刪除上，如果你不是對(duì)插入和刪除效率要求很高，你沒(méi)有理由不選擇基于rb-tree的stl::map。

大多數(shù)程序員寫不出比std::map更好的map，這是當(dāng)然的。然而并不是std::map的所有特性都出現(xiàn)在我們的程序中，自己編寫的可以更適合自己的程序，的確會(huì)比std::map更快一些。

關(guān)于hash_map，它與map的實(shí)現(xiàn)機(jī)制是不一樣的，map內(nèi)部一般用樹來(lái)實(shí)現(xiàn)，其查找操作是O(logN)的，這個(gè)沒(méi)有爭(zhēng)議，我就不多說(shuō)了。
hash_map的查找，內(nèi)部是通過(guò)一個(gè)從key到value的運(yùn)算函數(shù)來(lái)實(shí)現(xiàn)的，這個(gè)函數(shù)“只接受key作為參數(shù)”，也就是說(shuō)，hash_map的查找 算法與數(shù)據(jù)量無(wú)關(guān)，所以認(rèn)為它是O(1)級(jí)的。來(lái)這里的應(yīng)該都是達(dá)人，可以參看《數(shù)據(jù)結(jié)構(gòu)》。當(dāng)然，事實(shí)總不這樣完美，再引一段前面我自已說(shuō)的話，進(jìn)一步 說(shuō)明，以免誤會(huì)：

-----------------------------------------
在不碰撞的情況下，hash_map是所有數(shù)據(jù)結(jié)構(gòu)中查找最快的，它是常數(shù)級(jí)的。
------------------------------------------
注意我的前提：“在不碰撞的情況下”，其實(shí)換句話說(shuō)，就是要有足夠好的hash函數(shù)，它要能使key到value的映射足夠均勻，否則，在最壞的情況下，它的計(jì)算量就退化到O(N)級(jí)，變成和鏈表一樣。
如果說(shuō)   hash_map   是所有容器中最慢的，也只能說(shuō)：“最拙劣的hash函數(shù)”會(huì)使hash_map成為查找最慢的容器。但這樣說(shuō)意義不大，因?yàn)椋顪惽傻呐帕心苁姑芭菖判虺蔀樽羁斓呐判蛩惴ā?/strong>