知识点

map 是有序键值对容器（自动按照键排序），它的元素的键是唯一的。搜索、移除和插入操作均拥有对数复杂度。可以把map理解成高级的桶数组，桶数组只能实现 int --> int 的映射，map则不受限制。

创建一个map：

map<类型, 类型> 名字;

比如要存储学生的名字和对应成绩，可以创建map<string, int> score;

map的常用操作方法：

map<int,int> mp;
mp[3] = 5; // 通过赋值创建一个键值对映射
mp[4] = 2;
mp[2] = 7;
mp.erase(4); // 删除{4，2}这个键值对
cout << mp.count(2); // 输出1，表示2这个键存在
cout << mp.count(5); // 输出0，表示5这个键不存在

// 枚举型遍历访问map的所有键值对
for (auto it : mp) 
{
  cout << it.first << " " << it.second << endl;
}

unordered_map 【哈希表】的基础用法和map一样，只不过它不会自动排序，所以访问速度更快。

练习：使用map完成下面的题目

某次科研调查时得到了$n$个自然数，每个数均不超过1500000000（1.5*10⁹）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入格式

第一行是整数n，表示自然数的个数，接下来每行一个自然数。

输出格式

包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例

8
2
4
2
4
5
100
2
100

2 3
4 2
5 1
100 2