admin管理员组文章数量:1624331
目录
前言
一、整体介绍
二、参数的介绍
1.底层容器
2.仿函数
三、使用
Ⅰ、定义方式
Ⅱ、接口
前言
前面介绍了两个容器适配器stack,queue,接下来再来看看一个适配器-----priority_queue,也叫做优先级队列!实际还是队列,使用时要包含头文件queue!
一、整体介绍
1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
2.此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3.优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
4.底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。 容器应该可以通过随机访问迭代器访问(支持迭代器),并支持以下操作:即可作为底层容器!标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
- empty():检测容器是否为空
- size():返回容器中有效元素个数
- front():返回容器中第一个元素的引用
- push_back():在容器尾部插入元素
- pop_back():删除容器尾部元素
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
版权声明:本文标题:【C++STL详解(九)】--------priority_queue介绍与使用 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728895387a1178340.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论