什麼是容器
容器，顧名思義，是用來容放東西的場所。C++容器容放某種數據結構，以利於對數據的搜尋或排序或其他特殊目的。眾所周知，常用的數據結構不外乎：數組array, 鏈表list， 樹tree， 棧stack， 隊列queue， 散列表hash table, 集合set、映射表map 等等。容器便是容納這些數據結構的。這些數據結構分為序列式與關聯式兩種，故容器也分為序列式容器和關聯式容器。
(圖來自《STL源碼剖析》)
vector 概述
1. vector是STL提供的一種序列式容器
所謂序列式容器，其中的元素都序，但未必有序，即元素集合呈線性關系排列，但未必是有序的。C++本身帶了一種序列式容器array，STL再提供其他的序列式容器：vector，list，deque,stack，queue，priority-queue等。
2. vector底層為動態數組
vector的數據安排以及操作方式與C++的array十分相似，它們間的唯一差別在於對空間的運用靈活性上。array為靜態數組，有著靜態數組最大的缺點：每次只能分配一定大小的存儲空間，當有新元素插入時，要經歷 “找到更大的內存空間”->“把數據復制到新空間” ->“銷毀舊空間” 三部曲， 且對於array而言，這種空間任務壓在使用它的用戶身上，用戶必須把握好數據的數量，盡量在第一次分配時就給數據分配合理的空間（這有時很難做到），以防止“三部曲”帶來的代價，而數據溢出也是靜態數組使用者需要注意的問題。
而vector用戶不需要親自處理空間運用問題。vector是動態空間，隨著新元素的插入，舊存儲空間不夠用時，vector內部機制會自行擴充空間以容納新元素，當然，這種空間擴充大部分情況下（幾乎是）也逃脫不了“三部曲”，只是不需要用戶自己處理，而且vector處理得更加安全高效。vector的實現技術關鍵就在於對其大小的控制以及重新配置時數據移動效率。
3. vector的迭代器
對於C語言的數組，我們使用普通指針就可以對數組進行各種操作。vector維護的是一個連續線性空間，與數組array一樣，所以無論其元素型別為何，普通指針都可以作為vector的迭代器而滿足所有必要的條件。vector所需要的迭代器操作，包括operator*,operator->,operator++,operator--,operator+=,operator-=等，普通指針都具有。
故，普通指針即可滿足vector對迭代器的需求。所以，vector提供了Random Access Iterators。
4. vector的數據結構
正如上面所說，vector底層為連續線性空間。它使用兩個迭代器：begin與finish該連續線性空間中的第一個元素的位置與超出末端的第一位位置，這兩個迭代器標志了連續線性空間的已使用范圍，並以end_of_storage迭代器標准整個連續線性空間的尾端。這裡begin與finish符合STL“前開後閉”的標准。
基於這三個迭代器，可以完成許多操作。包括提供首尾標示、大小、容量、空容器判斷、[]運算符、最前端元素值、最後端元素值等等。
值得注意的是，容器的大小與容量是不一樣的概念。只有在容器滿載時，大小才等於容器。在上面這張圖中，大小size為已使用的存儲空間長度，而容量為已使用+未使用的存儲空間長度。從它們的實現代碼上也可以看出來：
size_type size() const
{
return size_type( end() - begin() ) ;
}
size_type capacity () const
{
return size_type( end_of_storage - begin() );
}
5. vector的內存分配策略
標准庫的實現者使用了這樣的內存分配策略：以最小的代價連續存儲元素。為了使vector容器實現快速的內存分配，其實際分配的容量要比當前所需的空間多一些，vector容器預留了這些額外的存儲區用於存放添加的新元素，於是不必為每個新元素進行一次內存分配。當繼續向容器中加入元素導致備用空間被用光（超過了容量 capacity），此時再加入元素時vector的內存管理機制便會擴充容量至兩倍，如果兩倍容量仍不足，就擴張至足夠大的容量。容量擴張必須經歷“重新配置、元素移動、釋放原空間”這個浩大的工程。按照《STL源碼剖析》中提供的vector源碼，vector的內存配置原則為：
如果vector原大小為0，則配置1，也即一個元素的大小。
如果原大小不為0，則配置原大小的兩倍。
當然，vector的每種實現都可以自由地選擇自己的內存分配策略，分配多少內存取決於其實現方式，不同的庫采用不同的分配策略。
需要注意的是，使用vector迭代器時要時刻注意vector是否發生了擴容，一旦擴容引起了空間重新配置，指向原vector的所有迭代器都將失效。
關於vector各種接口的使用方法這裡就不再贅述了。對於vector有新認識會及時更新博文。
