C++ STL

C++ STL之map基本知识

STL基本是刚入队的时候讲的知识点，当时用的栈和队列比较多，map，vector，pair等用的较少，今天做题发现map一点也不会用了QAQ，赶紧复习一下，，，

Posted by zhangmh on 2021-11-22
Estimated Reading Time 7 Minutes
Words 1.7k In Total
Viewed Times

STL基本是刚入队的时候讲的知识点，当时用的栈和队列比较多，map，vector，pair等用的较少，今天做题发现map一点也不会用了QAQ，赶紧复习一下，，，

以题目为例：1058 人名查询 1185 统计数字 1321 众数

map：map是STL中的一个关联容器，它提供一对一（其中第一个（first）可以称为关键字key，每个关键字只能在map中出现一次，第二个（second）可能称为该关键字的值value）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。map为我们提供了一种数据之间的对应关系，并且这种关系支持快速的查找等操作，即通过键值快速地查找对应的值，也可以完成对键值的遍历等功能。

可以把map理解为 以任意数据类型为下标的超级数组。

注意：map传入的数据类型可以是string，double，int，bool，自定义的结构体等等。传入自定义结构体时，需用pair定义比较大小的方式，因map中数据有序，若不自定义比较大小的根据，系统会报错。

map数据结构存储、输出、查询较快，可提供O(logn)复杂度的过程。

在这两个map基础题中，主要复习map基本用法，即计数，在一般计数中，我们使用数组即可，但是当计数范围较大时，大概是超过1e6时，开数组计数会MLE，这时候我们就需要用map~

1321 众数

img点击并拖拽以移动

这个题数据范围较小，用数组大概也可以，但是我们在这里用map做。

下面AC代码~（map的用法和题目思想在代码中解释了）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int T,n,a;

int read()//快读 
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main()
{
//	freopen("test.in","r",stdin);
    map<int,int>mp;
    map<int,int>::iterator it;//迭代器，遍历map，在stl中常用，类比指针 
    scanf("%d",&T);
    while(T--)
    {
    	mp.clear();//注意初始化，栈、队列、数组在多组输入情况下均需初始化 
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a);
    		mp[a]++;//map可以类比数组用法 
		}
		int ans=0;//找众数 
		for(it=mp.begin();it!=mp.end();it++)//迭代器遍历 
		{
			if(it->second>ans)//second指关键字的值 
			ans=it->second;
		}
		int x=0;
		for(it=mp.begin();it!=mp.end();it++)
		{
			if(it->second==ans&&x==0)
			{
				cout<<it->first;//first指关键字，在这里指所计的数 
				x++;
			}
			else if(it->second==ans&&x!=0)
			cout<<' '<<it->first;
		}
		cout<<'\n';
		//上面这一段输出可以学习一下，怎样隔空格输出一行数，在普通for循环中同样适用 
	}
	return 0;
}

我们之所以可以直接把map中的数直接输出，是因为前面加粗黑字部分，数字存储在map中是有序的，输出时无需考虑排序问题。

注意：对于众数问题，若用数组方法做，本题每个数为0到1000，不存在负值问题，若数据范围中包含负值，则需要将每个数字加上偏移量，因为数组a[ ]中括号内为非负数。

1185 统计数字

这个题的数据范围就比较大了，用数组肯定是不行的，map做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int n,a;

int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main()
{
//	freopen("test.in","r",stdin);
    n=read();
    map<int,int>mp;
    map<int,int>::iterator it;
    for(int i=1;i<=n;i++)
    {
    	scanf("%d",&a);
    	mp[a]++;
	}
	for(it=mp.begin();it!=mp.end();it++)
	{
		cout<<it->first<<' '<<it->second<<'\n';
	}
	return 0;
}

1058 人名查询

我们已知map中有两个参量，在这个题中使用的是string和int。因为我们将map视为可以将任何类型定义为下标的超级数组，故做法同int型。下面AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1000005;
int n,m; 
string s[N];
string cur;

int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main()
{
//	freopen("test.in","r",stdin);
    n=read();
    m=read();
    map<string,bool>vis;
    for(int i=1;i<=n;i++)
    {
    	cin>>s[i];
    	vis[s[i]]=true;//边输入边更新 
	}
	while(m--)
	{
		cin>>cur;
		if(vis[cur]) //O（lgn）查询 
	    cout<<"YES\n";
	    else
	    cout<<"NO\n";
	}
	return 0;
}

思考：

在某些情况下map可以简化问题，或者减少时间复杂度，但是某些情况下反而会使空间复杂度不那么优化，这需要我们自己判断。oj上有个题我也是用map做的，放出来链接供大家试试手~ 1278 GXC捡宝石

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
C++ STL
FRIENDS
ESC