前言：

我們已經掌握了string vector list三種最基本的數據容器模板，而對于數據結構的內容來說，其余的數據結構容器基本都是這三種容器的延申和擴展，在他們的基礎上擴展出更多功能和用法，今天我們便來模擬實現一下C++庫中的棧和隊列以及優先級隊列。

1.適配器：

讓我們打開stack模板庫的介紹界面，我們會看到這樣一個東西：

stack的模板中的這個Container是什么呢？沒錯，在這里我們將其稱之為適配器，它的作用是，為我們的的棧或者其他數據結構自動匹配底層的容器模板庫，如下：

template<class T, class Container = deque<T>>
class stack
{
private:Container _con;
};
int main()
{hbw::stack<int,list<int>> a1;
}

你會發現，我們的私有的成員直接就是適配器類型的，這樣當我們的主程序讓其適配器為list類型的時候，適配器會去判斷當前的stack的功能函數能否復用到list的成員函數中，倘若可以，我們就可以通過list的底層模板函數功能直接實現出stack的功能。
因此，只要我們的容器的底層容器的功能能夠匹配我們當前容器的功能，適配器就可以自動適配到對應的容器中，這樣的復用大大節省了效率，讓我們在開發時不用再去自己構建復雜的函數和對應的容器即可實現，或許我這樣說，你還沒法理解，我們接下來的棧和隊列的模擬實現的代碼，你通過去與我C語言實現的棧和隊列去對比即可明白。

deque容器:

依舊是拿出來我們的stack的模板參數，你會發現，它在適配器參數上給了個缺省值deque，根據剛才的是適配器的知識點我們知道，這里的container指代的是一個容器類型，故我們的deque也一定是一個容器類型，因此，我們可以先猜測一下，這個deque為何讓它作為缺省參數呢？
根據之前的C語言棧的隊列篇我曾經說到，棧和隊列都是可以同時使用數組和鏈表來實現的，對應到C++里，也就是說vector或者list都可以作為stack的底層，因此，作為缺省值，這個deque理論上應當具備兩者都有的功能，如下：

沒錯，從它的成員函數來看，它既可以和vector一樣去利用[]訪問下標，也可以實現list的頭刪頭插，訪問頭尾的功能，因此，在這里讓deque作為缺省值，確實是合適不過的，但是，它是如何同時具備兩種數據結構的特點的呢？下面讓我們一起來分析一下它的容器構建原理：

deque容器的介紹：

deque被稱為雙端隊列。雖然叫它隊列，但實際上它并不是隊列，也就是說它不是僅僅可以尾插頭刪，只不過叫這個名字，這個首先要明確，別搞混。它是一種從中間向兩邊延申的結構，在它的模板中，我們看到了deque使用了內存池allocator來存儲數據：

或許說到這里，我們大致猜出來deque的大體模型是怎樣的了，在我看來更類似即可幾個數組通過某種方式拼接，讓這些數組在邏輯上是連續的，deque的具體構造如下圖：

我們的deque支持兩個容器的功能，可以說它的功能是全面的，而我們也知道它使用了內存池allocator,這個內存池的就是我們上圖中的BUFF子數組，每一個BUFF數組的長度都是統一的，這樣方便我們的下標訪問執行。
它實現功能大致如下：
1.尾插：
則在最后一個數組之后再開辟一個新的BUFF，將尾插數據放在這個數組的第一位
2.頭插：
在第一個BUFF之前再開辟一個BUFF，將頭插數據放在這個數組的最后一位
我們發現，這樣的處理方式是沒有擴容的消耗的，也不需要挪動數據，很高效
3.之間插入：
中間插入時，我們只有兩種辦法：
1.BUFF進行擴容/控制數據個數
2.局部整體挪動
這兩種方法都可以，但是都有各自的缺點，比如，如果我們對BUFF進行擴容，就會影響我們的[]下標訪問，根據deque的結構我們可以總結出，deque下標的計算公式是：x=i/10+i%10,當然，這里是我們假設我們的BUFF都為10的情況下，因此，首先/10確定對應的元素在哪個BUFF子數列里，然后%10確定它在這個子數列的第幾個，這樣，我們就可以精確的鎖定位置，從而讓下標訪問生效。所以，一旦我們去修改BUFF的長度，就會導致我們這個公式直接無效，十分影響[]訪問，但倘若挪動數據，則又會消耗大量的時間，因此，兩種方案各有取舍，我們可以根據庫STL去看看官方是如何實現的。
我們的deque只涉及到中控數組的擴容問題。但是，由于存儲的數據是指針，故只要進行淺拷貝即可，因此，它擴容的消耗并不大。
綜上，雖然deque兼具vector和list的雙重特點，但它卻沒有將自己的特性優化到極致，我們可以說deque在頭插和尾插方面確實有很大的優勢，但是它的下標訪問和中間的增刪都不如vector和list，具體的deque的實現如下：

它一共有四個指針去控制整個結構，其中cur用來指針的實時位置，first指向一個BUFF的頭，last指向這個BUFF的尾部，而node則用來控制中控數組的指針，當cur==last的時候，node自動向下移動一位，從而實現了下標的連續訪問。

2.stack模擬實現：

有了前面的知識鋪墊，我們已經不需要怎樣去解釋實現的細節，直接按照代碼理解即可

namespace hbw
{template<class T, class Container = deque<T>>//這里通過這個模板參數控制底層的容器是哪個類型，是誰，這個Container即為適配器，不管底層容器是誰，它都可以適配一個后進先出的棧，如果適配器不適用(比如對應的底層的容器不支持上層的功能）,則編譯器會報錯class stack//我們在這里加上了一個缺省參數，deque容器，這就符合了我們倘若不傳對應的數據類型，編譯器就會為我們自動適配deque容器，deque容器是一個功能很全面的容器，雖然效率上不夠極致，但是泛用性強，故用在這里可以支持list和vector兩者的全部功能，從而有了作為缺省值的條件{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

3.queue模擬實現:

namespace hbw
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

他們兩個的本質都是復用，復用底層的函數封裝成自己的函數功能，這就是適配器的優點所在，不過，值得注意的是，適配器只能轉換為符合當前功能的底層容器，對于不符合功能的容器，編譯器是沒法通過的

4.優先級隊列priority_queue容器：

何為優先級隊列，即是一個優先按照升序或者降序存儲輸出值的容器，我們可以先看一下它的一些模板功能：

沒錯，看到它的函數功能，它可以返回頂部的元素，又結合它按照順序輸出數的特性，我們不難看出，它很像我們曾經模擬實現的一個數據結構-堆。因此，它的默認底層容器為vector，也就死用數組作為默認的缺省底層容器
沒錯，雖然叫它優先級隊列，但實際上，它的本質就是一個升序或者降序的堆，既然是堆，我們就可以復用我們之前學過的堆的各種接口，故它的模擬實現如下：
首先，我們依舊使用適配器來作為priority_ queue的底層如下：

  template<class T,class Container=vector<T>,class Comapre=Less<T>>private:Container _con;};

1.push函數:

	void Adjustup(int child)//向上調整{Compare com;int parent = (child-1)/ 2;while (child > 0){if (com(_con[parent],_con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}
void push(const T& x)
{_con.push_back(x);Adjustup(_con.size()-1);
}

push函數，我們的基本思路就是，將任意數據放入我們的底層容器后，將其向上調整到對應的位置，保證我們的堆的數據之間的關系不會亂，這里的向上調整的函數之前實現過，在這里我們可以復習一遍。

2.pop函數：

