C++ STL初阶(14): map和set

1.关联式容器与键值对

 前导文章:C++ 二叉树进阶-CSDN博客

之前我们学习的线性的容器,如:vector deque list等都叫作序列式容器

与之对立的概念是关联式容器

关联式容器 也是用来存储数据的,与序列式容器不同的是,其 里面存储的是 <key, value> 结构的 键值对,在数据检索时比序列式容器效率更高

key就是键值,可以在容器中通过键值直接找到value.

比如:现在要建立一个英汉互译的字典,那该字典中必然 有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应 该单词,在词典中就可以找到与其对应的中文含义

我们在 前导文章中的代码的基础上继续往下写:

                             

在搜索二叉树中,有两种典型的模型:key模型和key_value模型

key模型对应set,key_value模型对应map


2. set

1. set 是按照一定次序存储元素的容器
2. set 中,元素的 value 也标识它 (value 就是 key ,类型为 T) ,并且每个 value 必须是唯一的。
set 中的元素不能在容器中修改 ( 元素总是 const) ,但是可以从容器中插入或删除它们。
3. 在内部, set 中的元素总是按照其内部比较对象 ( 类型比较 ) 所指示的特定严格弱排序准则进行排序。
4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢,但它们允许根据顺序对
子集进行直接迭代。
5. set 在底层是用二叉搜索树 ( 红黑树 ) 实现的。

set有三个参数,元素类型、用于比较的仿函数(默认是less)、内存池。

set的操作:

插入操作只有insert(先不管emplace), 线性的数据结构才能push。

set的底层是二叉搜索树中的key模式,并且迭代器在底层默认走的是中序

二叉搜索树的中序遍历一定是有序的,而且还有去重的功能:

  set能够去重(insert了两个三最后还是只出了一个3): 

                       


set的构造:

在c++98下,set只有范围构造和拷贝构造两种使用方法。

可以用迭代器range构造:

因为节点也是存的指针,所以拷贝构造也是走树的深拷贝:

                                              

关于销毁:

在实现析构函数时:

因为析构函数不能有参数,所以我们需要通过在析构函数里套一个Destroy函数来完成析构:

~BSTree()
{Destroy(_root);_root = nullptr;
}

采用后序遍历一个一个销毁节点

为什么要套用?

因为树的销毁是采用递归销毁的办法,而析构函数不能传参,也就无法递归

同理,拷贝构造也是需要递归遍历,也需要封装。

不能直接用BST(const BSTNode<K,V>& Node)去递归拷贝

增删查改

删除最小值就是删除begin()对应的数据就行。

因为iterator走的是中序遍历,所以begin()对应的一定是最左值,而最左值就是最小的数据。

                                   

可以通过erase的返回值来判断是否erase成功:


关于erase删除的报错:

erase删除数值

比如erase(80) , 有80就删除成功,没有80就删除失败。但是删除失败不会报错。

erase删除迭代器:

但是如果使用find()返回的迭代器来删除,find又没有找到,就会报错。

因为find在没有找到的时候,返回值是end(),直接erase(end())就会报错。


查找:

库中的find是根据iterator全部遍历一遍,暴力查找

set中的find是按照搜索二叉树走的;

因此效率有很大差距。

还有个count函数用于计数:

但是由于搜索二叉树是一种不允许冗余数据的容器

所以在目前的使用情境下,该数据存在就返回1,不存在就返回0

                       

因此在set中,count函数一般直接用于判断元素是否存在。 


lower_bound  和 upper_bound(返回的都是>或>=val的第一个数据)

louwer_bound返回的就是set中>=val的第一个数据的iterator

如果没有合适的元素,返回的就是end()

upper_bound同理:

返回的是set中第一个>val的数据的iterator

直接看官网的测试用例:

但是根据cpp左闭右开的性质,lower_bound(30)返回的就是30

upper_bound(60)返回的就是稍大于60的值(此处应该是70),最终能把[30,70)区间里的所有数都删掉,所以删掉的还是[30,60]的数据


3. multiset

multiset是set的变种容器:允许有冗余的元素,允许修改容器里的元素。

multiset和set的区别:

