一文帶你手撕 STL 容器源碼（下）

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 是一個循環(huán)的雙鏈表， 所以 push 和 pop 就必須實現(xiàn)是在頭插入，刪除還是在尾插入和刪除。

在 list 中，push 操作都調(diào)用 insert 函數(shù)， pop 操作都調(diào)用 erase 函數(shù)。

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

}

。。。

};

上面的兩個插入函數(shù)內(nèi)部調(diào)用的 insert 函數(shù)。

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;

}

這里需要注意的是

節(jié)點實際是以 node 空節(jié)點開始的。

插入操作是將元素插入到指定位置的前一個地址進行插入的。

刪除操作

刪除元素的操作大都是由 erase 函數(shù)來實現(xiàn)的，其他的所有函數(shù)都是直接或間接調(diào)用 erase。

list 是鏈表，所以鏈表怎么實現(xiàn)刪除元素， list 就在怎么操作：很簡單，先保留前驅(qū)和后繼節(jié)點， 再調(diào)整指針位置即可。

由于它是雙向環(huán)狀鏈表，只要把邊界條件處理好，那么在頭部或者尾部插入元素操作幾乎是一樣的，同樣的道理，在頭部或者尾部刪除元素也是一樣的。

template 《class T， class Alloc = alloc》

class list {

。。。

iterator erase（iterator first， iterator last）;

void clear（）;

// 參數(shù)是一個迭代器 修改該元素的前后指針指向再單獨釋放節(jié)點就行了

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 內(nèi)部提供一種所謂的遷移操作（transfer）：將某連續(xù)范圍的元素遷移到某個特定位置之前，技術(shù)上實現(xiàn)其實不難，就是節(jié)點之間的指針移動，只要明白了這個函數(shù)的原理，后面的 splice，sort，merge 函數(shù)也就一一知曉了，我們來看一下 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;

}

}

。。。

};

上面代碼的七行分別對應(yīng)下圖的七個步驟，看明白應(yīng)該不難吧。

另外 list 的其它的一些成員函數(shù)這里限于篇幅，就不貼出源碼了，簡單說一些注意點。

splice函數(shù)： 將兩個鏈表進行合并：內(nèi)部就是調(diào)用的 transfer 函數(shù)。

merge 函數(shù)： 將傳入的 list 鏈表 x 與原鏈表按從小到大合并到原鏈表中（前提是兩個鏈表都是已經(jīng)從小到大排序了）。 這里 merge 的核心就是 transfer 函數(shù)。

reverse 函數(shù)： 實現(xiàn)將鏈表翻轉(zhuǎn)的功能：主要是 list 的迭代器基本不會改變的特點， 將每一個元素一個個插入到 begin 之前。

sort 函數(shù)： list 這個容器居然還自己實現(xiàn)一個排序，看一眼源碼就發(fā)現(xiàn)其實內(nèi)部調(diào)用的 merge 函數(shù)，用了一個數(shù)組鏈表用來存儲 2^i 個元素， 當(dāng)上一個元素存儲滿了之后繼續(xù)往下一個鏈表存儲， 最后將所有的鏈表進行 merge歸并（合并）， 從而實現(xiàn)了鏈表的排序。

賦值操作： 需要考慮兩個鏈表的實際大小不一樣時的操作：如果原鏈表大 ： 復(fù)制完后要刪除掉原鏈表多余的元素；如果原鏈表小 ： 復(fù)制完后要還要將x鏈表的剩余元素以插入的方式插入到原鏈表中。

resize 操作： 重新修改 list 的大小，傳入一個 new_size，如果鏈表舊長度大于 new_size 的大小， 那就刪除后面多余的節(jié)點。

clear 操作： 清除所有節(jié)點：遍歷每一個節(jié)點，銷毀（析構(gòu)并釋放）一個節(jié)點。

remove 操作： 清除指定值的元素：遍歷每一個節(jié)點，找到就移除。

unique 操作： 清除數(shù)值相同的連續(xù)元素，注意只有“連續(xù)而相同的元素”，才會被移除剩一個：遍歷每一個節(jié)點，如果在此區(qū)間段有相同的元素就移除之。

感興趣的讀者可以自行去閱讀源碼體會。

list 總結(jié)

我們來總結(jié)一下。

list 是一種雙向鏈表。每個結(jié)點都包含一個數(shù)據(jù)域、一個前驅(qū)指針 prev 和一個后驅(qū)指針 next。

由于其鏈表特性，實現(xiàn)同樣的操作，相對于 STL 中的通用算法， list 的成員函數(shù)通常有更高的效率，內(nèi)部僅需做一些指針的操作，因此盡可能選擇 list 成員函數(shù)。

