头像

染染




离线:3小时前


最近来访(78)
用户头像
注册信息
用户头像
Mr.Szz
用户头像
国家级白嫖
用户头像
嘉然是牛马
用户头像
MC_5
用户头像
silver__gold
用户头像
ghb_zZZ
用户头像
l1247396180
用户头像
9d52643c
用户头像
愛.
用户头像
拟态Dream
用户头像
Troiy
用户头像
我是sun
用户头像
levelna
用户头像
明朗编程
用户头像
iforget
用户头像
爱吃面条的阿泽
用户头像
Syw丶
用户头像
冠军水手摸大鱼
用户头像
寂静之主

分享 map练习

染染
6天前

俗话说得好:光说不练假把式,你看懂了我的讲解,但你真的会用了吗?( ̄y▽, ̄)╭
做道题练练手吧
不要看到黄题就害怕,实际难度不大,只要你认真看过我的 map讲解 并且完全吃透,这道题完全不是问题。
题目传送门——洛谷
如果有任何问题或者想要我的代码可以直接私信我哦~



分享 set练习

染染
6天前

俗话说得好:光说不练假把式,你看懂了我的讲解,但你真的会用了吗?( ̄y▽, ̄)╭
做道题练练手吧
不要看到黄题就害怕,实际难度不大,只要你认真看过我的 set讲解 并且完全吃透,这道题完全不是问题。
题目传送门——洛谷
如果有任何问题或者想要我的代码可以直接私信我哦~


Ps:没有错,剩下的STL估计暂时鸽了,但我肯定在假期抽时间给大家写了


拓展:这道题似乎还可以用vectormap等等其他的STL容器解决,思考一下


水分享好快乐



新鲜事 原文

染染
8天前
QAQ
图片



染染
8天前

栈(stack)知识点整理总结

往期内容: 总目录
Ps:建议与 队列queue 搭配食用对比理解记忆


目录

  1. 栈是什么?
  2. 栈的相关概念
  3. 常用语法及操作

栈是什么?

栈(stack)也是c+ +标准模板库中的一个容器,他与queue同样属于线性数据存储结构,所以栈和队列有很多的相似之处。
那么我们来对比着看一看栈的特殊性质:
1.我们知道在队列中,元素遵循FIFO原则,即先进先出原则(First In First Out)。而在栈中,元素遵守的则是FILO原则,即先进后出原则(First In Last Out),或者也可以成为后进先出等。意思应该也很好理解,就像是一个桶,我们先放入的东西一定在桶的下面而后放入的东西存在桶的上面,取用时,后放入的东西(即在桶顶部)的东西会最先被取走。再比如说,我们洗完碗后,会将干净的碗摞起来,先放的碗在下面,后面的依次放在上面,这就是栈的储存方式。
2.在队列中,我们只能从队尾插入元素而只能从队头取出元素,而在栈中,我们只能从栈的“顶部”取用和存储元素,而栈底一般是不动的,还是和上面的桶一样的例子,你总不能把桶的底拆掉从里面拿东西吧。
所以,对栈的最简单的理解方式就是把它看作一个桶
生活中栈是很常见的:一摞东西,桶,汉诺塔,弹夹......
上图:
610439-20160130013806989-121668995.png

out610439-20160130013814661-295746330.png

栈的相关概念

  • 栈顶:栈中允许插入和弹出元素的一端
  • 栈底:栈中不是栈顶的另一端 //好像是废话
  • 压栈(入栈):栈中的插入操作,也叫进栈
  • 弹栈(出栈):栈中的删除操作。
  • 空栈:没有任何元素的栈

栈的数组表示(part 1)

栈与数组同为作为一种线性结构,我们也可以尝试将栈用数组表示出来:
一个栈可以用一个定长n的数组表示,在用一个“指针”top指向栈顶元素的位置。那我们根据栈的性质可以得到:
1.当top的值为0时,表示这个“栈”中没有任何元素,即栈空;
2.当top的值为数组的定长n时,表示我们所开的栈已经存满,不能再存入任何元素了。

常用语法及操作

头文件

#include <stack>

定义与声明

用法(格式):stack<类型> 名称

