目錄

1、priority_queue的使用

2、實現沒有仿函數的優先級隊列

3、實現有仿函數的優先級隊列

3.1 仿函數

3.2 真正的優先級隊列

3.3 優先級隊列放自定義類型

1、priority_queue的使用

priority_queue是優先級隊列，是一個容器適配器，不滿足先進先出的特點，而是優先級高的先出，默認的適配器是vector，底層是一個堆，默認是大堆

priority_queue是可以進行迭代器區間初始化的

void test_priority_queue1()
{vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1;for (auto& e : v)q1.push(e);while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;
}

void test_priority_queue2()
{vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1(v.begin(), v.end());while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;
}

可以用數組直接初始化?

void test_priority_queue3()
{int v[10] = {3,2,7,6,0,4,1,9,8,5};priority_queue<int> q1(v, v + 10);while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;
}

上面3段代碼的結果都是相同的，都是9 8 7 6 5 4 3 2 1 0，因為默認是建大堆

2、實現沒有仿函數的優先級隊列

namespace cxf
{template<class T,class Container = std::vector<T>>class priority_queue{public:// 建大堆void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else break;}}void adjust_down(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}if (_con[parent] < _con[child]){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else break;}}// 強制編譯器生成默認的構造函數，因為下面有迭代器區間初始化，這樣沒辦法用默認構造函數priority_queue() = default;// 迭代器區間初始化template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}// 建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

上面是建大堆的優先級隊列，當要建小堆時，需要在adjust_up和adjust_up中將<改成>，這樣是十分麻煩的，為例能夠在不修改代碼的情況下完成建小堆，所以引入了仿函數的概念

3、實現有仿函數的優先級隊列

3.1 仿函數

仿函數就是重載了operatror()的類，類的對象可以像調用函數一樣使用

operator()的特點是參數個數和返回值個數可以根據需求來定，很靈活，所以有很多用法

若用class來定義仿函數的類要加public，所以通常會用struct來定義仿函數

根據仿函數就可以來實現一個既可建大堆，又可建小堆的優先級隊列

3.2 真正的優先級隊列

namespace cxf
{template<class T>class myless // 小于是大堆{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class mygreater // 大于是小堆{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = std::vector<T>, class Comapre = myless<T>>class priority_queue{public:void adjust_up(int child){Comapre comfunc;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if(comfunc(_con[parent],_con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else break;}}void adjust_down(int parent){Comapre comfunc;int child = parent * 2 + 1;while (child < _con.size()){/*if (child + 1 < _con.size() && _con[child] < _con[child + 1])*/if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if(comfunc(_con[parent],_con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else break;}}// 強制編譯器生成默認的構造函數，因為下面有迭代器區間初始化，這樣沒辦法用默認構造函數priority_queue() = default;// 迭代器區間初始化template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}// 建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

priority_queue的第三個模板參數就是仿函數?

在STL庫中的priority_queue來建小堆

3.3 優先級隊列放自定義類型

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);
private:int _year;int _month;int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}
int main()
{priority_queue<Date> q1;q1.push(Date(2022, 9, 9));q1.push(Date(2022, 9, 10));q1.push(Date(2022, 9, 11));while (!q1.empty()){cout << q1.top() << endl;q1.pop();}return 0;
}

結果是正確的，因為只要這個自定義類型是能夠比較大小的，都能使用優先級隊列

但是若比較的不是這個自定義類型，而是這個自定義類型的指針，則會出現隨機結果

int main()
{priority_queue<Date*> q1;q1.push(new Date(2022, 9, 9));q1.push(new Date(2022, 9, 10));q1.push(new Date(2022, 9, 11));while (!q1.empty()){cout << *q1.top() << endl;q1.pop();}return 0;
}

此時是錯誤的，并且每次運行程序結果也不一定都相同。因為less比較的是Date*，是根據地址比較的，而new出來的地址是隨機的，所以幾次的運行結果也會不同。而且這個比較從邏輯上就是錯誤的，因為不應該使用對象的地址去比較，應該使用對象的值去比較

所以可以自己寫一個仿函數，達到想要的目的

struct PDateLess
{bool operator()(Date* p1, Date* p2){return *p1 < *p2;}
};
int main()
{priority_queue<Date*, vector<Date*>, PDateLess> q1;q1.push(new Date(2022, 9, 9));q1.push(new Date(2022, 9, 10));q1.push(new Date(2022, 9, 11));while (!q1.empty()){cout << *q1.top() << endl;q1.pop();}return 0;
}

此時就正確的

所以仿函數不僅可以支持比較大小，還可以支持修改比較邏輯，如果默認的比較邏輯不是想要的或者不支持比較大小，都可以通過仿函數來控制。