優(yōu)點

在內(nèi)部方便進行插入刪除操作。

可在兩端進行push和pop操作。

缺點

不支持隨機訪問，即下標(biāo)操作和.at（）。

相對于 vector 占用內(nèi)存多。

deque下面到了本篇最硬核的內(nèi)容了，接下來我們學(xué)習(xí)一下 雙端隊列 deque 。

deque 的功能很強大。

首先來一張圖吧。

上面就是 deque 的示例圖，deque 和 vector 的最大差異一在于 deque 允許常數(shù)時間內(nèi)對頭端或尾端進行元素的插入或移除操作。

二在于 deque 沒有所謂的容量概念，因為它是動態(tài)地以分段連續(xù)空間組合而成隨時可以增加一塊新的空間并拼接起來。

雖然 deque 也提供 隨機訪問的迭代器，但它的迭代器和前面兩種容器的都不一樣，其設(shè)計相當(dāng)復(fù)雜度和精妙，因此，會對各種運算產(chǎn)生一定影響，除非必要，盡可能的選擇使用 vector 而非 deque。一一來探究下吧。

deque 的中控器

deque 在邏輯上看起來是連續(xù)空間，內(nèi)部確實是由一段一段的定量連續(xù)空間構(gòu)成。

一旦有必要在 deque 的前端或尾端增加新空間，deque 便會配置一段定量的連續(xù)空間，串接在整個 deque 的頭部或尾部。

設(shè)計 deque 的大師們，想必設(shè)計的時候遇到的最大挑戰(zhàn)就是如何在這些分段的定量連續(xù)空間上，還能維護其整體連續(xù)的假象，并提供其隨機存取的接口，從而避開了像 vector 那樣的“重新配置-復(fù)制-釋放”開銷三部曲。

這樣一來，雖然開銷降低，卻提高了復(fù)雜的迭代器架構(gòu)。

因此 deque 數(shù)據(jù)結(jié)構(gòu)的設(shè)計和迭代器前進或后退等操作都非常復(fù)雜。

deque 采用一塊所謂的 map （注意不是 STL 里面的 map 容器）作為中控器，其實就是一小塊連續(xù)空間，其中的每個元素都是指針，指向另外一段較大的連續(xù)線性空間，稱之為緩沖區(qū)。在后面我們看到，緩沖區(qū)才是 deque 的儲存空間主體。

#ifndef __STL_NON_TYPE_TMPL_PARAM_BUGtemplate 《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 是連續(xù)空間，其內(nèi)的每個元素都是一個指針。

size_type map_size;

。。。

};

其示例圖如下：deque 的結(jié)構(gòu)設(shè)計中，map 和 node-buffer 的關(guān)系如下：

deque 的迭代器

deque 是分段連續(xù)空間，維持其“整體連續(xù)”假象的任務(wù)，就靠它的迭代器來實現(xiàn)，也就是 operator++ 和 operator-- 兩個運算子上面。

在看源碼之前，我們可以思考一下，如果讓你來設(shè)計，你覺得 deque 的迭代器應(yīng)該具備什么樣的結(jié)構(gòu)和功能呢？

首先第一點，我們能想到的是，既然是分段連續(xù)，迭代器應(yīng)該能指出當(dāng)前的連續(xù)空間在哪里；

其次，第二點因為緩沖區(qū)有邊界，迭代器還應(yīng)該要能判斷，當(dāng)前是否處于所在緩沖區(qū)的邊緣，如果是，一旦前進或后退，就必須跳轉(zhuǎn)到下一個或上一個緩沖區(qū)；

第三點，也就是實現(xiàn)前面兩種情況的前提，迭代器必須能隨時控制中控器。

有了這樣的思想準(zhǔn)備之后，我們再來看源碼，就顯得容易理解一些了。

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 的每一個緩沖區(qū)由設(shè)計了三個迭代器（為什么這樣設(shè)計？）

struct __deque_iterator {

。。。

typedef T value_type;

T* cur;

T* first;

T* last;

typedef T** map_pointer;

map_pointer node;

。。。

};

對啊，它為什么要這樣設(shè)計呢？回到前面我們剛才說的，因為它是分段連續(xù)的空間。

下圖描繪了deque 的中控器、緩沖區(qū)、迭代器之間的相互關(guān)系：

看明白了嗎，每一段都指向一個緩沖區(qū) buffer，而緩沖區(qū)是需要知道每個元素的位置的，所以需要這些迭代器去訪問。

