admin管理员组文章数量:1623787
【算法分析】
一、pair
pair将两个数据(经常为不同数据类型)组合成一组数据。
pair的实现是一个结构体,主要的两个成员变量是first、second。
pair的常见构造方法如下:
1.pair<T1, T2> p1;
创建一个空的pair对象,它的两个元素分别是T1和T2类型,然后赋值初始化。实例如下:
#include<bits/stdc++.h>
using namespace std;
int main() {
pair<int,double> p1;
p1.first=1;
p1.second=2.5;
cout<<p1.first<<" "<<p1.second<<endl;
return 0;
}
输出为:1 2.5
2.pair<T1, T2> p1(v1, v2);
创建一个pair对象,它的两个元素分别是T1和T2类型,其中first成员初始化为v1,second成员初始化为v2。实例如下:
#include<bits/stdc++.h>
using namespace std;
int main() {
pair<string, double> p2("Algorithm", 56.8);
cout<<p2.first<<" "<<p2.second<<endl;
return 0;
}
输出为:Algorithm 56.8
3.make_pair(v1, v2);
以v1和v2的值创建一个新的pair对象,其元素类型分别是v1和v2的类型。实例如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
int age=8;
string name="James";
pair<int,string> p3;
p3=make_pair(age,name);
cout<<p3.first<<" "<<p3.second<<endl;
return 0;
}
输出为:8 James
二、优先队列priority_queue
优先队列priority_queue,本质上是用堆实现的,可用于实现“堆优化的Dijkstra算法”。
1.基本语法
·升序队列,小根堆:priority_queue <int,vector<int>,greater<int> > p;
·降序队列,大根堆:priority_queue <int,vector<int>,less<int> >q;
·对于基础数据类型,默认是大顶堆:priority_queue<int> r; //等同于 priority_queue<int, vector<int>, less<int> > r;
2.基本操作
优先队列priority_queue和队列基本操作相同:
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容
优先队列priority_queue的常见实现如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
priority_queue<int> a;
priority_queue<int,vector<int>,greater<int> > b;
priority_queue<string> c;
for (int i=0;i<5;i++){
a.push(i);
b.push(i);
}
while (!a.empty()){
cout<<a.top()<<" ";
a.pop();
}
cout<<endl;
while(!b.empty()){
cout<<b.top()<<" ";
b.pop();
}
cout<<endl;
c.push("abc");
c.push("abcd");
c.push("cbd");
while (!c.empty()){
cout<<c.top()<<" ";
c.pop();
}
cout<<endl;
return 0;
}
输出为:
4 3 2 1 0
0 1 2 3 4
cbd abcd abc
【程序代码】
#include<bits/stdc++.h>
using namespace std;
int main() {
priority_queue<pair<int, int> > a;
pair<int,int> b(1,5);
pair<int,int> d(1,2);
pair<int,int> c(6,1);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty()) {
cout<<a.top().first<<" "<<a.top().second<<endl;
a.pop();
}
return 0;
}
【程序输出】
pair的比较规则:先比较第一个元素,第一个相等比较第二个。
6 1
1 5
1 2
【参考文献】
https://blog.csdn/sevenjoin/article/details/81937695
https://wwwblogs/huashanqingzhu/p/11040390.html
https://www.sohu/a/256022793_478315
本文标签: 队列例子元素pairpriorityqueue
版权声明:本文标题:用pair做优先队列priority_queue元素的例子 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728896783a1178514.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论