前言
源碼之前，了無秘密。
上一篇，我們剖析了 STL 迭代器源碼與 traits 編程技法 ，這一篇我們來學習下容器。
在 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);
}
list 的頭插和尾插
因為 list 是一個循環的雙鏈表， 所以 push 和 pop 就必須實現是在頭插入，刪除還是在尾插入和刪除。
在 list 中，push 操作都調用 insert 函數， pop 操作都調用 erase 函數。
template <class T, class Alloc = alloc>
class list {
...
// 直接在頭部或尾部插入
void push_front(const T& x) { insert(begin(), x); }
void push_back(const T& x) { insert(end(), x); }
// 直接在頭部或尾部刪除
void pop_front() { erase(begin()); }
void pop_back() {
iterator tmp = end();
erase(--tmp);
}
...
};
上面的兩個插入函數內部調用的 insert 函數。
class list {
...
public:
// 最基本的insert操作, 之插入一個元素
iterator insert(iterator position, const T& x) {
// 將元素插入指定位置的前一個地址
link_type tmp = create_node(x);
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
這里需要注意的是
節點實際是以 node 空節點開始的。 插入操作是將元素插入到指定位置的前一個地址進行插入的。
刪除操作
刪除元素的操作大都是由 erase 函數來實現的，其他的所有函數都是直接或間接調用 erase。
list 是鏈表，所以鏈表怎么實現刪除元素， list 就在怎么操作：很簡單，先保留前驅和后繼節點， 再調整指針位置即可。
由于它是雙向環狀鏈表，只要把邊界條件處理好，那么在頭部或者尾部插入元素操作幾乎是一樣的，同樣的道理，在頭部或者尾部刪除元素也是一樣的。
template <class T, class Alloc = alloc>
class list {
...
iterator erase(iterator first, iterator last);
void clear();
// 參數是一個迭代器 修改該元素的前后指針指向再單獨釋放節點就行了
iterator erase(iterator position) {
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
...
};
...
}
list 內部提供一種所謂的遷移操作(transfer)：將某連續范圍的元素遷移到某個特定位置之前，技術上實現其實不難，就是節點之間的指針移動，只要明白了這個函數的原理，后面的 splice，sort，merge 函數也就一一知曉了，我們來看一下 transfer 的源碼：
template <class T, class Alloc = alloc>
class list {
...
protected:
void transfer(iterator position, iterator first, iterator last) {
if (position != last) {
(*(link_type((*last.node).prev))).next = position.node;
(*(link_type((*first.node).prev))).next = last.node;
(*(link_type((*position.node).prev))).next = first.node;
link_type tmp = link_type((*position.node).prev);
(*position.node).prev = (*last.node).prev;
(*last.node).prev = (*first.node).prev;
(*first.node).prev = tmp;
}
}
...
};
上面代碼的七行分別對應下圖的七個步驟，看明白應該不難吧。
另外 list 的其它的一些成員函數這里限于篇幅，就不貼出源碼了，簡單說一些注意點。
splice函數： 將兩個鏈表進行合并：內部就是調用的 transfer 函數。
merge 函數： 將傳入的 list 鏈表 x 與原鏈表按從小到大合并到原鏈表中(前提是兩個鏈表都是已經從小到大排序了). 這里 merge 的核心就是 transfer 函數。
reverse 函數： 實現將鏈表翻轉的功能：主要是 list 的迭代器基本不會改變的特點, 將每一個元素一個個插入到 begin 之前。
sort 函數： list 這個容器居然還自己實現一個排序，看一眼源碼就發現其實內部調用的 merge 函數，用了一個數組鏈表用來存儲 2^i 個元素, 當上一個元素存儲滿了之后繼續往下一個鏈表存儲, 最后將所有的鏈表進行 merge歸并(合并), 從而實現了鏈表的排序。
賦值操作： 需要考慮兩個鏈表的實際大小不一樣時的操作：如果原鏈表大 : 復制完后要刪除掉原鏈表多余的元素；如果原鏈表小 : 復制完后要還要將x鏈表的剩余元素以插入的方式插入到原鏈表中。
resize 操作： 重新修改 list 的大小，傳入一個 new_size，如果鏈表舊長度大于 new_size 的大小, 那就刪除后面多余的節點。
clear 操作： 清除所有節點：遍歷每一個節點，銷毀(析構并釋放)一個節點。
remove 操作： 清除指定值的元素：遍歷每一個節點，找到就移除。
unique 操作： 清除數值相同的連續元素，注意只有“連續而相同的元素”，才會被移除剩一個：遍歷每一個節點，如果在此區間段有相同的元素就移除之。
感興趣的讀者可以自行去閱讀源碼體會。
list 總結
我們來總結一下。
list 是一種雙向鏈表。每個結點都包含一個數據域、一個前驅指針 prev 和一個后驅指針 next。
由于其鏈表特性，實現同樣的操作，相對于 STL 中的通用算法， list 的成員函數通常有更高的效率，內部僅需做一些指針的操作，因此盡可能選擇 list 成員函數。
優點
在內部方便進行插入刪除操作。 可在兩端進行push和pop操作。
缺點
不支持隨機訪問，即下標操作和.at()。 相對于 vector 占用內存多。
deque
下面到了本篇最硬核的內容了，接下來我們學習一下 雙端隊列 deque 。
deque 的功能很強大。
首先來一張圖吧。
上面就是 deque 的示例圖，deque 和 vector 的最大差異一在于 deque 允許常數時間內對頭端或尾端進行元素的插入或移除操作。
二在于 deque 沒有所謂的容量概念，因為它是動態地以分段連續空間組合而成隨時可以增加一塊新的空間并拼接起來。
雖然 deque 也提供 隨機訪問的迭代器，但它的迭代器和前面兩種容器的都不一樣，其設計相當復雜度和精妙，因此，會對各種運算產生一定影響，除非必要，盡可能的選擇使用 vector 而非 deque。一一來探究下吧。
deque 的中控器
deque 在邏輯上看起來是連續空間，內部確實是由一段一段的定量連續空間構成。
一旦有必要在 deque 的前端或尾端增加新空間，deque 便會配置一段定量的連續空間，串接在整個 deque 的頭部或尾部。
設計 deque 的大師們，想必設計的時候遇到的最大挑戰就是如何在這些分段的定量連續空間上，還能維護其整體連續的假象，并提供其隨機存取的接口，從而避開了像 vector 那樣的“重新配置-復制-釋放”開銷三部曲。
這樣一來，雖然開銷降低，卻提高了復雜的迭代器架構。
因此 deque 數據結構的設計和迭代器前進或后退等操作都非常復雜。
deque 采用一塊所謂的 map （注意不是 STL 里面的 map 容器）作為中控器，其實就是一小塊連續空間，其中的每個元素都是指針，指向另外一段較大的連續線性空間，稱之為緩沖區。在后面我們看到，緩沖區才是 deque 的儲存空間主體。
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class T, class Ref, class Ptr, size_t BufSiz>
class deque {
public:
typedef T value_type;
typedef value_type* pointer;
...
protected:
typedef pointer** map_pointer;
map_pointer map;//指向 map，map 是連續空間，其內的每個元素都是一個指針。
size_type map_size;
...
};
其示例圖如下：deque 的結構設計中，map 和 node-buffer 的關系如下：
deque 的迭代器
deque 是分段連續空間，維持其“整體連續”假象的任務，就靠它的迭代器來實現，也就是 operator++ 和 operator-- 兩個運算子上面。
在看源碼之前，我們可以思考一下，如果讓你來設計，你覺得 deque 的迭代器應該具備什么樣的結構和功能呢？
首先第一點，我們能想到的是，既然是分段連續，迭代器應該能指出當前的連續空間在哪里；
其次，第二點因為緩沖區有邊界，迭代器還應該要能判斷，當前是否處于所在緩沖區的邊緣，如果是，一旦前進或后退，就必須跳轉到下一個或上一個緩沖區；
第三點，也就是實現前面兩種情況的前提，迭代器必須能隨時控制中控器。
有了這樣的思想準備之后，我們再來看源碼，就顯得容易理解一些了。
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
// 迭代器定義
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
// deque是random_access_iterator_tag類型
typedef random_access_iterator_tag iterator_category;
// 基本類型的定義, 滿足traits編程
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// node
typedef T** map_pointer;
map_pointer node;
typedef __deque_iterator self;
...
};
deque 的每一個緩沖區由設計了三個迭代器（為什么這樣設計？）
struct __deque_iterator {
...
typedef T value_type;
T* cur;
T* first;
T* last;
typedef T** map_pointer;
map_pointer node;
...
};
對啊，它為什么要這樣設計呢？回到前面我們剛才說的，因為它是分段連續的空間。
下圖描繪了 deque 的中控器、緩沖區、迭代器之間的相互關系：
看明白了嗎，每一段都指向一個緩沖區 buffer，而緩沖區是需要知道每個元素的位置的，所以需要這些迭代器去訪問。
其中 cur 表示當前所指的位置；
first 表示當前數組中頭的位置；
last 表示當前數組中尾的位置。
這樣就方便管理，需要注意的是 deque 的空間是由 map 管理的， 它是一個指向指針的指針， 所以三個參數都是指向當前的數組，但這樣的數組可能有多個，只是每個數組都管理這3個變量。
那么，緩沖區大小是誰來決定的呢？這里呢，用來決定緩沖區大小的是一個全局函數:
inline size_t __deque_buf_size(size_t n, size_t sz) {
return n != 0 ? n : (sz < 512 ? size_t(512 / sz): size_t(1));
}
//如果 n 不為0，則返回 n，表示緩沖區大小由用戶自定義
//如果 n == 0，表示 緩沖區大小默認值
//如果 sz = (元素大小 sizeof(value_type)) 小于 512 則返回 521/sz
//如果 sz 不小于 512 則返回 1
我們來舉例說明一下：
假設我們現在構造了一個 int 類型的 deque，設置緩沖區大小等于 32，這樣一來，每個緩沖區可以容納 32/sizeof(int) = 4 個元素。經過一番操作之后，deque 現在有 20 個元素了，那么成員函數 begin() 和 end() 返回的兩個迭代器應該是怎樣的呢？
如下圖所示：
20 個元素需要 20/(sizeof(int)) = 3 個緩沖區。
所以 map 運用了三個節點，迭代器 start 內的 cur 指針指向緩沖區的第一個元素，迭代器 finish 內的 cur 指針指向緩沖區的最后一個元素(的下一個位置)。
注意，最后一個緩沖區尚有備用空間，如果之后還有新元素插入，則直接插入到備用空間。
deque 迭代器的操作
主要就是兩種：前進和后退。
operator++ 操作代表是需要切換到下一個元素，這里需要先切換再判斷是否已經到達緩沖區的末尾。
self& operator++() {
++cur; //切換至下一個元素
if (cur == last) { //如果已經到達所在緩沖區的末尾
set_node(node+1); //切換下一個節點
cur = first;
}
return *this;
}
operator-- 操作代表切換到上一個元素所在的位置，需要先判斷是否到達緩沖區的頭部，再后退。
self& operator--() {
if (cur == first) { //如果已經到達所在緩沖區的頭部
set_node(node - 1); //切換前一個節點的最后一個元素
cur = last;
}
--cur; //切換前一個元素
return *this;
} //結合前面的分段連續空間，你在想一想這樣的設計是不是合理呢？deque 的構造和析構函數
deque 的構造函數有多個重載函數，接受大部分不同的參數類型，基本上每一個構造函數都會調用 create_map_and_nodes，這就是構造函數的核心，后面我們來分析這個函數的實現。
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
...
public: // Basic types
deque() : start(), finish(), map(0), map_size(0){
create_map_and_nodes(0);
} // 默認構造函數
deque(const deque& x) : start(), finish(), map(0), map_size(0) {
create_map_and_nodes(x.size());
__STL_TRY {
uninitialized_copy(x.begin(), x.end(), start);
}
__STL_UNWIND(destroy_map_and_nodes());
}
// 接受 n:初始化大小, value:初始化的值
deque(size_type n, const value_type& value) : start(), finish(), map(0), map_size(0) {
fill_initialize(n, value);
}
deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0) {
fill_initialize(n, value);
}
deque(long n, const value_type& value) : start(), finish(), map(0), map_size(0){
fill_initialize(n, value);
}
...
下面我們來看一下 deque 的中控器是如何配置的。
void deque<T,Alloc,BufSize>::create_map_and_nodes(size_type_num_elements) {
//需要節點數= (每個元素/每個緩沖區可容納的元素個數+1)
//如果剛好整除，多配一個節點
size_type num_nodes = num_elements / buffer_size() + 1;
//一個 map 要管理幾個節點，最少 8 個，最多是需要節點數+2
map_size = max(initial_map_size(), num_nodes + 2);
map = map_allocator::allocate(map_size);
// 計算出數組的頭前面留出來的位置保存并在nstart.
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;//指向所擁有的節點的最中央位置
...
}
注意了，看了源碼之后才知道：deque 的 begin 和 end 不是一開始就是指向 map 中控器里開頭和結尾的，而是指向所擁有的節點的最中央位置。
這樣帶來的好處是可以使得頭尾兩邊擴充的可能性和一樣大，換句話來說，因為 deque 是頭尾插入都是 O(1)， 所以 deque 在頭和尾都留有空間方便頭尾插入。
那么，什么時候 map 中控器 本身需要調整大小呢？觸發條件在于 reserve_map_at_back 和 reserve_map_at_front 這兩個函數來判斷，實際操作由 reallocate_map 來執行。
那 reallocate_map 又是如何操作的呢？這里先留個懸念。
// 如果 map 尾端的節點備用空間不足，符合條件就配置一個新的map(配置更大的，拷貝原來的，釋放原來的)
void reserve_map_at_back (size_type nodes_to_add = 1) {
if (nodes_to_add + 1 > map_size - (finish.node - map))
reallocate_map(nodes_to_add, false);
}
// 如果 map 前端的節點備用空間不足，符合條件就配置一個新的map(配置更大的，拷貝原來的，釋放原來的)
void reserve_map_at_front (size_type nodes_to_add = 1) {
if (nodes_to_add > start.node - map)
reallocate_map(nodes_to_add, true);
}
deque 的插入元素和刪除元素
因為 deque 的是能夠雙向操作，所以其 push 和 pop 操作都類似于 list 都可以直接有對應的操作，需要注意的是 list 是鏈表，并不會涉及到界線的判斷， 而deque 是由數組來存儲的，就需要隨時對界線進行判斷。
push 實現
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
...
public: // push_* and pop_*
// 對尾進行插入
// 判斷函數是否達到了數組尾部. 沒有達到就直接進行插入
void push_back(const value_type& t) {
if (finish.cur != finish.last - 1) {
construct(finish.cur, t);
++finish.cur;
}
else
push_back_aux(t);
}
// 對頭進行插入
// 判斷函數是否達到了數組頭部. 沒有達到就直接進行插入
void push_front(const value_type& t) {
if (start.cur != start.first) {
construct(start.cur - 1, t);
--start.cur;
}
else
push_front_aux(t);
}
...
};
pop 實現
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
...
public:
// 對尾部進行操作
// 判斷是否達到數組的頭部. 沒有到達就直接釋放
void pop_back() {
if (finish.cur != finish.first) {
--finish.cur;
destroy(finish.cur);
}
else
pop_back_aux();
}
// 對頭部進行操作
// 判斷是否達到數組的尾部. 沒有到達就直接釋放
void pop_front() {
if (start.cur != start.last - 1) {
destroy(start.cur);
++start.cur;
}
else
pop_front_aux();
}
...
};
pop 和 push 都先調用了 reserve_map_at_XX 函數，這些函數主要是為了判斷前后空間是否足夠。
刪除操作
不知道還記得，最開始構造函數調用 create_map_and_nodes 函數，考慮到 deque 實現前后插入時間復雜度為O(1)，保證了在前后留出了空間，所以 push 和 pop 都可以在前面的數組進行操作。
現在就來看 erase，因為 deque 是由數組構成，所以地址空間是連續的，刪除也就像 vector一樣，要移動所有的元素。
deque 為了保證效率盡可能的高，就判斷刪除的位置是中間偏后還是中間偏前來進行移動。
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
...
public: // erase
iterator erase(iterator pos) {
iterator next = pos;
++next;
difference_type index = pos - start;
// 刪除的地方是中間偏前, 移動前面的元素
if (index < (size() >> 1)) {
copy_backward(start, pos, next);
pop_front();
}
// 刪除的地方是中間偏后, 移動后面的元素
else {
copy(next, finish, pos);
pop_back();
}
return start + index;
}
// 范圍刪除, 實際也是調用上面的erase函數.
iterator erase(iterator first, iterator last);
void clear();
...
};
最后講一下 insert 函數
deque 源碼的基本每一個insert 重載函數都會調用了 insert_auto 判斷插入的位置離頭還是尾比較近。
如果離頭進：則先將頭往前移動，調整將要移動的距離，用 copy 進行調整。
如果離尾近：則將尾往前移動，調整將要移動的距離，用 copy 進行調整。
注意 : push_back 是先執行構造在移動 node，而 push_front 是先移動 node 在進行構造，實現的差異主要是 finish 是指向最后一個元素的后一個地址而 first指 向的就只第一個元素的地址，下面 pop 也是一樣的。
deque 源碼里還有一些其它的成員函數，限于篇幅，這里就不貼出來了，簡單的過一遍
reallocate_map：判斷中控器的容量是否夠用，如果不夠用，申請更大的空間，拷貝元素過去，修改 map 和 start，finish 的指向。
fill_initialize 函數：申請空間，對每個空間進行初始化，最后一個數組單獨處理。畢竟最后一個數組一般不是會全部填充滿。
clear 函數：刪除所有元素，分兩步執行：
首先從第二個數組開始到倒數第二個數組一次性全部刪除，這樣做是考慮到中間的數組肯定都是滿的，前后兩個數組就不一定是填充滿的，最后刪除前后兩個數組的元素。
deque 的 swap 操作：只是交換了 start, finish, map，并沒有交換所有的元素。
resize 函數： 重新將 deque 進行調整, 實現與 list一樣的。
析構函數： 分步釋放內存。
deque 總結
deque 其實是在功能上合并了 vector 和 list。
優點：
1、隨機訪問方便，即支持 [ ] 操作符和 vector.at()；
2、在內部方便的進行插入和刪除操作；
3、可在兩端進行 push、pop
缺點：因為涉及比較復雜，采用分段連續空間，所以占用內存相對多。
使用區別：
1、如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用 vector。
2、如果你需要大量的插入和刪除，而不關心隨機存取，則應使用 list。
3、如果你需要隨機存取，而且關心兩端數據的插入和刪除，則應使用 deque 。
棧和隊列
以 deque 為底層容器的適配器
最后要介紹的三種常用的數據結構，準確來說其實是一種適配器，底層都是已其它容器為基準。
棧-stack：先入后出，只允許在棧頂添加和刪除元素，稱為出棧和入棧。
隊列-queue：先入先出，在隊首取元素，在隊尾添加元素，稱為出隊和入隊。
優先隊列-priority_queue：帶權值的隊列。
常見棧的應用場景包括括號問題的求解，表達式的轉換和求值，函數調用和遞歸實現，深度優先遍歷 DFS 等；
常見的隊列的應用場景包括計算機系統中各種資源的管理，消息緩沖隊列的管理和廣度優先遍歷 BFS 等。
翻一下源碼，就知道 stack 和 queue 的底層其實就是使用 deque，用 deque 為底層容器封裝。
stack 的源碼：
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class stack {
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
queue 的源碼：
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class queue {
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
heap堆
最后我們來看一下，heap ，heap 并不是一個容器，所以他沒有實現自己的迭代器，也就沒有遍歷操作，它只是一種算法。
push_heap 插入元素
插入函數是 push_heap， heap 只接受 RandomAccessIterator 類型的迭代器。
template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
__push_heap_aux(first, last, distance_type(first), value_type(first));
}
template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*) {
// 這里傳入的是兩個迭代器的長度, 0, 還有最后一個數據
__push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1)));
}
pop_heap 刪除元素
pop 操作其實并沒有真正意義去刪除數據，而是將數據放在最后，只是沒有指向最后的元素而已，這里使用 arrary 也可以，畢竟沒有對數組的大小進行調整。
pop 的實現有兩種，這里都羅列了出來，另一個傳入的是 cmp 仿函數。
template <class RandomAccessIterator, class Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp) {
__pop_heap_aux(first, last, value_type(first), comp);
}
template <class RandomAccessIterator, class T, class Compare>
inline void __pop_heap_aux(RandomAccessIterator first,
RandomAccessIterator last, T*, Compare comp) {
__pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
distance_type(first));
}
template <class RandomAccessIterator, class T, class Compare, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
RandomAccessIterator result, T value, Compare comp,
Distance*) {
*result = *first;
__adjust_heap(first, Distance(0), Distance(last - first), value, comp);
}
template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
RandomAccessIterator result, T value, Distance*) {
*result = *first; // 因為這里是大根堆, 所以first的值就是最大值, 先將最大值保存.
__adjust_heap(first, Distance(0), Distance(last - first), value);
}
make_heap 將數組變成堆存放
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
__make_heap(first, last, value_type(first), distance_type(first));
}
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
Distance*) {
if (last - first < 2) return;
// 計算長度, 并找出中間的根值
Distance len = last - first;
Distance parent = (len - 2)/2;
while (true) {
// 一個個進行調整, 放到后面
__adjust_heap(first, parent, len, T(*(first + parent)));
if (parent == 0) return;
parent--;
}
}
sort_heap 實現堆排序
其實就是每次將第一位數據彈出從而實現排序功。
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
while (last - first > 1) pop_heap(first, last--);
}
template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp) {
while (last - first > 1) pop_heap(first, last--, comp);
}
priority_queue 優先隊列
最后我們來看一下 priority_queue。
上一節分析 heap 其實就是為 priority_queue 做準備，priority_queue 是一個優先級隊列，是帶權值的， 支持插入和刪除操作，其只能從尾部插入，頭部刪除， 并且其順序也并非是根據加入的順序排列的。
priority_queue 因為也是隊列的一種體現， 所以也就跟隊列一樣不能直接的遍歷數組，也就沒有迭代器。
priority_queue 本身也不算是一個容器，它是以 vector 為容器以 heap為數據操作的配置器。
類型定義
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = vector<T>,
class Compare = less<typename Sequence::value_type> >
#else
template <class T, class Sequence, class Compare>
#endif
class priority_queue {
public:
// 符合traits編程規范
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; // 定義vector容器的對象
Compare comp; // 定義比較函數(偽函數)
...
};
屬性獲取
priority_queue 只有簡單的 3 個屬性獲取的函數, 其本身的操作也很簡單, 只是實現依賴了 vector 和 heap 就變得比較復雜。
class priority_queue {
...
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
...
};
push 和 pop 實現
push 和 pop 具體都是采用的 heap 算法。
priority_queue 本身實現是很復雜的，但是當我們已經了解過 vector，heap 之后再來看，它其實就簡單了。
就是將 vector 作為容器， heap 作為算法來操作的配置器，這也體現了 STL 的靈活性： 通過各個容器與算法的結合就能實現另一種功能。
最后，來自實踐生產環境的一個體會：上面所列的所有容器的一個原則：為了避免拷貝開銷，不要直接把大的對象直接往里塞，而是使用指針。
好了，本期的內容就到這里了，我們下期再見。
PS：看有多少人點贊，下期不定期更新關聯式容器哦，先買個關子，下期有個硬核的內容帶大家手撕紅黑樹源碼，紅黑樹的應用可以說很廣了，像 Java 集合中的 TreeSet 和 TreeMap、STL 中的 set 和 map、Linux 虛擬內存的管理都用到了哦。
參考
1、《STL 源碼剖析》
2、https://github.com/FunctionDou/STL
往期推薦
C++學習資料免費獲取方法：關注程序喵大人，后臺回復“程序喵”即可免費獲取40萬字C++進階獨家學習資料。