C++ 优先队列 priority_queue 使用篇-Toy模板网

这篇具有很好参考价值的文章主要介绍了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>, greater<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;
	}
};

用户自己实现比较类后，就可以进行使用了：文章来源地址https://www.toymoban.com/news/detail-839053.html

//自定义类型元素的地址
#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);
}

到了这里，关于C++ 优先队列 priority_queue 使用篇的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！