★ C++进阶篇 ★ map和set

Ciallo~(∠・ω< )⌒☆ ~ 今天,我将继续和大家一起学习C++进阶篇第四章----map和set ~

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页:椎名澄嵐-CSDN博客

C++基础篇专栏:★ C++基础篇 ★_椎名澄嵐的博客-CSDN博客

C++进阶篇专栏:★ C++进阶篇 ★_椎名澄嵐的博客-CSDN博客

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

目录

一  序列式容器和关联式容器

二  set系列的使用

2.1 set类的介绍

2.2 set的构造和迭代器

2.3 set的增删查

2.4 set的使用

2.5 multiset和set的差异

2.6 两道set经典例题

三  map系列的使用

3.1 map类的介绍

3.2 pair类型介绍

3.3 map的构造

3.4 map的增删查

3.5 构造遍历及增删查使用样例

3.6 insert & operator[ ]

3.7 multimap和map的差异


一  序列式容器和关联式容器

序列式容器:有string、vector、list、deque、array、forward_list等。逻辑结构为线性序列的数据结构,两个位置存储的值之间⼀般没有紧密的关联关系,比如交换⼀下,他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器:有map/set系列和unordered_map/unordered_set系列。关联式容器逻辑结构通常是非线性结构, 两个位置有紧密的关联关系,交换⼀下,他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。

本次学习的map和set底层是红黑树,红⿊树是⼀颗平衡二叉搜索树set是key搜索场景的结构, map是key/value搜索场景的结构。

二  set系列的使用

2.1 set类的介绍

set - C++ Reference (cplusplus.com)

  • set的声明如上,T就是set底层关键字的类型
  • set默认要求T支持小于比较,如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数
  • set底层存储数据的内存是从空间配置器申请的,如果需要可以自己实现内存池,传给第三个参数。
  • ⼀般情况下,我们都不需要传后两个模版参数。
  • set底层是用红黑树实现,增删查效率是 ,迭代器遍历是走的搜索树的中序,所以是有序的。 O(logN) 。

2.2 set的构造和迭代器

set的各种构造~( 无参默认构造,迭代器区间构造, 拷贝构造,移动构造, initializer列表构造 )

set的支持正向和反向迭代遍历,遍历默认按升序顺序,因为底层是⼆叉搜索树,迭代器遍历走的中序;支持迭代器就意味着支持范围for,set的iterator和const_iterator都不支持迭代器修改数据,修改关键字数据,破坏了底层搜索树的结构。

2.3 set的增删查

set 不支持修改,主要有以下接口~

