前言源碼之前，了無秘密。

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

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

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

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

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

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

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

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

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

迭代器，遍歷容器的元素，控制容器空間的邊界和元素的移動；

構(gòu)造函數(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& reference;

typedef const value_type& const_reference;

typedef size_t size_type;

typedef ptrdiff_t difference_type;

。。.

protected：

typedef simple_alloc《value_type， Alloc》 data_allocator; // 設(shè)置其空間配置器

iterator start; // 當(dāng)前使用空間的頭

iterator finish; // 當(dāng)前使用空間的尾

iterator end_of_storage; // 當(dāng)前可用空間的尾

。。.

};

因為 vector 需要表示用戶操作的當(dāng)前數(shù)據(jù)的起始地址，結(jié)束地址，還需要其真正的最大地址。所以總共需要 3 個迭代器，分別來指向數(shù)據(jù)的頭（start），數(shù)據(jù)的尾（finish），數(shù)組的尾（end_of_storage）。

構(gòu)造函數(shù)

vector 有多個構(gòu)造函數(shù)， 為了滿足多種初始化。

我們看到，這里面，初始化滿足要么都初始化成功， 要么一個都不初始化并釋放掉拋出異常，在 STL 里面，異常機(jī)制這塊拿捏的死死的呀。

因為 vector 是一種 class template， 所以呢，我們并不需要手動的釋放內(nèi)存， 生命周期結(jié)束后就自動調(diào)用析構(gòu)從而釋放調(diào)用空間，當(dāng)然我們也可以直接調(diào)用析構(gòu)函數(shù)釋放內(nèi)存。

void deallocate（） {

if （start）

data_allocator：：deallocate（start， end_of_storage - start）;

}

// 調(diào)用析構(gòu)函數(shù)并釋放內(nèi)存

~vector（） {

destroy（start， finish）;

deallocate（）;

}

屬性獲取

下面的部分就涉及到了位置參數(shù)的獲取， 比如返回 vector 的開始和結(jié)尾，返回最后一個元素，返回當(dāng)前元素個數(shù)，元素容量，是否為空等。

這里需要注意的是因為 end（） 返回的是 finish，而 finish 是指向最后一個元素的后一個位置的指針，所以使用 end（） 的時候要注意。

public：

// 獲取數(shù)據(jù)的開始以及結(jié)束位置的指針。 記住這里返回的是迭代器， 也就是 vector 迭代器就是該類型的指針。

iterator begin（） { return start; }

iterator end（） { return finish; }

reference front（） { return *begin（）; } // 獲取值

reference back（） { return *（end（） - 1）; }

。。.

size_type size（） const { return size_type（end（） - begin（））; } // 數(shù)組元素的個數(shù)

size_type max_size（） const { return size_type（-1） / sizeof（T）; } // 最大能存儲的元素個數(shù)

size_type capacity（） const { return size_type（end_of_storage - begin（））; } // 數(shù)組的實際大小

bool empty（） const { return begin（） == end（）; }

//判斷 vector 是否為空， 并不是比較元素為 0，是直接比較頭尾指針。

push 和 pop 操作

vector 的 push 和 pop 操作都只是對尾進(jìn)行操作， 這里說的尾部是指數(shù)據(jù)的尾部。當(dāng)調(diào)用 push_back 插入新元素的時候，首先會檢查是否有備用空間，如果有就直接在備用空間上構(gòu)造元素，并調(diào)整迭代器 finish。

當(dāng)如果沒有備用空間，就擴(kuò)充空間（重新配置-移動數(shù)據(jù)-釋放原空間），這里實際是調(diào)用了另外一個函數(shù)：insert_aux 函數(shù)。

在上面這張圖里，可以看到，push_back 這個函數(shù)里面又判斷了一次 finish ！= end_of_storage 這是因為啥呢？這里的原因是因為 insert_aux 函數(shù)可能還被其他函數(shù)調(diào)用哦。

