C++ 优先队列 priority_queue 使用篇
目录
1.储备知识
(1)数据结构：堆
(2)仿函数(函数对象)
[1]理解仿函数
[2]实现仿函数
(3)priority_queue理解
[1]什么是priority_queue (优先队列)？
[2]优先队列性质
2.priority_queue的参数理解(重要！！！)
(1)priority_queue的参数
[1]priority_queue类模板参数
[2]比较类的函数参数
[3]构造函数的参数列表
3.priority_queue的使用
(1)常用函数介绍
(2)priority_queue中存储内置类型元素
(3)priority_queue中存储自定义类型元素
(4)priority_queue中存储自定义类型元素的地址
priority_queue（优先队列）也是容器适配器，理解优先队列需要较多的铺垫知识：堆、仿函数。如果不了解的话需要先学习这两个知识点，很重要。
本文代码在win10系统下的vs2019验证。
1.储备知识
(1)数据结构：堆
堆是以二叉树为基础的数据结构，分为大堆与小堆。但因为篇幅过长就不在这篇文章详细说了，有需要的可以看这篇文章：http://t.csdn.cn/xlWlH
(2)仿函数(函数对象)
[1]理解仿函数
什么是仿函数(函数对象)？
仿函数就是假函数，它是把对象当作函数使用，所以也称为函数对象。因为普通函数在某些特殊场景下使用比较麻烦，所以就诞生了仿函数。
如何实现仿函数？
重载()运算符即可。
[2]实现仿函数
代码中定义Less类，重载()，函数中定义了a、b两个参数，当a小于b就返回true，否则返回false。
在main函数中创建了Less类的对象，如果想要调用重载()，常规的调用方法应该是对象名.函数名(参数列表)。但因为重载()函数是可以省略.operator()的，所以我们可以使用简化的方式调用，这样是不是看起来跟使用普通函数一模一样了。这就是仿函数的使用。
#include "iostream"
using namespace std;
class Less {
public:
bool operator()(const int a,const int b) const{
return a < b;
}
};
int main() {
//创建对象
Less lessCompare;
//常规的调用方式
//bool result = lessCompare.operator()(2, 8);
//简化后的调用方式
bool result = lessCompare(2, 8);
cout << result << endl;
}(3)priority_queue理解
[1]什么是priority_queue (优先队列)？
优先队列是一种容器适配器，采用了堆这样的数据结构，保证了第一个元素总是整个优先队列中最大的(或最小的)元素。
优先队列默认使用vector作为底层存储数据的容器，在vector上使用了堆算法将vector中的元素构造成堆的结构，所以其实我们就可以把它当作堆，凡是需要用堆的位置，都可以考虑优先队列。(所以需要先学习堆)
[2]优先队列性质
priority_queue默认使用vector作为底层容器。
默认情况下priority_queue是大堆。
2.priority_queue的参数理解(重要！！！)
(1)priority_queue的参数
priority_queue的模板参数很重要，因为这里有很多东西要用到，比如仿函数。当然这里只看一些常用的。
[1]priority_queue类模板参数
这是priority_queue类的模板参数列表，里面有三个参数：class T,class Container = vector<T>,class Compare = less<typename Container::value_type>
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> >
class priority_queue;
接下来将仔细阐述这三个参数是什么，很重要。
class T：T是优先队列中存储的元素的类型。
class Container = vector<T>：Container是优先队列底层使用的存储结构，可以看出来，默认采用vector。
class Compare = less<typename Container::value_type> ：Compar是定义优先队列中元素的比较方式的类。这个需要着重解释。Compare 后面跟着的这一串会在后面单独讲。
什么是优先队列中元素的比较方式？
之前也提到了，优先队列其实就是堆，堆中元素都是有固定大小关系的。比如大堆：每个结点的值都不大于它的双亲结点，堆顶元素是最大的。堆中会存储各种各样的元素，所以它们的比较方式自然不会相同，编译器中的比较类只能比较内置类型，所以自定义类的比较方式是需要用户自己给出的，并且需要手动填充到Compare 参数的位置。
[2]比较类的函数参数
class Compare = less<typename Container::value_type> ：Compare后面跟着的less<typename Container::value_type>就是默认的比较类，默认是按小于(less)的方式比较，这种比较方式创建出来的就是大堆。所以优先队列默认就是大堆。
如果需要创建大堆，就需要将less改为greater。
接下来看一下less类和greater类的函数参数。
template <class T>
struct less : binary_function <T,T,bool> {
bool operator() (const T& x, const T& y) const {return x<y;}
};
上面是less类的内部函数，less类的内部重载()，这也就是前面提到的仿函数，参数列表中有左右两个参数，左边小于右边的时候返回true，此时优先队列就是大堆。
template <class T>
struct greater : binary_function <T,T,bool> {
bool operator() (const T& x, const T& y) const {return x>y;}
};
上面是greater类的内部函数，greater类的内部重载()，这也就是前面提到的仿函数，参数列表中有左右两个参数，左边大于右边的时候返回true，此时优先队列就是小堆。
注意：less类和greater类只能比较内置类型的数据的大小，如果用户需要比较自定义类型的数据，就需要自己定义一个比较类，并且重载()。
同时less类和greater类也具有模板参数，因为他们也是模板，所以我们如果要存储自定义类型的元素，就要将自定义类型作为模板参数传递给less类和greater类。
[3]构造函数的参数列表
下面看一下priority_queue构造函数的参数列表：
priority_queue (const Compare& comp = Compare(), const Container& ctnr = Container());
构造函数中有两个参数，都具有默认值。这两个参数分别是Compare类和Container类的对象。
构造函数默认将vector的对象传入构造函数作为底层结构，将less的对象传入构造函数按小于的方式比较构造大堆。
3.priority_queue的使用
(1)常用函数介绍
| 函数说明 | 功能说明 |
| priority_queue(const Compare& comp = Compare(), const Container& ctnr = Container()); | 构造函数，当不传递参数时，括号内的参数就用默认值填充。 此时底层空间是vector，按大堆存储 |
| priority_queue(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Container& ctnr = Container()); | 区间构造函数 |
| push(const value_type& val) | 插入元素 |
| void pop() | 删除队头元素 |
| const value_type& top() const | 返回队头元素的引用(队头元素不可以修改，队头元素也就是堆顶元素) |
| bool empty() const | 判断队列是否是空 |
(2)priority_queue中存储内置类型元素
因为priority_queue是模板，所以创建对象时需要传入模板参数，但是由于模板参数内部是具有默认值的，所以创建大堆时可以只传递元素类型即可。但创建小堆的时候，模板参数是不可以省略的。
注意：队头元素是不可以修改的！因为top函数返回的const类型的引用。
其余的操作其实和堆就很相似了。
//插入内置类型数据
#include "iostream"
#include "queue"
using namespace std;
int main() {
//完整版按大堆创建对象
//priority_queue<int,vector<int>, less<int>> q;
//按小堆创建对象(按小堆创建时参数列表不可以省略)
//priority_queue<int,vector<int>, less<int>> q;
int arr[] = { 6,3,5 };
//简化版按大堆创建对象
//默认创建大堆
priority_queue<int> q(arr,arr+sizeof(arr)/sizeof(arr[0]));
//尾插
q.push(9);
q.push(1);
q.push(4);
//获取队头元素
//队头元素不可修改
int TOP = q.top();
//判空
cout << q.empty() << endl;
//获取队中元素个数
cout << q.size() << endl;
//队头元素出队列
q.pop();
}
(3)priority_queue中存储自定义类型元素
接下来看一下存放内置类型元素时的使用方法。上文也提到了，存放内置类型元素时，我们需要自己实现比较类，在比较类中重载()。
这里用来举例的依旧是多次出场的日期类。我们需要在日期类中重载<和>。这是为什么？
仔细回忆一下，之前是不是讲解了priority_queue类的模板参数，如果我们要往priority_queue中存储内置类型元素，我们在创建priority_queue对象时该怎么写？
看下面，存储日期类，自然要传入日期类。在构造函数中默认会传入比较类的对象，比较类的对象(仿函数)会调用重载()来比较两个元素的大小，此时日期类对象就会调用重载的<或>来进行比较。
//Date是日期类
priority_queue<Date, vector<Date>, less<Date>> q1;下面是存储自定义类型对象的详细使用方法。
#include "iostream"
#include "queue"
using namespace std;
class Date {
private:
int year;
int month;
int day;
public:
//构造函数
Date(int _year, int _month, int _day)
:year(_year)
, month(_month)
, day(_day)
{}
//重载<
//当this指向的对象小于d对象返回true
bool operator<(const Date& d) const {
if ((year < d.year) || (year == d.year && month < d.month) ||
(year == d.year && month == d.month && day < d.day)) {
return true;
}
else {
return false;
}
}
//重载>
//当this指向的对象大于d对象返回true
bool operator>(const Date& d) const {
if ((year > d.year) || (year == d.year && month > d.month) ||
(year == d.year && month == d.month && day > d.day)) {
return true;
}
else {
return false;
}
}
};
int main() {
Date d1(2021, 12, 12);
Date d2(2020, 12, 12);
Date d3(2022, 1, 1);
priority_queue<Date, vector<Date>, less<Date>> q1;
q1.push(d1);
q1.push(d2);
q1.push(d3);
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(d1);
q2.push(d2);
q2.push(d3);
}(4)priority_queue中存储自定义类型元素的地址
如果priority_queue中存储的日期类对象的地址，但我们的要求是，堆中依旧按照日期类对象的大小来比较，而不是按日期类对象的地址。
这个时候就需要我们自己来实现比较类了，因为默认提供的比较类不能满足我们的要求。因为默认的比较类按照的是传入的类型来比较，我们传入地址，它就按地址大小比较。而不是日期类对象的大小。
比较类的实现如下：
既然传入的参数是日期类对象的地址，那么我们可以先把地址解引用，然后进行比较，这样不就又调用到日期类中重载的<和>了吗。
class Less {
public:
bool operator()(const Date* left,const Date* right)const {
return *left < *right;
}
};
class Greater {
public:
bool operator()(const Date* left, const Date* right)const {
return *left > *right;
}
};用户自己实现比较类后，就可以进行使用了：
//自定义类型元素的地址
#include "iostream"
#include "queue"
using namespace std;
class Date {
private:
int year;
int month;
int day;
public:
Date(int _year, int _month, int _day)
:year(_year)
, month(_month)
, day(_day)
{}
bool operator<(const Date& d) const {
if ((year < d.year) || (year == d.year && month < d.month) ||
(year == d.year && month == d.month && day < d.day)) {
return true;
}
else {
return false;
}
}
bool operator>(const Date& d) const {
if ((year > d.year) || (year == d.year && month > d.month) ||
(year == d.year && month == d.month && day > d.day)) {
return true;
}
else {
return false;
}
}
};
class Less {
public:
bool operator()(const Date* left,const Date* right)const {
return *left < *right;
}
};
class Greater {
public:
bool operator()(const Date* left, const Date* right)const {
return *left > *right;
}
};
int main() {
Date d1(2021, 12, 12);
Date d2(2020, 12, 12);
Date d3(2022, 1, 1);
priority_queue<Date*, vector<Date*>, Less> q1;
q1.push(&d1);
q1.push(&d2);
q1.push(&d3);
priority_queue<Date*, vector<Date*>, Greater> q2;
q2.push(&d1);
q2.push(&d2);
q2.push(&d3);
}