參考：STL源碼分析
（一）vector容器
vector的數(shù)據(jù)安排以及操作方式，與array非常相似。兩者的唯一區(qū)別在于空間的運(yùn)用的靈活性。array是靜態(tài)空間，一旦配置了就不能改變。vector是動(dòng)態(tài)空間，隨著元素的加入，它的內(nèi)部機(jī)制會(huì)自行擴(kuò)充空間以容納新元素。因此，vector的運(yùn)用對(duì)于內(nèi)存的合理利用與運(yùn)用的靈活性有很大的幫助，我們?cè)僖膊槐匾驗(yàn)楹ε驴臻g不足而一開(kāi)始要求一個(gè)大塊的array。
vector動(dòng)態(tài)增加大小，并不是在原空間之后持續(xù)新空間（因?yàn)闊o(wú)法保證原空間之后尚有可供配置的空間），而是以原大小的兩倍另外配置一塊較大的空間，然后將原內(nèi)容拷貝過(guò)來(lái)，然后才開(kāi)始在原內(nèi)容之后構(gòu)造新元素，并釋放原空間。因此，對(duì)vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效了。
（二）list容器
相對(duì)于vector的連續(xù)空間，list就顯得復(fù)雜許多，它的好處是每次插入或刪除一個(gè)元素，就配置或釋放一個(gè)元素空間。因此，list對(duì)于空間的運(yùn)用有絕對(duì)的精準(zhǔn)，一點(diǎn)也不浪費(fèi)。而且，對(duì)于任何位置的元素插入或元素移除，list永遠(yuǎn)是常數(shù)時(shí)間。STL中的list是一個(gè)雙向鏈表，而且是一個(gè)環(huán)狀雙向鏈表。
（三）deque容器
deque 是一種雙向開(kāi)口的連續(xù)線性空間。所謂雙向開(kāi)口，意思是可以在隊(duì)尾兩端分別做元素的插入和刪除操作。deque和vector的最大差異，一在于deque允許于常數(shù)時(shí)間內(nèi)對(duì)起頭端進(jìn)行元素的插入或移除操作，二在于deque沒(méi)有所謂容量觀念，因?yàn)樗莿?dòng)態(tài)地以分段連續(xù)空間組合而成，隨時(shí)可以增加一段新的空間并鏈接在一起。換句話說(shuō)，像vector那樣"因舊空間不足而重新配置一塊更大空間，然后復(fù)制元素，再釋放舊空間"這樣的事情在 deque是不會(huì)發(fā)生的。
deque是由一段一段的定量連續(xù)空間構(gòu)成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續(xù)空間，串接在整個(gè)deque的頭端或尾端。deque的最大任務(wù)，便是在這些分段的定量連續(xù)空間上，維護(hù)其整體連續(xù)的假象，并提供隨機(jī)存取的接口。避開(kāi)了"重新配置，復(fù)制，釋放"的輪回，代價(jià)則是復(fù)雜的迭代器架構(gòu)。因?yàn)橛蟹侄芜B續(xù)線性空間，就必須有中央控制，而為了維持整體連續(xù)的假象，數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及迭代器前進(jìn)后退等操作都頗為繁瑣。
deque采用一塊所謂的map作為主控。這里的map是一小塊連續(xù)空間，其中每個(gè)元素都是指針，指向另一段連續(xù)線性空間，稱為緩沖區(qū)。緩沖區(qū)才是deque的存儲(chǔ)空間主體。SGI STL允許我們指定緩沖區(qū)大小，默認(rèn)值0表示將使用512 bytes緩沖區(qū)。
（四）stack
stack 是一種先進(jìn)后出（First In Last Out , FILO）的數(shù)據(jù)結(jié)構(gòu)。它只有一個(gè)出口，stack 允許新增元素，移除元素，取得最頂端元素。但除了最頂端外，沒(méi)有任何其它方法可以存取stack的其它元素，stack不允許遍歷行為。
以某種容器作為底部結(jié)構(gòu)，將其接口改變，使之符合“先進(jìn)后出”的特性，形成一個(gè)stack，是很容易做到的。deque是雙向開(kāi)口的數(shù)據(jù)結(jié)構(gòu)，若以deque為底部結(jié)構(gòu)并封閉其頭端開(kāi)口，便輕而易舉地形成了一個(gè)stack.因此，SGI STL 便以deque作為缺省情況下的stack底部結(jié)構(gòu)，由于stack 系以底部容器完成其所有工作，而具有這種"修改某物接口，形成另一種風(fēng)貌"之性質(zhì)者，稱為adapter（配接器），因此，STL stack 往往不被歸類為container(容器)，而被歸類為 container adapter.
(五） queue
queue是一種先進(jìn)先出(First In First Out,FIFO) 的數(shù)據(jù)結(jié)構(gòu)。它有兩個(gè)出口，queue允許新增元素，移除元素，從最底端加入元素，取得最頂端元素。但除了最底端可以加入，最頂端可以取出外，沒(méi)有任何其它方法可以存取queue的其它元素。
以某種容器作為底部結(jié)構(gòu)，將其接口改變，使之符合“先進(jìn)先出”的特性，形成一個(gè)queue，是很容易做到的。deque是雙向開(kāi)口的數(shù)據(jù)結(jié)構(gòu)，若以 deque為底部結(jié)構(gòu)并封閉其底部的出口和前端的入口，便輕而易舉地形成了一個(gè)queue.因此，SGI STL 便以deque作為缺省情況下的queue底部結(jié)構(gòu)，由于queue 系以底部容器完成其所有工作，而具有這種"修改某物接口，形成另一種風(fēng)貌"之性質(zhì)者，稱為adapter（配接器），因此，STL queue往往不被歸類為container(容器)，而被歸類為 container adapter.
(六)heap
heap并不歸屬于STL容器組件，它是個(gè)幕后英雄，扮演priority queue的助手。priority queue允許用戶以任何次序?qū)⑷魏卧赝迫肴萜髦校〕鰰r(shí)一定按從優(yōu)先權(quán)最高的元素開(kāi)始取。按照元素的排列方式，heap可分為max-heap和min-heap兩種，前者每個(gè)節(jié)點(diǎn)的鍵值(key)都大于或等于其子節(jié)點(diǎn)鍵值，后者的每個(gè)節(jié)點(diǎn)鍵值(key)都小于或等于其子節(jié)點(diǎn)鍵值。因此， max-heap的最大值在根節(jié)點(diǎn)，并總是位于底層array或vector的起頭處；min-heap的最小值在根節(jié)點(diǎn)，亦總是位于底層array或vector起頭處。STL 供應(yīng)的是max-heap，用c++實(shí)現(xiàn)。
堆排序c語(yǔ)言實(shí)現(xiàn)
http://www.shnenglu.com/tankzhouqiang/archive/2011/03/21/142413.html
（七）priority_queue
priority_queue是一個(gè)擁有權(quán)值觀念的queue,它允許加入新元素，移除舊元素，審視元素值等功能。由于這是一個(gè)queue，所以只允許在底端加入元素，并從頂端取出元素，除此之外別無(wú)其它存取元素的途徑。priority_queue帶有權(quán)值觀念，其內(nèi)的元素并非依照被推入的次序排列，而是自動(dòng)依照元素的權(quán)值排列（通常權(quán)值以實(shí)值表示）。權(quán)值最高者，排在最前面。缺省情況下priority_queue系利用一個(gè)max-heap完成，后者是一個(gè)以vector表現(xiàn)的 complete binary tree.max-heap可以滿足priority_queue所需要的"依權(quán)值高低自動(dòng)遞減排序"的特性。
priority_queue完全以底部容器作為根據(jù)，再加上heap處理規(guī)則，所以其實(shí)現(xiàn)非常簡(jiǎn)單。缺省情況下是以vector為底部容器。queue以底部容器完成其所有工作。具有這種"修改某物接口，形成另一種風(fēng)貌"之性質(zhì)者，稱為adapter(配接器)，因此，STL priority_queue往往不被歸類為container(容器)，而被歸類為container adapter.
(八)set,multiset
set的特性是，所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序。set的元素不像map那樣可以同時(shí)擁有實(shí)值(value)和鍵值(key), set 元素的鍵值就是實(shí)值，實(shí)值就是鍵值，set不允許兩個(gè)元素有相同的值。set是通過(guò)紅黑樹(shù)來(lái)實(shí)現(xiàn)的，由于紅黑樹(shù)（RB-tree）是一種平衡二叉搜索樹(shù)，自動(dòng)排序的效果很不錯(cuò)，所以標(biāo)準(zhǔn)的STL的set即以RB-Tree為底層機(jī)制。又由于set所開(kāi)放的各種操作接口，RB-tree也都提供了，所以幾乎所有的set操作行為，都只有轉(zhuǎn)調(diào)用RB-tree的操作行為而已。
multiset的特性以及用法和set完全相同，唯一的差別在于它允許鍵值重復(fù)，因此它的插入操作采用的是底層機(jī)制RB-tree的insert_equal()而非insert_unique().
（九）map,multimap
map的特性是，所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序。map的所有元素都是pair,同時(shí)擁有實(shí)值（value）和鍵值（key）. pair的第一元素被視為鍵值，第二元素被視為實(shí)值。map不允許兩個(gè)元素?fù)碛邢嗤逆I值.由于RB-tree是一種平衡二叉搜索樹(shù)，自動(dòng)排序的效果很不錯(cuò)，所以標(biāo)準(zhǔn)的STL map即以RB-tree為底層機(jī)制。又由于map所開(kāi)放的各種操作接口，RB-tree也都提供了，所以幾乎所有的map操作行為，都只是轉(zhuǎn)調(diào)RB-tree的操作行為。
multimap的特性以及用法與map完全相同，唯一的差別在于它允許鍵值重復(fù)，因此它的插入操作采用的是底層機(jī)制RB-tree的insert_equal()而非insert_unique。