C++STL中map容器的学习笔记

发布于 / 笔记 / 1 条评论

弱鸡冻葱虽然瞎吉尔搞了三年的OI,但其实只是一个从pascal起手,后来直接硬套的C艹的语法的沙雕选手。所以之前很少使用STL的相关内容,也很少使用C++11以上的各种特性。而今天我刷题的时候被一道题蜜汁卡60分而困扰不已。后来观察了学长cy的代码之后发现学长使用了一个对我来说很陌生的容器——map。当然,对我来说很陌生就是因为我太菜了。

于是我便去搜了一搜map的相关内容,发现这个东西真的很劲。可以用来解决之前卡住我的很多问题。下面是我学习map的一些笔记和实例。

1.初步了解

Map(映射)是一种有序STL关联容器,提供一种一对一键-值(key-value)对应关系。每个键只能在map中出现一次,而且是按照key的升序有序排列的。Map的内部是通过一颗红黑树排列的(一种非严格意义上的平衡二叉树),这棵树有对数据进行自动排序的功能而这要求key的类有对operator<的定义。关联式容器的特点是增加和删除节点对迭代器的影响很小,并且除了操作节点外,对其他节点不会造成成影响。对于迭代器来说,可以修改value,但是不能修改key。

Map支持自动建立键值对的功能,其中key和value可以使用自定义的类。也支持根据key快速查找记录,查找的复杂度基本是log(N)。快速插入键值对,快速删除键值对,根据key修改value记录和遍历所有记录的功能。当然,Map也支持其他STL容器公用的许多功能。比如查找元素是否存在(find()),查询map大小(size())等等,不在一一赘述。

2. 简单使用

1.构造

Map的构造函数有6个,但是常用的有三(yi)个。我们一般使用如下方法构造一个map:

map<int, string> map_1;

这样,我们就构造了一个名为map_1的,key类型为intvalue类型为string的map。

2.数据的插入

一般插入数据有两种方法——使用insert()或者使用一种类似于数组的结构插入数据。

insert()有两种用法,分别是插入pair类型和value_type类型(其实都挺麻烦的)

map_1.insert(pair<int, string> (1, “One”));

map_1.insert(map<int, string>::value_type (2, “Two”);

这样,我们就插入了两个键值对。

当然,还有这个最常用的:

map_1[4] = “Four”;

这样,就自动创建了一个( 4 : “Four”)的键值对。比insert函数简洁了很多。而且数组方式和insert方式有一个显著的不同点:当要插入的键值被占用时,insert函数会添加失败并且返回异常值,而数组法会替换掉原来的value值。

3.数据的删除

数据的删除有三种方式,分别是删除一个对象(参数是一个迭代器),删除一个范围(参数是两个迭代器),删除一个key值对应的键值对(参数是key的类)。当然,也可以使用clear()来清空(等价于map_1.erase(map_1.begin(), map_1.end());)。

3.注意点

需要注意的是,如果你使用形如for (auto it = map_1.begin(); it != map_1.end(); it++)来遍历map的话。在这个循环中,迭代器it有两个成员:it->firstit->second,分别表示该键值对中的keyvalue。而如果你使用形如for (auto it : map_1)来遍历的话,在这个循环中,你需要使用.运算符来调用it的两个成员而不是’->’运算符,即it.firstit.second(我还没明白为啥但是这么搞就对了)

4.一个实例

其实就是上边我提到的那道洛谷题。这道题如果使用map的话,就会十分简洁。这里是我的代码,直接放上去算了。

 

至于我一开始一直卡60分的代码,可以在冻葱云公开文件的Code文件夹找到。技术十分菜,还请轻喷。

以上,就是弱鸡冻葱的map学习笔记。

转载原创文章请注明,转载自: 冻葱Tewi » C++STL中map容器的学习笔记
  1. 冻葱Tewi

    补充1:

    for (auto it : map_1)中,这个it被定义成了一个类似于pair的东西,所以可以直接调用其成员。
    for (auto it = map_1.begin(); it != map_1.end(); it++) 一句中,迭代器是一个指针,所以需要使用->运算符。

    由cy学长提供