前言:
STL是C++中的标准库之一,主要由迭代器,算法,容器,仿函数,内存配置器和配接器留部分组成,可以帮助程序员完成许多功能完善,形式多样的程序,而这在ACM竞赛中,STL也因此成为了AC利器
map与映射
其实,map就是一种映射,只不过相当灵活,他可以做到向Python中的字典一样,形成唯一的键值对,通过访问键,就能够完成对值的访问,当然我们再这里便不再深入的谈论Python的东西,如果有需要我以后会单独出一篇博文讲Python的数据类型
map的灵活之处就体现于他可以将一种数据类型,映射到另一种数据类型上去,就好比查字典一样,比如我们要查“language”这个单词,我们就只能去996页查找(我胡诌的,假设是在这页吧),而不能在233页查找,因此,language和996便有了一一对应的关系,这就是映射。
用map来表示,就可以写为:
map<string,int>dictionary;
当我们需要写入一对键值对的话,可以这样表示:
dictionary["language"]=996;
于是language=>996的键值对便被生成出来的,当我们访问“language”的时候,就会显示为:996
cout<<dictionary["language"]<<endl;
//输出:996
map的映射类型
map的一个厉害的地方就是在于他的映射对象十分灵活,可以是string-->int,也可以是string-->string,也可以是用struct
定义的结构类型,map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器),但是必须保证键和值得唯一性
我何时应该选择map
- 需要建立字符串和整数之间的映射
- 判断大整数或者其他类型整数是否存在,可以吧map当做布尔类型的数组使用(哈希表)
- 字符串与字符串之间的映射
map该如何使用呢
使用map,应该先引入map头文件< map >,同时要有using namespace std;
然后再通过map<string,int>dictionary;
来定义一个新的map
访问map的时候只能通过键或者迭代器访问,这点与Python不同
使用迭代器来访问map
通过迭代器来访问的话,要先做如下定义:
map<typename1,typename2>::iterator it;
这样便定义了一个新的迭代器 it,我们便可以通过迭代器来访问map了,
其中通过 it-->first 来访问键, it-->second 来访问值
map常见函数
函数 | 用法 |
---|---|
.size() | 用来获取映射的对数,时间复杂度为o(1) |
.clear() | 用来清空map,时间复杂度为o(n) |
.find(key) | 返回键为key的映射的迭代器,时间复杂度为o(log2 N),N为映射的对数 |
.erase() | 可以用来删除单个元素,也可以删除一个区间的所有函数,删除单个元素时可以用erase(it),it为要删除的映射的键,时间复杂度为o(log2 n),删除一个区间的所有元素用erase(first,last),first为去见的起始迭代器,last为区间的末尾迭代器的下一个地址,也就是左闭右开的区间[first,last),时间复杂度为o(last-first),例如,erase("indexx")可以删去indexx这个键及其映射 |
更多函数可以参考:
pair的定义和使用
pair是“二元结构体”的替代品,将两个元素捆绑在一起,节省编码时间,相当于以下定义:
struct pair{
typename1 first;
typename2 second;
}
使用pair的时候,一定记得要加头文件< utility > 和using namespace std;
因为map的内部实现中会涉及pair,所以用< map >也可以替代
pair有两个参数,分别对应first和second的数据类型,可以是基本数据类型或者容器:
//定义一个pair
pair <typename1,typename2> name;
//访问pair的第一个成员变量
name.first;
//访问pair的第二个成员变量
name.second;
此处一定要记得和map区分过来!!!
map的二维表示
1.map嵌套pair,二元结构体pair当map的键
//定义
map<pair<int,int>,int >vis;
pair 会自动将first从小到大排序,如果相同,则从大到小排序
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,y;
map<pair<ll,ll>,int>vis;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
vis[{x,y}]++;//结构体当下标
}
printf("\n正向遍历\n");
map<pair<ll,ll>,int>::iterator it;
for(it=vis.begin();it!=vis.end();it++)//正向遍历
printf("%lld %lld %d\n",it->first.first,it->first.second,it->second);
//输出x,y,{x,y}出现次数
//pair 访问用".", map访问用"->"
printf("反向遍历\n");
map<pair<ll,ll>,int>::reverse_iterator re_it;//注意反向遍历写的是reverse_iterator
for(re_it=vis.rbegin();re_it!=vis.rend();re_it++)//反向遍历
printf("%lld %lld %d\n",re_it->first.first,re_it->first.second,re_it->second);
//输出x,y,{x,y}出现次数
return 0;
}
/*
版权声明:本文为CSDN博主「nefu_ljw」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/ljw_study_in_CSDN/article/details/104355672
*/
2.map嵌套map,当俄罗斯套娃二维数组用
//定义
map<int,map<int,int> >vis;
示例:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,map<ll,int> >vis;
ll n,x,y;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
vis[x][y]++;
}
map<ll,map<ll,int> >::iterator i;
map<ll,int>::iterator j;
printf("\n正向遍历\n");
for(i=vis.begin();i!=vis.end();i++)
for(j=i->second.begin();j!=i->second.end();j++)
printf("%lld %lld %d\n",i->first,j->first,j->second);
map<ll,map<ll,int> >::reverse_iterator re_i;
printf("反向遍历\n");
for(re_i=vis.rbegin();re_i!=vis.rend();re_i++)//i需要倒序,j不需要
for(j=re_i->second.begin();j!=re_i->second.end();j++)
printf("%lld %lld %d\n",re_i->first,j->first,j->second);
return 0;
}
/*
版权声明:本文为CSDN博主「nefu_ljw」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/ljw_study_in_CSDN/article/details/104355672
*/
出处:https://grimoire.cn/algorithm/stl-map.html
版权:本文《STL的神奇容器之map》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任