欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++标准模板库(STL)(二)

程序员文章站 2022-07-12 17:59:24
...

map(映射)

头文件

#include<map>
using namespace std;

定义

//map可以将任何基本类型映射到任何基本类型	
//<>内第一个是键的类型,第二个为值的类型 
	map<typename1,typename2> mp;
//如果是字符串到整形的映射,必须用string而不是char数组,因为char数组作为数组,是不能当作键值的 
	map<string,int> mp;

访问

//map中的键是唯一的
//通过下标访问
	map<char,int> mp;
	mp['c']=20;
	mp['c']=30;
	printf("%d\n",mp['c']); 

30

//map可以用it->first访问键,用it->second访问值
//map以键从小到大顺序自动排序
	map<char,int> mp;
	mp['m']=20;
	mp['r']=30;
	mp['a']=40;
	for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++){
		printf("%c %d\n",it->first,it->second);
	}

a 40
m 20
r 30

查找元素

//find(key)返回键为key的映射的迭代器
	map<char,int> mp;
	mp['m']=20;
	mp['r']=30;
	mp['a']=40;
	map<char,int>::iterator it=mp.find('m');
	printf("%c %d\n",it->first,it->second);

删除元素

	mp.erase(it);
	mp.erase(key);
	mp.erase(first,last);

pair

头文件

#include<utility>
#include<string>

添加map头文件会自动添加utility头文件,可以直接#include< map >
初始化,访问元素

#include<iostream>
#include<utility>
#include<string>
using namespace std;
int main(){
	pair<string,int> p("hehe",5);
	cout<<p.first<<" "<<p.second<<endl;
	p.first="haha";
	p.second=55;
	cout<<p.first<<" "<<p.second<<endl;
	p=make_pair("xixi",555);
	cout<<p.first<<" "<<p.second<<endl;
	p=pair<string,int>("heihei",5555);
	cout<<p.first<<" "<<p.second<<endl;
	return 0;
}

hehe 5
haha 55
xixi 555
heihei 5555

比较操作数
比较规则为先以first大小为标准,first相等时再判别second大小

	pair<int,int> p1(5,10);
	pair<int,int> p2(5,15);
	pair<int,int> p3(10,5);
	if(p1<p2)
		printf("p1<p2\n");
	if(p2<p3)
		printf("p2<p3\n"); 

p1<p2
p2<p3

作为map键值对其进行插入

#include<iostream>
#include<map>
using namespace std;
int main(){
	map<string,int> mp;
	pair<string,int> p("hehe",5);
	mp.insert(p);
	mp.insert(pair<string,int>("haha",55));
	mp.insert(make_pair("heihei",555));
	for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
		cout<<it->first<<" "<<it->second<<endl;
	}
	return 0;
}

hehe 5
haha 55
heihei 555


queue(队列)

头文件

#include<queue>
using namespace std;

定义

	queue<typename> name;

出入队列

	queue<int> q;
	q.push(x);
	x=q.pop();

访问元素

//队列是限制性数据结构,只能访问队头和队尾元素
	x=q.front();
	x=q.back();

判空

//使用pop(),front()函数前,必须用empty()判断队列是否为空
	if(!q.empty()){
		q.pop();
	}

priority_queue(优先队列)

底层是用堆实现的,队首元素一定是当前队列中优先级最高的那个。

#include<stdio.h>
#include<queue>
using namespace std;

int main(){
//只能通过top()访问队首元素 
//使用top()函数时必须用empty()函数判空
	priority_queue<int> q;
	q.push(3);
	q.push(4);
	q.push(4);
	q.push(1);
	printf("%d\n",q.top());
	q.pop();
	printf("%d\n",q.top());
	return 0;
}

4
4

元素优先级设置 基本数据类型

基本数据类型默认数字大的优先级高,下面两种写法等价

	priority_queue<int> q;
	priority_queue<int,vector<int>,less<int> > q;

其中第二个参数vector< int >表示承载底层数据结构堆的容器,
第三个参数是对第一个参数的比较类,less< int>表示数字大的优先级大,greater< int>表示数字小的优先级大

#include<stdio.h>
#include<queue>
using namespace std;

int main(){
	priority_queue<int,vector<int>,greater<int> > q;
	q.push(3);
	q.push(4);
	q.push(1);
	printf("%d\n",q.top());
	return 0;
}

1

元素优先级设置 结构体类型
在结构体中添加一个函数,将小于号重载
重载大于号会导致编译错误

#include<iostream>
#include<queue>
#include<string>
using namespace std;

struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2){
		return f1.price<f2.price;
	}
};

int main(){
	fruit f1,f2,f3;
	f1.name="桃子";
	f1.price=3;
	f2.name="梨子";
	f2.price=4;
	f3.name="苹果";
	f3.price=1;
	priority_queue<fruit> q;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	cout<<q.top().name<<" "<<q.top().price<<endl;
	return 0;
}

梨子 4

若将小于号重载为大于号

struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2){
		return f1.price>f2.price;
	}
};

苹果 1

若要将该函数写在结构体外面,需用基本数据类型的方式来定义优先队列

#include<iostream>
#include<string>
#include<queue>
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="桃子";
	f1.price=3;
	f2.name="梨子";
	f2.price=4;
	f3.name="苹果";
	f3.price=1;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	cout<<q.top().name<<" "<<q.top().price<<endl; 
	return 0;
}

苹果 1

若结构体内数据比较庞大,可使用引用来提高效率

struct cmp{
	bool operator () (const fruit& f1,const fruit& f2){
		return f1.price<f2.price;
	}
};
	friend bool operator < (const fruit& f1,const fruit&f2){
		return f1.price<f2.price;
	}

stack(栈)

#include<stdio.h>
#include<stack>
using namespace std;
int main(){
	stack<int> st;
	for(int i=1;i<=5;i++){
		st.push(i);
	}
	st.pop();
	if(!st.empty()){
		printf("%d\n",st.top());
	}
	return 0;
}

4

相关标签: 算法笔记