ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 技术分享
  3. 学科学习
  4. 正文

[C++STL教程]4.map超强的容器,它终于来了!零基础都能理解的入门教程

2023年3月16日 42点热度 0人点赞 0条评论

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

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ C++STL教程 map STL 容器 教程 算法竞赛
最后更新:2023年3月16日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 什么是 map
  • 初始化 map
  • 插入数据
  • 删除数据 & 清空map
  • 获取map大小(元素个数)
  • 获取map中的数据
  • 遍历输出map
  • 判断某个key是否存在
  • swap方法
  • 总结

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号