之前咱们介绍过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原创,创作不易,如果对您有帮忙,欢送小伙伴们点赞👍、珍藏⭐、留言💬