因为multiset是可以插入相同元素的,所以在find时,multiset的find返回的是中序遇到的第一个值:

multiset更能解释count函数存在的意义了,count在multiset中就可以返回相同数值的节点的个数。

还有刚才的lower_bound和upper_bound两个功能下面的被我们忽视的功能:equal_range

equal_range :找到一个数据所有相同数值所在的左闭右开的区间(multiset中相同数据一定是紧挨着的)。

因为相等的数据一定是在相邻的位置。

equal_range返回的是一个pair

pair 中有两个数据,表示的是整个满足条件的区间。

pair是一种结构体。

equal_range返回的pair就是这个区间。


4. map 

map结构

map就是在本文开始处讲的基于搜索二叉树的<key,value>类型

pair是一个结构体模版,在map中统一规定所有的value_type都是pair类型的。

来观察下pair:

成员有first和second

                       

map的结构和set很像

最大的区别map支持方括号访问。(将在后文解释)


map使用(make_pair)

现在就不需要手搓平衡二叉树了,可以直接使用map来创建一个简易字典。

               

但是这样insert是不对的,在map内部,key和value不是分开存放的,而是一起被放在pair中的

正确的四种写法:

第一种,构造有名对象。

第二种,构造匿名对象。

第三种,是库中函数make_pair()对pair<T1,T2>的一种封装

                     

第四种,多参数构造函数可以用{}来进行隐式类型转换。

其实是用{"string","字符串"}构造了一个pair,然后被insert进去。

最后还有一种初始化的方法:

map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插入"},{ "string", "字符串" } };

使用的是所有的容器都支持的initializer_list

外围花括号就是针对一个一个pair的initializer_list, 内层花括号就是隐式类型转换构造的pair

map的遍历: 

想要访问map中的元素,需要pair.去访问内部元素(如上图)。

还可以用->去访问。因为it是像指针一样的东西,之前在链表部分也讲过

库中是通过重载operator->()来使用:

这里的it是为了可读性而省略了一个箭头。

map访问数据多是使用operator->

查询时同理:

    


★★★map的方括号访问(重难点):

(mapped_type就是value_type , 也就是我们常说的value)

不同于传统的方括号访问,

参数是key,返回的是value的引用。换句话说,方括号是通过key去找value的

首先要知道map中insert的返回值:

insert返回的是一个pair
只要插入成功,bool的值就是true, iterator指向的是新插入成功的节点。

在 C++ 中,std::map 是一个基于红黑树实现的关联容器,它不允许插入具有相同键(key)的元素std::map 的每个键值对都是唯一的,键用于组织数据,因此它会自动根据键的顺序对元素进行排序。

如果你尝试插入一个已经存在的键,std::map 会拒绝这个插入操作,并且不会覆盖原有的键值对。如果你需要检查插入是否成功,可以使用 insert 方法,它会返回一个 pair,其中 pair.second 表示插入是否成功(如果键已存在,则为 false),而 pair.first 会指向插入的元素或者已存在的元素。

这就是下图为什么第二次insert"你好"这个键失败的原因

了解了insert的原理,我们再回过头来观察方括号访问:

将operator[]的逻辑写成函数:

             

所以,如果operator[k]的时候,k是一个没有出现过的key , map就会自动创建一个k为key,v为mapped_value()的匿名构造的pair,存在map中。

并且方括号返回的是mapped_value的引用,可以再对这个value的值进行修改。

所以这个operator[]是一个插入+修改的功能。

如果我们再调用一次operator[]:

              

第二次调用["left"],先查找有没有left,因为第一次插入已经创建了left了,所以第二次就找到了<"left","左边">,然后返回了"左边"的引用,通过赋值符号将"左边"改成了 "左边、剩余"

如果只调用一次这个:

                                             

相对于插入了一个"insert",V()的pair

小结:

                   

综上,map的方括号引用是一个复合功能。

所以使用方括号访问的时候要小心,否则一不小心就可能变成插入一个不希望插入的内容。

方括号访问了一个本来不存在的键也会导致插入一个不想插入的pair

使用这个特性,之前计数的代码就可以:

