前言源碼之前，了無(wú)秘密。

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

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

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

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

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

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

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

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& 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)前可用空間的尾

。。.

};

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

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

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

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

因?yàn)?vector 是一種 class template， 所以呢，我們并不需要手動(dòng)的釋放內(nèi)存， 生命周期結(jié)束后就自動(dòng)調(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 的開(kāi)始和結(jié)尾，返回最后一個(gè)元素，返回當(dāng)前元素個(gè)數(shù)，元素容量，是否為空等。

這里需要注意的是因?yàn)?end（） 返回的是 finish，而 finish 是指向最后一個(gè)元素的后一個(gè)位置的指針，所以使用 end（） 的時(shí)候要注意。

public：

// 獲取數(shù)據(jù)的開(kāi)始以及結(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ù)組元素的個(gè)數(shù)

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

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

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

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

push 和 pop 操作

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

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

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

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

pop 元素：從尾端刪除一個(gè)元素。

public：

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

void pop_back（） {

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

destroy（finish）;

}

erase 刪除元素

erase 函數(shù)清除指定位置的元素， 其重載函數(shù)用于清除一個(gè)范圍內(nèi)的所有元素。實(shí)際實(shí)現(xiàn)就是將刪除元素后面所有元素往前移動(dòng)，對(duì)于 vector 來(lái)說(shuō)刪除元素的操作開(kāi)銷還是很大的，所以說(shuō) vector 它不適合頻繁的刪除操作，畢竟它是一個(gè)數(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é)合圖解來(lái)看一下：

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

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

insert 插入元素

vector 的插入元素具體來(lái)說(shuō)呢，又分三種情況：

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

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

3、如果備用空間不夠；

我們一個(gè)一個(gè)來(lái)分析。

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

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

如果備用空間不足

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

由于插入元素，使得容器元素整體遷移導(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方法會(huì)拋異常），使用者要自己確保迭代器和索引值的合法性。

我們來(lái)總結(jié)一下 vector 的優(yōu)缺點(diǎn)。

優(yōu)點(diǎn)

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

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

節(jié)省空間。

缺點(diǎn)

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

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

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

list好了，下面我們來(lái)看一下 list，list 是一種雙向鏈表。

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

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

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

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

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

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

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

template 《class T》 struct __list_node {

// 前后指針

typedef void* void_pointer;

void_pointer next;

void_pointer prev;

// 屬性

T data;

};

來(lái)瞅一瞅，list 的節(jié)點(diǎn)長(zhǎng)啥樣，因?yàn)?list 是一種雙向鏈表，所以基本結(jié)構(gòu)就是下面這個(gè)樣子：

基本類型

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é)點(diǎn)指針

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， 因?yàn)閘ist是一個(gè)雙向鏈表

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 類型，并不是一個(gè)普通指針。

list 在定義 node 節(jié)點(diǎn)時(shí)， 定義的不是一個(gè)指針，這里要注意。

template 《class T， class Alloc = alloc》

class list {protected：

typedef void* void_pointer;

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

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：

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

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ù)實(shí)現(xiàn)

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

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

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

template 《class T， class Alloc = alloc》

class list {protected：

typedef void* void_pointer;

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

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

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

class list {protected：

// 配置一個(gè)節(jié)點(diǎn)并返回

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

// 釋放一個(gè)節(jié)點(diǎn)

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

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

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)并釋放）一個(gè)節(jié)點(diǎn)

void destroy_node（link_type p） {

destroy（&p-》data）;

put_node（p）;

}

// 對(duì)節(jié)點(diǎn)初始化

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; } // 返回最后一個(gè)元素的后一個(gè)的地址

const_iterator end（） const { return node; }

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

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（））;

}

// 判斷是否為空鏈表， 這是判斷只有一個(gè)空node來(lái)表示鏈表為空。

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

// 因?yàn)檫@個(gè)鏈表， 地址并不連續(xù)， 所以要自己迭代計(jì)算鏈表的長(zhǎng)度。

size_type size（） const {

size_type result = 0;

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

return result;

}

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

// 返回第一個(gè)元素的值

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

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

// 返回最后一個(gè)元素的值

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