Dev.C++STL好之映射map:map可以作为一个工具使用,也可以作为一个主考点。
今天我们来讲一个特殊的容器:map。他的基本形式是
map<typename,typename>name
他的意思是将第一个类型映射到第二个类型中。这句话可能有点迷,下面我们来举个栗子。
————CSP比赛成绩出来了!你记得你的考号吗?
————记得,是123456(信口瞎编)
————下面发布一下成绩(重点)
......
123454 125分
123455 215分
123456 0分
......
这里可以理解为下面一段代码
...
int a[600600];
...
a[123454]=125;
a[123455]=215;
a[123456]=0;
...
//事实上可以拿循环打
这是最正常的数组对吧,以有迹可循的考号作为下标。然鹅......(剧情重演)
————CSP比赛成绩出来了!你记得你的考号吗?
————呜呜呜不记得了!!!
(全剧终)
(接上)
————名字记得吗?
————肯定记得呀!
————我们刚刚看了riced的博客,启用了map......(你们当做没看到就好了)
什么意思?假设这个人叫riced,那么有以下程序
int a[name];
...
a[riced]=0;
...
读入名字,以名字为下标,这就是我们传说中的映射map!
对于map,我不做过多解释,这里引用一段oi-wiki的话
你可能需要存储一些键值对,例如存储学生姓名对应的分数: Tom 0 , Bob 100 , Alan 100 。但是由于数组下标只能为非负整数,所以无法用姓名作为下标来存储,这个时候最简单的办法就是使用 STL 中的 map 了!
map 重载了 operator[] ,可以用任意定义了 operator < 的类型作为下标(在 map 中叫做 key ,也就是索引):
map<Key, T> yourMap;
其中, Key 是键的类型, T 是值的类型,下面是使用 map 的实例:
map<string, int> mp;
map应用
map有两种应用,这里举两个例子。
map<string,int>mp1;
map<int,int>mp2;
对于第一种,就是单纯的映射运用。而第二种(就是Key为int的时候),可以理解为数组下标离散化防止爆空间和CE。好了,你学会了吗?
禁止下滑
禁止下滑
事不过三
为什么今天打一个map呢?今天我遇到了一道题。
题目描述
数组是一个以下标来储存一些信息的一种数据结构,方便起见,本题中,我们认为,数组是一个以整数为下标来储存整数的数据结构。
现在 Cuber QQ 需要进行一些简单的数组读写操作。
简而言之, Cuber QQ 的任务有两种:
在下标为 XX 的位置存入数字 YY
输出下标为 XX 的位置存放的数字,若 XX 处没有数字,则输出 00
你能帮 Cuber QQ 解决这个问题吗?
数据范围
对于所有数据,保证 1 ≤ OPT ≤ 2 , X ≤ M,Y ≤ (10^9) .
众所周知,int a[1e9]铁定会爆,于是我打了一发我自己也不知道是什么的东西
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt=0;
struct line
{
long long to,a,ln;
}l[100100];
void add(int num,int line)
{
l[++cnt].a=num;
l[cnt-1].to=cnt;
l[cnt].ln = line;
}
int main()
{
scanf("%d%d",&n,&m);
while(n--)
{
int opt,x,y;
scanf("%d%d",&opt,&x);
if(opt==2)
{
bool flag=false;
for(int i=1;i<=cnt;i++)
{
if(l[i].ln == x)
{
flag=true;
printf("%lld
",l[i].a);
break;
}
}
if(flag==false)printf("0
");
}
else
{
scanf("%d",&y);
bool flag=false;
for(int i=1;i<=cnt;i++)
{
if(y==l[i].ln)
{
flag=true;
l[i].a = x;
break;
}
}
if(flag==false)add(y,x);
}
}
}
然鹅,讲完题之后,我知道了一个主考点(以前讲过):map。于是我就懂了map到底是什么,换句话说我就更深层次的了解了map。