头像

染染




离线:1小时前


最近来访(63)
用户头像
黎寅睿
用户头像
Troiy
用户头像
我是sun
用户头像
levelna
用户头像
愛.
用户头像
注册信息
用户头像
明朗编程
用户头像
iforget
用户头像
MC_5
用户头像
爱吃面条的阿泽
用户头像
Syw丶
用户头像
冠军水手摸大鱼
用户头像
寂静之主
用户头像
l1247396180
用户头像
xdd10
用户头像
潮声两岸
用户头像
雪菜弟弟
用户头像
include敲得飞快
用户头像
zxt
用户头像
ADMlN

分享 map练习

染染
12小时前

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



分享 set练习

染染
13小时前

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


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


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


水分享好快乐



新鲜事 原文

染染
2天前
QAQ
图片



染染
2天前

栈(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掰掰



新鲜事 原文

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



染染
3天前

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掰掰



新鲜事 原文

染染
3天前
继续肝queue


新鲜事 原文

染染
4天前
图片



染染
4天前



染染
4天前

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中第一组元素的迭代器和最后一组元素的迭代器

接上段代码:


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

//it = mapp.end();
//也可以使迭代器指向mapp的最后一个元素

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

...
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