參考：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)容之后構(gòu)造新元素，并釋放原空間。因此，對vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效了。
（二）list容器
相對于vector的連續(xù)空間，list就顯得復(fù)雜許多，它的好處是每次插入或刪除一個元素，就配置或釋放一個元素空間。因此，list對于空間的運用有絕對的精準，一點也不浪費。而且，對于任何位置的元素插入或元素移除，list永遠是常數(shù)時間。STL中的list是一個雙向鏈表，而且是一個環(huán)狀雙向鏈表。
（三）deque容器
deque 是一種雙向開口的連續(xù)線性空間。所謂雙向開口，意思是可以在隊尾兩端分別做元素的插入和刪除操作。deque和vector的最大差異，一在于deque允許于常數(shù)時間內(nèi)對起頭端進行元素的插入或移除操作，二在于deque沒有所謂容量觀念，因為它是動態(tài)地以分段連續(xù)空間組合而成，隨時可以增加一段新的空間并鏈接在一起。換句話說，像vector那樣"因舊空間不足而重新配置一塊更大空間，然后復(fù)制元素，再釋放舊空間"這樣的事情在 deque是不會發(fā)生的。
deque是由一段一段的定量連續(xù)空間構(gòu)成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續(xù)空間，串接在整個deque的頭端或尾端。deque的最大任務(wù)，便是在這些分段的定量連續(xù)空間上，維護其整體連續(xù)的假象，并提供隨機存取的接口。避開了"重新配置，復(fù)制，釋放"的輪回，代價則是復(fù)雜的迭代器架構(gòu)。因為有分段連續(xù)線性空間，就必須有中央控制，而為了維持整體連續(xù)的假象，數(shù)據(jù)結(jié)構(gòu)的設(shè)計及迭代器前進后退等操作都頗為繁瑣。
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é)構(gòu)。它只有一個出口，stack 允許新增元素，移除元素，取得最頂端元素。但除了最頂端外，沒有任何其它方法可以存取stack的其它元素，stack不允許遍歷行為。
以某種容器作為底部結(jié)構(gòu)，將其接口改變，使之符合“先進后出”的特性，形成一個stack，是很容易做到的。deque是雙向開口的數(shù)據(jù)結(jié)構(gòu)，若以deque為底部結(jié)構(gòu)并封閉其頭端開口，便輕而易舉地形成了一個stack.因此，SGI STL 便以deque作為缺省情況下的stack底部結(jié)構(gòu)，由于stack 系以底部容器完成其所有工作，而具有這種"修改某物接口，形成另一種風(fēng)貌"之性質(zhì)者，稱為adapter（配接器），因此，STL stack 往往不被歸類為container(容器)，而被歸類為 container adapter.
(五） queue
queue是一種先進先出(First In First Out,FIFO) 的數(shù)據(jù)結(jié)構(gòu)。它有兩個出口，queue允許新增元素，移除元素，從最底端加入元素，取得最頂端元素。但除了最底端可以加入，最頂端可以取出外，沒有任何其它方法可以存取queue的其它元素。
以某種容器作為底部結(jié)構(gòu)，將其接口改變，使之符合“先進先出”的特性，形成一個queue，是很容易做到的。deque是雙向開口的數(shù)據(jù)結(jié)構(gòu)，若以 deque為底部結(jié)構(gòu)并封閉其底部的出口和前端的入口，便輕而易舉地形成了一個queue.因此，SGI STL 便以deque作為缺省情況下的queue底部結(jié)構(gòu)，由于queue 系以底部容器完成其所有工作，而具有這種"修改某物接口，形成另一種風(fēng)貌"之性質(zhì)者，稱為adapter（配接器），因此，STL queue往往不被歸類為container(容器)，而被歸類為 container adapter.
(六)heap
heap并不歸屬于STL容器組件，它是個幕后英雄，扮演priority queue的助手。priority queue允許用戶以任何次序?qū)⑷魏卧赝迫肴萜髦校〕鰰r一定按從優(yōu)先權(quán)最高的元素開始取。按照元素的排列方式，heap可分為max-heap和min-heap兩種，前者每個節(jié)點的鍵值(key)都大于或等于其子節(jié)點鍵值，后者的每個節(jié)點鍵值(key)都小于或等于其子節(jié)點鍵值。因此， max-heap的最大值在根節(jié)點，并總是位于底層array或vector的起頭處；min-heap的最小值在根節(jié)點，亦總是位于底層array或vector起頭處。STL 供應(yīng)的是max-heap，用c++實現(xiàn)。
堆排序c語言實現(xiàn)
http://m.shnenglu.com/tankzhouqiang/archive/2011/03/21/142413.html
（七）priority_queue
priority_queue是一個擁有權(quán)值觀念的queue,它允許加入新元素，移除舊元素，審視元素值等功能。由于這是一個queue，所以只允許在底端加入元素，并從頂端取出元素，除此之外別無其它存取元素的途徑。priority_queue帶有權(quán)值觀念，其內(nèi)的元素并非依照被推入的次序排列，而是自動依照元素的權(quán)值排列（通常權(quán)值以實值表示）。權(quán)值最高者，排在最前面。缺省情況下priority_queue系利用一個max-heap完成，后者是一個以vector表現(xiàn)的 complete binary tree.max-heap可以滿足priority_queue所需要的"依權(quán)值高低自動遞減排序"的特性。
priority_queue完全以底部容器作為根據(jù)，再加上heap處理規(guī)則，所以其實現(xiàn)非常簡單。缺省情況下是以vector為底部容器。queue以底部容器完成其所有工作。具有這種"修改某物接口，形成另一種風(fēng)貌"之性質(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完全相同，唯一的差別在于它允許鍵值重復(fù)，因此它的插入操作采用的是底層機制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完全相同，唯一的差別在于它允許鍵值重復(fù)，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique。