c++ STL 容器

參考：STL源碼分析

（一）vector容器
vector的數(shù)據(jù)安排以及操作方式,，與array非常相似。兩者的唯一區(qū)別在 于空間的運用的靈活性,。array是靜態(tài)空間,，一旦配置了就不能改變。vector是動態(tài)空間,，隨著元素的加入,，它的內(nèi)部機制會自行擴充空間以容納新元 素。因此,，vector的運用對于內(nèi)存的合理利用與運用的靈活性有很大的幫助,，我們再也不必因為害怕空間不足而一開始要求一個大塊的array。

vector 動態(tài)增加大小，并不是在原空間之后持續(xù)新空間（因為無法保證原空間之后尚有可供配置的空間）,，而是以原大小的兩倍另外配置一塊較大的空間,，然后將原內(nèi)容拷 貝過來，然后才開始在原內(nèi)容之后構造新元素,，并釋放原空間,。因此，對vector的任何操作,，一旦引起空間重新配置,，指向原vector的所有迭代器就都 失效了。

（二）list容器
相對于vector的連續(xù)空間,，list就顯得復雜許多,，它的好處是每次插入或刪除一個元素，就配置 或釋放一個元素空間,。因此,，list對于空間的運用有絕對的精準，一點也不浪費,。而且,，對于任何位置的元素插入或元素移除，list永遠是常數(shù)時間,。 STL中的list是一個雙向鏈表,，而且是一個環(huán)狀雙向鏈表。

（三）deque容器
 deque 是一種雙向開口的連續(xù)線性空間,。所謂雙向開口,，意思是可以在隊尾兩端分別做元素的插入和刪除操作。deque和vector的最大差異,，一在于deque 允許于常數(shù)時間內(nèi)對起頭端進行元素的插入或移除操作,，二在于deque沒有所謂容量觀念，因為它是動態(tài)地以分段連續(xù)空間組合而成,，隨時可以增加一段新的空 間并鏈接在一起,。換句話說，像vector那樣"因舊空間不足而重新配置一塊更大空間,，然后復制元素,，再釋放舊空間"這樣的事情在 deque是不會發(fā)生的。

deque是由一段一段的定量連續(xù)空間構成,。一旦有必要在deque的前端或尾端增加新空間,，便配置一段定量連 續(xù)空間，串接在整個deque的頭端或尾端,。deque的最大任務,，便是在這些分段的定量連續(xù)空間上,，維護其整體連續(xù)的假象，并提供隨機存取的接口,。避開 了"重新配置,，復制，釋放"的輪回,，代價則是復雜的迭代器架構,。因為有分段連續(xù)線性空間，就必須有中央控制,，而為了維持整體連續(xù)的假象,，數(shù)據(jù)結(jié)構的設計及 迭代器前進后退等操作都頗為繁瑣。

deque采用一塊所謂的map作為主控,。這里的map是一小塊連續(xù)空間,，其中每個元素都是指針，指向另一段連續(xù)線性空間,，稱為緩沖區(qū),。緩沖區(qū)才是deque的存儲空間主體。SGI STL允許我們指定緩沖區(qū)大小,，默認值0表示將使用512 bytes緩沖區(qū),。

（四）stack
stack 是一種先進后出（First In Last Out , FILO）的數(shù)據(jù)結(jié)構。它只有一個出口,，stack 允許新增元素,，移除元素，取得最頂端元素,。但除了最頂端外，沒有任何其它方法可以存取stack的其它元素,，stack不允許遍歷行為,。

以 某種容器作為底部結(jié)構，將其接口改變,，使之符合“先進后出”的特性,，形成一個stack，是很容易做到的,。deque是雙向開口的數(shù)據(jù)結(jié)構,，若以 deque為底部結(jié)構并封閉其頭端開口，便輕而易舉地形成了一個stack.因此,，SGI STL 便以deque作為缺省情況下的stack底部結(jié)構,，由于stack 系以底部容器完成其所有工作，而具有這種"修改某物接口,，形成另一種風貌"之性質(zhì)者,，稱為adapter（配接器）,，因此，STL stack 往往不被歸類為container(容器),，而被歸類為 container adapter.