其中cur 表示當(dāng)前所指的位置；

first 表示當(dāng)前數(shù)組中頭的位置；

last 表示當(dāng)前數(shù)組中尾的位置。

這樣就方便管理，需要注意的是 deque 的空間是由 map 管理的， 它是一個指向指針的指針， 所以三個參數(shù)都是指向當(dāng)前的數(shù)組，但這樣的數(shù)組可能有多個，只是每個數(shù)組都管理這3個變量。

那么，緩沖區(qū)大小是誰來決定的呢？這里呢，用來決定緩沖區(qū)大小的是一個全局函數(shù)：

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，表示緩沖區(qū)大小由用戶自定義//如果 n == 0，表示 緩沖區(qū)大小默認(rèn)值//如果 sz = （元素大小 sizeof（value_type）） 小于 512 則返回 521/sz//如果 sz 不小于 512 則返回 1

我們來舉例說明一下：

假設(shè)我們現(xiàn)在構(gòu)造了一個 int 類型的 deque，設(shè)置緩沖區(qū)大小等于 32，這樣一來，每個緩沖區(qū)可以容納 32/sizeof（int） = 4 個元素。經(jīng)過一番操作之后，deque 現(xiàn)在有 20 個元素了，那么成員函數(shù) begin（） 和 end（） 返回的兩個迭代器應(yīng)該是怎樣的呢？

如下圖所示：

20 個元素需要 20/（sizeof（int）） = 3 個緩沖區(qū)。

所以 map 運用了三個節(jié)點，迭代器 start 內(nèi)的 cur 指針指向緩沖區(qū)的第一個元素，迭代器 finish 內(nèi)的 cur 指針指向緩沖區(qū)的最后一個元素（的下一個位置）。

注意，最后一個緩沖區(qū)尚有備用空間，如果之后還有新元素插入，則直接插入到備用空間。

deque 迭代器的操作

主要就是兩種：前進和后退。

operator++ 操作代表是需要切換到下一個元素，這里需要先切換再判斷是否已經(jīng)到達緩沖區(qū)的末尾。

self& operator++（） {

++cur; //切換至下一個元素

if （cur == last） { //如果已經(jīng)到達所在緩沖區(qū)的末尾

set_node（node+1）; //切換下一個節(jié)點

cur = first;

}

return *this;

}

operator-- 操作代表切換到上一個元素所在的位置，需要先判斷是否到達緩沖區(qū)的頭部，再后退。

self& operator--（） {

if （cur == first） { //如果已經(jīng)到達所在緩沖區(qū)的頭部

set_node（node - 1）; //切換前一個節(jié)點的最后一個元素

cur = last;

}

--cur; //切換前一個元素

return *this;

} //結(jié)合前面的分段連續(xù)空間，你在想一想這樣的設(shè)計是不是合理呢？

deque 的構(gòu)造和析構(gòu)函數(shù)

deque 的構(gòu)造函數(shù)有多個重載函數(shù)，接受大部分不同的參數(shù)類型，基本上每一個構(gòu)造函數(shù)都會調(diào)用 create_map_and_nodes，這就是構(gòu)造函數(shù)的核心，后面我們來分析這個函數(shù)的實現(xiàn)。

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

} // 默認(rèn)構(gòu)造函數(shù)

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） {

//需要節(jié)點數(shù)= （每個元素/每個緩沖區(qū)可容納的元素個數(shù)+1）

//如果剛好整除，多配一個節(jié)點

size_type num_nodes = num_elements / buffer_size（） + 1;

//一個 map 要管理幾個節(jié)點，最少 8 個，最多是需要節(jié)點數(shù)+2

map_size = max（initial_map_size（）， num_nodes + 2）;

map = map_allocator：：allocate（map_size）;

// 計算出數(shù)組的頭前面留出來的位置保存并在nstart.

map_pointer nstart = map + （map_size - num_nodes） / 2;

map_pointer nfinish = nstart + num_nodes - 1;

map_pointer cur;//指向所擁有的節(jié)點的最中央位置

。。。

}

注意了，看了源碼之后才知道：deque 的 begin 和 end 不是一開始就是指向 map 中控器里開頭和結(jié)尾的，而是指向所擁有的節(jié)點的最中央位置。

這樣帶來的好處是可以使得頭尾兩邊擴充的可能性和一樣大，換句話來說，因為 deque 是頭尾插入都是 O（1）， 所以 deque 在頭和尾都留有空間方便頭尾插入。

