问题标题: 酷町堂：STL-map

谢谢

以下内容部分参考网上文章，敬请谅解。

map是STL的一个关联容器，它提供一对一的数据处理能力（有序键值对），第一个元素称为关键字，第二个称为关键字的值，其中关键字是唯一的。map内部自建一颗红黑树（一 种非严格意义上的平衡二叉树），这颗树具有对数据自动排序的功能。

1、map简介

map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。

对于迭代器来说，可以修改实值，而不能修改key。

2、map的功能

自动建立Key－value的对应。key 和 value可以是任意你需要的类型。

根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。

3、使用map

使用map得包含map类所在的头文件

#include <map>  //注意，STL头文件没有扩展名.h

4、map的格式

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

5、map的构造函数

map共提供了6个构造函数，这块涉及到内存分配器的一些东西，这里略过。我们通常用如下方法构造一个map：

map<int, string> maps;

6、map的一些函数

函数名功能maps.insert()或maps["key"]=value插入maps.find()查找一个元素maps.clear()清空maps.erase()删除一个元素maps.size()长度maps.begin()返回指向map头部的迭代器maps.end()返回指向map末尾的迭代器maps.rbegin()返回一个指向map尾部的逆向迭代器maps.rend()返回一个指向map头部的逆向迭代器maps.empty()如果map为空则返回trueswap()交换两个map

• map的插入（map内部是自动排序号的，单词则按字母序排序）

maps.insert(pair<int,string>(1, "one")); 
maps[1] = "one";  

• map的遍历

//迭代，根据key排序的，我的key是string，故是字典序排序，从a-z
map< string,int>::iterator iter;
for(iter = maps.begin(); iter != maps.end(); iter++)
    cout<< iter->first << ' ' << iter->second << endl;//输出的是key value值
//数组形式的遍历
int nSize = maps.size();    
for(int index = 0; index < nSize; index++)  
    cout << maps[index] << endl; 

• map的删除

iterator erase（iterator it);//通过一个条目对象删除
iterator erase（iterator first，iterator last）//删除一个范围
size_type erase(const Key&key);//通过关键字删除

• map的查找

map<int, string>::iterator iter = maps.find(1);  
if(iter != mapStudent.end())  
    cout<< "Find, the value is " << iter->second << endl;  

下面给大家一道STL的map练习的小例题

题目描述

在一个网络系统中有 N 个用户、 M 次上网记录。每个用户可以自己注册一个用户名，每个用户名只包含小写字母且长度小于 1000 的字符串，每次上网日志里都会有记录，现在请统计每个用户每次浏览了多少个网页。

输入

第 1 行包含两个正整数 NN (1≤N≤1000) 和 MM (1≤M≤5000)。

第 2 ~ M+1 行，每行包含 2 个字符串，分别表示用户名和浏览的网页名。

输出

共 NN 行，每行的第一个字符串时用户名，接下来的若干字符串是这个用户依次浏览的网页名(之间用一个空格隔开)。按照用户名出现的次序排序输出。

样例输入

5 7
goodstudyer bookshopa
likespacea spaceweb
goodstudyer bookshopb
likespaceb spaceweb
likespacec spaceweb
likespacea juiceshop
gameplayer gameweb

样例输出

goodstudyer bookshopa bookshopb
likespacea spaceweb juiceshop
likespaceb spaceweb
likespacec spaceweb
gameplayer gameweb

数据规模与约定

时间限制：1 s

内存限制：256 M