(五） queue
queue是一種先進先出(First In First Out,FIFO) 的數(shù)據(jù)結(jié)構,。它有兩個出口，queue允許新增元素,，移除元素,，從最底端加入元素，取得最頂端元素,。但除了最底端可以加入,，最頂端可以取出外，沒有任何其它方法可以存取queue的其它元素,。


(六)heap
heap 并不歸屬于STL容器組件,，它是個幕后英雄，扮演priority queue的助手,。priority queue允許用戶以任何次序?qū)⑷魏卧赝迫肴萜髦?，但取出時一定按從優(yōu)先權最高的元素開始取。按照元素的排列方式,，heap可分為max-heap和 min-heap兩種,，前者每個節(jié)點的鍵值(key)都大于或等于其子節(jié)點鍵值，后者的每個節(jié)點鍵值(key)都小于或等于其子節(jié)點鍵值,。因此,， max-heap的最大值在根節(jié)點，并總是位于底層array或vector的起頭處,；min-heap的最小值在根節(jié)點,，亦總是位于底層array或 vector起頭處,。STL 供應的是max-heap，用c++實現(xiàn),。
堆排序c語言實現(xiàn)
（七）priority_queue
priority_queue 是一個擁有權值觀念的queue,它允許加入新元素,，移除舊元素，審視元素值等功能,。由于這是一個queue,，所以只允許在底端加入元素，并從頂端取出元 素,，除此之外別無其它存取元素的途徑,。priority_queue帶有權值觀念，其內(nèi)的元素并非依照被推入的次序排列,，而是自動依照元素的權值排列（通 常權值以實值表示）,。權值最高者，排在最前面,。缺省情況下priority_queue系利用一個max-heap完成,，后者是一個以vector表現(xiàn)的 complete binary tree.max-heap可以滿足priority_queue所需要的"依權值高低自動遞減排序"的特性。
priority_queue 完全以底部容器作為根據(jù),，再加上heap處理規(guī)則,，所以其實現(xiàn)非常簡單。缺省情況下是以vector為底部容器,。queue以底部容器完成其所有工作,。具 有這種"修改某物接口，形成另一種風貌"之性質(zhì)者,，稱為adapter(配接器),，因此，STL priority_queue往往不被歸類為container(容器),，而被歸類為container adapter.

(八)set,multiset
set 的特性是,，所有元素都會根據(jù)元素的鍵值自動被排序。set的元素不像map那樣可以同時擁有實值(value)和鍵值(key), set 元素的鍵值就是實值,，實值就是鍵值,，set不允許兩個元素有相同的值,。set是通過紅黑樹來實現(xiàn)的,，由于紅黑樹（RB-tree）是一種平衡二叉搜索樹， 自動排序的效果很不錯,，所以標準的STL的set即以RB-Tree為底層機制,。又由于set所開放的各種操作接口，RB-tree也都提供了,，所以幾乎 所有的set操作行為,，都只有轉(zhuǎn)調(diào)用RB-tree的操作行為而已,。

multiset的特性以及用法和set完全相同，唯一的差別在于它允許鍵值重復,，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique().

（九）map,multimap
map 的特性是,，所有元素都會根據(jù)元素的鍵值自動被排序。map的所有元素都是pair,同時擁有實值（value）和鍵值（key）.  pair的第一元素被視為鍵值,，第二元素被視為實值,。map不允許兩個元素擁有相同的鍵值.由于RB-tree是一種平衡二叉搜索樹，自動排序的效果很不 錯,，所以標準的STL map即以RB-tree為底層機制,。又由于map所開放的各種操作接口，RB-tree也都提供了,，所以幾乎所有的map操作行為,，都只是轉(zhuǎn)調(diào)RB- tree的操作行為。
multimap的特性以及用法與map完全相同,，唯一的差別在于它允許鍵值重復,，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique。

posted on 2011-06-02 11:28 周強 閱讀(711) 評論(0)  編輯 收藏 引用 所屬分類: c++ STL源碼分析