前言

繼上一篇stack和queue我們講解了其實現原理，里面也提到了容器適配器的概念，本篇我們要講的優先級隊列，也是一種容器適配器，另外我們再順帶講一下反向迭代器，這個也是一個容器適配器哦，廢話不多說，我們直接切入正題

一、 priority_queue

1.priority_queue的介紹

priority_queue他是一種容器適配器，但其實他底層和堆差不多，接口和堆也非常像，功能也是，默認情況下是大堆，你也可以用仿函數把他改成小堆

它的接口有以下幾個：

1. empty()：檢測容器是否為空
2. size()：返回容器中有效元素個數
3. front()：返回容器中第一個元素的引用
4. push_back()：在容器尾部插入元素
5. pop_back()：刪除容器尾部元素

priority_queue的底層是堆，堆其實是完全二叉樹，而完全二叉樹的物理結構又是類似數組這種連續的物理空間，所以說適配priority_queue的容器要能夠隨機訪問下標，需要支持隨機訪問迭代器，以便始終在內部保持堆結構，一般我們用vector作為它的默認容器，deque也可以

2.priority_queue的使用

2.1、接口使用說明

2.2、優先級隊列的使用樣例

priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5);
while (!pq.empty())
{cout << pq.top() << " ";pq.pop();
}
//打印結果是5,4,3,2,1

tips：默認情況下大的優先級高，底層是個大堆

3.priority_queue的底層實現

3.1、庫里面關于priority_queue的定義

priority_queue類模板參數多了一個Compare，這個參數是用來調節大小堆的，默認的less是大堆，greater是小堆
tips:

3.2、仿函數

1.什么是仿函數？

仿函數又被叫做函數對象，它們是通過重載operator()運算符的類的實例，它們可以像函數那樣被調用，具有這樣特性的就是仿函數

2.仿函數樣例

template<class T>
struct Less
{bool operator()(const T& x, const T& y){return x < y;}
};int main()
{Less<int> lessfunc;cout << lessfunc.operator()(1, 2) << endl;cout << lessfunc(2, 3) << endl;//就這樣乍一看還以為是函數調用，其實這是仿函數cout << Less<int>()(1, 2) << endl;//通過匿名對象來調用return 0;
}

3.3、實現優先級隊列

1. 1.0版本的實現

template<class T,class Container=vector<T>>
class priority_queue
{
public:size_t size(){return _con.size();}void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 <_con.size() && _con[child] < _con[child + 1]){child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);//先尾插adjust_up(_con.size()-1);//再向上調整}void pop(){swap(_con[0], _con[_con.size() - 1]);//先把要刪除的堆頂元素和最后一個元素交換_con.pop_back();//然后刪除最后一個元素adjust_down(0);//再進行向下調整}const T& top(){return _con[0];}bool empty(){return _con.empty();}private:Container _con;
};

這里重點講一下向上調整建堆和向下調整建堆，我們以建小堆為例：

向下調整的原理和向上調整很像，我就不多講解了

2. 2.0版本的實現

template<class T>
struct less//這個雖然叫less但是它是大堆
{bool operator()(const T& x, const T& y){return x < y;}
};
template<class T>
struct greater//這個雖然叫greater,但是他是小堆
{bool operator()(const T& x, const T& y){return x > y;}
};
template<class T,class Container=vector<T>,class Com=less<T>>
class priority_queue
{
public:size_t size(){return _con.size();}void adjust_up(size_t child){Com com;//搞一個仿函數對象size_t parent = (child - 1) / 2;while (child>0){//if (_con[child] > _con[parent])//if ( _con[parent]<_con[child] )if(com(_con[parent],_con[child])){//注意這里換成仿函數的時候要和它里面的<對上，再替換成仿函數對象調用swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Com com;size_t child = parent * 2 + 1;while (child<_con.size()){//if (child + 1 <_con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){child++;}//if (_con[child] > _con[parent])//if (_con[parent]< _con[child])if (com(_con[parent] , _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);//先尾插adjust_up(_con.size()-1);//再向上調整}void pop(){swap(_con[0], _con[_con.size() - 1]);//先把要刪除的堆頂元素和最后一個元素交換_con.pop_back();//然后刪除最后一個元素adjust_down(0);//再進行向下調整}const T& top(){return _con[0];}bool empty(){return _con.empty();}private:Container _con;
};

tips:

int main()
{priority_queue<int,vector<int>,greater<int>> pq;//注意這里：如果你要傳仿函數的參數類型，一定不要忘記了這個vector<int>//不能跳過這個缺省參數去傳他后面的其他參數，切記切記！！！return 0;
}

二、反向迭代器適配器

反向迭代器適配器，可以根據正向迭代器適配出它相應的反向迭代器

反向迭代器的實現思想其實很簡單，相比我們前面list的實現；我們在這里實現反向迭代器主要是利用正向迭代器來替我們完成，庫里面的實現講求了對稱，begin/end和rbegin/rend是堆成的

template<class iterator, class Ref, class Ptr>
struct ReserveIterator
{typedef ReserveIterator<iterator, Ref, Ptr> Self;iterator _it;ReserveIterator(iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}
};

---

關于容器適配器之類的容器我們就先講到這里，我們下期淺談一下模板?