72      阿裏雲  技術社區[雲棲]

STL之七：STL各種容器的使用時機詳解

    C++標準程序庫提供了各具特長的不同容器。現在的問題是：該如何選擇最佳的容器類別？下表給出了概述。

但是其中有些描述可能不一定實際。例如：如果你需呀處理的元素數量很少，可以虎落複雜度，因為線性算法通常對元素本身的處理過程比較快，這種情況下，“顯性複雜度搭配快速的元素處理”要比“對數複雜度搭配慢的元素處理”來得劃算。

    作為對上表的補充，使用時：

    1.缺省情況下應該使用vector。vector的內部結構最簡單，並允許隨機存取，所以數據的存取十分方便靈活，數據的處理也夠快。

    2.如果經常要在序列頭部和尾部安插和移除元素，應該采用deque。如果你希望元素被移除時，容器能夠自動縮減內存，那麼你也應該采用deque。此外，由於vector通常才有用一個內存區塊來存放元素，而deque采用多個區塊，所以後者可內含更多元素。

   3.如果需要經常在容器的中段執行元素的安插、移除和移動，可考慮使用list。list提供特殊的成員函數，可以在常數時間內將元素從A容器轉移到B容器。但由於list不支持隨機存取，所以如果隻要知道list的頭部卻要造訪list中的元素，性能會大打折扣。

     和所有“以節點為基礎”的容器相似，隻要元素還是容器的已不複，list就不會令指向那些元素的迭代器失效。vector則不然，一旦超過其容量，它的所有iterators,pointers.references都會失效；執行安插或移除操作時，也會令一部分iterators、pointers、references失效。至於deque,當它的大小改變，所有iterators，pointers，references都會失效。

    4.如果你要的容器是這種性質：每次操作若不成功，便無效用，那麼你應該選用list，或是采用關聯式容器。

    5.如果你經常需要根據某個準則來搜尋元素，那麼應當使用“以該排序準則對元素進行排序”的set或multiset。記住，理論上，麵對1000個元素的排序，對數複雜度比線性複雜度好10倍。就搜尋速度而言，hash table通常比二叉樹還要快5-10倍。但是hash table的元素並未排序，所以如果元素必須排序，它就用不上了。

    6.如果想處理key/value pair，請采用map或multimap。

    7.如果需要關聯式數組，應采用map。

    8.如果需要字典結構，應采用multimap。

最後更新：2017-04-04 07:03:41

  上一篇： 常用Maven插件介紹（上）

  下一篇： C++ Primer經典書目閱讀之五：表達式