如果水果名字是第一次出现,那么就会在map中插入一个<新的水果名,0>,然后对返回值0进行一次++;如果水果名字不是第一次出现,就是直接对返回的(*iterator).second的value进行++


multimap

multimap map 的唯一不同就是: map 中的 key 是唯一的,而 multimap key 是可以
重复的 。并且multimap不支持方括号访问,inser返回的也只是iterator,而不是一个pair

 甚至还可以在<key,value>都相同的情况下insert一个一模一样的pair


5. 大试牛刀

138. 随机链表的复制 - 力扣(LeetCode) 

我们曾经使用C语言解决过这个问题,解决方法是在原链表的基础上,每一个节点后面都拷贝一份一样的,这样做的本质就是建立相对映射关系。

但是现在有了map可以自主建立映射关系了,就不需要上述麻烦了。

先遍历深拷贝一下节点:

                 

每深拷贝一个节点,就赛一个进入map,可以insert进去也可以直接通过方括号访问调用insert

                 

然后通过映射关系处理深拷贝的所有节点的random

class Solution {
public:Node* copyRandomList(Node* head) {Node* cur = head;map<Node*,Node*> NodeMap;Node* phead = nullptr;Node* ptail = nullptr;while(cur){if(ptail==nullptr){phead = ptail = new Node(cur->val);}else{ptail->next = new Node(cur->val);ptail = ptail->next;}  //每拷贝一个,就让被拷贝的和其对应的两个节点入mapNodeMap.insert(make_pair(cur,ptail));//也可以这样进入map//NodeMap[cur] = ptail;cur = cur->next;}//最后来处理randomcur = head;ptail = phead;while(cur){if(cur->random == nullptr){ptail->random = nullptr;}else{ptail->random = NodeMap[cur->random];}cur = cur->next;ptail = ptail->next;}return phead;}
};

判断是否有环

142. 环形链表 II - 力扣(LeetCode)

放在以前,我们需要利用追击问题的数学知识,推出:

在fast和slow相遇在meet点时,从头出发一个cur,cur和slow同时遍历,一定在环的入口相遇。

现在利用set插入时的特点,第一个插入失败的元素就是环的入口点。

class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur = head;while(cur && (s.insert(cur)).second){cur = cur->next;}return cur;}
};

349. 两个数组的交集 - 力扣(LeetCode)

求交集或者差集,第一步建议:排序+去重

先使用set的迭代器区间构造:

                              

然后使用双指针:

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();vector<int> ans;while(it1 != s1.end() && it2 != s2.end()){if(*it1 == *it2){ans.push_back(*it1);++it1,++it2;}else if(*it1 < *it2){++it1;}else{++it2;}}return ans;}
};

用set可以完美实现排序加去重。然后再利用一个双指针依次遍历

实践中,云平台的同步服务就需要以上的通过交集和并集的同步操作


692. 前K个高频单词 - 力扣(LeetCode) 

        这是一个映射+topk的结合问题,思路如下:

        先把words中的词全部加入到map<单词,出现次数>中去(同遍历水果名字并且计数)

为了让map中的数据根据出现次数来排序,又需要把map中的一个一个pair给放入vector中,然后自己传仿函数(根据出现次数和字典序来排序),比较完之后再将排在前面的k个数据给push到要返回的vector<string>中去。

但是要通过countMap.second来排序以便获得topk

但是排序(数据量小直接用sort,数据量大的时候必须用优先级队列)必须用支持随机迭代器的容器。

所以先将map中的数据入到一个vector中去

 不过对于pair自带的比大小:

不同于我们的期望,我们现在只希望按照次数去比较,所以需要我们自己去实现一个仿函数

然后再创建一个vector来储存答案。

但是发很多测试用例不能通过。

原因是忽略了一个题目的要求:

也不能直接在最后的vector中排序,因为只要求对出现次数相同的单词进行字典序排序

明明在加入到map中的时候已经经过了一次字典序的排序,为怎么现在又乱了?

因为sort的底层是快排,快排是不稳定排序。

可以使用stable_sort:

                

或者改写我们的仿函数:

注意,关于sort要传的用于比较的仿函数:

        返回值需要是bool并且要传两个参数 ,希望是降序就要保证第一个参数大于第二个参数为真。

