之前咱们介绍过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关键字，在这篇文章末尾有简略介绍：www.eriktse.com/algorithm/1…

判别某个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原创，创造不易，假如对您有协助，欢迎小伙伴们点赞、收藏⭐、留言