Member types
key_type -> T
value_type -> T// 单个数据插⼊,如果已经存在则插⼊失败
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊,已经在容器中存在的值不会插⼊
void insert(initializer_list<value_type> il);
// 迭代器区间插⼊,已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找val,返回val所在的迭代器,没有找到返回end()
iterator find(const value_type& val);
// 查找val,返回Val的个数
size_type count(const value_type& val) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除val,val不存在返回0,存在返回1
size_type erase(const value_type& val);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等val位置的迭代器
iterator lower_bound(const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound(const value_type& val) const;

2.4 set的使用

  • 迭代器 & insert
#include<iostream>
#include<set>
using namespace std;
int main()
{// 去重+升序排序set<int> s1;// 去重+降序排序set<int, greater<int>> s2;s1.insert(5);s1.insert(2);s1.insert(7);s1.insert(5);//set<int>::iterator it = s.begin();auto it = s1.begin();while (it != s1.end()){// error C3892: “it”: 不能给常量赋值// *it = 1;cout << *it << " ";++it;}cout << endl; // 2 5 7// 插入⼀段initializer_list列表值,已经存在的值插入失败s1.insert({ 2,8,3,9 });for (auto e : s1){cout << e << " ";}cout << endl; // 2 3 5 7 8 9set<string> strset = { "sort", "insert", "add" };// 遍历string比较ascll码大小顺序遍历的for (auto& e : strset){cout << e << " ";} cout << endl; // add insert sortreturn 0;
}

  •  erase & find 

int main()
{set<int> s = { 4,2,7,2,8,5,9 };for (auto e : s){cout << e << " ";}cout << endl;// 删除最小值s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl;// 直接删除xint x;cin >> x;int num = s.erase(x);if (num == 0){cout << x << "不存在!" << endl;}for (auto e : s){cout << e << "删除成功!" << " ";}cout << endl;// 直接查找在利⽤迭代器删除xcin >> x;auto pos = s.find(x);if (pos != s.end()){// pos在erase后失效s.erase(pos);}else{cout << x << "不存在!" << endl;}for (auto e : s){cout << e << "删除成功!" << " ";}cout << endl;// 算法库的查找 O(N)auto pos1 = find(s.begin(), s.end(), x);// set⾃⾝实现的查找 O(logN)auto pos2 = s.find(x);// 利⽤count间接实现快速查找cin >> x;if (s.count(x)){cout << x << "在!" << endl;}else{cout << x << "不存在!" << endl;}return 0;
}

 注意迭代器失效的问题

int main()
{std::set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout << e << " ";}cout << endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 >= 30auto itlow = myset.lower_bound(30);// 返回 > 60auto itup = myset.upper_bound(60);// 实现查找到的[itlow,itup)包含[25, 55]区间// 返回 >= 25auto itlow = myset.lower_bound(25);// 返回 > 55auto itup = myset.upper_bound(55);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}cout << endl;return 0;
}

2.5 multiset和set的差异

multiset和set的使用基本完全类似,主要区别点在于multiset⽀持值冗余,那么 insert/find/count/erase都围绕着⽀持值冗余有所差异,具体参看下面的样例代码理解。

int main()
{// 相比set不同的是,multiset是排序,但是不去重multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;// 相比set不同的是,x可能会存在多个,find查找中序的第⼀个int x;cin >> x;auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;}cout << endl;// 相比set不同的是,count会返回x的实际个数cout << s.count(x) << endl;// 相比set不同的是,erase给值时会删除所有的xs.erase(x);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

2.6 两道set经典例题

1.  两个数组的交集

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

首先用两个集合s1和s2来存储nums1和nums2的元素,因为集合会自动去重并且排序~
然后,函数用两个迭代器it1和it2来分别遍历s1和s2。在遍历的过程中,如果it1指向的元素小于it2指向的元素,就让it1向后移动一位;如果it1指向的元素大于it2指向的元素,就让it2向后移动一位;如果它们相等,就把这个元素加入到结果向量ret中,并且让it1和it2都向后移动一位

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());// 因为set遍历是有序的,有序值,依次⽐较// ⼩的++,相等的就是交集vector<int> ret;auto it1 = s1.begin();auto it2 = s2.begin();while (it1 != s1.end() && it2 != s2.end()){if (*it1 < *it2){it1++;}else if (*it1 > *it2){it2++;}else{ret.push_back(*it1);it1++;it2++;}}return ret;}
};

2.  环形链表

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

把每个节点遍历插入set, 若插入时发现set中已经有此节点,则带环。

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

三  map系列的使用

3.1 map类的介绍

map的声明如上,Key就是map底层关键字的类型,T是map底层value的类型,set默认要求Key⽀持小于比较,如果不⽀持或者需要的话可以自行实现仿函数传给第⼆个模版参数,map底层存储数据的内存是从空间配置器申请的。⼀般情况下,我们都不需要传后两个模版参数。map底层是用红黑树实现,增删查改效率是 O(logN) ,迭代器遍历是⾛的中序,所以是按key有序顺序遍历的。

3.2 pair类型介绍

map 的成员中的 value_type 使用了 pair 类型,那什么是 pair 类型呢~

3.3 map的构造

