C++ 优先队列 priority_queue 使用篇

priority_queue(优先队列)也是容器适配器,理解优先队列需要较多的铺垫知识:堆、仿函数。如果不了解的话需要先学习这两个知识点,很重要。

本文代码在win10系统下的vs2019验证。

1.储备知识 

(1)数据结构:堆

堆是以二叉树为基础的数据结构,分为大堆与小堆。但因为篇幅过长就不在这篇文章详细说了,有需要的可以看这篇文章:

(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);
}
经验分享 程序员 微信小程序 职场和发展