1.5　map、multimap（映射、多重映射）

map是映射，multimap是多重映射。映射的键和值可以是不同的类型，键是唯一的，每个键都对应一个值。多重映射与映射类似，只是允许一个键对应多个值。映射可被当作散列表使用，它建立了从键到值的映射关系。映射是键和值的一一映射，多重映射是键和值的一对多映射。用map或multimap时，需要引入头文件#include＜map＞。

映射的迭代器和集合类似，支持双向访问，不支持随机访问，执行一次“++”和“--”操作的时间复杂度均为O（logn）。默认的元素排序方式为升序排序，也可以通过模板的第3个参数设置为降序排序。

上述映射模板的第1个参数为键的类型，第2个参数为值的类型，第3个是可选参数，用于对键进行排序的比较函数或对象。

在映射中，键和值是一对数（二元组），可以用make_pair（）生成一对数。

输出时，可以分别输出第1个元素（键）和第2个元素（值）。

map、multimap的成员函数如下。

·　size（）、empty（）、clear（）：返回元素数量、判断是否为空、清空。

·　begin（）、end（）：返回开始位置、返回结束位置。

·　insert（x）：将x插入映射（x为二元组）。

·　erase（x）：删除所有等于x的元素（x为二元组）。

·　erase（it）：删除it指向的元素（it为指向二元组的迭代器）。

·　find（k）：查找键为k的二元组的位置，若不存在，则返回尾指针。

可以通过“［］”操作符直接得到键映射的值，也可以通过赋值操作改变键映射的值，例如“mp［key］=val”表示将映射mp中key对应的值改为val。

例如，可以用map统计字符串的出现次数。

注意　若查找的key不存在，则执行mp［key］后会自动新建一个二元组（key，0）并返回0，进行多次查找后有可能包含很多无用的二元组。因此进行查找时最好先查询key是否存在。

多重映射的一个键可以对应多个值。由于是一对多的映射关系，所以对multimap不使用“［］”操作符。

例如，可以添加多个关于X和Y的数据：

输出所有关于X的数据：