stack<int> a;
//构造一个名为a存储int类型数据的栈
stack<string> b;
//构造一个名为b存储string类型数据的栈

压栈 .push()

拥有了一个栈后,第一步便是向栈中压入一个元素,那么一如既往,我们先来介绍插入元素的操作——压栈
用法(格式):名称.push(x)x为与定义的栈类型相同的一个数据

stack<int> a;
stack<string> b;
//构造一个存储int类型数据的栈a和一个存储string类型的栈b

a.push(1);
//a:1
b.push("Hello stack!");
//b:Hello stack!
a.push(2);
//a:1 2

弹栈 .pop()

有了输入,那么必然会有输出,再强调一遍:栈只能从栈顶一端插入或弹出元素。
用法(格式):名称.pop()

stack<int> a;
a.push(1);
a.push(2);
a.push(3);
//a: 1 2 3

a.pop();
//a: 1 2

查看栈中元素的个数 .size()

关于这个STL必备函数,应该也没有什么太多可说的了,你的栈中共存储了几个元素,它的返回值就是几(整型)
用法(格式):名称.size()

stack<int> a;
a.size() == 0;
a.push(1);
a.size() == 1;
a.push(2);
a.size() == 2;

判断栈是否为空栈 .empty()

rt,他能返回一个bool类型的值,用于判断栈是否为空,即是否存储了元素。
用法(格式):名称.empty()

stack<int> a;

a.empty() == true;

a.push(1);
a.empty() == false;

访问栈顶元素 .top()

由于栈是一个只有一端可被访问的容器,所以.top()是唯一一个用于查看元素的函数,他的返回值即为栈顶元素的值。它只返回栈顶元素的值而不删除栈顶元素。
用法(格式):名称.top()

stack<int> a;
a.push(1);

a.top() == 1;
a.push(3);
a.top() == 3;
a.size() == 2;

栈的数组表示(part 2)

在了解了栈的基本操作后,我们回到刚刚提到过的用数组表示的栈,在数组结构中,我们又该怎样执行这些操作呢?
如果top<0,我们称为下溢。(如弹出的次数大于栈中原有的元素个数时)
1、进栈(PUSH)算法
①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作②);
②TOP++(栈指针加1,指向进栈地址);
③S[TOP]=X,结束(X为新进栈的元素);
2、退栈(POP)算法
①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈, 空则下溢;不空则作②);
②X=S[TOP],(退栈后的元素赋给X);
③TOP- -,结束(栈指针减1,指向栈顶)。

再次注意:栈指针top永远指向栈顶元素

栈的遍历

啊这个嘛,据我所知,stl中的栈应该没有什么遍历的方法。。。
(算法位招租)

尾声

感觉这期有点短QAQ
栈还是相对比较简单的,因为STL给它提供的内容太少了。。。
图片来自网络,如有侵权立即联系删除~
内容如有错误,或各位巨佬如有补充,敬请指导~
Orz

点赞👍🔼收藏⭐关注✅


