所謂順序容器(sequential containers)，其中的元素都可序(ordered)，但未必有序(sorted)。C++本身提供了一個順序容器
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可以用變量初始化，會自動擴容
array<typeName, n_elem> arr; //array的n_elem必須由常量指定，不會自動擴容
兩者的唯一差別在于空間運用的靈活性：array是靜態(tài)空間，一旦配置就不能改變；vector是動態(tài)空間，隨著元素的加入，他的內(nèi)部機制會自動擴充空間以容納新的元素。vector的實現(xiàn)技術(shù)，關(guān)鍵在于對其大小的控制以及重新配置時的數(shù)據(jù)移動效率！
1、迭代器
vector維護的是一個連續(xù)線性空間。不論其元素類型為何，普通指針都可作為vector的迭代器而滿足所有必要條件，因為vector迭代器所需要的操作行為(例如operator操作)，普通指針天生就具備。vector支持隨機存取，而普通指針正有這種能力。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的類型其實就是int*
vector<Shape>::iterator svite; //svite的類型其實就是Shape*
2、數(shù)據(jù)結(jié)構(gòu)
vecotr所采用的數(shù)據(jù)結(jié)構(gòu)非常簡單：線性連續(xù)空間。它以兩個迭代器start和finish分別指向配置得來的連續(xù)空間中目前已被使用過的范圍，并以迭代器end_of_storage指向整塊連續(xù)空間(含備用空間)的尾端：
template<class T, class Alloc = alloc>
class vector {
......
protected:
iterator start; //已使用空間的頭
iterator finish; //已使用空間的尾
iterator end_of_storage; //可用空間的尾
......
}
為降低空間配置時的速度成本，vector實際配置的大小可能比客戶端需求量更大一些，以備將來可能的擴充。換言之，一個vector的容量永遠大于或等于其大小。一旦容量等于大小，便是滿載，下次再有新增元素，整個vecotr就得另尋居所。
3、構(gòu)造與內(nèi)存管理：constructor、push_back
vector缺省使用alloc作為空間配置器，并據(jù)此定義了一個data_allocator，為的是更方便以元素大小為配置單位：
template<class T, class Alloc = alloc>
class vector {
......
protected:
typedef simple_alloc<value_type, Alloc> data_allocator;
......
于是，data_allocator::allocate(n)表示配置n個元素空間。我們考察vector提供的眾多constructors中的一個：
//構(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個元素空間
uninitialized_fill_n(result, n, x);
return result;
}
uninitialized_fill_n()會根據(jù)第一個參數(shù)的類型特性(type traits)來決定填充數(shù)據(jù)的算法：如果是POD類型(Plain Old Data，也就是標量類型(scalar types)或傳統(tǒng)的C struct類型。POD類型必然擁有trivial ctor/dtor/copy/assignment函數(shù))則使用算法fill_n()，如果不是POD類型則循環(huán)調(diào)用construct()來填充所有配置而來的空間。
當我們以push_back()將元素插入于vector尾端時，該函數(shù)首先檢查是否還有備用空間，如果有就直接在備用空間上構(gòu)造函數(shù)，并調(diào)整迭代器finish，使vector變大。如果沒有備用空間就擴充空間。
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)造一個元素，并以vector最后一個元素值為其初值
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（個元素大?。? //如果原大小不為0，則配置原大小的兩倍，
//前半段用來放置原數(shù)據(jù)，后半段準備用來放置新數(shù)據(jù)
iterator new_start = data_allocator::allocate(len); //實際配置
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)容也拷貝過來（說實話感覺有點多此一舉）
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就顯得復雜許多，它的好處是每次插入或刪除一個元素，就配置或釋放一個元素空間。因此，list對于空間的運用有絕對的精準，一點也不浪費。而且對于任何位置的元素插入或元素刪除，list的時間復雜度永遠為常數(shù)。
1、list的節(jié)點(node)
list本身和list的節(jié)點是不同的數(shù)據(jù)結(jié)構(gòu)，需要分開設(shè)計，以下是STL list的節(jié)點(node)結(jié)構(gòu)：
template<class T>
struct __list_node {
typedef void * void_pointer;
void_pointer prev; //類型為void*，實際上設(shè)為__list_node<T>*也可以
void_pointer next;
T data;
}
顯然這是一個雙向鏈表。
2、迭代器
list迭代器必須有能力指向list的節(jié)點，并有能力做正確的遞增、遞減、取值、成員存取等操作，list提供的是Bidirectional Iterators。list有一個重要性質(zhì)：插入動作(insert)和拼接動作(splice)都不會造成原有的list迭代器失效。這在vector是不成立的，因為vector的插入動作可能造成記憶體重新配置，導致原有的迭代器全部失效。甚至list的元素刪除動作(erase)，也只有「指向被刪除元素」的那個迭代器失效，其它迭代器不受任何影響。
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)部當然要有一個原生指標，指向list的節(jié)點
//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é)點的資料值。
reference operator*() const { return (*node).data; }
//以下是迭代器的成員存?。╩ember access）運算子的標準做法。
pointer operator->() const { return &(operator*()); }
//對迭代器累加 1，就是前進一個節(jié)點
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
self operator++(int) { //后綴++
self tmp = *this;
++*this;
return tmp;
}
//對迭代器遞減 1，就是后退一個節(jié)點
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不僅是一個雙向鏈表，而且還是一個環(huán)狀雙向鏈表。所以它只需要一個指針，便可以完整表現(xiàn)整個鏈表：
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; // 只要一個指針，便可表示整個環(huán)狀雙向鏈表
.......
};
如果讓指針node指向刻意置于尾端的一個空白節(jié)點，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ù)迭代器的類型，用不同的方法計算兩個迭代器之間的距離，list的迭代器需要逐一累計計算距離
return result;
}
// 取頭節(jié)點的內(nèi)容（元素值）。
reference front() { return *begin(); }
// 取尾節(jié)點的內(nèi)容（元素值）。
reference back() { return *(--end()); }
4、構(gòu)造與內(nèi)存管理：constructor、push_back、insert
list預設(shè)使用alloc做為空間配置器，并據(jù)此另外定義了一個list_node_allocator，為的是更方便地以節(jié)點大小為配置單位：
template <class T, class Alloc = alloc> // 預設(shè)使用alloc為配置器
class list {
protected:
typedef __list_node<T> list_node;
// 專屬之空間配置器，每次配置一個節(jié)點大?。? typedef simple_alloc<list_node, Alloc> list_node_allocator;
......
};
于是，list_node_allocator(n)表示配置n個節(jié)點空間。以下四個函數(shù)，分別用來配置、釋放、構(gòu)造、摧毀一個節(jié)點：
protected:
// 配置一個節(jié)點并傳回
link_type get_node() { return list_node_allocator::allocate(); }
// 釋放一個節(jié)點
void put_node(link_type p) { list_node_allocator::deallocate(p); }
// 產(chǎn)生（配置并建構(gòu)）一個節(jié)點，帶有元素值
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)并釋放）一個節(jié)點
void destroy_node(link_type p) {
destroy(&p->data); // 全域函式，構(gòu)造/析構(gòu)基本工具。
put_node(p);
}
list提供有許多constructors，其中一個是default constructor，允許我們不指定任何參數(shù)做出一個空的list出來：
public:
list() { empty_initialize(); } // 產(chǎn)生一個空鏈表。
protected:
void empty_initialize()
node = get_node(); // 配置一個節(jié)點空間，令node指向它。
node->next = node; // 令node頭尾都指向自己，不設(shè)元素值。
node->prev = node;
}
當我們以push_back()將新元素安插于list尾端，此函數(shù)內(nèi)部調(diào)用insert()函數(shù)：
void push_back(const T& x) { insert(end(), x); }
insert()是一個重載函數(shù)，有多種形式，其中最簡單的一種如下，符合以上所需。首先配置并建構(gòu)一個節(jié)點，然后在尾端做適當?shù)闹羔槻僮鳎瑢⑿鹿?jié)點插入進去：
// 函數(shù)目的：在迭代器position所指位置安插一個節(jié)點，內(nèi)容為x。
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x); // 產(chǎn)生一個節(jié)點（設(shè)內(nèi)容為 x）
// 調(diào)整雙向指針，使tmp安插進去。
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é)點，首先必須確定插入位置，例如希望在數(shù)據(jù)值為3的節(jié)點處插入一個數(shù)據(jù)值為99的節(jié)點，可以這么做：
ilite = find(il.begin(), il.end(), 3);
if (ilite!=0)
il.insert(ilite, 99);
注意：
- 1、使用
list::merge()可以獲得兩個有序鏈表的二路歸并排序結(jié)果，但是前提是這個兩個list都必須有序！ - 2、
list不能使用STL算法sort()，必須使用自己的list::sort()member function，因為STL算法sort()只接受Random Access Iterator。list::sort()函數(shù)使用快排算法，實現(xiàn)細節(jié)如下：
template <class T, class Alloc>
void list<T, Alloc>::sort() {
// 以下判斷，如果是空白串行，或僅有一個元素，就不做任何動作。
// 使用 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ù)時間內(nèi)對頭尾兩端進行元素的入插或刪除動作，二在于deque沒有容量（capacity）概念，因為它是動態(tài)地以分段連續(xù)空間組合而成，隨時可以增加一段新的空間并鏈接起來。換句話說，像vector那樣「因舊空間不足而重新配置一塊更大空間，然后復制元素，再釋放舊空間」這樣的事情在deque是不會發(fā)生的。
1、控制器
deque由一段一段的定量連續(xù)空間構(gòu)成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續(xù)空間，串接在整個deque的頭端或尾端。deque的最大任務(wù)，便是在這些分段的定量連續(xù)空間上，維護其整體連續(xù)的假象，并提供隨機存取的界面。避開了「重新配置、復制、釋放」的輪回，代價則是復雜的迭代器架構(gòu)。使用分段連續(xù)線性空間，就必須有中央控制，而為了維護整體連續(xù)的假象，數(shù)據(jù)結(jié)構(gòu)的設(shè)計及迭代器前進后退等動作都頗為繁瑣。deque的實作碼份量遠比vector或list都多得多。
deque采用一塊所謂的map（不是STL的map容器）做為主控。這里所謂map是一小塊連續(xù)空間，其中每個元素（此處稱為一個節(jié)點，node）都是指針，指向另一段（較大的）連續(xù)線性空間，稱為緩沖區(qū)。緩沖區(qū)才是deque的儲存空間主體。SGI STL允許我們指定緩沖區(qū)大小，默認值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)的每個元素都是一個指針（稱為節(jié)點），指向一塊緩沖區(qū)。
size_type map_size; // map內(nèi)可容納多少指針。
......
};
整理一下，我們便可發(fā)現(xiàn)，map其實是一個T**，也就是說它是一個指針，所指之物又是一個指針，指向類型為T的一塊空間。
2、迭代器
deque是分段連續(xù)空間。維護其「整體連續(xù)」假象的任務(wù)，則落在迭代器的operator++和operator--兩個運算符身上。deque迭代器必須能夠指出分段連續(xù)空間（亦即緩沖區(qū)）在哪里，其次它必須能夠判斷自己是否已經(jīng)處于其所在緩沖區(qū)的邊緣，如果是，一旦前進或后退時就必須跳躍至下一個或上一個緩沖區(qū)。為了能夠正確跳躍，deque必須隨時掌握控制中心（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，所以必須自行撰寫五個必要的迭代器相應(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()，后者是個全局函數(shù)，定義如下：
// 如果n不為0，傳回n，表示buffer size由使用者自定。
// 如果n為0，表示buffer size使用默認值，那么
// 如果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)在有一個deque<int>，并令其緩沖區(qū)大小為32，于是每個緩沖區(qū)可容納32/sizeof(int)=8個元素。經(jīng)過某些操作之后，deque擁有20個元素，那么其begin()和end()所傳回的兩個迭代器如下圖所示。這兩個迭代器事實上一直保持在deque內(nèi)，名為start和finish。
20個元素需要20/8 = 3個緩沖區(qū)，所以map之內(nèi)運用了三個節(jié)點。迭代器start內(nèi)的cur指標當然指向緩沖區(qū)的第一個元素，迭代器finish內(nèi)的cur指標當然指向緩沖區(qū)的最后元素（的下一位置）。注意，最后一個緩沖區(qū)尚有備用空間。稍后如果有新元素要安插于尾端，可直接拿此備用空間來使用。
下面是deque迭代器的幾個關(guān)鍵行為。由于迭代器內(nèi)對各種指針運算都做了重載操作，所以各種指針運算如加、減、前進、后退等都不能直觀視之。其中最關(guān)鍵的就是：一旦行進時遇到緩沖區(qū)邊緣，要特別當心，視前進或后退而定，可能需要調(diào)用set_node()跳一個緩沖區(qū)：
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
// 以下各個重載運算符是 __deque_iterator<> 成功運作的關(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; // 切換至下一個元素。
if (cur == last) { // 如果已達所在緩沖區(qū)的尾端，
set_node(node + 1); // 就切換至下一節(jié)點（亦即緩沖區(qū)）
cur = first; // 的第一個元素。
}
return *this;
}
self operator++(int) { // 用int告訴編譯器++為后置式
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) { // 如果已達所在緩沖區(qū)的頭端，
set_node(node - 1); // 就切換至前一節(jié)點（亦即緩沖區(qū)）
cur = last; // 的最后一個元素。
}
--cur; // 切換至前一個元素。
return *this;
}
self operator--(int) { // 用int告訴編譯器++為后置式
self tmp = *this;
--*this;
return tmp;
}
// 以下實現(xiàn)隨機存取。迭代器可以直接跳躍n個距離。
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
// 標的位置在同一緩沖區(qū)內(nèi)
cur += n;
else {
// 標的位置不在同一緩沖區(qū)內(nèi)
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
// 切換至正確的節(jié)點（亦即緩沖區(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-=
}
// 以下實現(xiàn)隨機存取。迭代器可以直接跳躍 n 個距離。
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除了維護一個先前說過的指向map的指針外，也維護start,finish兩個迭代器，分別指向第一緩沖區(qū)的第一個元素和最后緩沖區(qū)的最后一個元素（的下一位置）。此外它當然也必須記住目前的map大小。因為一旦map所提供的節(jié)點不足，就必須重新配置更大的一塊map。
// 見 __deque_buf_size()。BufSize 默認值為 0 的唯一理由是為了閃避某些
// 編譯器在處理常數(shù)算式（constant expressions）時的bug。
// 預設(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)第一個節(jié)點。
iterator finish; // 表現(xiàn)最后一個節(jié)點。
map_pointer map; // 指向 map，map 是塊連續(xù)空間，其每個元素都是個指針，指向一個節(jié)點（緩沖區(qū)）。
size_type map_size; // map 內(nèi)有多少指標。
......
};
有了上述結(jié)構(gòu)，以下數(shù)個功能便可輕易完成：
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);
// 因為 __deque_iterator<> 沒有為 (finish-1) 定義運算?!
}
// 下行最后有兩個 ‘;’，雖奇怪但合乎語法。
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ū)擴充動作相當瑣碎繁雜，以下將以分解動作的方式一步一步圖解說明。假設(shè)程序一開始創(chuàng)建了一個deque：
deque<int,alloc,32> ideq(20,9);
其緩沖區(qū)大小為32bytes，并令其保留20個元素空間，每個元素初值為9。為了指定deque的第三個template參數(shù)（緩沖區(qū)大?。?，我們必須將前兩個參數(shù)都指明出來（這是C++語法規(guī)則），因此必須明確指定alloc為空間配置器?，F(xiàn)在，deque的情況如圖（該圖并未顯示每個元素的初值為 9）。
deque自行定義了兩個專屬的空間配置器:
protected: // Internal typedefs
// 專屬之空間配置器，每次配置一個元素大小
typedef simple_alloc<value_type, Alloc> data_allocator;
// 專屬之空間配置器，每次配置一個指針大小
typedef simple_alloc<pointer, Alloc> map_allocator;
并提供有一個 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()負責產(chǎn)生并安排好deque的結(jié)構(gòu)，并將元素的初值設(shè)定妥當：
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 {
// 為每個節(jié)點的緩沖區(qū)設(shè)定初值
for (cur = start.node; cur < finish.node; ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
// 最后一個節(jié)點的設(shè)定稍有不同（因為尾端可能有備用空間，不必設(shè)初值）
uninitialized_fill(finish.first, finish.cur, value);
}
catch(...) {
...
}
}
其中create_map_and_nodes()負責產(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é)點數(shù)=(元素個數(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);
// 以上配置出一個 “具有 map_size 個節(jié)點” 的 map。
// 以下令 nstart 和 nfinish 指向 map 所擁有之全部節(jié)點的最中央?yún)^(qū)段。
// 保持在最中央，可使頭尾兩端的擴充能量一樣大。每個節(jié)點可對應(yīng)一個緩沖區(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)的每個現(xiàn)用節(jié)點配置緩沖區(qū)。所有緩沖區(qū)加起來就是 deque 的
// 可用空間（最后一個緩沖區(qū)可能留有一些余裕）。
for (cur = nstart; cur <= nfinish; ++cur)
*cur = allocate_node();
}
catch(...) {
// "commit or rollback" 語意：若非全部成功，就一個不留。
...
}
// 為 deque 內(nèi)的兩個迭代器 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();
// 前面說過，如果剛好整除，會多配一個節(jié)點。
// 此時即令 cur 指向這多配的一個節(jié)點（所對映之緩沖區(qū)）的起頭處。
}
接下來以下標運算符為每個元素重新設(shè)值，然后在尾端安插三個新元素：
for(int i=0; i<ideq.size(); ++i)
ideq[i] = i;
for(int i=0;i<3;i++)
ideq.push_back(i);
由于此時最后一個緩沖區(qū)仍有4個備用元素空間，所以不會引起緩沖區(qū)的再配置。此時的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ū)尚有一個以上的備用空間
construct(finish.cur, t); // 直接在備用空間上建構(gòu)元素
++finish.cur; // 調(diào)整最后緩沖區(qū)的使用狀態(tài)
}
else // 最后緩沖區(qū)已無（或只剩一個）元素備用空間。
push_back_aux(t);
}
現(xiàn)在，如果再新增加一個新元素于尾端：
ideq.push_back(3);
由于尾端只剩一個元素備用空間，于是push_back()調(diào)用push_back_aux()，先配置一整塊新的緩沖區(qū)，再設(shè)妥新元素內(nèi)容，然后更改迭代器finish的狀態(tài)：
// 只有當 finish.cur == finish.last – 1 時才會被調(diào)用。
// 也就是說只有當最后一個緩沖區(qū)只剩一個備用元素空間時才會被調(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(); // 若符合某種條件則必須重換一個 map
*(finish.node + 1) = allocate_node(); // 配置一個新節(jié)點（緩沖區(qū)）
__STL_TRY {
construct(finish.cur, t_copy); // 針對標的元素設(shè)值
finish.set_node(finish.node + 1); // 改變 finish，令其指向新節(jié)點
finish.cur = finish.first; // 設(shè)定 finish 的狀態(tài)
}
__STL_UNWIND(deallocate_node(*(finish.node + 1)));
}
現(xiàn)在，deque 的狀態(tài)如下：
接下來程序在deque的前端安插一個新元素：
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()：
// 只有當 start.cur == start.first 時才會被呼叫。
// 也就是說只有當?shù)谝粋€緩沖區(qū)沒有任何備用元素時才會被呼叫。
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(); // 若符合某種條件則必須重換一個 map
*(start.node - 1) = allocate_node(); // 配置一個新節(jié)點（緩沖區(qū)）
__STL_TRY {
start.set_node(start.node - 1); // 改變 start，令其指向新節(jié)點
start.cur = start.last - 1; // 設(shè)定 start 的狀態(tài)
construct(start.cur, t_copy); // 針對標的元素設(shè)值
}
catch(...) {
// "commit or rollback" 語意：若非全部成功，就一個不留。
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
}
此函數(shù)一開始即調(diào)用`reserve_map_at_front()`， 后者用來判斷是否需要擴充map，如有需要就付諸行動。稍后我會展示`reserve_map_at_front()`函數(shù)的內(nèi)容。目前的狀態(tài)不需要重新整治map，所以后繼流程便配置了一塊新緩沖區(qū)并直接將節(jié)點安置于現(xiàn)有的map上，然后設(shè)定新元素，然后改變迭代器start的狀態(tài)，如下：
接下來程序又在`deque`的最前端安插兩個新元素：
```C++
ideq.push_front(98);
ideq.push_front(97);
這一次，由于第一緩沖區(qū)有備用空間，push_front() 可以直接在備用空間上建構(gòu)新元素，如下：
上面的連環(huán)圖解，已經(jīng)充份展示了deque容器的空間運用策略。讓我們回頭看看一個懸而未解的問題：什么時候map需要重新整治？這個問題的判斷由reserve_map_at_back()和reserve_map_at_front()進行，實際動作則由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é)點備用空間不足
// 符合以上條件則必須重換一個 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é)點備用空間不足
// 符合以上條件則必須重換一個 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;
// 配置一塊空間，準備給新 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是一種先進后出（First In Last Out，F(xiàn)ILO）的數(shù)據(jù)結(jié)構(gòu)，它只有一個出口。stack允許新增元素、移除元素、取得最頂端元素。但除了最頂端外，沒有任何其它方法可以存取stack的其它元素。換言之stack不允許有走訪行為。將元素推入 stack 的動作稱為push，將元素推出stack的動作稱為pop。
1、定義式完整列表
以某種既有容器做為底部結(jié)構(gòu)，將其接口改變，使符合「先進后出」的特性，形成一個stack，是很容易做到的。deque是雙向開口的數(shù)據(jù)結(jié)構(gòu)，若以deque為底部結(jié)構(gòu)并封閉其頭端開口，便輕而易舉地形成了一個stack。因此，SGI STL 便以deque做為預設(shè)情況下的stack底部結(jié)構(gòu)，stack的實作因而非常簡單，源碼十分簡短，本處完整列出。
由于stack系以底部容器完成其所有工作，而具有這種「修改某物接口，形成另一種風貌」之性質(zhì)者，稱為 adapter（配接器），因此 STL stack 往往不被歸類為container（容器），而被歸類為 container adapter。
//deque<T> >中間有個空格是為了兼容較老的版本
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 是兩頭可進出，stack 是末端進，末端出（所以后進者先出）。
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所有元素的進出都必須符合「先進后出」的條件，只有stack頂端的元素，才有機會被外界取用。stack不提供走訪功能，也不提供迭代器！
3、以list做為stack的底層容器
除了deque之外，list也是雙向開口的數(shù)據(jù)結(jié)構(gòu)。上述stack源碼中使用的底層容器的函式有empty, size, back, push_back, pop_back，凡此種種list都具備。因此若以list為底部結(jié)構(gòu)并封閉其頭端開口，一樣能夠輕易形成一個stack。下面是作法示范。
#include <stack>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
stack<int,list<int> > istack;
}
五、queue
queue是一種先進先出（First In First Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)，它有兩個出口。queue允許新增元素、移除元素、從最底端加入元素、取得最頂端元素。但除了最底端可以加入、最頂端可以取出，沒有任何其它方法可以存取queue的其它元素。換言之queue不允許有走訪行為。將元素推入queue的動作稱為push，將元素推出queue的動作稱為pop。
1、定義式完整列表
以某種既有容器為底部結(jié)構(gòu)，將其接口改變，使符合「先進先出」的特性，形成一個queue，是很容易做到的。deque是雙向開口的數(shù)據(jù)結(jié)構(gòu)，若以deque為底部結(jié)構(gòu)并封閉其底端的出口和前端的入口，便輕而易舉地形成了一個queue。因此，SGI STL 便以deque做為預設(shè)情況下的queue底部結(jié)構(gòu)，queue的實作因而非常簡單，源碼十分簡短，本處完整列出。
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 是兩頭可進出，queue 是末端進，前端出（所以先進者先出）。
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所有元素的進出都必須符合「先進先出」的條件，只有queue頂端的元素，才有機會被外界取用。queue不提供走訪功能，也不提供迭代器。
3、以list做為queue的底層容器
除了deque之外，list也是雙向開口的數(shù)據(jù)結(jié)構(gòu)。上述queue源碼中使用的底層容器的函式有empty, size, back, push_back, pop_back，凡此種種list都具備。因此若以list為底部結(jié)構(gòu)并封閉其頭端開口，一樣能夠輕易形成一個queue。下面是作法示范。
#include <queue>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
queue<int,list<int> > iqueue;
}
六、堆
heap并不歸屬于STL容器組件，它是個幕后英雄，扮演priority queue的推手。顧名思義，priority queue允許使用者以任何次序?qū)⑷魏卧赝迫肴萜鲀?nèi)，但取出時一定是從優(yōu)先權(quán)最高（也就是數(shù)值最高）之元素開始取。binary max heap 正是具有這樣的特性，適合做為priority queue的底層機制。
所謂 binary heap 就是一種complete binary tree（完全二叉樹），也就是說，整棵 binary tree 除了最底層的葉節(jié)點(s) 之外，是填滿的，而最底層的葉節(jié)點(s) 由左至右又不得有空隙。complete binary tree整棵樹內(nèi)沒有任何節(jié)點漏洞，因此我們可以利用 array 來儲存所有節(jié)點。將 array 的 0 號元素保留（或設(shè)為無限大值或無限小值），那么當 complete binary tree 中的某個節(jié)點位于 array 的 i 處，其左子節(jié)點必位于 array 的 2i 處，其右子節(jié)點必位于 array 的 2i+1 處，其父節(jié)點必位于「i/2」處。這種以array 表述 tree 的方式，我們稱為隱式表述法（implicit representation）。
這么一來，我們需要的工具就很簡單了：一個 array 和一組heap算法（用來安插元素、刪除元素、取極值、將某一整組數(shù)據(jù)排列成一個heap）。array 的缺點是無法動態(tài)改變大小，而heap卻需要這項功能，因此以 vector代替array是更好的選擇。
1、heap算法
push_heap算法：
為了滿足complete binary tree的條件，新加入的元素一定要放在最下一層做為葉節(jié)點，并填補在由左至右的第一個空格，也就是把新元素安插在底層vector的end()處。下圖所示是push_heap算法的實際操作過程：
為滿足max-heap的條件（每個節(jié)點的鍵值都大于或等于其子節(jié)點鍵值），我們執(zhí)行一個所謂的percolate up（上溯）程序：將新節(jié)點拿來與其父節(jié)點比較，如果其鍵值（key）比父節(jié)點大，就父子對換位置。如此一直上溯，直到不需對換或直到根節(jié)點為止。
該函數(shù)接受兩個迭代器，用來表現(xiàn)一個heap底部容器（vector）的頭尾，新元素并且已經(jīng)安插到底部容器的最尾端。如果不符合這兩個條件，push_heap的執(zhí)行結(jié)果將不可預測。
pop_heap算法：
為滿足max-heap的條件（每個節(jié)點的鍵值都大于或等于其子節(jié)點鍵值），我們執(zhí)行一個所謂的percolate down（下放）程序：將根節(jié)點（最大值被取走后，形成一個「洞」）填入上述那個失去生存空間的葉節(jié)點值，再將它拿來和其兩個子節(jié)點比較鍵值（key），并與較大子節(jié)點對調(diào)位置。如此一直下放，直到這個「洞」的鍵值大于左右兩個子節(jié)點，或直到下放至葉節(jié)點為止。下圖所示是pop_heap算法的實際操作過程：
此函式接受兩個迭代器，用來表現(xiàn)一個heap 底部容器（vector）的頭尾。如果不符合這個條件，pop_heap 的執(zhí)行結(jié)果將不可預測。
sort_heap算法(堆排序)：
既然每次pop_heap可獲得heap之中鍵值最大的元素，如果持續(xù)對整個heap做pop_heap動作，每次將操作范圍從后向前縮減一個元素（因為pop_heap會把鍵值最大的元素放在底部容器的最尾端），當整個程序執(zhí)行完畢，我們便有了一個遞增序列。下圖是sort_heap的實際操演情況。
該函數(shù)接受兩個迭代器，用來表現(xiàn)一個heap底部容器（vector）的頭尾。如果不符合這個條件，sort_heap的執(zhí)行結(jié)果將不可預測。注意，排序過后，原來的heap就不再是個合法的heap了。下面是sort_heap算法的實現(xiàn)細節(jié)：
// 以下這個 sort_heap() 不允許指定「大小比較標準」
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算法:
這個算法用來將一段現(xiàn)有的數(shù)據(jù)轉(zhuǎn)化為一個 heap。其主要依據(jù)complete binary tree的隱式表述（implicit representation）。
// 將 [first,last) 排列為一個 heap。
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
__make_heap(first, last, value_type(first), distance_type(first));
}
// 以下這組 make_heap() 不允許指定「大小比較標準」。
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;
// 找出第一個需要重排的子樹頭部，以 parent 標示出。由于任何葉節(jié)點都不需執(zhí)行
// perlocate down，所以有以下計算。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é)點，就結(jié)束。
// （即將重排之子樹的）頭部向前一個節(jié)點
}
}
參考文獻：《STL源碼剖析》——侯捷
