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

在 STL 編程中，容器是我們經常會用到的一種數據結構，容器分為序列式容器和關聯式容器。

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

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

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

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

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

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

vector 基本數據結構

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

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

構造函數，滿足容器的多種初始化；

屬性的獲取，比如 begin（），end（）等；

vector 也不例外，其實看了源碼之后就發現，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; // 設置其空間配置器

iterator start; // 當前使用空間的頭

iterator finish; // 當前使用空間的尾

iterator end_of_storage; // 當前可用空間的尾

。。.

};

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

構造函數

vector 有多個構造函數， 為了滿足多種初始化。

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

因為 vector 是一種 class template， 所以呢，我們并不需要手動的釋放內存， 生命周期結束后就自動調用析構從而釋放調用空間，當然我們也可以直接調用析構函數釋放內存。

void deallocate（） {

if （start）

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

}

// 調用析構函數并釋放內存

~vector（） {

destroy（start， finish）;

deallocate（）;

}

屬性獲取

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

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

public：

// 獲取數據的開始以及結束位置的指針。 記住這里返回的是迭代器， 也就是 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（））; } // 數組元素的個數

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

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

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

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

push 和 pop 操作

vector 的 push 和 pop 操作都只是對尾進行操作， 這里說的尾部是指數據的尾部。當調用 push_back 插入新元素的時候，首先會檢查是否有備用空間，如果有就直接在備用空間上構造元素，并調整迭代器 finish。

當如果沒有備用空間，就擴充空間（重新配置-移動數據-釋放原空間），這里實際是調用了另外一個函數：insert_aux 函數。

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

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

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

public：

//將尾端元素拿掉 并調整大小

void pop_back（） {

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

destroy（finish）;

}

erase 刪除元素

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

//清楚［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 全局函數

}

--finish;

destroy（finish）;

return position;

}

void clear（） {

erase（begin（）， end（））;

}

我們結合圖解來看一下：

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

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

insert 插入元素

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

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

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

3、如果備用空間不夠；

我們一個一個來分析。

插入點之后的現有元素個數 》 新增元素個數

插入點之后的現有元素個數 《= 新增元素個數

如果備用空間不足

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

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

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

前面提到的一些全局函數，這里在總結一下：

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

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

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

vector 總結

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

我們來總結一下 vector 的優缺點。

優點

在內存中是分配一塊連續的內存空間進行存儲，可以像數組一樣操作，并且支持動態擴容。

因此元素的隨機訪問方便，支持下標訪問和 vector.at（） 操作。

節省空間。

缺點

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

只能在末端進行 pop 和 push。

當動態長度超過默認分配大小后，要整體重新分配、拷貝和釋放空間。

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

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

注意：list 源碼里其實分了兩個部分，一個部分是 list 結構，另一部分是 list 節點的結構。

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

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

list 的節點結構如下圖所示：

list 數據結構-節點

__list_node 用來實現節點，數據結構中就儲存前后指針和屬性。

template 《class T》 struct __list_node {

// 前后指針

typedef void* void_pointer;

void_pointer next;

void_pointer prev;

// 屬性

T data;

};

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

基本類型

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;

。。.

};

構造函數

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

。。.

// 定義節點指針

typedef __list_node《T》* link_type;

link_type node;

// 構造函數

__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 結構

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

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

template 《class T， class Alloc = alloc》

class list {protected：

typedef void* void_pointer;

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

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：

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

link_type node;

public：

// 定義迭代器

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

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

。。.

};

list 構造和析構函數實現

構造函數前期準備：

每個構造函數都會創造一個空的 node 節點，為了保證我們在執行任何操作都不會修改迭代器。

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

template 《class T， class Alloc = alloc》

class list {protected：

typedef void* void_pointer;

typedef __list_node《T》 list_node; // 節點

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

其中，list_node_allocator（n） 表示配置 n 個節點空間。以下四個函數，分別用來配置，釋放，構造，銷毀一個節點。

class list {protected：

// 配置一個節點并返回

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

// 釋放一個節點

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

// 產生（配置并構造）一個節點帶有元素初始值

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;

}

//銷毀（析構并釋放）一個節點

void destroy_node（link_type p） {

destroy（&p-》data）;

put_node（p）;

}

// 對節點初始化

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; }

// 這里是為旋轉做準備， 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; }

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

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