那么，什么時候 map 中控器 本身需要調(diào)整大小呢？觸發(fā)條件在于 reserve_map_at_back 和 reserve_map_at_front 這兩個函數(shù)來判斷，實際操作由 reallocate_map 來執(zhí)行。

那 reallocate_map 又是如何操作的呢？這里先留個懸念。

// 如果 map 尾端的節(jié)點備用空間不足，符合條件就配置一個新的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 前端的節(jié)點備用空間不足，符合條件就配置一個新的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 都可以直接有對應(yīng)的操作，需要注意的是 list 是鏈表，并不會涉及到界線的判斷， 而deque 是由數(shù)組來存儲的，就需要隨時對界線進行判斷。

push 實現(xiàn)

template 《class T， class Alloc = alloc， size_t BufSiz = 0》

class deque {

。。。

public： // push_* and pop_*

// 對尾進行插入

// 判斷函數(shù)是否達到了數(shù)組尾部。 沒有達到就直接進行插入

void push_back（const value_type& t） {

if （finish.cur ！= finish.last - 1） {

construct（finish.cur， t）;

++finish.cur;

}

else

push_back_aux（t）;

}

// 對頭進行插入

// 判斷函數(shù)是否達到了數(shù)組頭部。 沒有達到就直接進行插入

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

template 《class T， class Alloc = alloc， size_t BufSiz = 0》

class deque {

。。。

public：

// 對尾部進行操作

// 判斷是否達到數(shù)組的頭部。 沒有到達就直接釋放

void pop_back（） {

if （finish.cur ！= finish.first） {

--finish.cur;

destroy（finish.cur）;

}

else

pop_back_aux（）;

}

// 對頭部進行操作

// 判斷是否達到數(shù)組的尾部。 沒有到達就直接釋放

void pop_front（） {

if （start.cur ！= start.last - 1） {

destroy（start.cur）;

++start.cur;

}

else

pop_front_aux（）;

}

。。。

};

pop 和 push 都先調(diào)用了 reserve_map_at_XX 函數(shù)，這些函數(shù)主要是為了判斷前后空間是否足夠。

刪除操作

不知道還記得，最開始構(gòu)造函數(shù)調(diào)用 create_map_and_nodes 函數(shù)，考慮到 deque 實現(xiàn)前后插入時間復(fù)雜度為O（1），保證了在前后留出了空間，所以 push 和 pop 都可以在前面的數(shù)組進行操作。

現(xiàn)在就來看 erase，因為 deque 是由數(shù)組構(gòu)成，所以地址空間是連續(xù)的，刪除也就像 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;

}

// 范圍刪除， 實際也是調(diào)用上面的erase函數(shù)。

iterator erase（iterator first， iterator last）;

void clear（）;

。。。

};

最后講一下 insert 函數(shù)

deque 源碼的基本每一個insert 重載函數(shù)都會調(diào)用了 insert_auto判斷插入的位置離頭還是尾比較近。

如果離頭進：則先將頭往前移動，調(diào)整將要移動的距離，用 copy 進行調(diào)整。

如果離尾近：則將尾往前移動，調(diào)整將要移動的距離，用 copy 進行調(diào)整。

注意 ： push_back 是先執(zhí)行構(gòu)造在移動 node，而 push_front 是先移動 node 在進行構(gòu)造，實現(xiàn)的差異主要是 finish 是指向最后一個元素的后一個地址而 first指 向的就只第一個元素的地址，下面 pop 也是一樣的。

deque 源碼里還有一些其它的成員函數(shù)，限于篇幅，這里就不貼出來了，簡單的過一遍

reallocate_map：判斷中控器的容量是否夠用，如果不夠用，申請更大的空間，拷貝元素過去，修改 map 和 start，finish 的指向。

fill_initialize 函數(shù)：申請空間，對每個空間進行初始化，最后一個數(shù)組單獨處理。畢竟最后一個數(shù)組一般不是會全部填充滿。

clear 函數(shù)：刪除所有元素，分兩步執(zhí)行：

首先從第二個數(shù)組開始到倒數(shù)第二個數(shù)組一次性全部刪除，這樣做是考慮到中間的數(shù)組肯定都是滿的，前后兩個數(shù)組就不一定是填充滿的，最后刪除前后兩個數(shù)組的元素。

deque 的 swap 操作：只是交換了 start， finish， map，并沒有交換所有的元素。

resize 函數(shù)： 重新將 deque 進行調(diào)整， 實現(xiàn)與 list一樣的。

析構(gòu)函數(shù)： 分步釋放內(nèi)存。

deque 總結(jié)

deque 其實是在功能上合并了 vector 和 list。