在下面的 else 分支里面，我們看到了 vector 的動態(tài)擴(kuò)容機(jī)制：如果原空間大小為 0 則分配 1 個元素，如果大于 0 則分配原空間兩倍的新空間，然后把數(shù)據(jù)拷貝過去。

pop 元素：從尾端刪除一個元素。

public：

//將尾端元素拿掉 并調(diào)整大小

void pop_back（） {

--finish;//將尾端標(biāo)記往前移動一個位置 放棄尾端元素

destroy（finish）;

}

erase 刪除元素

erase 函數(shù)清除指定位置的元素， 其重載函數(shù)用于清除一個范圍內(nèi)的所有元素。實際實現(xiàn)就是將刪除元素后面所有元素往前移動，對于 vector 來說刪除元素的操作開銷還是很大的，所以說 vector 它不適合頻繁的刪除操作，畢竟它是一個數(shù)組。

//清楚［first， last）中的所有元素

iterator erase（iterator first， iterator last） {

iterator i = copy（last， finish， first）;

destroy（i， finish）;

finish = finish - （last - first）;

return first;

}

//清除指定位置的元素

iterator erase（iterator position） {

if （position + 1 ！= end（））

copy（position + 1， finish， position）;//copy 全局函數(shù)

}

--finish;

destroy（finish）;

return position;

}

void clear（） {

erase（begin（）， end（））;

}

我們結(jié)合圖解來看一下：

清楚范圍內(nèi)的元素，第一步要將 finish 迭代器后面的元素拷貝回去，然后返回拷貝完成的尾部迭代器，最后在刪除之前的。

刪除指定位置的元素就是實際就是將指定位置后面的所有元素向前移動， 最后析構(gòu)掉最后一個元素。

insert 插入元素

vector 的插入元素具體來說呢，又分三種情況：

1、如果備用空間足夠且插入點的現(xiàn)有元素多于新增元素；

2、如果備用空間足夠且插入點的現(xiàn)有元素小于新增元素；

3、如果備用空間不夠；

我們一個一個來分析。

插入點之后的現(xiàn)有元素個數(shù) 》 新增元素個數(shù)

插入點之后的現(xiàn)有元素個數(shù) 《= 新增元素個數(shù)

如果備用空間不足

這里呢，要注意一個坑，就是所謂的迭代器失效問題。通過圖解我們就明白了，所謂的迭代器失效問題是由于元素空間重新配置導(dǎo)致之前的迭代器訪問的元素不在了，總結(jié)來說有兩種情況：

由于插入元素，使得容器元素整體遷移導(dǎo)致存放原容器元素的空間不再有效，從而使得指向原空間的迭代器失效。

由于刪除元素，使得某些元素次序發(fā)生變化導(dǎo)致原本指向某元素的迭代器不再指向期望指向的元素。

前面提到的一些全局函數(shù)，這里在總結(jié)一下：

copy（a，b，c）：將（a，b）之間的元素拷貝到（c，c-（b-a））位置

uninitialized_copy（first， last， result）：具體作用是將 ［first，last）內(nèi)的元素拷貝到 result 從前往后拷貝

copy_backward（first， last， result）：將 ［first，last）內(nèi)的元素拷貝到 result 從后往前拷貝

vector 總結(jié)

到這里呢，vector 分析的就差不多了，最后提醒需要注意的是：vector 的成員函數(shù)都不做邊界檢查 （at方法會拋異常），使用者要自己確保迭代器和索引值的合法性。

我們來總結(jié)一下 vector 的優(yōu)缺點。

優(yōu)點

在內(nèi)存中是分配一塊連續(xù)的內(nèi)存空間進(jìn)行存儲，可以像數(shù)組一樣操作，并且支持動態(tài)擴(kuò)容。

因此元素的隨機(jī)訪問方便，支持下標(biāo)訪問和 vector.at（） 操作。

節(jié)省空間。

缺點

由于其順序存儲的特性，vector 插入刪除操作的時間復(fù)雜度是 O（n）。

只能在末端進(jìn)行 pop 和 push。

