所謂順序容器(sequential containers)混萝，其中的元素都可序(ordered)躺同，但未必有序(sorted)遮婶。C++本身提供了一個(gè)順序容器
array，STL另外提供vector旗扑，list慈省，deque臀防，stack袱衷，queue致燥，priority-queue等順序容器怖侦。其中stack和queue是將deque改頭換面而成搬葬，技術(shù)上被歸類為一種適配器(adapter)急凰。
一抡锈、vector
vector的數(shù)據(jù)安排以及操作方式一罩，與array十分相似：
vector<typeName> vt(n_elem); //vector可以用變量初始化聂渊，會自動擴(kuò)容
array<typeName, n_elem> arr; //array的n_elem必須由常量指定汉嗽，不會自動擴(kuò)容
兩者的唯一差別在于空間運(yùn)用的靈活性：array是靜態(tài)空間饼暑，一旦配置就不能改變弓叛；vector是動態(tài)空間，隨著元素的加入闭专，他的內(nèi)部機(jī)制會自動擴(kuò)充空間以容納新的元素影钉。vector的實(shí)現(xiàn)技術(shù)平委，關(guān)鍵在于對其大小的控制以及重新配置時(shí)的數(shù)據(jù)移動效率！
1蜡塌、迭代器
vector維護(hù)的是一個(gè)連續(xù)線性空間馏艾。不論其元素類型為何铁孵，普通指針都可作為vector的迭代器而滿足所有必要條件蜕劝，因?yàn)?code>vector迭代器所需要的操作行為(例如operator操作)鳖擒，普通指針天生就具備蒋荚。vector支持隨機(jī)存取惊奇，而普通指針正有這種能力颂郎。vector提供的是Random Access Iterators。
template<class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator; //vector的迭代器是普通指針
......
}
//如果客戶端寫這樣的代碼
vector<int>::iterator ivite; //ivite的類型其實(shí)就是int*
vector<Shape>::iterator svite; //svite的類型其實(shí)就是Shape*
2替劈、數(shù)據(jù)結(jié)構(gòu)
vecotr所采用的數(shù)據(jù)結(jié)構(gòu)非常簡單：線性連續(xù)空間。它以兩個(gè)迭代器start和finish分別指向配置得來的連續(xù)空間中目前已被使用過的范圍眨业，并以迭代器end_of_storage指向整塊連續(xù)空間(含備用空間)的尾端：
template<class T, class Alloc = alloc>
class vector {
......
protected:
iterator start; //已使用空間的頭
iterator finish; //已使用空間的尾
iterator end_of_storage; //可用空間的尾
......
}
為降低空間配置時(shí)的速度成本，vector實(shí)際配置的大小可能比客戶端需求量更大一些墅茉，以備將來可能的擴(kuò)充就斤。換言之洋机，一個(gè)vector的容量永遠(yuǎn)大于或等于其大小喜鼓。一旦容量等于大小庄岖，便是滿載，下次再有新增元素背桐，整個(gè)vecotr就得另尋居所。
3弊仪、構(gòu)造與內(nèi)存管理：constructor、push_back
vector缺省使用alloc作為空間配置器曲横，并據(jù)此定義了一個(gè)data_allocator，為的是更方便以元素大小為配置單位：
template<class T, class Alloc = alloc>
class vector {
......
protected:
typedef simple_alloc<value_type, Alloc> data_allocator;
......
于是，data_allocator::allocate(n)表示配置n個(gè)元素空間孽椰。我們考察vector提供的眾多constructors中的一個(gè)：
//構(gòu)造函數(shù)栏渺，允許指定大小n和初值value
vector(size_type n, const T& value) {
fill_initialize(n, value);
}
//填充并予以初始化
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
//配置而后填充
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allcoate(n); //配置n個(gè)元素空間
uninitialized_fill_n(result, n, x);
return result;
}
uninitialized_fill_n()會根據(jù)第一個(gè)參數(shù)的類型特性(type traits)來決定填充數(shù)據(jù)的算法：如果是POD類型(Plain Old Data，也就是標(biāo)量類型(scalar types)或傳統(tǒng)的C struct類型霎终。POD類型必然擁有trivial ctor/dtor/copy/assignment函數(shù))則使用算法fill_n()，如果不是POD類型則循環(huán)調(diào)用construct()來填充所有配置而來的空間保礼。
當(dāng)我們以push_back()將元素插入于vector尾端時(shí)目派，該函數(shù)首先檢查是否還有備用空間企蹭，如果有就直接在備用空間上構(gòu)造函數(shù)徒河，并調(diào)整迭代器finish，使vector變大代兵。如果沒有備用空間就擴(kuò)充空間。
void push_back(cosnt T& x) {
if (finish != end_of_storage) { //還有備用空間
construct(finish, x);
++finish; //調(diào)整水位高度
}
else //已無備用空間
insert_aux(and(), x);
} //vecotr member function
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
if (finish != end_of_storage) { //還有備用空間
//在備用空間起始處構(gòu)造一個(gè)元素鹿响，并以vector最后一個(gè)元素值為其初值
construct(finish, *(finish - 1));
++finish; //調(diào)整水位
T x_copy = x;
copy_backward(position, finish - 2, finish - 1);
*position = x_copy;
}
else { //已無備用空間
const size_type old_size = size();
const size_type len = old_size != 0 ? 2 * old_size : 1;
//以上配置原則：如果原大小為0，則配置1（個(gè)元素大兄腹隆）；
//如果原大小不為0叉跛，則配置原大小的兩倍，
//前半段用來放置原數(shù)據(jù)酥艳，后半段準(zhǔn)備用來放置新數(shù)據(jù)
iterator new_start = data_allocator::allocate(len); //實(shí)際配置
iterator new_finish = new_start;
try{
//將原vector的內(nèi)容拷貝到新vector
new_finish = uninitialized_copy(start, position, new_start);
//為新元素設(shè)定初值x
construct(new_finish, x);
//調(diào)整水位
++new_finish;
//將原vector的備用空間中的內(nèi)容也拷貝過來（說實(shí)話感覺有點(diǎn)多此一舉）
new_finish = uninitialized_copy(position, finish, new_finish);
}
catch(...) {
//"commit or rollback"原則
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
//析構(gòu)并釋放原vector
destroy(begin(), end());
deallocate();
//調(diào)整迭代器霞玄，指向新vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
所謂動態(tài)增加大小坷剧，并不是在原空間之后接續(xù)新空間撕瞧，而是以原大小的兩倍另外配置一塊較大空間，然后將原內(nèi)容拷貝過來硼婿，然后才開始在原內(nèi)容之后構(gòu)造新元素刊殉，并釋放原空間愉老。因此，特別注意：對vector的任何操作，一旦引起空間重新配置弛说，指向原vector的所有迭代器就都失效了Ｐ攀痢Ｓ嫒隆！
二搀罢、list
相較于vector的連續(xù)線性空間榔至，list就顯得復(fù)雜許多铅鲤，它的好處是每次插入或刪除一個(gè)元素，就配置或釋放一個(gè)元素空間伊履。因此，list對于空間的運(yùn)用有絕對的精準(zhǔn)哄辣，一點(diǎn)也不浪費(fèi)。而且對于任何位置的元素插入或元素刪除，list的時(shí)間復(fù)雜度永遠(yuǎn)為常數(shù)超全。
1、list的節(jié)點(diǎn)(node)
list本身和list的節(jié)點(diǎn)是不同的數(shù)據(jù)結(jié)構(gòu)，需要分開設(shè)計(jì)财异，以下是STL list的節(jié)點(diǎn)(node)結(jié)構(gòu)：
template<class T>
struct __list_node {
typedef void * void_pointer;
void_pointer prev; //類型為void*，實(shí)際上設(shè)為__list_node<T>*也可以
void_pointer next;
T data;
}
顯然這是一個(gè)雙向鏈表。
2拆吆、迭代器
list迭代器必須有能力指向list的節(jié)點(diǎn)，并有能力做正確的遞增娄昆、遞減、取值扒俯、成員存取等操作，list提供的是Bidirectional Iterators。list有一個(gè)重要性質(zhì)：插入動作(insert)和拼接動作(splice)都不會造成原有的list迭代器失效荔茬。這在vector是不成立的，因?yàn)?code>vector的插入動作可能造成記憶體重新配置，導(dǎo)致原有的迭代器全部失效。甚至list的元素刪除動作(erase)惦积，也只有「指向被刪除元素」的那個(gè)迭代器失效蛛勉，其它迭代器不受任何影響毡熏。
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node; //迭代器內(nèi)部當(dāng)然要有一個(gè)原生指標(biāo)，指向list的節(jié)點(diǎn)
//constructor
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
//以下對迭代器取值（dereference），取的是節(jié)點(diǎn)的資料值搭儒。
reference operator*() const { return (*node).data; }
//以下是迭代器的成員存溶畋狻（member access）運(yùn)算子的標(biāo)準(zhǔn)做法毁习。
pointer operator->() const { return &(operator*()); }
//對迭代器累加 1，就是前進(jìn)一個(gè)節(jié)點(diǎn)
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
self operator++(int) { //后綴++
self tmp = *this;
++*this;
return tmp;
}
//對迭代器遞減 1隆檀，就是后退一個(gè)節(jié)點(diǎn)
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) { //后綴--
self tmp = *this;
--*this;
return tmp;
}
};
3为鳄、數(shù)據(jù)結(jié)構(gòu)
SGI list不僅是一個(gè)雙向鏈表歧斟，而且還是一個(gè)環(huán)狀雙向鏈表静袖。所以它只需要一個(gè)指針，便可以完整表現(xiàn)整個(gè)鏈表：
template <class T, class Alloc = alloc> // 缺省使用alloc為配置器
class list {
protected:
typedef __list_node<T> list_node;
public:
typedef list_node* link_type;
protected:
link_type node; // 只要一個(gè)指針俊扭，便可表示整個(gè)環(huán)狀雙向鏈表
.......
};
如果讓指針node指向刻意置于尾端的一個(gè)空白節(jié)點(diǎn)队橙，node便能符合STL對于“前閉后開”區(qū)間的要求，成為last迭代器捐康。
iterator begin() { return (link_type)((*node).next); }
iterator end() { return node; }
bool empty() const { return node->next == node; }
size_type size() const {
size_type result = 0;
distance(begin(), end(), result); // 根據(jù)迭代器的類型仇矾，用不同的方法計(jì)算兩個(gè)迭代器之間的距離，list的迭代器需要逐一累計(jì)計(jì)算距離
return result;
}
// 取頭節(jié)點(diǎn)的內(nèi)容（元素值）解总。
reference front() { return *begin(); }
// 取尾節(jié)點(diǎn)的內(nèi)容（元素值）贮匕。
reference back() { return *(--end()); }
4、構(gòu)造與內(nèi)存管理：constructor倾鲫、push_back粗合、insert
list預(yù)設(shè)使用alloc做為空間配置器，并據(jù)此另外定義了一個(gè)list_node_allocator乌昔，為的是更方便地以節(jié)點(diǎn)大小為配置單位：
template <class T, class Alloc = alloc> // 預(yù)設(shè)使用alloc為配置器
class list {
protected:
typedef __list_node<T> list_node;
// 專屬之空間配置器隙疚，每次配置一個(gè)節(jié)點(diǎn)大小：
typedef simple_alloc<list_node, Alloc> list_node_allocator;
......
};
于是磕道，list_node_allocator(n)表示配置n個(gè)節(jié)點(diǎn)空間溺蕉。以下四個(gè)函數(shù)，分別用來配置疯特、釋放漓雅、構(gòu)造录别、摧毀一個(gè)節(jié)點(diǎn)：
protected:
// 配置一個(gè)節(jié)點(diǎn)并傳回
link_type get_node() { return list_node_allocator::allocate(); }
// 釋放一個(gè)節(jié)點(diǎn)
void put_node(link_type p) { list_node_allocator::deallocate(p); }
// 產(chǎn)生（配置并建構(gòu)）一個(gè)節(jié)點(diǎn)邻吞，帶有元素值
link_type create_node(const T& x) {
link_type p = get_node();
construct(&p->data, x); // 全局函數(shù)崔列，構(gòu)造/析構(gòu)基本工具旺遮。
return p;
}
// 摧毀（析構(gòu)并釋放）一個(gè)節(jié)點(diǎn)
void destroy_node(link_type p) {
destroy(&p->data); // 全域函式瘦癌，構(gòu)造/析構(gòu)基本工具。
put_node(p);
}
list提供有許多constructors西傀，其中一個(gè)是default constructor娘锁，允許我們不指定任何參數(shù)做出一個(gè)空的list出來：
public:
list() { empty_initialize(); } // 產(chǎn)生一個(gè)空鏈表饺鹃。
protected:
void empty_initialize()
node = get_node(); // 配置一個(gè)節(jié)點(diǎn)空間悔详，令node指向它缝驳。
node->next = node; // 令node頭尾都指向自己用狱，不設(shè)元素值夏伊。
node->prev = node;
}
當(dāng)我們以push_back()將新元素安插于list尾端，此函數(shù)內(nèi)部調(diào)用insert()函數(shù)：
void push_back(const T& x) { insert(end(), x); }
insert()是一個(gè)重載函數(shù)，有多種形式刀森，其中最簡單的一種如下研底，符合以上所需。首先配置并建構(gòu)一個(gè)節(jié)點(diǎn)乾胶，然后在尾端做適當(dāng)?shù)闹羔槻僮魇读瑢⑿鹿?jié)點(diǎn)插入進(jìn)去：
// 函數(shù)目的：在迭代器position所指位置安插一個(gè)節(jié)點(diǎn)缩宜，內(nèi)容為x锻煌。
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x); // 產(chǎn)生一個(gè)節(jié)點(diǎn)（設(shè)內(nèi)容為 x）
// 調(diào)整雙向指針，使tmp安插進(jìn)去乃秀。
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
如果希望在list內(nèi)的某處插入新節(jié)點(diǎn)，首先必須確定插入位置刀脏，例如希望在數(shù)據(jù)值為3的節(jié)點(diǎn)處插入一個(gè)數(shù)據(jù)值為99的節(jié)點(diǎn)，可以這么做：
ilite = find(il.begin(), il.end(), 3);
if (ilite!=0)
il.insert(ilite, 99);
注意：
- 1暂雹、使用
list::merge()可以獲得兩個(gè)有序鏈表的二路歸并排序結(jié)果，但是前提是這個(gè)兩個(gè)list都必須有序涧尿！ - 2、
list不能使用STL算法sort()桥言，必須使用自己的list::sort()member function虫蝶，因?yàn)镾TL算法sort()只接受Random Access Iterator。list::sort()函數(shù)使用快排算法扰柠，實(shí)現(xiàn)細(xì)節(jié)如下：
template <class T, class Alloc>
void list<T, Alloc>::sort() {
// 以下判斷，如果是空白串行劝枣，或僅有一個(gè)元素，就不做任何動作稳诚。
// 使用 size() == 0 || size() == 1 來判斷，雖然也可以氨距，但是比較慢。
if (node->next == node || link_type(node->next)->next == node)
return;
// 一些新的 lists舆驶，做為中介數(shù)據(jù)存放區(qū)
list<T, Alloc> carry;
list<T, Alloc> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}
for (int i = 1; i < fill; ++i)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}
三、deque
deque是一種雙向開口的連續(xù)線性空間撬陵，和vector的最大差異蟋定，一在于 deque允許于常數(shù)時(shí)間內(nèi)對頭尾兩端進(jìn)行元素的入插或刪除動作，二在于deque沒有容量（capacity）概念抄淑，因?yàn)樗莿討B(tài)地以分段連續(xù)空間組合而成，隨時(shí)可以增加一段新的空間并鏈接起來郑原。換句話說，像vector那樣「因舊空間不足而重新配置一塊更大空間栖秕，然后復(fù)制元素，再釋放舊空間」這樣的事情在deque是不會發(fā)生的暑塑。
1、控制器
deque由一段一段的定量連續(xù)空間構(gòu)成。一旦有必要在deque的前端或尾端增加新空間逢捺，便配置一段定量連續(xù)空間倘潜，串接在整個(gè)deque的頭端或尾端。deque的最大任務(wù)养泡，便是在這些分段的定量連續(xù)空間上，維護(hù)其整體連續(xù)的假象，并提供隨機(jī)存取的界面程梦。避開了「重新配置、復(fù)制挺份、釋放」的輪回，代價(jià)則是復(fù)雜的迭代器架構(gòu)。使用分段連續(xù)線性空間躲因，就必須有中央控制，而為了維護(hù)整體連續(xù)的假象镰矿，數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及迭代器前進(jìn)后退等動作都頗為繁瑣棍矛。deque的實(shí)作碼份量遠(yuǎn)比vector或list都多得多。
deque采用一塊所謂的map（不是STL的map容器）做為主控茁帽。這里所謂map是一小塊連續(xù)空間，其中每個(gè)元素（此處稱為一個(gè)節(jié)點(diǎn)，node）都是指針琅束，指向另一段（較大的）連續(xù)線性空間，稱為緩沖區(qū)艾船。緩沖區(qū)才是deque的儲存空間主體。SGI STL允許我們指定緩沖區(qū)大小，默認(rèn)值0表示將使用512bytes緩沖區(qū)霉撵。
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: // Basic types
typedef T value_type;
typedef value_type* pointer;
......
protected: // Internal typedefs
// 元素的指針的指針（pointer of pointer of T）
typedef pointer* map_pointer;
protected: // Data members
map_pointer map; // 指向map，map是塊連續(xù)空間，其內(nèi)的每個(gè)元素都是一個(gè)指針（稱為節(jié)點(diǎn)）锦溪，指向一塊緩沖區(qū)防楷。
size_type map_size; // map內(nèi)可容納多少指針。
......
};
整理一下亿昏，我們便可發(fā)現(xiàn)，map其實(shí)是一個(gè)T**，也就是說它是一個(gè)指針，所指之物又是一個(gè)指針，指向類型為T的一塊空間。
2闸衫、迭代器
deque是分段連續(xù)空間。維護(hù)其「整體連續(xù)」假象的任務(wù)，則落在迭代器的operator++和operator--兩個(gè)運(yùn)算符身上。deque迭代器必須能夠指出分段連續(xù)空間（亦即緩沖區(qū)）在哪里踏烙，其次它必須能夠判斷自己是否已經(jīng)處于其所在緩沖區(qū)的邊緣辟癌，如果是，一旦前進(jìn)或后退時(shí)就必須跳躍至下一個(gè)或上一個(gè)緩沖區(qū)。為了能夠正確跳躍农渊，deque必須隨時(shí)掌握控制中心（map）
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator { // 未繼承 std::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)); }
// 未繼承 std::iterator囱挑，所以必須自行撰寫五個(gè)必要的迭代器相應(yīng)類型
typedef random_access_iterator_tag iterator_category;...... // 剩下的類型定義省略
// 保持與容器的聯(lián)結(jié)
T* cur; // 此迭代器所指之緩沖區(qū)中的現(xiàn)行（current）元素
T* first; // 此迭代器所指之緩沖區(qū)的頭
T* last; // 此迭代器所指之緩沖區(qū)的尾（含備用空間）
map_pointer node; // 指向管控中心
......
}
其中用來決定緩沖區(qū)大小的函數(shù)buffer_size()游添，調(diào)用__deque_buf_size()，后者是個(gè)全局函數(shù)，定義如下：
// 如果n不為0亡驰，傳回n，表示buffer size由使用者自定。
// 如果n為0蚓曼，表示buffer size使用默認(rèn)值，那么
// 如果sz（元素大小其弊，sizeof(value_type)）小于512，返回512/sz，
// 如果sz不小于512赂苗，返回1猜谚。
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));
}
下圖很清楚的展現(xiàn)了deque控制器，迭代器龄毡，緩沖區(qū)之間的關(guān)系。
假設(shè)現(xiàn)在有一個(gè)deque<int>锡垄，并令其緩沖區(qū)大小為32沦零，于是每個(gè)緩沖區(qū)可容納32/sizeof(int)=8個(gè)元素货岭。經(jīng)過某些操作之后路操，deque擁有20個(gè)元素，那么其begin()和end()所傳回的兩個(gè)迭代器如下圖所示千贯。這兩個(gè)迭代器事實(shí)上一直保持在deque內(nèi)屯仗，名為start和finish。
20個(gè)元素需要20/8 = 3個(gè)緩沖區(qū)搔谴，所以map之內(nèi)運(yùn)用了三個(gè)節(jié)點(diǎn)魁袜。迭代器start內(nèi)的cur指標(biāo)當(dāng)然指向緩沖區(qū)的第一個(gè)元素，迭代器finish內(nèi)的cur指標(biāo)當(dāng)然指向緩沖區(qū)的最后元素（的下一位置）。注意峰弹，最后一個(gè)緩沖區(qū)尚有備用空間店量。稍后如果有新元素要安插于尾端，可直接拿此備用空間來使用鞠呈。
下面是deque迭代器的幾個(gè)關(guān)鍵行為融师。由于迭代器內(nèi)對各種指針運(yùn)算都做了重載操作，所以各種指針運(yùn)算如加蚁吝、減旱爆、前進(jìn)、后退等都不能直觀視之窘茁。其中最關(guān)鍵的就是：一旦行進(jìn)時(shí)遇到緩沖區(qū)邊緣怀伦，要特別當(dāng)心，視前進(jìn)或后退而定庙曙，可能需要調(diào)用set_node()跳一個(gè)緩沖區(qū)：
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
// 以下各個(gè)重載運(yùn)算符是 __deque_iterator<> 成功運(yùn)作的關(guān)鍵空镜。
reference operator*() const { return *cur; }
pointer operator->() const { return &(operator*()); }
difference_type operator-(const self& x) const {
return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
}
// 參考 More Effective C++, item6: Distinguish between prefix and postfix forms of increment and decrement operators.
self& operator++() {
++cur; // 切換至下一個(gè)元素。
if (cur == last) { // 如果已達(dá)所在緩沖區(qū)的尾端捌朴，
set_node(node + 1); // 就切換至下一節(jié)點(diǎn)（亦即緩沖區(qū)）
cur = first; // 的第一個(gè)元素吴攒。
}
return *this;
}
self operator++(int) { // 用int告訴編譯器++為后置式
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) { // 如果已達(dá)所在緩沖區(qū)的頭端，
set_node(node - 1); // 就切換至前一節(jié)點(diǎn)（亦即緩沖區(qū)）
cur = last; // 的最后一個(gè)元素砂蔽。
}
--cur; // 切換至前一個(gè)元素洼怔。
return *this;
}
self operator--(int) { // 用int告訴編譯器++為后置式
self tmp = *this;
--*this;
return tmp;
}
// 以下實(shí)現(xiàn)隨機(jī)存取。迭代器可以直接跳躍n個(gè)距離左驾。
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
// 標(biāo)的位置在同一緩沖區(qū)內(nèi)
cur += n;
else {
// 標(biāo)的位置不在同一緩沖區(qū)內(nèi)
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
// 切換至正確的節(jié)點(diǎn)（亦即緩沖區(qū)）
set_node(node + node_offset);
// 切換至正確的元素
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
// 參考 More Effective C++, item22: Consider using op= instead of stand-alone op.
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n; // 調(diào)用 operator+=
}
self& operator-=(difference_type n) { return *this += -n; }
// 以上利用 operator+= 來完成 operator-=
// 參考 More Effective C++, item22: Consider using op= instead of stand-alone op.
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n; // 調(diào)用 operator-=
}
// 以下實(shí)現(xiàn)隨機(jī)存取镣隶。迭代器可以直接跳躍 n 個(gè)距離。
reference operator[](difference_type n) const { return *(*this + n); }
// 以上調(diào)用 operator*, operator+
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
3诡右、數(shù)據(jù)結(jié)構(gòu)
deque除了維護(hù)一個(gè)先前說過的指向map的指針外安岂，也維護(hù)start,finish兩個(gè)迭代器，分別指向第一緩沖區(qū)的第一個(gè)元素和最后緩沖區(qū)的最后一個(gè)元素（的下一位置）帆吻。此外它當(dāng)然也必須記住目前的map大小域那。因?yàn)橐坏﹎ap所提供的節(jié)點(diǎn)不足，就必須重新配置更大的一塊map猜煮。
// 見 __deque_buf_size()次员。BufSize 默認(rèn)值為 0 的唯一理由是為了閃避某些
// 編譯器在處理常數(shù)算式（constant expressions）時(shí)的bug。
// 預(yù)設(shè)使用 alloc 為配置器王带。
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: // Basic types
typedef T value_type;
typedef value_type* pointer;
typedef size_t size_type;
public: // Iterators
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
protected: // Internal typedefs
// 元素的指針的指針（pointer of pointer of T）
typedef pointer* map_pointer;
protected: // Data members
iterator start; // 表現(xiàn)第一個(gè)節(jié)點(diǎn)淑蔚。
iterator finish; // 表現(xiàn)最后一個(gè)節(jié)點(diǎn)。
map_pointer map; // 指向 map愕撰，map 是塊連續(xù)空間刹衫，其每個(gè)元素都是個(gè)指針醋寝，指向一個(gè)節(jié)點(diǎn)（緩沖區(qū)）。
size_type map_size; // map 內(nèi)有多少指標(biāo)绪妹。
......
};
有了上述結(jié)構(gòu)甥桂，以下數(shù)個(gè)功能便可輕易完成：
public: // Basic accessors
iterator begin() { return start; }
iterator end() { return finish; }
reference operator[](size_type n) {
return start[difference_type(n)]; // 調(diào)用 deque_iterator<>::operator[]
}
reference front() { return *start; } // 調(diào)用__deque_iterator<>::operator*
reference back() {
iterator tmp = finish;
--tmp; // 調(diào)用 __deque_iterator<>::operator--
return *tmp; // 調(diào)用 __deque_iterator<>::operator*
// 以上三行何不改為：return *(finish-1);
// 因?yàn)?__deque_iterator<> 沒有為 (finish-1) 定義運(yùn)算?!
}
// 下行最后有兩個(gè) ‘;’，雖奇怪但合乎語法邮旷。
size_type size() const { return finish - start;; }
// 以上調(diào)用 iterator::operator-
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }
4黄选、構(gòu)造與內(nèi)存管理：constuctor、push_back婶肩、push_front
deque的緩沖區(qū)擴(kuò)充動作相當(dāng)瑣碎繁雜办陷，以下將以分解動作的方式一步一步圖解說明。假設(shè)程序一開始創(chuàng)建了一個(gè)deque：
deque<int,alloc,32> ideq(20,9);
其緩沖區(qū)大小為32bytes律歼，并令其保留20個(gè)元素空間民镜，每個(gè)元素初值為9。為了指定deque的第三個(gè)template參數(shù)（緩沖區(qū)大邢栈佟）制圈，我們必須將前兩個(gè)參數(shù)都指明出來（這是C++語法規(guī)則），因此必須明確指定alloc為空間配置器∨峡觯現(xiàn)在鲸鹦，deque的情況如圖（該圖并未顯示每個(gè)元素的初值為 9）。
deque自行定義了兩個(gè)專屬的空間配置器:
protected: // Internal typedefs
// 專屬之空間配置器跷跪，每次配置一個(gè)元素大小
typedef simple_alloc<value_type, Alloc> data_allocator;
// 專屬之空間配置器馋嗜，每次配置一個(gè)指針大小
typedef simple_alloc<pointer, Alloc> map_allocator;
并提供有一個(gè) constructor 如下：
deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0) {
fill_initialize(n, value);
}
其內(nèi)所調(diào)用的fill_initialize()負(fù)責(zé)產(chǎn)生并安排好deque的結(jié)構(gòu)，并將元素的初值設(shè)定妥當(dāng)：
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_type n, const value_type& value) {
create_map_and_nodes(n); // 把 deque 的結(jié)構(gòu)都產(chǎn)生并安排好
map_pointer cur;
__STL_TRY {
// 為每個(gè)節(jié)點(diǎn)的緩沖區(qū)設(shè)定初值
for (cur = start.node; cur < finish.node; ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
// 最后一個(gè)節(jié)點(diǎn)的設(shè)定稍有不同（因?yàn)槲捕丝赡苡袀溆每臻g吵瞻，不必設(shè)初值）
uninitialized_fill(finish.first, finish.cur, value);
}
catch(...) {
...
}
}
其中create_map_and_nodes()負(fù)責(zé)產(chǎn)生并安排好deque的結(jié)構(gòu)：
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {
// 需要節(jié)點(diǎn)數(shù)=(元素個(gè)數(shù)/每個(gè)緩沖區(qū)可容納的元素個(gè)數(shù))+1
// 如果剛好整除葛菇，會多配一個(gè)節(jié)點(diǎn)。
size_type num_nodes = num_elements / buffer_size() + 1;
// 一個(gè) map 要管理幾個(gè)節(jié)點(diǎn)橡羞。最少 8 個(gè)眯停，最多是 “所需節(jié)點(diǎn)數(shù)加 2”
// （前后各預(yù)留一個(gè)，擴(kuò)充時(shí)可用）卿泽。
map_size = max(initial_map_size(), num_nodes + 2);
map = map_allocator::allocate(map_size);
// 以上配置出一個(gè) “具有 map_size 個(gè)節(jié)點(diǎn)” 的 map莺债。
// 以下令 nstart 和 nfinish 指向 map 所擁有之全部節(jié)點(diǎn)的最中央?yún)^(qū)段。
// 保持在最中央又厉，可使頭尾兩端的擴(kuò)充能量一樣大。每個(gè)節(jié)點(diǎn)可對應(yīng)一個(gè)緩沖區(qū)椎瘟。
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;
__STL_TRY {
// 為 map 內(nèi)的每個(gè)現(xiàn)用節(jié)點(diǎn)配置緩沖區(qū)覆致。所有緩沖區(qū)加起來就是 deque 的
// 可用空間（最后一個(gè)緩沖區(qū)可能留有一些余裕）。
for (cur = nstart; cur <= nfinish; ++cur)
*cur = allocate_node();
}
catch(...) {
// "commit or rollback" 語意：若非全部成功肺蔚，就一個(gè)不留煌妈。
...
}
// 為 deque 內(nèi)的兩個(gè)迭代器 start 和 end 設(shè)定正確內(nèi)容。
start.set_node(nstart);
finish.set_node(nfinish);
// first, cur 都是 public
start.cur = start.first;
finish.cur = finish.first + num_elements % buffer_size();
// 前面說過，如果剛好整除璧诵，會多配一個(gè)節(jié)點(diǎn)汰蜘。
// 此時(shí)即令 cur 指向這多配的一個(gè)節(jié)點(diǎn)（所對映之緩沖區(qū)）的起頭處。
}
接下來以下標(biāo)運(yùn)算符為每個(gè)元素重新設(shè)值之宿，然后在尾端安插三個(gè)新元素：
for(int i=0; i<ideq.size(); ++i)
ideq[i] = i;
for(int i=0;i<3;i++)
ideq.push_back(i);
由于此時(shí)最后一個(gè)緩沖區(qū)仍有4個(gè)備用元素空間族操，所以不會引起緩沖區(qū)的再配置。此時(shí)的deque狀態(tài)如下：
以下是push_back()函數(shù)內(nèi)容：
public:
// push_* and pop_*
void push_back(const value_type& t) {
if (finish.cur != finish.last - 1) {
// 最后緩沖區(qū)尚有一個(gè)以上的備用空間
construct(finish.cur, t); // 直接在備用空間上建構(gòu)元素
++finish.cur; // 調(diào)整最后緩沖區(qū)的使用狀態(tài)
}
else // 最后緩沖區(qū)已無（或只剩一個(gè)）元素備用空間比被。
push_back_aux(t);
}
現(xiàn)在色难，如果再新增加一個(gè)新元素于尾端：
ideq.push_back(3);
由于尾端只剩一個(gè)元素備用空間，于是push_back()調(diào)用push_back_aux()等缀，先配置一整塊新的緩沖區(qū)枷莉，再設(shè)妥新元素內(nèi)容，然后更改迭代器finish的狀態(tài)：
// 只有當(dāng) finish.cur == finish.last – 1 時(shí)才會被調(diào)用尺迂。
// 也就是說只有當(dāng)最后一個(gè)緩沖區(qū)只剩一個(gè)備用元素空間時(shí)才會被調(diào)用笤妙。
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_back(); // 若符合某種條件則必須重?fù)Q一個(gè) map
*(finish.node + 1) = allocate_node(); // 配置一個(gè)新節(jié)點(diǎn)（緩沖區(qū)）
__STL_TRY {
construct(finish.cur, t_copy); // 針對標(biāo)的元素設(shè)值
finish.set_node(finish.node + 1); // 改變 finish，令其指向新節(jié)點(diǎn)
finish.cur = finish.first; // 設(shè)定 finish 的狀態(tài)
}
__STL_UNWIND(deallocate_node(*(finish.node + 1)));
}
現(xiàn)在噪裕，deque 的狀態(tài)如下：
接下來程序在deque的前端安插一個(gè)新元素：
ideq.push_front(99);
push_front()函數(shù)動作如下：
public: // push_* and pop_*
void push_front(const value_type& t) {
if (start.cur != start.first) { // 第一緩沖區(qū)尚有備用空間
construct(start.cur - 1, t); // 直接在備用空間上建構(gòu)元素
--start.cur; // 調(diào)整第一緩沖區(qū)的使用狀態(tài)
}
else // 第一緩沖區(qū)已無備用空間
push_front_aux(t);
}
由于目前狀態(tài)下蹲盘，第一緩沖區(qū)并無備用空間，所以調(diào)用push_front_aux()：
// 只有當(dāng) start.cur == start.first 時(shí)才會被呼叫州疾。
// 也就是說只有當(dāng)?shù)谝粋€(gè)緩沖區(qū)沒有任何備用元素時(shí)才會被呼叫辜限。
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_front(); // 若符合某種條件則必須重?fù)Q一個(gè) map
*(start.node - 1) = allocate_node(); // 配置一個(gè)新節(jié)點(diǎn)（緩沖區(qū)）
__STL_TRY {
start.set_node(start.node - 1); // 改變 start，令其指向新節(jié)點(diǎn)
start.cur = start.last - 1; // 設(shè)定 start 的狀態(tài)
construct(start.cur, t_copy); // 針對標(biāo)的元素設(shè)值
}
catch(...) {
// "commit or rollback" 語意：若非全部成功严蓖，就一個(gè)不留薄嫡。
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
}
此函數(shù)一開始即調(diào)用`reserve_map_at_front()`， 后者用來判斷是否需要擴(kuò)充map颗胡，如有需要就付諸行動毫深。稍后我會展示`reserve_map_at_front()`函數(shù)的內(nèi)容。目前的狀態(tài)不需要重新整治map毒姨，所以后繼流程便配置了一塊新緩沖區(qū)并直接將節(jié)點(diǎn)安置于現(xiàn)有的map上哑蔫，然后設(shè)定新元素，然后改變迭代器start的狀態(tài)弧呐，如下：
接下來程序又在`deque`的最前端安插兩個(gè)新元素：
```C++
ideq.push_front(98);
ideq.push_front(97);
這一次闸迷，由于第一緩沖區(qū)有備用空間，push_front() 可以直接在備用空間上建構(gòu)新元素俘枫，如下：
上面的連環(huán)圖解腥沽，已經(jīng)充份展示了deque容器的空間運(yùn)用策略。讓我們回頭看看一個(gè)懸而未解的問題：什么時(shí)候map需要重新整治鸠蚪？這個(gè)問題的判斷由reserve_map_at_back()和reserve_map_at_front()進(jìn)行今阳，實(shí)際動作則由reallocate_map()執(zhí)行：
void reserve_map_at_back (size_type nodes_to_add = 1) {
if (nodes_to_add + 1 > map_size - (finish.node - map))
// 如果 map 尾端的節(jié)點(diǎn)備用空間不足
// 符合以上條件則必須重?fù)Q一個(gè) map（配置更大的师溅，拷貝原來的，釋放原來的）
reallocate_map(nodes_to_add, false);
}
void reserve_map_at_front (size_type nodes_to_add = 1) {
if (nodes_to_add > start.node - map)
// 如果 map 前端的節(jié)點(diǎn)備用空間不足
// 符合以上條件則必須重?fù)Q一個(gè) map（配置更大的盾舌，拷貝原來的墓臭，釋放原來的）
reallocate_map(nodes_to_add, true);
}
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add, bool add_at_front) {
size_type old_num_nodes = finish.node - start.node + 1;
size_type new_num_nodes = old_num_nodes + nodes_to_add;
map_pointer new_nstart;
if (map_size > 2 * new_num_nodes) {
new_nstart = map + (map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
if (new_nstart < start.node)
copy(start.node, finish.node + 1, new_nstart);
else
copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
}
else {
size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
// 配置一塊空間，準(zhǔn)備給新 map 使用妖谴。
map_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
// 把原 map 內(nèi)容拷貝過來窿锉。
copy(start.node, finish.node + 1, new_nstart);
// 釋放原 map
map_allocator::deallocate(map, map_size);
// 設(shè)定新 map 的起始地址與大小
map = new_map;
map_size = new_map_size;
}
// 重新設(shè)定迭代器 start 和 finish
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
}
四、stack
stack是一種先進(jìn)后出（First In Last Out窖维，F(xiàn)ILO）的數(shù)據(jù)結(jié)構(gòu)榆综，它只有一個(gè)出口。stack允許新增元素铸史、移除元素鼻疮、取得最頂端元素。但除了最頂端外琳轿，沒有任何其它方法可以存取stack的其它元素判沟。換言之stack不允許有走訪行為。將元素推入 stack 的動作稱為push崭篡，將元素推出stack的動作稱為pop挪哄。
1、定義式完整列表
以某種既有容器做為底部結(jié)構(gòu)琉闪，將其接口改變迹炼，使符合「先進(jìn)后出」的特性，形成一個(gè)stack颠毙，是很容易做到的斯入。deque是雙向開口的數(shù)據(jù)結(jié)構(gòu)，若以deque為底部結(jié)構(gòu)并封閉其頭端開口蛀蜜，便輕而易舉地形成了一個(gè)stack刻两。因此，SGI STL 便以deque做為預(yù)設(shè)情況下的stack底部結(jié)構(gòu)滴某，stack的實(shí)作因而非常簡單磅摹，源碼十分簡短，本處完整列出霎奢。
由于stack系以底部容器完成其所有工作户誓，而具有這種「修改某物接口，形成另一種風(fēng)貌」之性質(zhì)者幕侠，稱為 adapter（配接器）帝美，因此 STL stack 往往不被歸類為container（容器），而被歸類為 container adapter橙依。
//deque<T> >中間有個(gè)空格是為了兼容較老的版本
template <class T, class Sequence = deque<T> >
class stack {
// 以下的 __STL_NULL_TMPL_ARGS 會開展為 <>
friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const 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; // 底層容器
public:
// 以下完全利用 Sequence c 的操作证舟，完成 stack 的操作。
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
// deque 是兩頭可進(jìn)出窗骑，stack 是末端進(jìn)女责，末端出（所以后進(jìn)者先出）。
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c < y.c;
}
2创译、迭代器
stack所有元素的進(jìn)出都必須符合「先進(jìn)后出」的條件抵知，只有stack頂端的元素，才有機(jī)會被外界取用软族。stack不提供走訪功能刷喜，也不提供迭代器！
3立砸、以list做為stack的底層容器
除了deque之外掖疮，list也是雙向開口的數(shù)據(jù)結(jié)構(gòu)。上述stack源碼中使用的底層容器的函式有empty, size, back, push_back, pop_back颗祝，凡此種種list都具備浊闪。因此若以list為底部結(jié)構(gòu)并封閉其頭端開口，一樣能夠輕易形成一個(gè)stack螺戳。下面是作法示范搁宾。
#include <stack>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
stack<int,list<int> > istack;
}
五、queue
queue是一種先進(jìn)先出（First In First Out倔幼，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)盖腿，它有兩個(gè)出口。queue允許新增元素损同、移除元素翩腐、從最底端加入元素、取得最頂端元素揖庄。但除了最底端可以加入栗菜、最頂端可以取出，沒有任何其它方法可以存取queue的其它元素蹄梢。換言之queue不允許有走訪行為疙筹。將元素推入queue的動作稱為push，將元素推出queue的動作稱為pop禁炒。
1而咆、定義式完整列表
以某種既有容器為底部結(jié)構(gòu)，將其接口改變幕袱，使符合「先進(jìn)先出」的特性暴备，形成一個(gè)queue，是很容易做到的们豌。deque是雙向開口的數(shù)據(jù)結(jié)構(gòu)涯捻，若以deque為底部結(jié)構(gòu)并封閉其底端的出口和前端的入口浅妆，便輕而易舉地形成了一個(gè)queue。因此障癌，SGI STL 便以deque做為預(yù)設(shè)情況下的queue底部結(jié)構(gòu)凌外，queue的實(shí)作因而非常簡單，源碼十分簡短涛浙，本處完整列出康辑。
template <class T, class Sequence = deque<T> >
class queue {
// 以下的 __STL_NULL_TMPL_ARGS 會開展為 <>，見 1.9.1 節(jié)
friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
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; // 底層容器
public:
// 以下完全利用 Sequence c 的操作轿亮，完成 queue 的操作疮薇。
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
// deque 是兩頭可進(jìn)出，queue 是末端進(jìn)我注，前端出（所以先進(jìn)者先出）按咒。
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c < y.c;
}
2、迭代器
queue所有元素的進(jìn)出都必須符合「先進(jìn)先出」的條件但骨，只有queue頂端的元素胖齐，才有機(jī)會被外界取用。queue不提供走訪功能嗽冒，也不提供迭代器呀伙。
3、以list做為queue的底層容器
除了deque之外添坊，list也是雙向開口的數(shù)據(jù)結(jié)構(gòu)剿另。上述queue源碼中使用的底層容器的函式有empty, size, back, push_back, pop_back，凡此種種list都具備贬蛙。因此若以list為底部結(jié)構(gòu)并封閉其頭端開口雨女，一樣能夠輕易形成一個(gè)queue。下面是作法示范阳准。
#include <queue>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
queue<int,list<int> > iqueue;
}
六氛堕、堆
heap并不歸屬于STL容器組件，它是個(gè)幕后英雄野蝇，扮演priority queue的推手讼稚。顧名思義，priority queue允許使用者以任何次序?qū)⑷魏卧赝迫肴萜鲀?nèi)绕沈，但取出時(shí)一定是從優(yōu)先權(quán)最高（也就是數(shù)值最高）之元素開始取身弊。binary max heap 正是具有這樣的特性拟烫，適合做為priority queue的底層機(jī)制援制。
所謂 binary heap 就是一種complete binary tree（完全二叉樹）超燃，也就是說，整棵 binary tree 除了最底層的葉節(jié)點(diǎn)(s) 之外，是填滿的藕帜，而最底層的葉節(jié)點(diǎn)(s) 由左至右又不得有空隙烫罩。complete binary tree整棵樹內(nèi)沒有任何節(jié)點(diǎn)漏洞，因此我們可以利用 array 來儲存所有節(jié)點(diǎn)洽故。將 array 的 0 號元素保留（或設(shè)為無限大值或無限小值）嗡髓，那么當(dāng) complete binary tree 中的某個(gè)節(jié)點(diǎn)位于 array 的 i 處，其左子節(jié)點(diǎn)必位于 array 的 2i 處收津，其右子節(jié)點(diǎn)必位于 array 的 2i+1 處，其父節(jié)點(diǎn)必位于「i/2」處浊伙。這種以array 表述 tree 的方式撞秋，我們稱為隱式表述法（implicit representation）。
這么一來嚣鄙，我們需要的工具就很簡單了：一個(gè) array 和一組heap算法（用來安插元素吻贿、刪除元素、取極值哑子、將某一整組數(shù)據(jù)排列成一個(gè)heap）舅列。array 的缺點(diǎn)是無法動態(tài)改變大小，而heap卻需要這項(xiàng)功能卧蜓，因此以 vector代替array是更好的選擇帐要。
1、heap算法
push_heap算法：
為了滿足complete binary tree的條件弥奸，新加入的元素一定要放在最下一層做為葉節(jié)點(diǎn)榨惠，并填補(bǔ)在由左至右的第一個(gè)空格，也就是把新元素安插在底層vector的end()處盛霎。下圖所示是push_heap算法的實(shí)際操作過程：
為滿足max-heap的條件（每個(gè)節(jié)點(diǎn)的鍵值都大于或等于其子節(jié)點(diǎn)鍵值）赠橙，我們執(zhí)行一個(gè)所謂的percolate up（上溯）程序：將新節(jié)點(diǎn)拿來與其父節(jié)點(diǎn)比較，如果其鍵值（key）比父節(jié)點(diǎn)大愤炸，就父子對換位置期揪。如此一直上溯，直到不需對換或直到根節(jié)點(diǎn)為止规个。
該函數(shù)接受兩個(gè)迭代器凤薛，用來表現(xiàn)一個(gè)heap底部容器（vector）的頭尾，新元素并且已經(jīng)安插到底部容器的最尾端诞仓。如果不符合這兩個(gè)條件枉侧，push_heap的執(zhí)行結(jié)果將不可預(yù)測。
pop_heap算法：
為滿足max-heap的條件（每個(gè)節(jié)點(diǎn)的鍵值都大于或等于其子節(jié)點(diǎn)鍵值）狂芋，我們執(zhí)行一個(gè)所謂的percolate down（下放）程序：將根節(jié)點(diǎn)（最大值被取走后榨馁，形成一個(gè)「洞」）填入上述那個(gè)失去生存空間的葉節(jié)點(diǎn)值，再將它拿來和其兩個(gè)子節(jié)點(diǎn)比較鍵值（key）帜矾，并與較大子節(jié)點(diǎn)對調(diào)位置翼虫。如此一直下放屑柔，直到這個(gè)「洞」的鍵值大于左右兩個(gè)子節(jié)點(diǎn)，或直到下放至葉節(jié)點(diǎn)為止珍剑。下圖所示是pop_heap算法的實(shí)際操作過程：
此函式接受兩個(gè)迭代器掸宛，用來表現(xiàn)一個(gè)heap 底部容器（vector）的頭尾。如果不符合這個(gè)條件招拙，pop_heap 的執(zhí)行結(jié)果將不可預(yù)測唧瘾。
sort_heap算法(堆排序)：
既然每次pop_heap可獲得heap之中鍵值最大的元素，如果持續(xù)對整個(gè)heap做pop_heap動作别凤，每次將操作范圍從后向前縮減一個(gè)元素（因?yàn)?code>pop_heap會把鍵值最大的元素放在底部容器的最尾端）饰序，當(dāng)整個(gè)程序執(zhí)行完畢，我們便有了一個(gè)遞增序列规哪。下圖是sort_heap的實(shí)際操演情況求豫。
該函數(shù)接受兩個(gè)迭代器，用來表現(xiàn)一個(gè)heap底部容器（vector）的頭尾诉稍。如果不符合這個(gè)條件蝠嘉，sort_heap的執(zhí)行結(jié)果將不可預(yù)測。注意杯巨，排序過后蚤告，原來的heap就不再是個(gè)合法的heap了。下面是sort_heap算法的實(shí)現(xiàn)細(xì)節(jié)：
// 以下這個(gè) sort_heap() 不允許指定「大小比較標(biāo)準(zhǔn)」
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
// 以下服爷，每執(zhí)行一次 pop_heap()罩缴，極值（在 STL heap 中為極大值）即被放在尾端。
// 扣除尾端再執(zhí)行一次 pop_heap()层扶，次極值又被放在新尾端箫章。一直下去，最后即得
// 排序結(jié)果镜会。
while (last - first > 1)
pop_heap(first, last--); // 每執(zhí)行 pop_heap() 一次檬寂，操作范圍即退縮一格。
}
make_heap算法:
這個(gè)算法用來將一段現(xiàn)有的數(shù)據(jù)轉(zhuǎn)化為一個(gè) heap戳表。其主要依據(jù)complete binary tree的隱式表述（implicit representation）桶至。
// 將 [first,last) 排列為一個(gè) heap。
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
__make_heap(first, last, value_type(first), distance_type(first));
}
// 以下這組 make_heap() 不允許指定「大小比較標(biāo)準(zhǔn)」匾旭。
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*) {
if (last - first < 2)
return; // 如果長度為 0 或 1镣屹，不必重新排列。
Distance len = last - first;
// 找出第一個(gè)需要重排的子樹頭部价涝，以 parent 標(biāo)示出女蜈。由于任何葉節(jié)點(diǎn)都不需執(zhí)行
// perlocate down，所以有以下計(jì)算。parent 命名不佳伪窖，名為 holeIndex 更好逸寓。
Distance parent = (len - 2)/2;
while (true) {
// 重排以 parent 為首的子樹。len 是為了讓 __adjust_heap() 判斷操作范圍
__adjust_heap(first, parent, len, T(*(first + parent)));
if (parent == 0) return;
parent--;
// 走完根節(jié)點(diǎn)覆山，就結(jié)束竹伸。
// （即將重排之子樹的）頭部向前一個(gè)節(jié)點(diǎn)
}
}
參考文獻(xiàn)：《STL源碼剖析》——侯捷
