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 操作都調用 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;

}

這里需要注意的是

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

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

刪除操作

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

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

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

template 《class T， class Alloc = alloc》

class list {

。。。

iterator erase（iterator first， iterator last）;

void clear（）;

// 參數是一個迭代器 修改該元素的前后指針指向再單獨釋放節(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 內部提供一種所謂的遷移操作（transfer）：將某連續(xù)范圍的元素遷移到某個特定位置之前，技術上實現(xiàn)其實不難，就是節(jié)點之間的指針移動，只要明白了這個函數的原理，后面的 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 函數： 實現(xiàn)將鏈表翻轉的功能：主要是 list 的迭代器基本不會改變的特點， 將每一個元素一個個插入到 begin 之前。

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

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

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

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

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

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

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

list 總結

我們來總結一下。

list 是一種雙向鏈表。每個結點都包含一個數據域、一個前驅指針 prev 和一個后驅指針 next。

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

優(yōu)點

在內部方便進行插入刪除操作。

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

缺點

不支持隨機訪問，即下標操作和.at（）。

相對于 vector 占用內存多。

deque下面到了本篇最硬核的內容了，接下來我們學習一下 雙端隊列 deque 。

deque 的功能很強大。

首先來一張圖吧。

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

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

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

deque 的中控器

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

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

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

這樣一來，雖然開銷降低，卻提高了復雜的迭代器架構。

因此 deque 數據結構的設計和迭代器前進或后退等操作都非常復雜。

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ù)空間，其內的每個元素都是一個指針。

size_type map_size;

。。。

};

其示例圖如下：deque 的結構設計中，map 和 node-buffer 的關系如下：

deque 的迭代器

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

在看源碼之前，我們可以思考一下，如果讓你來設計，你覺得 deque 的迭代器應該具備什么樣的結構和功能呢？

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

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

第三點，也就是實現(xià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ū)由設計了三個迭代器（為什么這樣設計？）

struct __deque_iterator {

。。。

typedef T value_type;

T* cur;

T* first;

T* last;

typedef T** map_pointer;

map_pointer node;

。。。

};

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

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

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

其中cur 表示當前所指的位置；

first 表示當前數組中頭的位置；

last 表示當前數組中尾的位置。

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

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

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ū)大小默認值//如果 sz = （元素大小 sizeof（value_type）） 小于 512 則返回 521/sz//如果 sz 不小于 512 則返回 1

我們來舉例說明一下：

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

如下圖所示：

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

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

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

deque 迭代器的操作

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

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

self& operator++（） {

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

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

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

cur = first;

}

return *this;

}

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

self& operator--（） {

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

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

cur = last;

}

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

return *this;

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

deque 的構造和析構函數

deque 的構造函數有多個重載函數，接受大部分不同的參數類型，基本上每一個構造函數都會調用 create_map_and_nodes，這就是構造函數的核心，后面我們來分析這個函數的實現(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）;

} // 默認構造函數

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é)點數= （每個元素/每個緩沖區(qū)可容納的元素個數+1）

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

size_type num_nodes = num_elements / buffer_size（） + 1;

//一個 map 要管理幾個節(jié)點，最少 8 個，最多是需要節(jié)點數+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;//指向所擁有的節(jié)點的最中央位置

。。。

}

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

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

那么，什么時候 map 中控器 本身需要調整大小呢？觸發(fā)條件在于 reserve_map_at_back 和 reserve_map_at_front 這兩個函數來判斷，實際操作由 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 都可以直接有對應的操作，需要注意的是 list 是鏈表，并不會涉及到界線的判斷， 而deque 是由數組來存儲的，就需要隨時對界線進行判斷。

push 實現(xiàn)

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

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 實現(xiàn)前后插入時間復雜度為O（1），保證了在前后留出了空間，所以 push 和 pop 都可以在前面的數組進行操作。

現(xiàn)在就來看 erase，因為 deque 是由數組構成，所以地址空間是連續(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;

}

// 范圍刪除， 實際也是調用上面的erase函數。

iterator erase（iterator first， iterator last）;

void clear（）;

。。。

};

最后講一下 insert 函數

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

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

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

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

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

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

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

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

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

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

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

析構函數： 分步釋放內存。

deque 總結

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

優(yōu)點：

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

2、在內部方便的進行插入和刪除操作；

3、可在兩端進行 push、pop

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

使用區(qū)別：

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

2、如果你需要大量的插入和刪除，而不關心隨機存取，則應使用 list。

3、如果你需要隨機存取，而且關心兩端數據的插入和刪除，則應使用 deque 。

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

最后要介紹的三種常用的數據結構，準確來說其實是一種適配器，底層都是已其它容器為基準。

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

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

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

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

常見的隊列的應用場景包括計算機系統(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 插入元素

插入函數是 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 的實現(xiàn)有兩種，這里都羅列了出來，另一個傳入的是 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 實現(xiàn)堆排序

其實就是每次將第一位數據彈出從而實現(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 做準備，priority_queue 是一個優(yōu)先級隊列，是帶權值的， 支持插入和刪除操作，其只能從尾部插入，頭部刪除， 并且其順序也并非是根據加入的順序排列的。

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

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

類型定義

#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; // 定義比較函數（偽函數）

。。。

};

屬性獲取

priority_queue 只有簡單的 3 個屬性獲取的函數， 其本身的操作也很簡單， 只是實現(xiàn)依賴了 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 實現(xiàn)

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

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

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

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

編輯：jq