超硬核 | 2 萬字 20 圖帶你手撕 STL 序列式容器源碼

前言

源碼之前，了無秘密。

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

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

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

本篇著重剖析序列式容器相關(guān)背后的知識(shí)點(diǎn)。

容器分類

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

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

vector

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

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

vector 基本數(shù)據(jù)結(jié)構(gòu)

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

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

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

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