但是此题的字典序是针对string的升序,所以后面的条件是小于号。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1548262.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【Linux】图解详谈HTTPS的安全传输

文章目录 1.前置知识2.只使用对称加密3.只使用非对称加密 因为私钥加密只能公钥解开&#xff0c;公钥加密只能私钥解开4.双方都是使用非对称加密5.非对称加密 对称加密6.非对称加密对称加密CA认证&#xff08;一&#xff09;CA认证&#xff08;二&#xff09;https &#xff0…

Ks渲染做汽车动画吗?汽车本地渲染与云渲染成本分析

Keyshot是一款强大的实时光线追踪和全域光渲染软件&#xff0c;它确实可以用于制作汽车动画&#xff0c;包括汽车模型的渲染和动画展示。Keyshot的动画功能允许用户创建相机移动、物体变化等动态效果&#xff0c;非常适合用于汽车动画的制作。 至于汽车动画的渲染成本&#xff…

手机如何五开玩梦幻西游端游?用GameViewer远程手机免费畅玩梦幻西游

用手机就能免费玩梦幻西游端游&#xff0c;还可以随时查看挂机进度&#xff01; 想要实现这一点&#xff0c;就用网易GameViewer远程&#xff0c;而且不光手机可以玩梦幻西游端游&#xff0c;平板也能免费玩&#xff0c;并为你实现五开玩梦幻西游端游。 那么&#xff0c;通过Ga…

[001-03-007].第28节:SpringBoot整合Redis:

6.1.Redis的介绍&#xff1a; 1.Redis 是一个开源&#xff08;BSD许可&#xff09;的&#xff0c;内存中的数据结构存储系统&#xff0c;它可以用作数据库、缓存和消息中间件。2.它支持多种类型的数据结构&#xff0c;如 字符串&#xff08;strings&#xff09;&#xff0c; 散…

Python制作进度条,18种方式全网最全!(不全去你家扫厕所!)

想象一下&#xff0c;你的程序在执行复杂任务时&#xff0c;不再是冷冰冰的等待光标&#xff0c;而是伴随着色彩斑斓、动态变化的进度条&#xff0c;不仅让等待变得有趣&#xff0c;更让用户对你的作品刮目相看。从基础的文本进度条到高级的图形界面进度条&#xff0c;从简单的…

Excel FIND函数用法详解,附FIND函数提取文本示例

大家好&#xff0c;这里是效率办公指南&#xff01; &#x1f50e; 在处理文本数据时&#xff0c;我们经常需要在字符串中查找特定词语或字符的位置。Excel中的FIND函数是一个非常实用的工具&#xff0c;可以帮助我们在文本字符串中查找子字符串的位置。今天&#xff0c;我们将…

Ubuntu环境下字体安装

本文介绍Ubuntu环境下字体安装。 软件&#xff08;如Qt应用软件&#xff09;开发过程中经常会涉及到字体的选择&#xff0c;有时候Ubuntu环境下并没有我们想要的字体&#xff0c;本文介绍常用字体及在Ubuntu环境下如何安装。 1.常用开源字体 有些字体商用并不是免费的&#…

【解答篇】什么是SSL证书?它为什么很重要?

什么是SSL证书&#xff1f;它为什么很重要&#xff1f; 1 数据保护的金钟罩2 身份验证的守护者3 信任度与SEO的双重提升4 合规经营的必要条件5 某宝案例 SSL证书&#xff0c;全称安全套接层证书&#xff0c;是互联网安全通信的坚固基石。它并非仅仅是一份文档&#xff0c;而是用…

落魄前端搞副业之 改造淘宝首页(淘宝换肤)