優(yōu)點：

1、隨機訪問方便，即支持 ［ ］ 操作符和 vector.at（）；

2、在內(nèi)部方便的進行插入和刪除操作；

3、可在兩端進行 push、pop

缺點：因為涉及比較復(fù)雜，采用分段連續(xù)空間，所以占用內(nèi)存相對多。

使用區(qū)別：

1、如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用 vector。

2、如果你需要大量的插入和刪除，而不關(guān)心隨機存取，則應(yīng)使用 list。

3、如果你需要隨機存取，而且關(guān)心兩端數(shù)據(jù)的插入和刪除，則應(yīng)使用 deque 。

棧和隊列以 deque 為底層容器的適配器

最后要介紹的三種常用的數(shù)據(jù)結(jié)構(gòu)，準(zhǔn)確來說其實是一種適配器，底層都是已其它容器為基準(zhǔn)。

棧-stack：先入后出，只允許在棧頂添加和刪除元素，稱為出棧和入棧。

隊列-queue：先入先出，在隊首取元素，在隊尾添加元素，稱為出隊和入隊。

優(yōu)先隊列-priority_queue：帶權(quán)值的隊列。

常見棧的應(yīng)用場景包括括號問題的求解，表達式的轉(zhuǎn)換和求值，函數(shù)調(diào)用和遞歸實現(xiàn)，深度優(yōu)先遍歷 DFS 等；

常見的隊列的應(yīng)用場景包括計算機系統(tǒng)中各種資源的管理，消息緩沖隊列的管理和廣度優(yōu)先遍歷 BFS 等。

翻一下源碼，就知道 stack 和 queue 的底層其實就是使用 deque，用 deque 為底層容器封裝。

stack 的源碼：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate 《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_TEMPLATEStemplate 《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 并不是一個容器，所以他沒有實現(xiàn)自己的迭代器，也就沒有遍歷操作，它只是一種算法。

push_heap 插入元素

插入函數(shù)是 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， 還有最后一個數(shù)據(jù)

__push_heap（first， Distance（（last - first） - 1）， Distance（0）， T（*（last - 1）））;

}

pop_heap 刪除元素

pop 操作其實并沒有真正意義去刪除數(shù)據(jù)，而是將數(shù)據(jù)放在最后，只是沒有指向最后的元素而已，這里使用 arrary 也可以，畢竟沒有對數(shù)組的大小進行調(diào)整。

pop 的實現(xiàn)有兩種，這里都羅列了出來，另一個傳入的是 cmp 仿函數(shù)。

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 將數(shù)組變成堆存放

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） {

// 一個個進行調(diào)整， 放到后面

__adjust_heap（first， parent， len， T（*（first + parent）））;

if （parent == 0） return;

parent--;

}

}

sort_heap 實現(xiàn)堆排序

其實就是每次將第一位數(shù)據(jù)彈出從而實現(xiàn)排序功。

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 優(yōu)先隊列最后我們來看一下 priority_queue。

上一節(jié)分析 heap 其實就是為 priority_queue 做準(zhǔn)備，priority_queue 是一個優(yōu)先級隊列，是帶權(quán)值的， 支持插入和刪除操作，其只能從尾部插入，頭部刪除， 并且其順序也并非是根據(jù)加入的順序排列的。

priority_queue 因為也是隊列的一種體現(xiàn)， 所以也就跟隊列一樣不能直接的遍歷數(shù)組，也就沒有迭代器。

priority_queue 本身也不算是一個容器，它是以 vector 為容器以 heap為數(shù)據(jù)操作的配置器。

類型定義

#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate 《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編程規(guī)范

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; // 定義比較函數(shù)（偽函數(shù)）

。。。

};

屬性獲取

priority_queue 只有簡單的 3 個屬性獲取的函數(shù)， 其本身的操作也很簡單， 只是實現(xiàn)依賴了 vector 和 heap 就變得比較復(fù)雜。

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

push 和 pop 具體都是采用的 heap 算法。

priority_queue 本身實現(xiàn)是很復(fù)雜的，但是當(dāng)我們已經(jīng)了解過 vector，heap 之后再來看，它其實就簡單了。

就是將 vector 作為容器， heap 作為算法來操作的配置器，這也體現(xiàn)了 STL 的靈活性： 通過各個容器與算法的結(jié)合就能實現(xiàn)另一種功能。

最后，來自實踐生產(chǎn)環(huán)境的一個體會：上面所列的所有容器的一個原則：為了避免拷貝開銷，不要直接把大的對象直接往里塞，而是使用指針。

編輯：jq