之前我们介绍过vector, queue, stack，他们都有一个共同的特点，就是都可以用线性表来模拟。今天我们来学习一个全新且高封装性的容器：map。
作者：Eriktse
简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的方式讲解算法！️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）
个人博客：www.eriktse.com
什么是 map
std::map是C++标准库中的一个容器，数据以<key, value>的形式存储，也就是我们常说的“键值对”形式，且其“键值对”是有序的，也就是可以顺序遍历的。
这意味着一个key只能对应一个value，而一个value可能对应了多个key，其关系有点像高中学过的函数的关系。
map的底层一般实现为红黑树，这个仅作了解即可。搜索、移除和插入操作拥有log级别复杂度。
初始化 map
首先引入头文件：
#include <map>
用以下代码声明一个空的map：
map<int, string> mp;//声明一个类型为<int, string>的map
注意这里使用了string，也就需要引入头文件#include <string>。
插入数据
map有一个函数是insert()，支持将数据插入。时间复杂度O(logn)，n为map中已有的数据个数。
mp.insert({0, "张三"});//插入一条数据
当然还有另外一种办法来插入数据，就是直接赋值，像操作数组一样操作map，但是这个map的下标可不是连续的，可以是任意符合条件的key。
mp[2] = "李四";
//现在map中的数据：{0: "张三", 2: "李四"}
可能会有小伙伴疑惑，这里没有1的吗？在这里map的key只要int类型即可，就算是负数都可以！
mp[-1] = "王五";
//mp = {-1: "王五", 0: "张三", 2: "李四"};
mp[-1] = "eriktse";
//mp = {-1: "eriktse", 0: "张三", 2: "李四"};
值得注意的是，value是可覆盖的，且这里的key是有序的，虽然我的-1这个key是后面加入的，但是却排在了第一个，如果顺序遍历这个mp的话，{-1: "eriktse"}会是第一个被遍历到的。后面会讲到如何遍历map。
删除数据 & 清空map
erase(key)方法：删除key所对应的数据。时间复杂度O(logn)。
clear()方法：清空整个map。
mp.earse(-1);
////mp = {0: "张三", 2: "李四"};
获取map大小（元素个数）
size()方法：返回map的大小，是一个非负整数。
检查容器是否无元素，即是否 begin() == end() 。
获取map中的数据
直接像用数组一样获取就行了。
mp[key]表示map中这个key所对应的value。
cout << mp[0] << '\n';//输出： 张三
遍历输出map
遍历map需要用到std::iterator迭代器，没有接触过的同学可能不太了解，可以先看代码，或者用第二种方法。
方法一：迭代器法
void print(map<int, string> mp)
{
cout << '{';
for(map<int, string>::iterator it = mp.begin(); it != mp.end(); ++ it)
{
cout << i.first << ": " << "\"" << i.second << "\"";
if(next(it) != mp.end())cout << ", ";//这里的next(it)表示it的下一个位置，注意这里不能用 + 1运算，会报错
}
cout << '}';
}
在需要输出map的地方调用print(mp)即可。
方法二：auto关键字
void print(map<int, string> mp)
{
cout << '{';
for(auto &i : mp)
{
cout << i.first << ": " << "\"" << i.second << "\"";
if(i != *mp.rbegin())cout << ", ";
}
cout << '}';
}
关于auto关键字，在这篇文章末尾有简单介绍：https://www.eriktse.com/algorithm/1051.html
判断某个key是否存在
count(key)可以返回key出现的次数，但是在经典的map中一个key只能出现一次，所以当返回值为1时说明key存在，返回值为0说明key不存在。时间复杂度O(logn)。
在容器
multimap中一个key允许出现多次。
还可用find()函数判断。
find(key)返回一个迭代器表示找到的数据项，当找不到时返回end()。
if(mp.count(x))cout << "mp中存在key == x的项";
else cout << "mp中不存在key == x的项";
if(mp.find(x) != mp.end())cout << "mp中存在key == x的项";
else cout << "mp中不存在key == x的项";
swap方法
mp1.swap(mp2)方法：交换两个map容器。
看下面这个例子：
map<int, string> mp1, mp2;//声明一个类型为<int, string>的map
mp1.insert({0, "张三"});//插入一条数据
mp1[2] = "李四";
mp1[-1] = "eriktse";
mp2[5] = "A";
mp1.swap(mp2);
//print函数需要自己实现
print(mp1);//输出： {5: "A"}
总结
map是C++中常用的stl之一，也是算法竞赛中的常客，大家一定要牢牢记住map的用法、
本文由eriktse原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞、收藏、留言
