前言

源碼之前，了無秘密。

上一篇，我們剖析了 STL 迭代器源碼與 traits 編程技法?，這一篇我們來學習下容器。

在 STL 編程中，容器是我們經(jīng)常會用到的一種數(shù)據(jù)結構，容器分為序列式容器和關聯(lián)式容器。

兩者的本質區(qū)別在于：序列式容器是通過元素在容器中的位置順序存儲和訪問元素，而關聯(lián)容器則是通過鍵 (key) 存儲和讀取元素。

本篇著重剖析序列式容器相關背后的知識點。

容器分類

前面提到了，根據(jù)元素存儲方式的不同，容器可分為序列式和關聯(lián)式，那具體的又有哪些分類呢，這里我畫了一張圖來看一下。

限于篇幅，這篇文章小賀會來重點講解一下經(jīng)常使用到的那些容器，比如 vector，list，deque，以及衍生的棧和隊列其背后核心的設計和奧秘，不多 BB， 馬上就來分析。

vector

寫 C 的小伙伴們，應該對 vector 都非常熟悉了，vector 基本能夠支持任何類型的對象，同時它也是一個可以動態(tài)增長的數(shù)組，使用起來非常的方便。

但如果我問你，知道它是如何做到動態(tài)擴容的嗎？哎，是不是一時半會答不上來了，哈哈，沒事，我們一起來看看。

vector 基本數(shù)據(jù)結構

基本上，STL 里面所有的容器的源碼都包含至少三個部分：

• 迭代器，遍歷容器的元素，控制容器空間的邊界和元素的移動；
• 構造函數(shù)，滿足容器的多種初始化；
• 屬性的獲取，比如 begin()，end()等；

vector 也不例外，其實看了源碼之后就發(fā)現(xiàn)，vector 相反是所有容器里面最簡單的一種。

template?<class?T,?class?Alloc?=?alloc>
class?vector?{
public:
???//?定義?vector?自身的嵌套型別
????typedef?T?value_type;
????typedef?value_type*?pointer;
????typedef?const?value_type*?const_pointer;
????//?定義迭代器,?這里就只是一個普通的指針
????typedef?value_type*?iterator;
????typedef?const?value_type*?const_iterator;
????typedef?value_type