本文簡單地總結了STL的順序容器的知識點。文中並不涉及具體的實現技巧，對於細節的東西也沒有提及。一來不同的標准庫有著不同的實現，二來關於具體實現《STL源碼剖析》已經展示得全面細致。所以本文僅僅是對容器基礎知識的歸納。至於容器提供的接口與使用實例，建議查取官方文檔。文章難免有錯漏，希望指出。
容器，置物之所也。像桶可裝水，碗可盛湯，C++的容器，可以存儲對象。容器有多種，用來處理不同的元素操作訴求。按照元素存儲到容器中以及訪問方式的差異，容器分為順序容器與關聯容器。順序容器也稱為序列式容器。序列式容器按元素插入的順序存儲元素，這些元素可以進行排序，但未必是有序的。C++本身內置了一個序列式容器array（數組），STL另外提供了vector,list,forward_list,deque,stack,queue,priority-queue，string等等序列式容器。所有的容器都是基於模板實現的，因為容器必須保證能裝得下各種各樣的類型。其中，stack，queue都是基於deque來實現的，priority-queue基於heap來實現，從技術上來說它們屬於容器適配器（adapter）。其中array與forward_list是C++11添加的新容器類型。
array的底層數據結構是固定數組。與C-style的數組類似，它的大小在定義後就不能被改變。由於array具有固定的大小，它不支持添加和刪除元素或改變容器大小等其他容器擁有的操作。在定義一個array容器的時候必須指定大小：
Defined in header <array>
template<
class T,
std::size_t N
> struct array;在內存分配策略上，array也與C-style數組類似。編譯器在哪裡為array分配內存，取決於array定義的位置和方式。
例如，在函數定義的array局部對象在棧上分配內存，與此對比的是vector，它底層數據結構為動態數組，因此在自由存儲區上分配內存：
#include <array>
#include <vector>
#include <iostream>
using namespace std;
int main() {
int stack_var;
array<int, 5> a;
vector<int> b(5);
cout << "stack area: 0x" << hex << (uintptr_t)&stack_var << endl;
cout << "a[3] address: 0x" << hex << (uintptr_t)&a[3] << endl;
cout << "b[3] address: 0x" << hex << (uintptr_t)&b[3] << endl;
getchar();
return 0;
}結果：
另外，不像C-style數組，array容器類型的名稱不會自動轉換為指針。對於C++程序員來說，array要比C-style數組更好用。
forward_list的底層數據結構為單向鏈表。如C++標准所講，forward_list容器支持前向遍歷元素序列，允許常數時間內在任意位置的插入或刪除操作並進行自動的內存管理。與list的主要區別是forward_list沒有反方向的迭代器，不過也正因如此，forward_list的每個節點都節省了迭代器大小的開銷，在元素眾多的時候，將比list消耗少得多的內存。
受單向鏈表這種特殊結構的影響，forward_list在很多地方表現得和其他容器不同：
在所有已知的STL容器中，forward_list是唯一一個不提供size()的容器。不提供的原因在於計算一個forward_list的長度需要線性的時間，庫用戶有時無法忍受這樣的時間開銷。其他容器提供的size()操作皆可以在常數時間內完成（在C++98時，list也是線性時間）。為了節省內存，forward_list甚至不跟蹤序列的長度，要想獲得某個forward_list對象的長度，用戶需要通過distance()來計算。這帶來了一些不便，但使得用戶遠離了size()帶來的高消耗。每個容器類型都有三個與大小相關的操作：max_size(),empty(),size(),而forward_list只提供了前兩個。
int main()
{
forward_list<int> flist;
for (int i = 0; i < 10; i++)
{
flist.push_front(i);
}
std::cout << std::distance(flist.begin(), flist.end()); //輸出10
getchar();
}為此，forward_list提供了如下的插入接口：
其他所有STL容器都是在指定位置之前插入元素（除了std::array，它不允許插入）。forward_list的這種特殊處理，還是出於效率的考慮。對於單鏈表我們應該很熟悉，為了在某個指定節點之前插入插入節點，我們必須改變插入位置的前一個節點的指向。換句話說，為了在指定節點之前插入新元素，我們必須要先獲得插入位置前一個位置的節點，為了獲取前面這個節點，需要線性的操作時間。
而如果我們是在指定位置之後插入新元素，則無需線性時間的查找操作，這樣可實現常數時間的插入：
同樣的，處於性能的考慮，forward_list沒有提供在尾部進行操作的接口，包括push_back(),pop_back()和emplace_back(),這些操作對單列表來說都至少要花費O(n)來完成。
指向被刪除元素的迭代器，在刪除之後失效。
list同樣是一個模板類，它底層數據結構為雙向循環鏈表。因此，它支持任意位置常數時間的插入/刪除操作，不支持快速隨機訪問。
list的迭代器具備前移、後移的能力，所以list提供的是Bidirectional iterator(雙向迭代器)。由於采用的是雙向迭代器，自然也很方便在指定元素之前插入新節點，所以list很正常地提供了insert()操作與push_back()/pop_back()操作。在C++11中，list新增了三個接口，以支持在指定位置構造對象後插入容器中:
list的空間配置策略，自然是像我們普通雙向鏈表那樣，有多少元素申請多少內存。它不像vactor那樣需要預留空間供新元素的分配，也不會因找不到連續的空間而引起整個容器的內存遷移。
list 有一個重要性質：插入操作（insert）與接合操作（splice）都不會造成原有的list迭代器失效。這在vector是不成立的，因為vactor的插入可能引起空間的重新配置，導致原來的迭代器全部失效。list的迭代器失效，只會出現在刪除的時候，指向刪除元素的那個迭代器在刪除後失效。
通常來說，forward_list在使用靈活度上比不上list，因為它只能單向迭代元素，且提供的接口沒有list多。然而，在內存的使用上，它是比list占優勢的。當對內存的要求占首要位置時，應該選擇forward_list。
vector的底層數據結構是動態數組，因此，vector的數據安排以及操作方式與std::array十很相似，它們間的唯一差別在於對空間的運用靈活性上。array為靜態數組，有著靜態數組最大的缺點：每次只能分配一定大小的存儲空間，當有新元素插入時，要經歷 “找到更大的內存空間”->“把數據復制到新空間” ->“銷毀舊空間” 三部曲， 對於std::array而言，這種空間管理的任務壓在使用它的用戶身上，用戶必須把握好數據的數量，盡量在第一次分配時就給數據分配合理的空間（這有時很難做到），以防止“三部曲”帶來的代價，而數據溢出也是靜態數組使用者需要注意的問題。而vector用戶不需要親自處理空間運用問題。vector是動態空間，隨著新元素的插入，舊存儲空間不夠用時，vector內部機制會自行擴充空間以容納新元素，當然，這種空間擴充大部分情況下（幾乎是）也逃脫不了“三部曲”，只是不需要用戶自己處理，而且vector處理得更加安全高效。vector的實現技術關鍵就在於對其大小的控制以及重新配置時數據移動效率。
對於C_style數組，我們使用普通指針就可以對數組進行各種操作。vector維護的是一個連續線性空間，與數組一樣，所以無論其元素型別為何，普通指針都可以作為vector的迭代器而滿足所有必要的條件。vector所需要的迭代器操作，包括operator*,operator->,operator++,operator--,operator+=,operator-=等，普通指針都具有。因此，普通指針即可滿足vector對迭代器的需求。所以，vector提供了Random Access Iterators。
標准庫的實現者使用了這樣的內存分配策略：以最小的代價連續存儲元素。為了使vector容器實現快速的內存分配，其實際分配的容量要比當前所需的空間多一些(預留空間)，vector容器預留了這些額外的存儲區用於存放添加的新元素，於是不必為每個新元素進行一次內存分配。當繼續向容器中加入元素導致備用空間被用光（超過了容量 capacity），此時再加入元素時vector的內存管理機制便會擴充容量至兩倍，如果兩倍容量仍不足，就擴張至足夠大的容量。容量擴張必須經歷“重新配置、元素移動、釋放原空間”這個浩大的工程。按照《STL源碼剖析》中提供的vector源碼，vector的內存配置原則為：
當然，vector的每種實現都可以自由地選擇自己的內存分配策略，分配多少內存取決於其實現方式，不同的庫采用不同的分配策略。
vector是單向開口的線性連續空間，deque則是一種雙向開口的連續數據空間。所謂的雙向開口，意思是可以在頭尾兩端分別做元素的插入和刪除操作。當然vector也可以在頭尾兩端進行操作，但是其頭部操作效果奇差，所以標准庫沒有為vector提供push_front或pop_front操作。與vector類似，deque支持元素的快速隨機訪問。deque的示意圖如下：
現在問題來了：如果deque以數組來實現，如何做到在頭部的常數時間插入？如果是采用鏈表來實現，又如何做到快速隨機訪問？deque的內部數據結構到底如何？想必你已經猜到了，要實現如上需求，需要由一段一段的連續空間鏈接起來的數據結構才能滿足。
接著上面講。deque由一段一段的連續空間所鏈接而成，一旦需要在deque的前端或尾端增加新空間，便配置一段定量的連續空間，並將該空間串接在deque的頭部或尾部。deque復雜的迭代器架構，構建出了所有分段連續空間”整體連續“的假象。
既然deque是由一段一段定長的連續空間所構成，就需要有結構來管理這些連續空間。deque采用一塊map（非STL中的map）作為主控，map是一塊小的連續空間，其中每個元素都是指針，指向一塊較大的線性連續空間，稱為緩沖區。而緩沖區才是存儲deque元素的空間主體。示例圖：
map本身也是一塊固定大小的連續空間，當緩沖區數量增多，map容不下更多的指針時，deque會尋找一塊新的空間來作為map。
為了使得這些分段的連續空間看起來像是一個整體，deque的迭代器必須有這樣的能力：它必須能夠指出分段連續空間在哪裡，判斷自己所指的位置是否位於某一個緩沖區的邊緣，如果位於邊緣，則執行operator-- 或operator++時要能夠自動跳到下一個緩沖區。因此，盡管deque的迭代器也是Ramdon Access Iterator 迭代器，但它的實現要比vector的復雜太多。SGI版本的STL deque實現思路可以看侯捷的《STL源碼剖析》。
stack，也稱為棧，是一種先進後出的數據結構。STL中的statck是一種容器適配器。所謂的容器適配器，是以某種容器作為底部容器，在底部容器之上修改接口，形成另一種風貌。stack默認以雙端隊列deque作為底部容器。stack沒有提供迭代器，通過push/pop接口對棧頂元素進行操作。
queue，也稱為隊列，是一種先進先出的數據結構，它同樣也是一種容器適配器。它的底部容器默認為deque。同樣，queue也沒有提供迭代器，通過push向隊尾壓入元素，pop從隊首彈出元素。
priority-queue，優先隊列，是一種擁有權值觀念的隊列，例如在以整數大小作為衡量的權值定義下，priority-queue總是彈出最大的數。priority-queue的底部數據結構默認是max-heap，大頂堆。
注意：