void Adjustdown(int parent)//向下調整
{Compare com;int child = 2 * parent + 1;while(child<_con.size()){if (child + 1 < _con.size() &&com(_con[child],_con[child+1])){child++;}if(com(_con[parent],_con[child])){std::swap(_con[child], _con[parent]);parent = child;child = 2 * child + 1;}else{break;}}
}void pop(){std::swap(_con[0],_con[_con.size()-1]);_con.pop_back();//尾刪一個Adjustdown(0);}

對于刪除來說，我們一定是刪除頭數據比較有價值，故我們采取的方式是，首先讓頭尾數據交換位置，然后將尾部數據刪除，然后將頭數據向下調整到正確的位置，保證堆的數據大小關系不會錯誤。

3.其余的接口

const T& top()
{return _con[0];
}bool empty()
{return _con.empty();
}size_t size()
{return _con.size();
}T& operator[](size_t i)
{return _con[i];
}

都是一些很簡單的接口，我在這里不多解釋，讀代碼就應該能看懂。

4.仿函數(關鍵！！！！）：

在priority_queue中，我們看到了這樣的一個模板參數，compare，它的默認參數值給了一個less，經過嘗試，我們知道，這個less實際上就是構建大堆的意思，但是，在這里的這個Compare是什么意思呢？這就是我們要說的仿函數.
那什么是仿函數呢？我們先看一個例子：

template<class T>
class Less//仿函數less
{
public:bool operator()(T& x, T& y){return x < y;}
};template<class T>
class Greater//仿函數greater
{
public:bool operator()(T& x, T& y){return x > y;}
};

仿函數的本質就是一個只封裝了一個()運算符重載的函數的類，當我們使用的時候，直接在類名后面帶上括號即可調用這個函數，導致我們看到它的形式就類似一個函數調用，但本質上它依舊是一個類，所以稱它為仿函數。如下：

void Adjustdown(int parent)//向下調整
{Compare com;int child = 2 * parent + 1;while(child<_con.size()){if (child + 1 < _con.size() &&com(_con[child],_con[child+1])){child++;}if(com(_con[parent],_con[child])){std::swap(_con[child], _con[parent]);parent = child;child = 2 * child + 1;}else{break;}}
}

當我們看到這個compare com時，這個com就是仿函數類，后續比較的時候，直接利用仿函數傳入參數就可以直接進行比較,比如這里的com(_con[child],_con[child+1]。

仿函數的優點和用處：

有了仿函數，我們就可以像預處理那樣對一些運算方法進行復用和小成本的修改，比如我們想從建立大堆變成建立小堆，就像上面一樣，分別寫一個大堆一個小堆兩個仿函數，想使用哪個直接在模板參數里實例化即可，這樣提高了效率。
但是仿函數的用處更多的在于它替換了函數指針，我們不用在寫繁雜的函數指針參數去使用回調函數，不僅難寫而且易錯，而是利用仿函數，調用即可，其實本質上仿函數和回調函數的用處一樣的，但是仿函數更加好用和簡單。
一般仿函數都寫成模板類，讓其可以針對任意類型進行函數使用，讓其運用的場景更加廣泛。

5.構造函數：迭代器數據傳入構造建堆

priority_queue()//寫一個默認無參的構造函數，讓編譯器自己生成默認的構造函數構成重載
{}template<class InputIterator>
priority_queue(InputIterator first, InputIterator end)//利用區間進行構造函數:_con(first,end)//首先利用vector可以區間構造的特點，先把數據放入到vector容器中
{int i = 0;for (i = (_con.size() - 2) / 2; i >= 0; i--){Adjustdown(i);}
}

priority_queue支持傳入迭代器區間去建堆，其構造的特點就是首先利用底層容器的vector支持迭代器區間構建數組的特點先初始化_con,然后利用向下建堆的方法，從而建立一個堆，但是寫下這個構造函數之后，我們的默認構造函數就沒有了，也就是說，后續的構造函數都得傳區間，這個是不一定，故我們再寫一個默認無參或者全缺省的構造函數，這個就是由編譯器自動生成的構造函數，由此，我們就可以同時支持區間迭代器構造和默認構造了。

總結：

以上便是我們的stack queue 優先級隊列的基本內容，到這里，我們基本已經掌握了STL庫的基本容器模板，但我還是要強調的一點，我已經反復強調了，模擬實現模板的目的是讓我們更好的去使用模板，從C語言的思維中走出來，嘗試利用C++的思維去解題和分析，熟練的利用模板去簡化代碼和提高開發效率。同時，模擬實現的過程中我們也學到了如迭代器，迭代器自定義封裝，內存池，如何忽略空格任意字符識別，如何擴容，迭代器失效，仿函數等一系列更加重要的屬于C++的知識點，我認為這些才是關鍵，因此，我們應該要抓住我們的重點去學習，在我看來，這是最關鍵的。