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

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_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 并不是一個容器，所以他沒有實現自己的迭代器，也就沒有遍歷操作，它只是一種算法。

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_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編程規范

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 的靈活性： 通過各個容器與算法的結合就能實現另一種功能。

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

編輯：jq