ヾ(•ω•`)o掰掰



新鲜事 原文

染染
8天前
昨晚去打模拟赛了,今早继续肝



染染
9天前

queue知识点整理总结

往期内容: 总目录


目录

  1. queue是什么
  2. 基本语法
  3. 队列的遍历
  4. 循环队列

queue是什么?

queue的中文名字是队列,是一种“线性”储存结构,听了这两个名字,我们来想象一个画面,在游乐园的某个项目门口,排起了一条长长的直队(图文不符请谅解,只可意会不可言传) 屏幕截图 2021-10-14 210012.jpg
队列就是一个“队列”一样的容器,先来的人站到队伍的最前面,后来的只能排在后面,队伍前面的先离队,后面的只有等排到自己时才能离开。
所以我们能总结出queue的性质:

  • 先进先出,first in first out,就是我们常说的“FIFO”
  • 只能从队尾插入元素,每次只能弹出队首的元素

这样大家应该就能理解我们为什么会称队列为一种“线性结构”了。
下面用一组图标演示一下队列中存储数据的特点

入队操作.jpg 出队操作.jpg

同样的,队列中存储的数据的类型也是任意的~

接下来看一下queue中的几个概念

  • 队头(首):即允许元素删除的一端
  • 队尾:即允许元素插入的一端
  • 入队:队列的插入操作
  • 出队:队列的删除操作
  • 空队列:没有插入任何元素的队列

队列的基本语法

相较于setmap来说,queue的用法更为简单,因为它的结构较为简单,没有复杂的功能,所以大可放心食用下面的内容

头文件

#include <queue>

定义与声明

用法(结构):queue<类型> 名称

#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
    queue<int> a;
    //定义一个名为a,存储int类型数据的队列
    queue<string> b;
    //定义一个名为b,存储string类型数据的队列
    return 0;
}

入队(插入元素) .push()

定义完一个属于我们自己的队列,接下来的第一步当然是要向队列中存入数据了,这时候便要用到.push()了。就像我们在前面说过的,由于队列具有FIFO的性质,所以.push()是将一个数据放到队尾(将一个数据压入队尾)。
用法(格式):名称.push(x)x为与队列类型相同的数据

queue<int> que;
//构造int类型的队列

que.push(1); //que:1
que.push(3); //que:1,3
que.push(2); //que:1,3,2(队列不具有有序性,按存入顺序储存)

出队(弹出元素) .pop()

对应着入队的就是出队了,我们可以看到它的另一个名字叫“‘弹出’元素”,既然叫弹出,就表示了这个函数能够使队头元素被“弹出”,即删除队头元素而不返回队头元素的值。
用法(格式):名称.pop()

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

que.pop();
//que:3,2
//一定要记住弹出的是第一个元素而不是最后一个
que.pop();
//que:2

查看队列的长度 .size()

几乎是每个STL容器必备的函数.size(),依然,它的返回值是队列中元素的个数
用法(格式):名称.size()

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

cout << que.size() << endl;
//输出:3
que.pop();
cout << que.size() << endl;
//输出:2

查看队列是否为空 .empty()

同样是极为常见但较为少见的函数,它万年不变功能就是返回一个bool类型用于判断一个队列是否为空队列,如果为空队列返回true,否则返回false。一般作为if条件语句的判断条件。
用法(结构):名称.empty()

queue<int> que;
//构造

if (que.empty()) {
    cout << "Nothing here" << endl;
} else {
    cout << "Have something" << endl;
}
//输出:Nothing here

que.push(1);
//向队列中插入一个元素,使队列不为空

//再判断
if (que.empty()) {
    cout << "Nothing here" << endl;
} else {
    cout << "Have something" << endl;
}
//输出:Have something

查看队头元素的值 .front() 查看队尾元素的值 .back()

setmap不同的是,queue不需要也没有迭代器的写法!好耶ヽ(✿゚▽゚)ノ元素的调用更为简单,但有一定的限制,我们可以直接通过.front().back()查看和调用队头和队尾的元素。但同时,我们也只有这两个函数可用。这就意味着,我们无法查看队伍中间的其他元素。
用法(格式):名称.front() 名称.back()

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

cout << a.front() << endl;
//输出:1
cout << a.back() << endl;
//输出:2

队列的遍历

为什么要单独说一说遍历呢?因为,队列的遍历方式不是靠单个函数或用法就能实现的,我们已经说过,队列中,只有队头元素和队尾元素是可以直接访问的,这就意味着,队列的遍历需要一点点小技巧。

思路1:

既然我们能访问的只有队头元素和队尾元素,那最简单的遍历方式便是:每次都查看队头元素,然后将队头元素弹出,队列中有几个元素我们就执行几次,这当然是可以很轻松的实现的:

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

for (int i = 0; i < que.size(); i++) { //遍历每一个元素
    cout << que.front() << " "; //输出当前队头元素
    que.pop(); //将队头元素弹出,使第二个元素变成队头元素
}
//输出:1 3 2

但问题是,如果我们用这种方式遍历完整个队列,我们的队列就被我们清空了!所以在大多数情况下,这种方式是不可行的。那么怎么办呢?

思路2

既然我们想保留这个队列,那我们就再开一个新的队列,一边输出一边存入不就好了吗?

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

queue<int> que1;
//构造一个新的队列用来重新存储原队列中的元素

for (int i = 0; i < que.size(); i++) {
    cout << que.front() << " ";
    que1.push(que.front()); //将原队列中的队头元素压入到新队列中
    que.pop();
}
//输出:1 3 2
//que1:1,3,2
//使que1成功的代替了que

思路3

虽然我们已经完成了任务,但我们可以发现这种方法还是太麻烦了,还要重新开一个新的队列,浪费空间不说,还容易让人搞混,典型的费力不讨好,那有没有更好的方法呢?当然有!
我们发现:思路2中其实并没有开一个新的队列的必要,我们完全可以将两个队列合并为一个,方法也很简单,循环的次数是一定的,而队尾的元素也不会对循环过程产生影响,那我们为什么要开一个新的队列呢,把原来的队首元素直接输出后移动到队尾不就好了吗?如果难以理解请继续看…

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

for (int i = 0; i < que.size(); i++) {
    cout << que.front() << " ";
    que.push(que.front());//将队首元素再次压入队尾
    que.pop();//弹出队头元素
}
//输出:1 3 2

上述代码中队列中元素的变化:

que:
1 3 2 (初始状态)

输出当前队头元素1  
//cout << que.front() << " ";

将当前队头元素1重新压入队尾 
//que.push(que.front());
1 3 2 1

弹出队头元素1 
//que.pop();
3 2 1

输出当前队头元素3

将当前队头元素3重新压入队尾
3 2 1 3

弹出当前队头元素3
2 1 3

输出当前队头元素2

将当前队头元素2重新压入队尾
2 1 3 2

弹出当前队头元素2
1 3 2

可以看到,经过一番操作,队列被我们完整的遍历了一遍,并且队列中元素的个数和顺序都没有发生改变,这样,我们就完成了对队列的完整遍历!ψ(`∇´)ψ
此外,还有一点需要注意的是:我们可以发现循环的条件中用到了.size(),这意味着我们不能在循环的过程中插入或弹出一个元素(即改变队列的长度),所以如果我们想插入元素的话,需要实现定义好一个常量存储循环的次数,如int n = a.size()这样就避免了改变队列而导致循环次数出现变化的情况。

