【C++STL详解(九)】--------priority_queue介绍与使用

admin管理员组

文章数量:1624327

目录

前言

一、整体介绍

二、参数的介绍

1.底层容器

2.仿函数

三、使用

Ⅰ、定义方式

Ⅱ、接口

---

前言

前面介绍了两个容器适配器stack，queue，接下来再来看看一个适配器-----priority_queue，也叫做优先级队列！实际还是队列，使用时要包含头文件queue！

一、整体介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

2.此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

 3.优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4.底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。 容器应该可以通过随机访问迭代器访问(支持迭代器)，并支持以下操作：即可作为底层容器！

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

 6.需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。

注意：它可以使用迭代器了，和前面的两个容器适配器不同！

二、参数的介绍

1.底层容器

不难看出它的底层容器实际上是vector，但是呢在vector上又使用了堆算法将vector中元素构造成 堆的结构，因此priority_queue就是堆所有需要用到堆的位置，都可以考虑使用priority_queue。注意： 默认情况下priority_queue是大堆。也就是大的优先级大，会先出队列，结果默认就是降序！

2.仿函数

什么叫仿函数？

这个实际上是一个类，它实例化出来的对象可以像函数那样使用，因此称之为仿函数或者叫做函数对象！！此外，该类里面就重载了一个operator()! ！！

实际上，只要一个类重载了operator()，他就可以叫做仿函数！！！

上代码演示一下：

#include <iostream>
using namespace std;

//仿函数
class Less
{
public:
	bool operator()(const int& x, const int& y)
	{
		return x < y;
	}
};


int main()
{
	Less lecmp;
	cout << lecmp(1, 2) << endl;
	return 0;
}

上面代码的功能就是比较两个数的大小！如果单看下面这条语句，是不是很像函数调用？

cout << lecmp(1, 2) << endl;

实际上完整是这样的：

cout << lecmp.operator()(1, 2) << endl;

而优先级队列的第三个参数就是仿函数，只不过是一个模板类，它的底层就是类似上面的功能，可以控制比较的逻辑！

//第三个参数的底层
template<class T>
class less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

三、使用

Ⅰ、定义方式

priority_queue<int> q1;//默认底层容器vector,仿函数为less，默认大堆存储，输出结果降序！

priority_queue<int，vector<int>,greater<int>> q2;
//规定底层容器：vector，仿函数：greater，小堆存储，输出结果为升序

priority_queue<int，deque<int>,greater<int>> q3;
//规定底层容器：deque，仿函数：greater，小堆存储，输出结果为升序

注意：要用自定义的仿函数需要连底层容器也给出，因为需要参数对应！

Ⅱ、接口

它还是个队列，常用接口和queue类似：

empty()	判断队列是否为空
size()	获取有效数据个数
top()	返回优先级队列中最大(最小)元素的的引用，即堆顶元素
push()	元素入队列
pop()	删除优先级队列中最大(或者最小)的元素

使用示例：

①大堆存储

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	priority_queue<int> q;
	for (int i = 0; i <= 9; i++)
	{
		q.push(i);
	}

	cout << q.empty() << endl;
	cout << q.size() << endl;

	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	return 0;
}

默认大堆存储，输出降序结果！！！

②小堆存储

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	priority_queue<int,vector<int>,greater<int>> q;
	for (int i = 0; i <= 9; i++)
	{
		q.push(i);
	}

	cout << q.empty() << endl;
	cout << q.size() << endl;

	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	return 0;
}

小堆，升序结果

注意：greater库里本来就有的仿函数，但是不是优先级队列的默认仿函数！！！

---

好了，今天的内容就分享到这里，觉得有所收获，一健三连！！！

本文标签： 详解stlpriorityqueue