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
技巧：有的时候可以定义一个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
CODE：
#includeusing 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; }
银行系统 题目描述 某银行有一个系统，银行的每个客户端都由一个正整数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
CODE：
#includeusing 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 ("0n") ; continue ; } map < int , int > :: iterator it ; if (cmd == 2) { it = dict.end () ; it -- ; }else { it = dict.begin () ; } printf ("%dn" , it -> second) ; dict.erase (it) ; } } return 0; }