循环队列

这部分内容属于进阶内容,难度较高,理解难度较大,本蒟蒻也只是略知一二,仅为对循环队列的概念的理解做一个参考,代码实现部分还需要在修炼修炼Orz

同样是从名字入手,“‘循环’队列”重在这循环二字,我们刚刚讲过的队列是一条线,那么怎么会出现循环呢?没有错,当我们把一条线首位相接,出现的难道不就是一条循环的数据了吗。而循环队列正式这样的一种存储方式。
用更加专业一些的文字叙述:

循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。
——百度

那么在循环队列中数据是如何存入的呢?我们说了循环队列是形如一条闭环的,但他本质上还是一条线,并且是一条长度固定的线,那么我们依然有从尾部压入数据的存储方式,同时由于环形(循环)的特性,对于尾部空间排满的情况下,在头部存入一个数据的效果和在尾部压入的效果是一样的。所以:

在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。——百度

我能说的也就这么多了,剩下的部分需要和大家一起再学学…
循环队列(度娘)
循环队列的实现

链队列

如名,链队列就是用链表实现的队列…

这个登西更难QAQ,所以…

传送门:
链队列知识
链队列的实现


尾声

终于码完了
队列好难a
图片来自网络,如有侵权,请立刻联系我(我改还不行嘛)QAQ
emm…应该没什么了
不对!

点赞!收藏!关注!

帮我宣传一下也不是不可以
好啦!

