（二十九）STL map容器（映射）与STL pair容器（值对）
C++中的map容器是什么？可以说这个是python中的字典（dict）
T = {'1':5, '3':7, '5':4, '4':9, '2':6}
print(T)
学过python的都知道字典的每一项都有一个键（key）和一个值（value），而且键是不能重复的
在C++还有一个特点：可以自排序
那值对pair又是个什么东西呢？一个pair可以存储两个数据，这是他的定义：
template<class _T1, class _T2>
struct pair
{ ...
_T1 first;
_T2 second;
...
}
在这里_T1指第一项的类型，_T2指第二项的类型，因此first指第一项的值，second指第二项的值
map中的每一项都有一个值对pair，因此map和pair有很大的关系。我们可以说“pair是只有一项的map，map是有多项的pair”
map与pair的定义和vector、set一样，需要这两个得导入头文件#include <map>
map<Typ1, Typ2> T; //定义一个map容器T，它的键的类型是Typ1，值的类型是Typ2
pair<Typ1, Typ2> P; //定义一个pair容器P，first的类型是Typ1，second的类型是Typ2
想要制作一个值对，可以使用make_pair()函数
make_pair(first, second) //返回一个第一项为first，第二项为second的值对
这些是map容器中的一些函数：
T.insert(x)：x为一个值对，这个代码表示添加一个新项x（如果存在x.first则无事发生）T.erase(x)：如果T中确实存在x这个键，那么删除它，否则无事发生T.erase(it)：如果T中确实存在it这个有效迭代器，那么删除迭代器的内容，否则运行错误T[x]：返回T中键为x的那一项的值（未存在返回0）T.find(x)：如果存在键x，返回它存在的迭代器，否则返回T.end()（类型map::iterator）T.count(x)：如果存在键x，返回1，否则返回0（返回类型size_t）T.size()：返回T的大小T.capacity()：返回T占用的大小（T.erase()函数没有真正的删除，只是把它标记成了nullptr，所以这里的删除仍然在占用空间）T.begin()：返回T的首元素迭代器T.end()：返回T的末尾截止元素迭代器
这些是pair容器中的一些函数：
P.first：返回P的第一个元素P.second：返回P的第二个元素Pit->first：返回地址为Pit的值对的第一项Pit->second：返回地址为Pit的值对的第二项
如果需要用迭代器遍历map容器，可以使用类型map<类型1, 类型2>::iterator
for(map<Typ1, Typ2>::iterator it = T.begin(); it != T.end(); it ++)
cout << it->first << ':' << it->second << endl;
因为map的每一项都是pair，所以可以使用迭代器->first来获取某项的键，用迭代器->second来获取某项的值
一样的，map也支持foreach循环
for(auto it: T)
cout << it.first << ':' << it.second << endl;
注意，foreach每项返回的不是迭代器
map容器可以自自定义排序方法，和set容器的方法一样，重载()
struct cmp {
bool operator() (int a, int b) const //增加const后可以增加防御性
{ return a > b; }
};
map<int,int,cmp> T;
这种使用结构体来包装重载运算的方法叫做伪函数（functor）
如果不想让它排序呢？聪明点，定义一个vector数组
vector<pair<类型前, 类型后>> T;
只不过用法就变了，例如insert()变身push_back()，访问元素还要依次查询
预览：
- 二十二：类（class）
- 二十三：高精度运算
- 二十四：算法进阶
- 二十五：递归
- 二十六：vector容器
- 二十七：递推
- 二十八：
set容器 - 二十九：
map容器 - 三十：二分查找（
Binary Search, BS） - 三十一：前缀和与差分
- 三十二：栈（
stack） - 三十三：队列（
queue）和双向队列（deque） - 三十四：电脑基础知识
- 三十五：链表
- 三十六：树
- 三十七：图
- 三十八：预处理命令
…