bsp;
6.4 priority_queue内元素优先级的设置
1.基本数据类型的优先级设置
基本数据类型指int、double、char型等数据类型。
下面两种优先队列的定义是等价的。
priority_queue<int> q;
priority_queue<int,vector<int>,less<int> > q;
vector<int> 是来承载底层数据结构堆(heap)的容器,而less<int>是比较类。
less<int> 表示数字大的优先级越大,而greater<int>表示数字小的优先级越大。char类型按字典序。
2.结构体的优先级设置
需要重载比较符号。
例如:
struct fruit{
string name;
int price;
friend bool operator<(fruit f1,fruit f2){
return f1.price<f2.price;
}
};
判断f1==f2,则相当于!(f1<f2)&&!(f2<f1)。
所以 priority_queue<fruit> q; 内部以价格高的水果优先级高。
同理,如果想以价格低的水果为优先级高,那么把<改成>。
struct fruit{
string name;
int price;
friend bool operator<(fruit f1,fruit f2){
return f1.price>f2.price;
}
};
注:只能重载<,重载>会编译错误。
不用greater<typename>,不重载<,不用friend函数
用cmp。
#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct fruit{
string name;
int price;
}f1,f2,f3;
struct cmp{
bool operator () (fruit f1,fruit f2){
return f1.price>f2.price;
}
};
int main()
{
priority_queue<fruit,vector<fruit>,cmp> q;
f1.name="a";
f1.price=3;
f2.name="b";
f2.price=2;
f3.name="c";
f3.price=1;
q.push(f1);
q.push(f2);
q.push(f3);
cout<<q.top().name<<" "<<q.top().price;
return 0;
}
结果: c 1
即便是基本数据类型或其他STL容器(如set),也可以用同样的方式定义优先级。如果结构体内数据较庞大,前面加const & 引用来提高效率。
friend bool operator<(const & fruit f1,const & fruit f2){
return f1.price>f2.price;
}
struct cmp{
bool operator () (const & fruit f1,const & fruit f2){
return f1.price>f2.price;
}
};
priority_queue的本质是堆。
7.stack
栈,一个后进先出的容器。
头文件
#include<stack>
7.1stack的定义
stack<typename> name;
7.2stack容器内元素的访问
由于栈是一种后进先出的数据结构,所以只能用top()来访问栈顶元素。
st.top();
7.3 stack常用函数
(1)push()
st.push(x)将x入栈
(2)top()
st.top()访问栈顶元素。
(3)pop()
st.pop()删除栈顶元素。
(4)empty()
st.empty()检测是否为空,为空返回true,否则返回false。
(5)size()
st.size()返回栈中元素的个数。
8.pair
当想要将两个元素绑在一起作为一个合成元素,又不想定义结构体时,可以使用pair。
头文件
#include<utility>
map实现用了pair,所以#include<map>包含#include<utility>,用map不需要再包含utility头文件。
pair 相当于
struct pair{
typeName1 first;
typeName2 second;
};
8.1 pair的定义
pair<typeName1,typeName2> name;
例如:
pair<string ,int> p;
初始化:
pair<string ,int> p(“haha”,5);
pair<string,int> p=make_pair(“haha”,5);
8.2 pair中元素的访问
用p.first和p.second访问。
8.3 pair常用函数
(1)比较操作数,pair可以直接使用==,!=,<,<=,>,>=比较大 小。
比较规则是先以first的大小作为标准,只有当first相等时才 去比较second的大小。
8.4 pair常见用途
例如:
#include<iostream>
#include<map>
using namespace std;
int main(){
map<string,int>mp;
mp.insert(make_pair("heihei",5));
mp.insert(pair<string,int>("haha",10));
//auto it ==map<string,int>::iterator it
for(auto it = mp.begin();it!=mp.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
}
9.algorithm头文件
(1)max() /min()/