ヾ(•ω•`)o掰掰



新鲜事 原文

染染
9天前
继续肝queue


新鲜事 原文

染染
10天前
图片



染染
10天前



染染
10天前

map知识点总结整理

往期内容: 总目录

目录

  1. map是什么?
  2. 基本语法(常用函数)
  3. 函数时间复杂度及返回值总表

小tip

map中有大量与set相似的内容,也可以说是set的一个进阶,推荐先学习一下set的知识,会对map的理解有很大帮助。

map是什么

setvector相同的,map也是c+ +标准模板库(STL)中提供的一个“容器”(即一个放置、包含数据的地方),更进一步说,它是一个关联容器,他能存入“一组对应的值”。那这时估计有些大佬应该能想到另一个类型——pair
pair是什么呢?
简单地说,我们其实可以直接把pair理解为一个含有两个数据的结构体,如

struct pair {
    Type1 first;
    Type2 second;
};
//其中Type处是两个数据的类型,不必相同

简单的了解了pair,我们再回过头来看一看map,与pair相似的,map是以键->值储存的数据类型,即是由一个关键字(key)和一个对应的值(value)组成的。其中,key和value的类型是任意的,包括自己新定义好的类型。需要注意的是,key的存储和set一样具有互异性,即一个map类型中不会出现重复的key值,这样便保证了map中每个key都对应着一个确定的value值,而value的值可以是任意的(可重复)。
key值与set同样的,也具有有序性,即key值也会从小到大自动排好顺序。

综上,我们可以直接将map中的key值理解为是以set的形式储存的。再进一步说,map可以理解为一个set,但这个set中存储的每个值都还对应着一个另外的值。

如果觉得上面的文字还不是很好了解的话,下面我来举个栗子例子对比理解一下setmap这两个容器:一个班级中的同学是固定且不重复的,并且每个同学都有一个只属于自己的学号,那么set便只能够让我们存储这个班级中每个同学的名字只能存储学号,而map能更进一步的存储班级中每个学号将每个学号对应上相应的同学。
由此可见,map的功能相较于set似乎更为强大,而且在我们平时的做题过程中,map的应用也更为广泛。

基本语法(常用函数)

注意:map类型侧重的是后面的value值,这意味着多数的函数都是对key值进行操作的,最终得到相应改变后key值对应的value值

头文件

map同样是有自己的头文件的
#include <map>
这应该没什么可说的吧…

定义(声明)(构造)

用法(格式):map<类型1, 类型2> 名称
如:

#include <iostream>
#include <string>
#include <map> //打上头文件
using namespace std;

map<int, string> mapp; 
//构造一个key值为int类型,value值为string类型的名为“mapp”的map;

int main() {

    ...

    return 0;
}

插入元素

set不同的是,作为一个更加高大上的容器,它的读入方式是多种多样且复杂的,这里我们介绍较为简单的两种方式。

第一种:

最最最最简单的一种方式,数组爱好者狂喜,没错,就是set用不了的a[i]式调用!应该不需要太多解释了,直接看一下打法:
用法(格式):名称[key值] = value值

map<int, string> mapp;
mapp[0] = "Hello map!"; //即在mapp中  0->"Hello map!"
mapp[2] = "Hello RanRan!" //0->"Hello map!"  2->"Hello RanRan!"

还需要注意的是[]中的内容不再是存储的位置而是key值,不要把两个概念搞混了。

第二种:

虽然说mapset高级,但是.insert()该用还是要用的(真香),但由于map存储的不再是单一的一个值,所以我们当然也不能用.insert()单单的向map中直接放入一个值,而是应该放入一组对应的key值和value值,那这时候我们开头提到的pair类型就能派上用场了。
用法(格式):名称.insert(pair<类型1,类型2>(key值,value值)) (pair的类型1和类型2与map的两个类型是相对应的)。

map<int, string> mapp;
mapp.insert(pair<int, string>(0, "Hello map!"));
//在mapp中存入一对数据:0->"Hello map!"
介绍完这两种输入方式,那么他们完全是等价的吗?

答案是否定的!我们已经说过,map实际上完全可以理解为一种特殊的set,就像说过的“key值是不能重复的”。那我们回忆一下set中的.insert()有什么特别的地方吗?

互异性 即如果存入的数据在set中已经存在即自动忽略。

那同样在map中,.insert()具有相同的性质,即如果插入的元素在原map中已经存在,如果此时用.insert()的方式读入的话,便会直接忽略这条指令。
而对于“数组式”的插入来说结果是不同的,当用“数组式”插入时,如果插入的一组数据的key值是已经存在的,这个时候这条插入的指令并不会被忽略,++而是让新的value值覆盖原本对应的value值。
如:

map<int, string> mapp;
mapp[1] = "Hello map!";
//构造一个map容器并 令:1->"Hello map!"

//用.insert()插入另一组key值为1的数据
mapp.insert(pair<int, string>(1, "Hello RanRan!"));
//此时mapp中依然有 1->"Hello map!"

//用数组式插入另一组key值为1的数据
mapp[1] = "Hello RanRan!";
//此时mapp有新的 1->"Hello RanRan!"

调取元素

这个就直接用最简单的数组式应该最方便了吧…
迭代器当然也可以,放在后面开专栏了Orz
用法(格式):名称[key值] -> 返回key值对应的value值

map<int, string> mapp;
mapp[1] = "Hello map!"
//构造

cout << mapp[1] << endl;
//输出:Hello map!

查看元素组数 .size()

这个应该也没太多可说的,大家应该再熟悉不过了吧…如果我们想要知道map中共存入了几组元素,.size()可以帮我们解决。
用法(格式):名称.size()

map<int, string> mapp;
mapp[123] = "Hello map!";
//构造

cout << mapp.size() << endl;
//输出:1

检查map是否为空 .empty()

如名…
用法(格式):名称.empty()

map<int, string> mapp;
//构造

//mapp.empty() == true;
//此时还没有插入任何元素,所以map中是空的

mapp[123] = "Hello map!";
//mapp.empty() == false;
//插入了一组元素,此时mapp以不为空

数某组元素(key值)出现次数 .count()

如名…
还是那句话,map作为一个特殊的set,它的.count()set中的也是一样的,由于互异性的存在,它的返回值只能是1或0,所以基本上唯一的用途便是判断一个元素是否存在了…
用法(格式):名称.count(x)这里的x是一个key值而不能是一个value值!!!

map<int, string> mapp;
mapp[0] = "Hello map!";
//构造

cout << mapp.count(0) << endl;
//由于mapp中存在0这个key值且只能出现一次,所以返回1
//输出:1

cout << mapp.count(1) << endl;
//由于mapp中不存在key值为1的数据,所以返回0
//输出:0

cout << mapp.count("Hello map!") << endl;
//.count()只能查找key值,而我们定义的mapp的key值是一个int类型的变量,所以你得到的只能是 编译错误

迭代器

没有错,该来的还是来了QAQ
迭代器的基本概念在set的讲解中已经涵盖了,这里不再赘述,我们直接来看一下它的用法。
其实基本的格式和set中的基本上是一样的…那就直接上代码吧…
用法(格式):map<类型1, 类型2>::iterator 迭代器名称
如:

map<int, string> mapp;
mapp[123] = "Hello map!";
mapp[456] = "Hello RanRan!";
mapp[789] = "QAQ";
//构造

map<int, string>::iterator it;//注意迭代器的两个类型必须与所要查看的map的两个类型完全对应好
//构造一个指向key值为int类型,value值为string类型的map的迭代器it

这样我们便拥有了一个迭代器,但这个迭代器依然是没有值的,它还没有指向任何东西,所以我们需要给它一个初始值,这个值可以是.begin().end(),但必须是你要查看的map类型中的位置。

此处.begin()和.end()两个函数与set中的.begin()和.end()完全相同,分别返回的是map中第一组元素的迭代器和最后一组元素的下一位的迭代器。一定要注意.end()指向的并不是最后一组元素,当你输出*(mapp.end())时不会返回任何结果,.end()--指向的才是最后一组元素

接上段代码:


...
it = mapp.begin();
//使迭代器指向mapp的第一个元素

//it = mapp.end();

当我们的迭代器有了一个初始的值,接下来就可以开始遍历了:
接上段代码:

...
for (it; it != mapp.end(); it++) {

}

但我们知道map中的元素都是成组的,而迭代器指向的是这一组数组的整体,所以如何输出迭代器指向的数据组中的key值或value值呢?
这里,我们引入一个(或者说一对两个)新的符号->,就是这个长得和小箭头一样的符号,他便能使迭代器的指向更加精确,精确到这组数据中的key值或value值。在map中,我们把key值作为一级数据(first)而value值作为二级数据(second),那么,迭代器名称->first便可以得到迭代器当前指向的一组数据中的key值,同理,迭代器名称->second可以得到这组数据中的value值。
用法(格式):迭代器名称 -> first/second

...
for (it; it != mapp.end(); it++) {
    cout << it->first << endl;
}

//依次输出mapp中所有的key值
for (it; it != mapp.end(); it++) {
    cout << it->second << endl;
}
//依次输出mapp中所有的value值

删除元素 .erase()

基本用法:删除某一key值及其对应的value值
用法(结构):名称.erase(x)x值为某一key值

map<int, string> mapp;
mapp[123] = "Hello map!";
//构造

//mapp.empty() == false;
//此时mapp中有一组元素123->Hello map!

mapp.erase(123);
//mapp.empty() == true;
//仅有的一组元素被清除

其他用法:
1.名称.erase(x)中x除了可以是一个key值外,还可以是迭代器
2.由于.erase()会有一个返回值,所以

int n = mapp.erase(123); //如果删除了返回1,否则返回0

3.可以用迭代器将map范围清空(如清空),与set中相同的,清除的范围为[first, last)内的所有元素

a.erase(a.begin(), a.end()); //清空

删除所有元素 .clear()

如名字,清空一个map
用法(结构):名称.clear()

map<int, string> mapp;
mapp[123] = "Hello map!";
mapp[456] = "Hello RanRan!";
mapp[789] = "QAQ";

cout << mapp.size() << endl;
//输出:3

mapp.clear();//清空
cout << mapp.size() << endl;
//输出:0

查找一个key值是否被存储 .find()

set中的.find()函数相同,它的返回值固定为一个迭代器,如果查找的元素(key值)存在,返回key值所在一组元素的迭代器的值,否则返回.end()的值。

map<int, string> a;
//构造
a[0] = "Hello map!";
//存入
map<int, string>::iterator it;
//构造一个迭代器
it = a.find(0);
//迭代器的值更新为指向key值为0的一组元素
cout << it->second << endl;
//输出key值为0的这组元素的value值
//输出:Hello map!

.lower_bound() & upper _bound()

set中的用法依然相同…
.lower_bound()表示=> 查找key值≥x的元素中最小的一个,并返回指向该元素的迭代器
.upper_bound()表示=> 查找key值>x的元素中最小的一个,并返回指向该元素的迭代器
用法(格式):名称.lower_bound() 名称.upper_bound()

map<int, string> mapp;
mapp[123] = "Hello map!";
mapp[456] = "Hello RanRan!";
mapp[789] = "QAQ";

map<int, string>::iterator it;

it = mapp.lower_bound(456);
cout << it->second << endl;
//≥456的最小key值即为456,所以迭代器指向456->Hello RanRan!这组数据
//输出:Hello RanRan!

it = mapp.upper_bound(456);
cout << it->second << endl;
//>456的最小key值为789,所以迭代器指向789->QAQ这组数据
//输出:QAQ

Ps:特殊的,对于比map中最大的元素大的元素,两个函数返回的都是mapp.end()

各函数时间复杂度及返回值

序号 算法名 时间复杂度 返回值
1 .size() O(1) 整形
2 .empty() O(1) bool类型
3 .clear() O(n) -
4 .count() O(log n) 整形
5 迭代器的+ +和- - O(log n) 迭代器
6 .begin() O(1) 迭代器
7 .end() O(1) 迭代器
8 .insert() O(log n) 返回插入地址的迭代器和是否插入成功的bool并成的pair(基本用不到)
9 .erase() O(log n) 返回下一个元素的迭代器(容易报错,基本用不到)
10 .find() O(log n) 返回指向该元素的迭代器,若不存在,返回set.end()
11 .lower_bound() O(log n) 迭代器
11 .upper_bound() O(log n) 迭代器

尾声

制作较为仓促,有问题请指正Orz
全文markdown语法共3600余字,感谢您耐心读完~
希望能被更多人看到(疯狂暗示)

ヾ(•ω•`)o