當(dāng)動態(tài)長度超過默認(rèn)分配大小后，要整體重新分配、拷貝和釋放空間。

list好了，下面我們來看一下 list，list 是一種雙向鏈表。

list 的設(shè)計更加復(fù)雜一點，好處是每次插入或刪除一個元素，就配置或釋放一個元素，list 對于空間的運(yùn)用有絕對的精準(zhǔn)，一點也不浪費(fèi)。而且對于任何位置的元素插入或刪除，list 永遠(yuǎn)是常數(shù)空間。

注意：list 源碼里其實分了兩個部分，一個部分是 list 結(jié)構(gòu)，另一部分是 list 節(jié)點的結(jié)構(gòu)。

那這里不妨思考一下，為什么 list 節(jié)點分為了兩個部分，而不是在一個結(jié)構(gòu)體里面呢？ 也就是說為什么指針變量和數(shù)據(jù)變量分開定義呢？

如果看了后面的源碼就曉得了，這里是為了給迭代器做鋪墊，因為迭代器遍歷的時候不需要數(shù)據(jù)成員的，只需要前后指針就可以遍歷該 list。

list 的節(jié)點結(jié)構(gòu)如下圖所示：

list 數(shù)據(jù)結(jié)構(gòu)-節(jié)點

__list_node 用來實現(xiàn)節(jié)點，數(shù)據(jù)結(jié)構(gòu)中就儲存前后指針和屬性。

template 《class T》 struct __list_node {

// 前后指針

typedef void* void_pointer;

void_pointer next;

void_pointer prev;

// 屬性

T data;

};

來瞅一瞅，list 的節(jié)點長啥樣，因為 list 是一種雙向鏈表，所以基本結(jié)構(gòu)就是下面這個樣子：

基本類型

template《class T， class Ref， class Ptr》 struct __list_iterator {

typedef __list_iterator《T， T&， T*》 iterator; // 迭代器

typedef __list_iterator《T， const T&， const T*》 const_iterator;

typedef __list_iterator《T， Ref， Ptr》 self;

// 迭代器是bidirectional_iterator_tag類型

typedef bidirectional_iterator_tag iterator_category;

typedef T value_type;

typedef Ptr pointer;

typedef Ref reference;

typedef size_t size_type;

typedef ptrdiff_t difference_type;

。。.

};

構(gòu)造函數(shù)

template《class T， class Ref， class Ptr》 struct __list_iterator {

。。.

// 定義節(jié)點指針

typedef __list_node《T》* link_type;

link_type node;

// 構(gòu)造函數(shù)

__list_iterator（link_type x） ： node（x） {}

__list_iterator（） {}

__list_iterator（const iterator& x） ： node（x.node） {}

。。.

};

重載

template《class T， class Ref， class Ptr》 struct __list_iterator {

。。.

// 重載

bool operator==（const self& x） const { return node == x.node; }

bool operator！=（const self& x） const { return node ！= x.node; }

。。.

// ++和--是直接操作的指針指向next還是prev， 因為list是一個雙向鏈表

self& operator++（） {

node = （link_type）（（*node）.next）;

return *this;

}

self operator++（int） {

self tmp = *this;

++*this;

return tmp;

}

self& operator--（） {

node = （link_type）（（*node）.prev）;

return *this;

}

self operator--（int） {

self tmp = *this;

--*this;

return tmp;

}

};

list 結(jié)構(gòu)

list 自己定義了嵌套類型滿足 traits 編程， list 迭代器是 bidirectional_iterator_tag 類型，并不是一個普通指針。

list 在定義 node 節(jié)點時， 定義的不是一個指針，這里要注意。

template 《class T， class Alloc = alloc》

