admin管理员组文章数量:1624325
可以在优先级队列中自定义数据的优先级, 让优先级高的排在队列前面,优先出队。
优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的。
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容
用法:priority_queue<Type, Container, Functional>
Type为元素类型(分三种:基本,pair对象,自定义),Container为容器类型(默认是vector,还可以是deque,不可为list)
Functional:比较的方式,STL中提供了less(大的先出)和greater(小的先出),定义在 xfunctional 文件中
1、当存放基本数据类型
std::priority_queue s;
等价于
std:: priority_queue<int, vector, less > s;
表明:优先级队列中存放的是int型数据,优先级队列基于的容器是vector,出队原则是优先级高的出队。
2、当存放pair对象
存放基本数据类型,其实就是把优先级队列当成有序数组用。只有存放pair对象,才能体现优先级的作用。
用法如下:
#include<iostream>
#include<vector>
#include<queue>
#include<xfunctional>
int main()
{
typedef std::pair<int, int> Ty;
std::priority_queue<Ty> a;//等价于std::priority_queue<Ty,std::vector<Ty>,std::less<Ty> > a;
std::priority_queue<Ty,std::vector<Ty>,std::greater<Ty> > b;
a.emplace(std::make_pair(1, 100));
a.emplace(std::make_pair(2, 100));
b.emplace(std::make_pair(1, 100));
b.emplace(std::make_pair(2, 100));
std::cout << a.top().first<<std::endl;//优先级大的在队头
std::cout << b.top().first << std::endl;//优先级小的在队头
system("pause");
return 0;
}
3、存放自定义数据类型
优先级队列不同于map,可以存放自定义数据类型(map只能存放pair对象)。
所有我们可以在优先级队列中存放这样的数据类型:
key value1 value2 value3…
(这种数据类型想放到map中,就必须把后面的value做成一个结构体,使其符合pair模板)
要求自定义的数据类型里面要重载<或者写一个仿函数
struct tmp1 //运算符重载<
{
int x;
int y;
tmp1(int a,int b)
{
x = a;
y = b;
}
bool operator<(const tmp1& a) const
{
return x < a.x;
}
};
int main()
{
std::priority_queue<tmp1> a;//因为重载了<
a.emplace(1,100);
}
如果不在数据类型里定义仿函数,就要写仿函数
#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<xfunctional>
struct tmp1 //运算符重载<
{
int x;
int y;
tmp1() {}
tmp1(int a,int b)
{
x = a;
y = b;
}
};
struct myGreater {
bool operator() (tmp1 a, tmp1 b)
{
return a.x > b.x; //大顶堆
}
};
struct myLess {
bool operator() (tmp1 a, tmp1 b)
{
return a.x < b.x; //大顶堆
}
};
int main()
{
std::priority_queue<tmp1,std::vector<tmp1>,myLess> a;
std::priority_queue<tmp1,std::vector<tmp1>,myGreater> b;
a.emplace(1, 100);
a.emplace(2, 100);
b.emplace(1, 100);
b.emplace(2, 100);
std::cout << a.top().x<<std::endl;//优先级大的在队头
std::cout << b.top().x << std::endl;//优先级小的在队头
system("pause");
return 0;
}
本文标签: stdpriorityqueue
版权声明:本文标题:std::priority_queue 用法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728896237a1178445.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论