map的构造我们关注以下⼏个接口即可。 map⽀持正向和反向迭代遍历,遍历默认按key的升序顺序,因为底层是⼆叉搜索树,迭代器遍历⾛的中序;⽀持迭代器就意味着⽀持范围formap⽀持修改value数据,不⽀持修改key数据,修改关键字数据,破坏了底层搜索树的结构。

3.4 map的增删查

map增接口,插⼊的pair键值对数据,跟set所有不同,但是查和删的接⼝只⽤关键字key跟set是完全类似的,不过find返回iterator,不仅仅可以确认key在不在,还找到key映射的value,同时通过迭代还可以修改value。

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>// 单个数据插⼊,如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊,已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊,已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);// 查找k,返回k所在的迭代器,没有找到返回end()
iterator find (const key_type& k);
// 查找k,返回k的个数
size_type count (const key_type& k) const;// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除k,k存在返回0,存在返回1
size_type erase (const key_type& k);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type& k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type& k) const;

3.5 构造遍历及增删查使用样例

int main()
{map<string, string> dict;pair<string, string> kv1("first", "第一个");dict.insert(kv1); // 有名对象dict.insert(pair<string, string>("second", "第二个")); // 匿名对象dict.insert(make_pair("third", "第三个")); // make_pair函数dict.insert({ "forth", "第四个" }); // C++11// 隐式类型转换构造map<string, string> dict2 = { { "left", "左边" }, { "right", "右边" }, { "insert", "插入" }, { "erase", "删除" } };auto it = dict.begin();while (it != dict.end()){// cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;// 存结构可以用箭头// 实际上是cout << it.operator->()->first << ":" << it.operator->()->second << endl;++it;}return 0;
}

 

3.6 insert & operator[ ]

insert 插⼊⼀个 pair 对象

  • 1 、如果 key 已经在 map 中,插⼊失败,则返回⼀个 pair 对象,返回 pair 对象 first 是 key 所在结点的迭代器, second 是 false。
  • 2 、如果 key 不在在 map 中,插⼊成功,则返回⼀个 pair 对象,返回 pair 对象 first 是新插⼊ key 所在结点的迭代器, second 是 true。
  • ⽆论插⼊成功还是失败,返回 pair 对象的 first 都会指向 key 所在的迭代器。
  • 那么也就意味着 insert 插⼊失败时充当了查找的功能,正是因为这⼀点,insert 可以⽤来实现 operator[]。
  • 需要注意的是这⾥有两个 pair ,不要混淆了,⼀个是 map 底层红⿊树节点中存的 pair ,另 ⼀个是 insert 返回值 pair。

operator[ ] 有插入,查找,修改,三个功能 ~

// operator的内部实现
mapped_type& operator[] (const key_type& k)
{// 1、如果k不在map中,insert会插⼊k和mapped_type默认值,// 同时[]返回结点中存储mapped_type值的引⽤,那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能// 2、如果k在map中,insert会插⼊失败,但是insert返回pair对象的first是指向key结点的迭代器,// 返回值同时[]返回结点中存储mapped_type值的引⽤,所以[]具备了查找+修改的功能pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

operator[ ]的使用:

确定key存在才能使用[ ]查找~要不就变成插入了~

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插入{ "insert", string() }dict["insert"];// 插入+修改dict["left"] = "左边";// 修改dict["left"] = "左边、剩余";// key存在->查找cout << dict["left"] << endl;return 0;
}

 使用find统计次数:

