下载掌阅APP，畅读海量书库
立即打开
map的键和值可以是不同的类型，键是唯一的，每个键都对应一个值。multimap与map类似，只是允许一个键对应多个值。map可被当作哈希表使用，它建立了从键（关键字）到值的映射。map是键和值的一一映射，multimap是一对多映射。使用map或multimap时需要引入头文件#include<map>。
map的迭代器和set类似，支持双向访问，不支持随机访问，执行一次“++”和“--”操作的时间复杂度均为 O (log n )。默认的元素顺序为升序，也可以通过第3个模板参数设置为降序。
上述map模板的第1个参数为键的类型，第2个参数为值的类型，第3个参数可选，用于对键进行排序的比较函数或对象。
在map中，键和值是一对数，可以使用make_pair生成一对数(键,值)进行插入。
输出时，可以分别输出第1个元素（键）和第2个元素（值）。
成员函数如下。
● size/empty/clear：元素个数、判空、清空。
● begin/end：开始位置和结束位置。
● insert( x )：将元素 x 插入集合（ x 为二元组）。
● erase( x )：删除所有等于 x 的元素（ x 为二元组）。
● erase(it)：删除it指向的元素（it为指向二元组的迭代器）。
● find( k )：查找键为 k 的二元组的位置，若不存在，则返回尾指针。
可以通过“[ ]”操作符直接得到键映射的值，也可以通过赋值操作改变键映射的值，例如h[key]=val。是不是特别像哈希表？
例如，可以用map统计字符串出现的次数。
需要特别注意的是，如果查找的key不存在，则执行h[key]之后会自动新建一个二元组(key,0)并返回0，进行多次查找之后，有可能包含很多无用的二元组。因此使用查找时最好先查询key是否存在。
multimap和map类似，不同的是一个键可以对应多个值。由于是一对多的映射关系，multimap不能使用“[ ]”操作符。
例如，可以添加多个关于X国的数据：
输出所有关于X国的数据：
题目描述（POJ2418）： 某国有数百种硬木树种，该国自然资源部利用卫星成像技术编制了一份特定日期每棵树的物种清单。计算每个物种占所有种群的百分比。
输入： 输入包括每棵树的物种清单，每行一棵树。物种名称不超过30个字符，不超过10 000种，不超过1 000 000棵树。
输出： 按字母顺序输出植物种群中代表的每个物种的名称，然后是占所有种群的百分比，保留小数点后4位。
本题统计每个物种的数量，计算占所有种群的百分比。可以在排序后统计并输出结果，也可以利用map自带的排序功能轻松统计。
题目描述（POJ3481）： 银行的每个客户都有一个正整数标识 K ，到银行请求服务时将收到一个正整数优先级 P 。银行经理提议打破传统，有时为优先级最低的客户服务，而不是为优先级最高的客户服务。系统将收到以下类型的请求。
● 0：系统需要停止服务。
● 1 K P ：将客户 K 及其优先级 P 添加到等待列表中。
● 2：为优先级最高的客户提供服务，并将其从等待名单中删除。
● 3：为优先级最低的客户提供服务，并将其从等待名单中删除。
输入： 输入的每一行都包含一个请求，只有最后一行包含停止请求（代码0）。假设在列表中包含新客户的请求时（代码1），在列表中没有同一客户的其他请求或有相同的优先级。标识符 K 小于10 6 ，优先级 P 小于10 7 。客户可以多次到银行请求服务，并且每次都可以获得不同的优先级。
输出： 对于代码为2或3的每个请求，都单行输出所服务客户的标识。如果请求时等待列表为空，则输出0。
本题包括插入、删除优先级最大元素和删除优先级最小元素这3种操作。map本身按第1元素（键）有序，因此将优先级作为第1元素即可。
题目描述（HDU1263）： Joe经营着一家水果店，他想要一份水果销售情况明细表，这样就可以很容易掌握所有水果的销售情况了。
输入： 第1行输入正整数 N （0< N ≤10），表示有 N 组测试数据。每组测试数据的第1行都是一个整数 M （0< M ≤100），表示共有 M 次成功的交易。其后有 M 行数据，每行都表示一次交易，由水果名称（小写字母组成，长度不超过80）、水果产地（由小写字母组成，长度不超过80）和交易的水果数量（正整数，不超过100）组成。
输出： 对每组测试数据，都按照输出样例输出水果销售情况明细表。这份明细表包括所有水果的产地、名称和销售数量的信息。水果先按产地分类，产地按照字母顺序排列；同一产地的水果按照名称排序，名称按照字母顺序排序。每两组测试数据之间都有一个空行。最后一组测试数据之后没有空行。
本题统计水果销售情况（产地、名称和销售数量）。水果按产地分类，产地按照字母顺序排序；同一产地的水果按照名称排序，名称按照字母顺序排序。可以利用map的有序性和映射关系轻松解决。
（1）定义一个map，其第1元素（键）为产地，第2元素（值）也是一个map，记录名称和销售数量。“map<string,map<string,int> >mp;”中map里面的值也是一个map，相当于二维map，可以使用mp[place][name]对销售数量进行统计。
（2）根据输入信息，统计销售数量，mp[place][name]+=num。
（3）按顺序输出统计信息。
