【c++入门（2）】关联容器map

一、map简介

map是一个关键字-值（key - value）的集合，就是可以通过key而找到value的一种关联数组。我们称这样的数据结构为：从key到value的映射，把key映射成value。

头文件：#include < map >

二、map的定义和访问

map 定义：map < key类型 , value类型 > 容器名称 ;

map < string , string > m1 ;   //定义一个key和value都是string的空容器m1
map < string , int> m2 ; //定义一个key为string value为int的空容器m2，通常用于字符串的桶数组
map < int , int > m3 ; //定义一个key和value都是int的空容器m3

1
2
3
4

技巧：有的时候可以定义一个map < long long , long long > 来做一个大桶数组，这样就相当于定义了一个cnt[long long]的桶数组，用普通的数组是无法实现的。

map的访问方式：下标访问

map类似于数组可以下标访问，访问的下表和key必须是一种数据类型！
例：
修改：dic[key] = value ;
访问：dic[key] ;

三、迭代器

（1）定义方式：map < key类型 , value类型 > ::iterator 名称 ;
（2）相关函数
提醒⚠:迭代器不支持< > <= >= += -= + -等操作

map会按照key从小到大排序所以输出顺序可能和输入顺序不同。
注意：end（）返回的是尾元素后一个位置的迭代器，左闭右开。
可以通过迭代器来判断map容器mp是否为空：
if (mp.begin () == mp.end ()) empty ;

迭代器遍历：
能像这样吗？
肯定是不能，因为迭代器不支持<，正确代码：

迭代器的修改方法：
查询操作：

四、例题

反片语[Ananagrams,UVa156]
题目描述

字谜中，一组由相同的字母按照不同的顺序组成的不同的单词，比如：OPTS、SPOT、STOP、POTS、POST，这样的单词我们称之为“anagrams”，但是另外有一些词确不具有这样的属性，比如QUIZ，无论你怎么重排单词中的字母顺序，都不能得到另一个单词。这样的单词我们称之为"ananagrams"。

编写一个程序，读入字典中的一些单词，然后找出所有的相对"ananagrams"（该单词不能通过重排字母，得到输入文件中的另外一个单词）。注意单个字母的词，事实上都是ananagrams，因为单个字母的词不能被重排。输入文件的单词总数不超过1000个。
输入格式

输入文件包含多行，每行多个单词，每一行的总长度不超过80个字符。每个单词由最多20个大写或者小写字母组成，且不会跨行。单词和单词之间可能有一个或者多个空格，

注意，在判断是否是"anagrams"时，不区分大小写，比如tIeD’和 ‘EdiT’是anagrams。

当遇到单独的一行“#”时，表示输入结束。
输出格式

输出包含多行，输出输入文件中的ananagrams，一行一个单词，输出顺序按照字典序排序（所有大写字母在所有小写字母前面），且输出时保留输入文件中这个单词的大小写。
输入输出样列
输入样例1：

ladder came tape soon leader acme RIDE lone Dreis peat
 ScAlE orb eye Rides dealer NotE derail LaCeS drIed
noel dire Disk mace Rob dries
#

输出样例1：

Disk
NotE
derail
drIed
eye
ladder
soon
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

💯CODE：

#include <bits/stdc++.h>

using namespace std;

vector < string > words ;
map < string , int > dict ;
string slove (const string & s)
{
	string t = s ;
	for (int i = 0; i < t.size (); i++)
	{
		if (t[i] >= 'A' && t[i] <= 'Z') t[i] += ' ' ;
	}
	sort (t.begin () , t.end ()) ;
	return t ;
}

int main()
{


	string w ;
	while (cin >> w)
	{
		if (w == "#") break ;
		words.push_back (w) ;
		string s = slove (w) ;
		if (dict.count (s) == 0) dict[s] = 1 ;
		else dict[s] ++ ;
	}
	
	sort (words.begin () , words.end ()) ;
	for (int i = 0; i < words.size (); i++)
	{
		if (dict[slove (words[i])] == 1) cout << words[i] << endl ;
	}
	


    return 0;
}

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

银行系统
题目描述

某银行有一个系统，银行的每个客户端都由一个正整数K(K≤10^6)标识，在到达银行办理某些业务时，会收到一个正整数优先级P(P≤10^7)。
此系统在办理业务时会接收到以下类型的服务请求：
① 1 K P表示添加优先级为P的客户K到等待列表中
② 2 表示处理等待列表中优先级最高的客户的业务，然后将此客户从等待列表中删除
③ 3 表示处理等待列表中优先级最低的客户的业务，然后将此客户从等待列表中删除
④ 0 系统停止服务
你的任务是帮助系统的开发人员编写程序来实现这种服务请求。
输入格式

输入多条服务请求，只有输入的最后一行是0.
一个客户端可以有多次请求。

数据保证，每个请求的优先级各不不同。
输出格式

对于所有服务编号为2或3的服务请求，输出此客户的客户端标识符。如果当一个服务请求过来时，此时服务的等待列表为0，则输出0.
输入输出样列
输入样例1：

2
1 20 14
1 30 3
2
1 10 99
3
2
2
0

输出样例1：

0
20
30
10
0
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

💯CODE：

#include <bits/stdc++.h>

using namespace std;

map < int , int > dict ;

int cmd , k , p ;

int main()
{


	while (scanf ("%d" , & cmd) == 1 && cmd)
	{
		if (cmd == 1)
		{
			cin >> k >> p ;
			dict[p] = k ;
		}else
		{
			if (dict.empty ())
			{
				printf ("0\n") ;
				continue ;
			}
			map < int , int > :: iterator it ;
			if (cmd == 2)
			{
				it = dict.end () ;
				it -- ;
			}else
			{
				it = dict.begin () ;
			}
			printf ("%d\n" , it -> second) ;
			dict.erase (it) ;
		}
	}


    return 0;
}
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