int main()
{// 利⽤find和iterator修改功能,统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// 先查找水果在不在map中// 1、不在,说明⽔果第⼀次出现,则插⼊{⽔果, 1}// 2、在,则查找到的节点中⽔果对应的次数++auto ret = countMap.find(str);if (ret == countMap.end()){countMap.insert({ str, 1 });}else{ret->second++;}}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

使用operator[ ] 统计次数:

int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// []先查找水果在不在map中// 1、不在,说明水果第⼀次出现,则插⼊{水果, 0},同时返回次数的引⽤,++⼀下就变成1次了// 2、在,则返回水果对应的次数++countMap[str]++;}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

3.7 multimap和map的差异

multimap和map的使⽤基本完全类似,主要区别点在于multimap⽀持关键值key冗余,那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异,这⾥跟set和multiset完全⼀样,⽐如find时,有多个key,返回中序第⼀个。其次就是multimap不⽀持[ ],因为⽀持key冗余,[ ]就只能⽀持插⼊了,不能⽀持修改

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

scrapy 爬取微博(五)【最新超详细解析】: 爬取微博文章

1 读取配置参数 爬取微博文章首先需要读取settings.py中的设置的配置变量&#xff0c;然后编写爬虫&#xff0c;读取的配置变量主要有爬取的关键词、时间范围、爬取区域等。 class WeiboSearchSpider(scrapy.Spider):name weibo_searchallowed_domains [weibo.com]settings…

Windows 环境下 MySQL5.5 安装与配置详解

Windows 环境下 MySQL5.5 安装与配置详解 目录 Windows 环境下 MySQL5.5 安装与配置详解一、MySQL 软件的下载二、安装 MySQL三、配置 MySQL1、配置环境变量2、安装并启动 MySQL 服务3、设置 MySQL 字符集4、为 root 用户设置登录密码 一、MySQL 软件的下载 1、登录网址&#…

基于Springboot+Vue的《计算机基础》网上考试系统(含源码数据库)

1.开发环境 开发系统:Windows10/11 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql5.7或8.0 数据库可视化工具: navicat 服务器: SpringBoot自带 apache tomcat 主要技术: Java,Springboot,mybatis,mysql,vue 2.视频演示地址 3.功能 系统中…

github项目--crawl4ai

github项目--crawl4ai 输出html输出markdown格式输出结构化数据与BeautifulSoup的对比 crawl4ai github上这个项目&#xff0c;没记错的话&#xff0c;昨天涨了3000多的star&#xff0c;今天又新增2000star。一款抓取和解析工具&#xff0c;简单写个demo感受下 这里我们使用cra…

ThreadLocal内存泄漏分析

一、ThreadLocal内存泄漏分析 1.1 ThreadLocal实现原理 1.1.1、set(T value)方法 查看ThreadLocal源码的 set(T value)方法&#xff0c;可以发现数据是存在了ThreadLocalMap的静态内部类Entry里面 其中key为使用弱引用的ThreadLocal实例&#xff0c;value为set传入的值。核…

031集——文本文件按空格分行——C#学习笔记

如下图&#xff0c;读取每行文本&#xff0c;每行文本再按空格分开读取一个字符串&#xff0c;输出到另一个文本&#xff1a; CAD环境下&#xff0c;代码如下&#xff1a; using Autodesk.AutoCAD.DatabaseServices; using Autodesk.AutoCAD.Runtime; using System; using Sys…

deepin 无线网络搜不到信号

搜索不到wifi信号和无法连接wifi&#xff0d;论坛&#xff0d;深度科技 (deepin.org)https://bbs.deepin.org/zh/post/218198

Python编码系列—Python责任链模式:打造灵活的请求处理流程

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

华为开源自研AI框架昇思MindSpore应用案例:计算高效的卷积模型ShuffleNet

如果你对MindSpore感兴趣&#xff0c;可以关注昇思MindSpore社区 ShuffleNet ShuffleNet网络介绍 ShuffleNetV1是旷视科技提出的一种计算高效的CNN模型&#xff0c;和MobileNet, SqueezeNet等一样主要应用在移动端&#xff0c;所以模型的设计目标就是利用有限的计算资源来达到…

解决VRM格式模型在Unity中运行出现头发乱飞等问题

1、问题 通过VRoidStudio制作导出的vrm格式的模型&#xff0c;放在unity中使用时&#xff0c;一运行就会出现头发乱飞&#xff0c;没有自然下垂的问题 2、解决方法 将模型下的secondary中的所有VRM Spring Bone脚本中的Drag Force改为1&#xff0c;Hit Radius改为0 修改后…

自定义注解加 AOP 实现服务接口鉴权以及内部认证

注解 何谓注解&#xff1f; 在Java中&#xff0c;注解&#xff08;Annotation&#xff09;是一种特殊的语法&#xff0c;用符号开头&#xff0c;是 Java5 开始引入的新特性&#xff0c;可以看作是一种特殊的注释&#xff0c;主要用于修饰类、方法或者变量&#xff0c;提供某些信…

基于定制开发与2+1链动模式的商城小程序搭建策略

摘要&#xff1a;本文探讨商城小程序的搭建策略&#xff0c;对比自主组建团队和第三方开发两种方式&#xff0c;强调以第三方开发模式为主的优势。阐述在第三方开发模式下&#xff0c;结合定制开发和21链动模式&#xff0c;如何搭建一款有助于企业商业模式创新与智能商业升级的…

【韩顺平Java笔记】第5章:程序控制结构

文章目录 102. 回顾上一章节103. 顺序控制103.1 顺序控制 104. 单分支使用104.1 分支控制 if-else 介绍104.2 单分支 105. 单分支流程图106. 双分支使用107. 双分支流程图108. 双分支练习题109. 多分支使用109.1 多分支的流程图 110. 多分支练习1111. 多分支练习2112. 嵌套分支…

大数据-151 Apache Druid 集群模式 配置启动【上篇】 超详细!

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…

网络通信——OSPF协议(基础篇)

这里基础是因为没有讲解OSPF中的具体算法过程&#xff0c;以及其中很多小细节。后续会更新。 目录 一.OSPF的基础信息 二.认识OSPF中的Router ID 三.OSPF中的三张表 四.OSPF中的度量方法&#xff08;计算开销值&#xff09; 五. OSPF选举DR和BDR&#xff08;就是这个区域…

Leetcode3295. 举报垃圾信息

Every day a Leetcode 题目来源&#xff1a;3295. 举报垃圾信息 解法1&#xff1a;哈希 将字符串数组 bannedWords 的字符串保存在一个哈希表里。 遍历字符串数组 message 的每一个字符串 mes&#xff0c;如果 mes 在哈希表中出现&#xff0c;count。 如果 count > 2&a…

剪刀面的做法

1 面和水称重准备好&#xff0c;鸡蛋敲孔流入面粉中两个蛋清。 2 边下水边和面&#xff0c;每次下水不要太多&#xff0c;这是和硬面要注意的&#xff0c;下水多&#xff0c;水用完了&#xff0c;面还没和起来&#xff0c;一边揉面一边搓面盆周围&#xff0c;这样可以使盆光&a…

WebRTC入门

主要参考资料&#xff1a; WebRTC 在 ESP32 系列硬件平台上的实现: https://www.bilibili.com/video/BV1AEHseWEda/?spm_id_from333.337.search-card.all.click&vd_sourcedd284033cd0c4d1f3f59a2cd40ae4ef9 火山 RTC豆包大模型&#xff0c;给用户体验装上银色子弹: https:…

python的内存管理机制

python的内存管理机制主要分为三个部分&#xff1a;引用计数、垃圾回收和内存池机制。 引用计数机制&#xff1a; python通过维护每个对象的引用计数来跟踪内存中的对象。当对象被创建时就会有一个引用计数&#xff0c;当对象不再被使用时&#xff0c;引用计数为0&#xff0c…

SSE的使用

文章目录 SSE的使用前提需求SSE简介使用demo客户端&#xff08;HTML&#xff09;服务端 SSE API常用方法&#xff1a;事件&#xff1a;自定义关联事件&#xff1a; 服务端数据处理 SSE的使用 前提需求 web开发过程中需要前后端进行实时数据或者定时数据推送的需求中&#xff…