class list {protected：

typedef void* void_pointer;

typedef __list_node《T》 list_node; // 節(jié)點 就是前面分析過的

typedef simple_alloc《list_node， Alloc》 list_node_allocator; // 空間配置器public：

// 定義嵌套類型

typedef T value_type;

typedef value_type* pointer;

typedef const value_type* const_pointer;

typedef value_type& reference;

typedef const value_type& const_reference;

typedef list_node* link_type;

typedef size_t size_type;

typedef ptrdiff_t difference_type;

protected：

// 定義一個節(jié)點， 這里節(jié)點并不是一個指針。

link_type node;

public：

// 定義迭代器

typedef __list_iterator《T， T&， T*》 iterator;

typedef __list_iterator《T， const T&， const T*》 const_iterator;

。。.

};

list 構(gòu)造和析構(gòu)函數(shù)實現(xiàn)

構(gòu)造函數(shù)前期準(zhǔn)備：

每個構(gòu)造函數(shù)都會創(chuàng)造一個空的 node 節(jié)點，為了保證我們在執(zhí)行任何操作都不會修改迭代器。

list 默認(rèn)使用 alloc 作為空間配置器，并根據(jù)這個另外定義了一個 list_node_allocator，目的是更加方便以節(jié)點大小來配置單元。

template 《class T， class Alloc = alloc》

class list {protected：

typedef void* void_pointer;

typedef __list_node《T》 list_node; // 節(jié)點

typedef simple_alloc《list_node， Alloc》 list_node_allocator; // 空間配置器

其中，list_node_allocator（n） 表示配置 n 個節(jié)點空間。以下四個函數(shù)，分別用來配置，釋放，構(gòu)造，銷毀一個節(jié)點。

class list {protected：

// 配置一個節(jié)點并返回

link_type get_node（） { return list_node_allocator：：allocate（）; }

// 釋放一個節(jié)點

void put_node（link_type p） { list_node_allocator：：deallocate（p）; }

// 產(chǎn)生（配置并構(gòu)造）一個節(jié)點帶有元素初始值

link_type create_node（const T& x） {

link_type p = get_node（）;

__STL_TRY {

construct（&p-》data， x）;

}

__STL_UNWIND（put_node（p））;

return p;

}

//銷毀（析構(gòu)并釋放）一個節(jié)點

void destroy_node（link_type p） {

destroy（&p-》data）;

put_node（p）;

}

// 對節(jié)點初始化

void empty_initialize（） {

node = get_node（）;

node-》next = node;

node-》prev = node;

}

};

基本屬性獲取

template 《class T， class Alloc = alloc》

class list {

。。.

public：

iterator begin（） { return （link_type）（（*node）.next）; } // 返回指向頭的指針

const_iterator begin（） const { return （link_type）（（*node）.next）; }

iterator end（） { return node; } // 返回最后一個元素的后一個的地址

const_iterator end（） const { return node; }

// 這里是為旋轉(zhuǎn)做準(zhǔn)備， rbegin返回最后一個地址， rend返回第一個地址。 我們放在配接器里面分析

reverse_iterator rbegin（） { return reverse_iterator（end（））; }

const_reverse_iterator rbegin（） const {

return const_reverse_iterator（end（））;

}

reverse_iterator rend（） { return reverse_iterator（begin（））; }

const_reverse_iterator rend（） const {

return const_reverse_iterator（begin（））;

}

// 判斷是否為空鏈表， 這是判斷只有一個空node來表示鏈表為空。

bool empty（） const { return node-》next == node; }

// 因為這個鏈表， 地址并不連續(xù)， 所以要自己迭代計算鏈表的長度。

size_type size（） const {

size_type result = 0;

distance（begin（）， end（）， result）;

return result;

}

size_type max_size（） const { return size_type（-1）; }

// 返回第一個元素的值

reference front（） { return *begin（）; }

const_reference front（） const { return *begin（）; }

// 返回最后一個元素的值

reference back（） { return *（--end（））; }

const_reference back（） const { return *（--end（））; }

// 交換

void swap（list《T， Alloc》& x） { __STD：：swap（node， x.node）; }

。。.

};

template 《class T， class Alloc》

inline void swap（list《T， Alloc》& x， list《T， Alloc》& y） {

x.swap（y）;

編輯：jq