事情发生是这样的: 无意间看到一个淘宝的网页版本换肤大赛, 本来我也是不懈看一眼的. 一脸高傲. 因为各种比赛, 要么就是对手太厉害, 拿不到奖, 要么就是主办方潜规则多, 最终坑人. 那, 按照我的性子, 那必然不会参加啊, /高傲 (奖金不多, 设计开发麻烦, 竞争还大, 说不定还…

智能制造的生产力基础设施

由于全球大多数细分市场的半导体工厂都满负荷运转&#xff0c;因此&#xff0c;生产力如今成为整个行业关注的重要问题也就不足为奇了。工厂经理会仔细监控关键绩效指标 (KPI)&#xff0c;以发现任何生产力下降的迹象&#xff0c;以便快速做出反应&#xff0c;找出并解决这些偏…

Metasploit渗透测试之服务端漏洞利用

简介 在之前的文章中&#xff0c;我们学习了目标的IP地址&#xff0c;端口&#xff0c;服务&#xff0c;操作系统等信息的收集。信息收集过程中最大的收获是服务器或系统的操作系统信息。这些信息对后续的渗透目标机器非常有用&#xff0c;因为我们可以快速查找系统上运行的服…

Spring5入门

Spring5 课程&#xff1a;3、IOC理论推导_哔哩哔哩_bilibili 文档&#xff1a;狂神SSM教程- 专栏 -KuangStudy 一.Spring概述 1.介绍 Spring : 春天 —->给软件行业带来了春天2002年&#xff0c;Rod Jahnson首次推出了Spring框架雏形interface21框架。2004年3月24日&…

AI驱动的智能运维:行业案例与挑战解析

华为、蚂蚁、字节跳动如何引领智能运维&#xff1f; ©作者|潇潇 来源|神州问学 引言 OpenAI 发布的 ChatGPT 就像是打开了潘多拉的魔盒&#xff0c;释放出了生产环境中的大语言模型&#xff08;LLMs&#xff09;。一些新的概念&#xff1a;“大语言模型运维 (LLMOps)”…

防火墙会话表解析

华为防火墙的会话表是防火墙用于记录和管理网络会话的重要数据结构&#xff0c;它对于实现精确的流量控制和安全管理起着至关重要的作用。以下是对华为防火墙会话表的详细解析&#xff1a; 一、会话表的作用 会话表主要用于记录TCP、UDP、ICMP等协议连接的状态信息&#xff0c;…

数据结构:链表算法题

目录 题1.删除链表中的某个元素val题目表述&#xff1a;思路1:在源链表中进行删除更改思路2:创建一个新链表 题2:反转一个链表问题描述&#xff1a;思路1:在源链表内部进行操作思路2:创建一个新链表 题3:寻找链表中间位置题目描述:思路1:思路2:快慢指针 题1.删除链表中的某个元…

003、网关路由问题

1. nginx配置404跳转回默认路由 https://blog.csdn.net/masteryee/article/details/83689954 https://blog.csdn.net/IbcVue/article/details/133230460 https://www.jb51.net/server/317970ynk.htm https://blog.csdn.net/u014438244/article/details/120531287 https://blog…

快速上手Make Sense:在线标注数据集的强大工具

链接&#xff1a; Makesense汉化版本 Makesense英文版 随着深度学习在计算机视觉领域的广泛应用&#xff0c;数据集标注成为了一项重要的任务。Make Sense正是一个为图像数据集提供标注功能的在线工具。其易用性和强大的功能使得它在众多标注工具中脱颖而出。本文将为你详细介绍…

搭建高效知识库:教培机构数字教学的关键一步

在数字化时代&#xff0c;教育培训行业正经历着前所未有的变革。随着在线教育的兴起和个性化学习需求的增长&#xff0c;构建一个高效、易用的知识库已成为教培机构提升教学质量、优化学习体验、增强竞争力的关键一步。本文将深入探讨构建高效知识库的重要性&#xff0c;以及如…

分享段 HTML to PDF 的 NodeJs代码

最近工具箱增加的一个功能&#xff1a; 代码如下&#xff1a; const puppeteer require(puppeteer); const moment require(moment);const TAG [convertTopPdf];async function html2pdf(url, wantFileName) {console.log(TAG, convertTopPdf start, url:, url);const no…

QT 获取视频帧Opencv获取清晰度

先展示结果&#xff1a; 1.获取摄像头的分辨率 mResSize.clear();mResSize camera_->supportedViewfinderResolutions();ui->comboBox_resulation->clear();int i0;foreach (QSize msize, mResSize) {qDebug()<<msize;ui->comboBox_resulation->addItem(…