admin管理员组文章数量:1623784
STL其他内容解析:关于C++中STL的理解和应用
首先要知道,队列和优先队列都是容器适配器,即在已有的容器之上封装而成。
关于容器适配器:C++ STL中的容器适配器详解
队列queue
队列queue是一种先进先出的数据结构,并且添加元素只能添加在尾部,删除元素只能删除首元素。
常用操作:
q.push(x); //入队:将x压入队列的末端
q.pop(); //出队:弹出队列的队首元素,不返回任何值
q.front(); //返回队首元素
q.back(); //返回队尾元素
q.empty(); //判断队列是否为空
q.size(); //返回队列的元素个数
底层实现:deque
在STL中队列queue的默认容器是双端队列 deque,也可以使用 list 自定义队列,但是vector不行,因为vector不能提供删除第一个元素这个操作。
优先队列priority_queue
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先出队的行为特征。
优先队列实现了类似堆的功能(其实底层就是用堆实现的)。
常用操作:
q.push(x); //入队
q.pop(); //出队
q.top(); //返回队内优先级最高的元素
q.empty(); //判断队列是否为空
q.size(); //返回队列的元素个数
自定义优先队列:
STL默认使用 < 操作符来确定对象之间的优先级关系(也就是从大到小排序,默认大根堆)。
priority_queue<int> q; //默认大根堆
小根堆:
priority_queue<int,vector<int>,greater<int>> q; //自定义小根堆
其中,第一个参数为数据类型,第二个参数为容器类型。第三个参数为比较函数。
结构体:需要重载运算符<
# include<iostream>
#include<queue>
using namespace std;
struct orz{
int sum;
int x,y;
};
priority_queue<orz> q;
operator <(orz a,orz b){
return a.sum>b.sum;
}
int main(){
for (int i=1; i<=10; i++){
orz p;
p.x=i;
p.y=i;
p.sum=i;
q.push(p);
}
while (q.size()!=0){
orz p=q.top();
cout<<p.sum<<endl;
q.pop();
}
return 0;
}
更常用的写法:对结构体排序
friend bool operator
struct Edge {
int u;
int v;
int w;
friend bool operator <(const Edge &x, const Edge &y)
{
return x.w > y.w;
}
};
Edge t[1000005];
priority_queue<Edge> q;
底层实现:
优先队列的底层是用堆实现的。
在优先队列中默认存放数据的容器是vector,在声明时也可以用deque(双向队列)
本文标签: 队列底层stlpriorityqueueQueue
版权声明:本文标题:C++ STL队列queue和优先队列priority_queue的底层实现和用法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728897351a1178580.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论