優先級隊列

認識優先級隊列

優先級隊列（priority_queue）不是隊列。優先級隊列是一種容器適配器，與棧（stack），隊列（queue）具有類似的功能。

先來了解一下優先級隊列有哪些功能。看下圖：

優先級隊列底層是一個堆（默認是大堆），第二個參數默認給的是vector，不適合list，第三個參數是仿函數（函數對象）。

模擬實現優先級隊列

大部分成員函數可以通過調用vector的成員函數來實現。

#pragma oncenamespace bit {//目前建堆默認大堆，如果想建小堆怎么辦？template<class T, class Container = vector<T>>class priority_queue {private://不想讓別人知道這兩個函數，可以設置為私有void AdjustUp(int child){//向上調整需要和兄弟比較嗎？int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下調整刪除數據調用void AdjustDown(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){++child;}if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}public:template<class InputIterator>priority_queue(InputIterator first, InputIterator last){//傳過來的迭代器可能不是有序的，所以要排序建堆。while (first != last){push(*first);++first;}}priority_queue()//會調用vector的默認構造函數{}void push(const T& val){_con.push_back(val);AdjustUp(_con.size() - 1);}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}void pop(){//為什么swap不交換swap(_con[0], _con[_con.size() - 1]);//_con.size() - 1;//為什么這個程序不執行？執行了，但是size沒變，只是_con.size() - 1_con.pop_back();AdjustDown(0);}void swap(priority_queue& pq){std::swap(_con, pq._con);}size_t size() const{return _con.size();}private:Container _con;};
}

如果想建小堆，但不增加代碼量的冗余，有辦法嗎？

淺談仿函數

仿函數的大致了解

怎么建小堆？可以增加一個參數函數指針，這個函數來控制大堆還是小堆。但是函數指針聲明比較復雜，有一些聲明很長，導致通用性變差。所以，仿函數就來了。

寫一個類，類中寫相應的方法，這個類作為參數，那么就可以調用該類中的方法了。

仿函數（函數對象）不是函數調用，只是具有函數的功能。

如下代碼是對上面代碼的補充與修改

仿函數的實現

#pragma oncenamespace bit {template<class T, class Container = vector<T>, class Compare = Greater<int>>class priority_queue {private://不想讓別人知道這兩個函數void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1], _con[child])){++child;}if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}public:template<class InputIterator>priority_queue(InputIterator first, InputIterator last){//傳過來的迭代器可能不是有序的，所以要排序建堆。while (first != last){push(*first);++first;}}priority_queue()//會調用默認的構造函數{}void push(const T& val){_con.push_back(val);AdjustUp(_con.size() - 1);}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}void pop(){//為什么swap不交換swap(_con[0], _con[_con.size() - 1]);//_con.size() - 1;//為什么這個程序不執行？執行了，但是size沒變，只是_con.size() - 1_con.pop_back();AdjustDown(0);}void swap(priority_queue& pq){std::swap(_con, pq._con);}size_t size() const{return _con.size();}private:Container _con;};
}
template<class T>
struct Less
{
public:bool operator()(T& x, T& y){return x > y;}
};
template<class T>
struct Greater
{
public:bool operator()(T& x, T& y){return x < y;}
};

仿函數很方便，類中寫許多的函數，資源的管理性不錯，參數就可以只傳一個類，封裝性很強，靈活性很高。

反向迭代器

什么是反向迭代器？

**反向迭代器（reverse_iterator)**就是迭代器的相反。rbegin就是end，rend就是begin。

圖中表示的rbegin，rend就是反向迭代器。

那如何實現反向迭代器呢？

反向迭代器的實現

仔細觀察上面那張圖，begin與rbegin，end與rend都是對稱的。

·反向迭代器初始化可以調用正向迭代器的初始化

·反向迭代器++就是正向迭代器 的–，–就是正向迭代器的++。

先來看看庫里面的反向迭代器是如何實現的。

反向迭代器中有一個正向迭代器成員。++和–操作沒有問題，都是調用正向迭代器的++和–函數，但是解引用（*）函數中為什么要–？

我們根據如下代碼進行分析：

#include<iostream>
#include<vector>
using namespace std;int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector<int>::reverse_iterator rit = v.rbegin();for (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;
}

)rbegin 是由 end 初始化的，所以指向最后一個元素的下一個位置。所以解引用時，rbegin 要到前一個位置，返回前一個位置的元素，rbegin不變，rbegin 和 rend 相等時循環結束。

反向迭代器的實現：

//反向迭代器可以封裝一個正向迭代器，各種操作可以調用正向迭代器的函數
template<class Iterator, class Ref, class Ptr>
class ReverseIterator {
private:Iterator _it;
public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator()//調用正向迭代器的構造函數{}ReverseIterator(const Iterator& it):_it(it)//調用正向迭代器的拷貝構造函數{}Ref operator*()//解引用指向前一個位置的元素，本身不變。{Iterator tmp = _it;return *(--tmp);}Self& operator++()//調用正向迭代器--函數{--_it;return *this;}Self& operator--()//調用正向迭代器++函數{++_it;return *this;}bool operator!=(const Self& s)//調用正向迭代器的!=函數{return _it != s._it;}
};

結語

優先級隊列（priority_queue）實現較為簡單，與數據結構中的堆很相似。實現優先級隊列與實現棧和隊列的區別是：棧和隊列可以直接復用其他容器的函數，優先級隊列則需要自己加一些東西進去加工，如向下調整，仿函數等。

仿函數替換成函數指針。函數指針很麻煩，寫個函數聲明很長，讀懂也容易繞暈。仿函數就是一個類，類中可以寫許多函數，封裝的很好，使用時很方便。

反向迭代器（reverse_iterator)就是理解解引用（*）的過程，寫起來就是封裝一個正向迭代器。