容器分為序列式容器和關聯式容器，序列式容器主要包括vector、list、deque、stack、queue、heap、priority_queue和slist等；關聯式容器主要是基于紅黑樹實現，主要包括set、map、hashtable、hash_set、hash_map等。本文主要梳理vector的相關知識點。

vector實現思想：

1.擴充空間包括的操作：（1）申請新空間（2）數據移動（3）釋放舊空間，這個過程十分耗時，而vector的關鍵就是如何處理自動擴充空間，從而提升效率。
2.連續線性空間、動態分配空間、隨機存取，所以vector提供的是random access Iterators
3.運用start、finish和end_of_storage三個迭代器，就可以實現首尾標示、大小、容量、空容器判斷、[]運算、最前端元素、最后段元素等功能。

vector關鍵技術

1.vector的構造與內存管理
關注點：構造的方式、元素的添加、大小和容量的變化
（1）元素添加與構造方式：將新元素插入vector尾端時，首先檢查是否還有備用空間，如果有就直接在備用空間上構造元素；如果沒有，就擴充空間。
（2）2倍擴容技術
在添加元素時，如果沒有足夠的備用空間，那么vector會使用2倍擴容技術，為新的元素申請新的存儲空間（如果原大小為0，則申請1個空間）。注意，動態增加大小，并不是在原有空間之后連接新空間，因為無法保證源空間之后還有可供配置的空間，而是以原來大小的兩倍重新配置一塊較大空間，然后將原內容拷貝過來，然后在原內容之后構造新元素，并釋放原空間。（申請新空間+拷貝原數據+釋放原空間）

vector插入元素實現（3種情況）