map是 stl 的一个关联容器,名叫“映射”，何为“映射”？其实就是一个数组，但有了数组何必还需映射，这是一个高深的问题。
目录
一、map 简介
1.空间复杂度
map 类似于 vector，可以随时创建新的“键”（类似下标），避免浪费过多空间，具体实现如下：
pair<iterator, bool> insert(_Pp&& __p)
{
return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));
}2.时间复杂度
map 使用了红黑树（一种自平衡二叉查找树），每次插入新的键和搜索时都只用 O(log size) 的时间复杂度，虽然数组只需 O(1) 的时间复杂度，但在空间方面数组极差。它与 vector 空间复杂度相同，但远优于 vector O(size) 的时间复杂度。具体实现在头文件 bits/stl_tree 中。
3.“键”的类型
map 键可以为任何类型，但必须具有小于比较模版或比较函数，在这一点上一个数组完全达不到。具体实现运用了类模板，如下：
template <class _Key, class _Tp, class _Compare = less<_Key>,
class _Allocator = allocator<pair<const _Key, _Tp> > >
二、 map 用法
1.声明
首先需要引用 “map” 头文件，如下：
#include <map>声明时和一般模版类的声明方式一样，先注明类型（即 map ）再填写模版，注意 map 的“键”和“值”的类型均需声明，最后为变量名。例如：
map <int,int> mp;2.新增“键”
由于 map 中兼容了中括号（“[”、“]”）所以可以像访问数组一样访问或创建，如下：
mp[2]=1;若只创建“键”而不赋值系统会默认为 0 ，例如：
mp[1];
cout << mp[1];输出：
0也可以使用 “insert” 函数，如下：
mp.insert(make_pair(1,1));“make_pair” 函数指生成一个 “pair” ，map 的实现中运用了 pair。
三、map 遍历
1.使用 “iterator”
“iterator” 中文名为“迭代器”，访问方式如下：
for(map <int,int>::iterator it = mp.begin();it != mp.end();++ it)
{
cout << it -> first << ' ' << it -> second;
}map 中有两个变量，"first" 和 "second"，即“键”和“值”，
由于 "it" 是一个指针，所以需要 "->" 来访问。
2.使用 “auto”
c++11 以后，新增了一种 for 循环语法（如下）， vector、list 等容器也可以这么访问。
for (auto i : v)
{
}
四、关于 map 的函数
1.find
查找 x 在 map 中的位置，若不存在这个键返回 “mp.end()”，各自返回指针，如下：
cout << mp.find(x) -> first;2.clear
清空 map，vector 等容器也有这个函数，如下：
mp.clear();3.erase
清除一个键对，或从 “begin” 到 “end” 的所有键对，注意参数需为指针，如下：
mp.eraser(mp.find(x));
mp.eraser(begin,end);若在循环中，需要更新迭代器：
for (map<string, int>::iterator it = mp.begin();it != mp.end();++ it);
it = mp.erase(it);
}4.empty
查看 map 是否为空，如下：
if(mp.empty()) cout << "Yes";5.swap
交换两个 map，如下：
mp.swap(temp);6.count
查找键 x 在 map 中出现了几次，返回值非 0 即 1，如下：
cout << mp.count(x);你学会了吗？
