【C++】map 和 set

文章目录

  • 一、关联式容器与键值对
    • 1、关联式容器
    • 2、键值对 pair
    • 3、树形结构的关联式容器
  • 二、set
    • 1、set 的介绍
    • 2、set 的使用
  • 三、multiset
  • 四、map
    • 1、map 的介绍
    • 2、map 的使用
  • 五、multimap

一、关联式容器与键值对

1、关联式容器

在C++初阶的时候,我们已经接触了 STL 中的部分容器并进行了模拟实现,比如 vector、list、stack、queue 等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身;

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

2、键值对 pair

键值对是用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量 – key 和 value;其中 key 代表键值,value 代表与 key 对应的信息。

我们在上一节学习二叉搜索树的时候提到的 KV 模型 (key-value 模型) 中的 KV 其实就是键值对;我们可以用上一节中提到的英汉互译的例子来理解 key-value 键值对 – 现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义。

STL 中键值对的定义如下:(SGI 版本)

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;   //key
	T2 second;  //value
	pair() : first(T1()), second(T2())  //默认构造
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};

可以看到,C++ 中的键值对是通过 pair 类来表示的,pair 类中的 first 就是键值 key,second 就是 key 对应的信息 value;那么以后我们在设计 KV 模型的容器时只需要在容器/容器的每一个节点中定义一个 pair 对象即可;

这里有的同学可能会有疑问,为什么不直接在容器中定义 key 和 value 变量,而是将 key、value 合并到 pair 中整体作为一个类型来使用呢?这是因为 C++ 一次只能返回一个值,如果我们将 key 和 value 单独定义在容器中,那么我们就无法同时返回 key 和 value;而如果我们将 key、value 定义到另一个类中,那我们就可以直接返回 pair,然后再到 pair 中分别去取 first 和 second 即可。

make_pair 函数

由于 pair 是类模板,所以我们通常是以 显式实例化 + 匿名对象 的方式来进行使用,但是由于显式实例化比较麻烦,所以 C++ 还提供了 make_pair 函数,其定义如下:

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

如上,make_pair 返回的是一个 pair 的匿名对象,匿名对象会自动调用 pair 的默认构造完成初始化;但由于 make_pair 是一个函数模板,所以模板参数的类型可以根据实参来自动推导完成隐式实例化,这样我们就不用每次都显式指明参数类型了。

注:由于 make_pair 使用起来比 pair 方便很多,所以我们一般都是直接使用 make_pair,而不使用 pair

3、树形结构的关联式容器

根据应用场景的不同,STL 总共实现了两种不同结构的关联式容器 – 树型结构与哈希结构;树型结构的关联式容器主要有四种 – map、set、multimap、multiset,这四种容器的共同点是使用平衡二叉搜索树作为其底层结构,容器中的元素是一个有序的序列;本文将介绍这四个容器的使用。


二、set

1、set 的介绍

set 是按照一定次序存储元素的容器,其底层是一棵平衡二叉搜索树,由于二叉搜索树的每个节点的值满足左孩子 < 根 < 右孩子,并且二叉搜索树中没有重复的节点,所以 set 可以用来排序、去重和查找,同时由于这是一棵平衡树,所以 set 查找的时间复杂度为 O(logN),效率非常高

同时,set 是一种 K模型 的容器,也就是说,set 中只有键值 key,而没有对应的 value,并且每个 key 都是唯一的;set 中的元素也不允许修改,因为这可能会破坏搜索树的结构,但是 set 允许插入和删除。image-20230323180144330

总结:

  1. set 是K模型的容器,所以 set 中插入元素时,只需要插入 key 即可,不需要构造键值对;
  2. set中的元素不可以重复,因此可以使用set进行去重;
  3. 由于 set 底层是搜索树,所以使用 set 的迭代器遍历 set 中的元素,可以得到有序序列,即 set 可以用来排序;
  4. set 默认使用的仿函数为 less,所以 set 中的元素默认按照小于来比较;
  5. 由于 set 底层是平衡树搜索树,所以 set 中查找某个元素,时间复杂度为 O(logN);
  6. set 中的元素不允许修改,因为这可能破坏搜索树的结构;
  7. set 中的底层使用平衡二叉搜索树 (红黑树) 来实现。

注:可能有的同学对 O(logN) 的时间复杂度没有什么具体的概念,那么我们可以列举一组数据大家就很清楚了:set 从1000个数据找查找某个数据最多找10次,从100万个数据中找某一个数据最多找20次,从10亿个数据中找某一个数据最多找30次;换一种说法,如果以身份证号作为 key 值存入 set 中 (假设内存足够),那么我们从地球所有人类中查找某一个身份证号对应的人时最多只用找 31 次;相信现在大家对 O(logN) 是什么量级的存在已经有了很清楚的认识了。

2、set 的使用

构造

和传统容器一样,set 也支持单个元素构造、迭代器区间构造以及拷贝构造:image-20230323180553971

迭代器

迭代器也一样,包括正向迭代器和反向迭代器,正向和反向又分为 const 和 非const:image-20230323181709675

修改

set 有如下修改操作:image-20230323182250500

其中 swap 就是交换两棵树的根,clear 就是释放树中的所有节点,emplace 和 emplace_hint 我们放在 C++11 章节中学习,大家现在不用管它;最重要的修改操作是 insert 和 erase;

insert 支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间,我们学会第一个即可,插入的过程就是二叉搜索树的插入过程;需要注意的是 insert 的返回值是 pair 类型,pair 中第一个元素代表插入的迭代器位置,第二个元素代表是否插入成功 (插入重复节点会返回 false):image-20230323182503760

erase 也有三种,常用的是第一种和第二种,删除指定键值的数据和删除指定迭代器位置的数据:image-20230323183111734

操作

set 还有一些其他操作相关的函数:image-20230323183411290

其中比较重要的只有 find,由于 set 中不允许出现相同的 key,因此在 set 中 count 函数的返回值只有1/0,可以说没有什么价值,set 中定义 count 主要是因为 count 在 multiset 中有作用,这里是为了保持一致;lower_bound 和 upper_bound 是得到一个左闭右开的迭代器区间,然后我们可以对这段区间进行某些操作,但实际中其实没什么人用;

find 的作用是在搜索树中查找 key 对应的节点,然后返回节点位置的迭代器,如果找不到,find 会返回 end():image-20230323184212751

set 使用范例

void set_test() {
	// 用数组array中的元素构造set
	int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
	set<int> s(array, array + sizeof(array) / sizeof(array[0]));
	cout << s.size() << endl;

	// 正向打印set中的元素,从打印结果中可以看出:set可去重
	for (const auto& e : s)
		cout << e << " ";
	cout << endl;

	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
		cout << *it << " ";
	cout << endl;

	// 查找+删除
	set<int>::iterator pos = s.find(9);
	if (pos != s.end())
		s.erase(pos);
	//输出key为9的节点的个数
	cout << s.count(9) << endl;  
}

image-20230323184825402

如果大家对 set 的使用还有不清楚的地方,建议查阅 set 文档:set - C++ Reference (cplusplus.com)


三、multiset

multiset 的介绍

multiset 也是 K模型 的容器,它和 set 唯一的区别在于 multiset 中允许存在重复的 key 值节点,所以 multiset 可以用来排序和查找,但是不能用来去重。

multiset 的使用

multiset 的使用其实和 set 也几乎一样,唯一需要注意的是 find 和 count 函数 – 由于 multiset 中允许存在重复 key 值的节点,所以 multiset 中 count 函数就有作用了,我们可以通过 count 函数来统计同一 key 中在 multiset 中的数量:image-20230323194646245

multiset 中 find 函数的使用也和 set 有所区别 – 由于 set 中没有重复的节点,所以 find 时要么返回该节点位置的迭代器,要么返回 end();而 multiset 中可能有重复的节点,所以 find 时返回的是同一 key 值中的哪一个节点呢?实际上 find 返回的是中序遍历过程中第一个匹配的节点位置的迭代器image-20230323195419090

multiset 使用范例

void multiset_test() {
	// 用数组array中的元素构造multiset
	int array[] = { 1, 3, 5, 7, 3, 2, 4, 6, 8, 0, 1, 3, 5, 7, 3, 2, 4, 6, 8, 3 };
	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
	cout << s.size() << endl;

	// 正向打印multiset中的元素,从打印结果中可以看出:multiset允许重复元素的出现
	for (const auto& e : s)
		cout << e << " ";
	cout << endl;

	//如果查找的key在multiset中有多个,则返回中序遍历中遇到的第一个节点的迭代器
	multiset<int>::iterator pos = s.find(3);
	while (pos != s.end()) {
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

	// 查找+删除
	//输出key为3的节点的个数
	cout << s.count(3) << endl;
	pos = s.find(3);
	if (pos != s.end())
		s.erase(pos);
	cout << s.count(3) << endl;
}

image-20230323200250179

如果大家对 multiset 的使用还有不清楚的地方,建议查阅 multiset 文档:multiset - C++ Reference (cplusplus.com)


四、map

1、map 的介绍

map 和 set 一样都是按照一定次序存储元素的容器,其底层也是一棵平衡二叉搜索树;和 set 不同的是,map 是 KV模型 的容器,在map 中,键值 key 通常用于排序和惟一地标识元素,而值 value中 用于存储与此键值 key 关联的内容,键值 key 和值value的类型可以不同;在 map 内部,key-value 通过成员类型 pair 绑定在一起,也就是我们文章开始提到的键值对

需要注意的是:map 中的元素是按照键值 key 进行比较排序的,而与 key 对应的 value 无关,同时,map 中也不允许有重复 key 值的节点;map 也可用于排序、查找和去重,且 map 查找的时间复杂度也为 O(logN)。image-20230323201008877

特别注意:map 允许修改节点中 key 对应的 value 的值,但是不允许修改 key,因为这样可能会破坏搜索树的结构

2、map 的使用

构造

image-20230323201622323

迭代器

image-20230323201653112

修改

image-20230323202623919

修改中的重点的仍然是 insert 和 erase,swap 为交换两棵树的根,clear 为释放树中的每一个节点;

和 set 一样,map 的 insert 也支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间,我们还是学会第一个即可,插入的过程就是二叉搜索树的插入过程;需要注意的是 insert 的返回值是 pair 类型,pair 中第一个元素代表插入的迭代器位置,第二个元素代表是否插入成功 (插入重复节点会返回 false)::image-20230323202826103

erase 一样也有三种,常用的是第一种和第二种,删除指定键值的数据和删除指定迭代器位置的数据:image-20230323203132825

元素访问

需要重点注意的是,map 重载了 [] 运算符,其函数原型如下:

//mapped_type: pair中第二个参数,即first
//key_type: pair中第一个参数,即second
mapped_type& operator[] (const key_type& k);

函数定义如下:

mapped_type& operator[] (const key_type& k) 
{
	(*((this->insert(make_pair(k, mapped_type()))).first)).second;
}

可以看到,map 中 operator[] 函数的实现看起来非常复杂,我们可以将它拆解一下:

V& operator[] (const K& k)
{
	pair<iterator, bool> ret = insert(make_pair(k, V()));
    //return *(ret.first)->second;
	return ret.first->second;
}

可以看到,operator[] 函数会先向 map 中插入 k,这里插入的结果有两种 – 如果 map 中已经有与该值相等的节点,则插入失败,返回的 pair 中存放着该节点位置的迭代器和false;如果 map 中没有与该值相等的节点,则会向 map 中插 key 值等于 k 的节点,该节点对应的 value 值为 V 默认构造的缺省值;

然后,operator[] 会取出 pair 中的迭代器 (ret.first),然后对迭代器进行解引用得到一个 pair<k, v> 对象,最后再返回排 pair 对象中的 second 的引用,即 key 对应的 value 的引用;所以我们可以在函数外部直接修改 key 对应的 value 的值image-20230323204954760

所以,map 中的 operator[] 是集插入、查找、修改为一体的一个函数;示例如下:image-20230323205942366

注意:

  1. 这里修改的是 key 对应的 value,而并没有修改 key,所以并没有破坏搜索树的结构;
  2. 我们上面拆解 operator[] 函数时之所以能将 *(ret.first)->second 改写为 ret.first->second 是因为编译器为了可读性省略了一个 -> 操作符,实际上应该是 ret.first->->second;关于这里的细节我在 list 模拟实现 中说过,有兴趣的可以去看看。

操作

和 set 一样,map 中有 count 函数是因为 multimap 需要count 函数,这里是为了保持一致性:image-20230323210452737

map 使用范例

void map_test() {
	map<string, string> m;
	//向map中插入元素的方式:用pair直接来构造键值对
	m.insert(pair<string, string>("peach", "桃子"));

	//为了方便,我们建议直接用make_pair函数来构造键值对
	m.insert(make_pair("banan", "香蕉"));

	// 借用operator[]向map中插入元素,operator[]的原理如下:
	//--------------------------------------------------------------------------------------//
	// 用<key, T()>构造一个键值对,然后调用insert()函数将该键值对插入到map中
	// 如果key已经存在,插入失败,insert函数返回该key所在位置的迭代器
	// 如果key不存在,插入成功,insert函数返回新插入元素所在位置的迭代器
	// operator[]函数最后将insert返回值键值对中的value返回
	// 注意:通过[]插入的键值对的value使用默认构造完成初始化,我们需要通过修改[]的返回值来对其重新赋值
	//---------------------------------------------------------------------------------------//
	// 将<"apple", "">插入map中,插入成功,返回value的引用,将“苹果”赋值给该引用结果,
	m["apple"] = "苹果";

	// 用迭代器去遍历map中的元素,可以得到一个按照key排序的序列
	for (auto& e : m)
		cout << e.first << ":" << e.second << endl;
	cout << endl;

	// map中的键值对key一定是唯一的,如果key存在将插入失败
	auto ret = m.insert(make_pair("peach", "桃色"));
	if (ret.second)
		cout << "<peach, 桃色>不在map中, 已经插入" << endl;
	else
		cout << "键值为 peach 的元素已经存在:" << ret.first->first << "--->" << ret.first->second << " 插入失败" << endl;

	// 删除key为"apple"的元素
	m.erase("apple");
	if (1 == m.count("apple"))
		cout << "apple还在" << endl;
	else
		cout << "apple被吃了" << endl;
}

image-20230323211450381

如果大家对 map 的使用还有不清楚的地方,建议查阅 map 使用文档:map - C++ Reference (cplusplus.com)


五、multimap

和 set 与 multiset 的关系一样,multimap 存在的意义是允许 map 中存在 key 值相同的节点,multimap 与map 的区别和 multiset 与 set 的区别一样 – find 返回中序遍历中遇到的第一个节点的迭代器,count 返回和 key 值相等的节点的个数:image-20230323211919225

image-20230323211950647

需要注意的是,multimap 中并没有重载 [] 运算符,因为 multimap 中的元素是可以重复的,如果使用 [] 运算符,会导致多个元素的 key 值相同,无法确定具体访问哪一个元素。

如果大家对 multimap的使用还有不清楚的地方,建议查阅 multimap文档:multimap - C++ Reference (cplusplus.com)


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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于SpringBoot的酒店管理系统

系统环境 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/i…

matplotlib参数详解

文章目录一、简介二、安装与调用三、绘图与风格设置3.1、绘图标记3.1.1、标记类型&#xff08;marker*&#xff09;3.1.2、标记大小、内部和边框颜色&#xff08;ms10、mfcr、mecg&#xff09;3.2、绘图线3.2.1、线类型&#xff08;linestyle--&#xff09;3.2.2、线宽&#xf…

C++入门教程||C++ 字符串||

C 字符串C 字符串C 提供了以下两种类型的字符串表示形式&#xff1a;C 风格字符串C 引入的 string 类类型C 风格字符串C 风格的字符串起源于 C 语言&#xff0c;并在 C 中继续得到支持。字符串实际上是使用 null 字符 终止的一维字符数组。因此&#xff0c;一个以 null 结尾的…

大文件上传

上图就是大致的流程一、标题图片上传课程的标题图片Ajax发送请求到后端后端接收到图片使用IO流去保存图片&#xff0c;返回图片的信息对象JS回调函数接收对象通过$("元素id").val(值)&#xff0c;方式给页面form表达img标签src属性值&#xff0c;达到上传图片并回显二…

若依微服务(ruoyi-cloud)保姆版容器编排运行

一、简介 项目gitee地址&#xff1a;https://gitee.com/y_project/RuoYi-Cloud 由于该项目运行有很多坑&#xff0c;大家可以在git克隆拷贝到本地后&#xff0c;执行下面的命令使master版本回退到本篇博客的版本&#xff1a; git reset --hard 05ca78e82fb4e074760156359d09a…

扒一扒抖音是如何做线程优化的

背景 最近在对一些大厂App进行研究学习&#xff0c;在对某音App进行研究时&#xff0c;发现其在线程方面做了一些优化工作&#xff0c;并且其解决的问题也是之前我在做线上卡顿优化时遇到的&#xff0c;因此对其具体实现方案做了深入分析。本文是对其相关源码的研究加上个人理…

人员玩手机离岗识别检测系统 yolov5

人员玩手机离岗识别检测系统根通过pythonyolov5网络模型识别算法技术&#xff0c;人员玩手机离岗识别检测算法可以对画面中人员睡岗离岗、玩手机打电话、脱岗睡岗情况进行全天候不间断进行识别检测报警提醒。Python是一种由Guido van Rossum开发的通用编程语言&#xff0c;它很…

【2023.3.18 美团校招】

文章目录1. 小美剪彩带2. 最多修改两个字符&#xff0c;生成字典序最小的回文串1. 小美剪彩带 题意&#xff1a;找出区间内不超过k种数字子数组的最大长度 使用双指针的方式&#xff0c;用哈希表来统计每个数出现次数。在双指针移动的过程中&#xff0c;动态的维护区间内不同数…

难以置信,已经有人用 ChatGPT 做 Excel 报表了?

要问2023年初科技领域什么最火&#xff0c;那自然是 ChatGPT。 ChatGPT 由人工智能研究实验室 OpenAI 于2022年11月30日推出。上线短短5天&#xff0c;用户数量已突破100万&#xff0c;在今年2月份&#xff0c;用户数量已经突破1亿。 ChatGPT 是一个超级智能聊天机器人&#…

【java】笔试强训Day4【计算糖果、进制转换】

目录 ⛳一、单选题 1.下列与队列结构有关联的是&#xff08; &#xff09; 2.类所实现接口的修饰符不能为&#xff08; &#xff09; 3.下列关于栈叙述正确的是&#xff08; &#xff09; 4.下面关于abstract关键字描述错误的是&#xff08; …

9.0 自定义SystemUI下拉状态栏和通知栏视图(十五)之悬浮通知布局

1.前言在进行9.0的系统rom产品定制化开发中&#xff0c;在9.0中针对systemui下拉状态栏和通知栏的定制UI的工作开发中&#xff0c;原生系统的下拉状态栏和通知栏的视图UI在产品开发中会不太满足功能&#xff0c;所以根据产品需要来自定义SystemUI的下拉状态栏和通知栏功能&…

【jenkins部署】一文弄懂自动打包部署(前后台)

这里写目录标题序言软件安装jdkmaven配置maven阿里镜像以及本地库位置git安装安装jenkins插件安装环境配置创建项目配置gitee生成gitee WebHookmaven打包验证是否打包成功连接远程服务器并重启服务远程服务器生成私钥配置ssh项目配置ssh脚本vue项目打包nodejs安装下载配置环境变…

【C++进阶】位图和布隆过滤器

文章目录位图位图概念位图使用场景位图的结构构造setresettest完整代码布隆过滤器布隆过滤器概念布隆过滤器结构构造setresettest完整版代码位图 位图概念 所谓位图&#xff0c;就是用每一位来存放某种状态&#xff0c;适用于海量数据&#xff0c;数据无重复的场景。通常是用…

智能火焰与烟雾检测系统(Python+YOLOv5深度学习模型+清新界面)

摘要&#xff1a;智能火焰与烟雾检测系统用于智能日常火灾检测报警&#xff0c;利用摄像头画面实时识别火焰与烟雾&#xff0c;另外支持图片、视频火焰检测并进行结果可视化。本文详细介绍基于智能火焰与烟雾检测系统&#xff0c;在介绍算法原理的同时&#xff0c;给出Python的…

【数据结构与算法】设计循环队列

文章目录&#x1f451;前言如何设计循环队列设计循环队列整体的代码&#x1f4ef;写在最后&#x1f451;前言 &#x1f6a9;前面我们 用队列实现了一个栈 &#xff0c;用栈实现了一个队列 &#xff0c;相信大家随随便便轻松拿捏&#xff0c;而本章将带大家上点难度&#xff0c;…

【Linux】SIGCHLD信号

文章目录SIGCHLD信号SIGCHLD信号 回忆: 为了避免出现僵尸进程,父进程需要使用wait或waitpid函数等待子进程结束,父进程可以阻塞等待子进程结束,也可以非阻塞地查询的是否有子进程结束等待清理,即轮询的方式 如果采用阻塞等待:父进程阻塞就不能处理自己的工作了如果采用非阻塞等…

Python日志logging实战教程

一、什么是日志 在《网络安全之认识日志采集分析审计系统》中我们认识了日志。日志数据的核心就是日志消息或日志&#xff0c;日志消息是计算机系统、设备、软件等在某种刺激下反应生成的东西。 日志数据&#xff08;log data&#xff09;就是一条日志消息的内在含义&#xf…

第十四届蓝桥杯第三期模拟赛 【python】

第十四届蓝桥杯第三期模拟赛 【python】 文章目录第十四届蓝桥杯第三期模拟赛 【python】✨最小的十六进制&#xff08;python的16进制&#xff09;❓️问题描述答案提交&#x1f9e0;思路&#x1f5a5;︎参考答案✨Excel的列&#xff08;进制转化&#xff09;❓️问题描述答案…

串口通信(STM32演示实现)

目录 一、串行通信的概念 二、寄存器 2.1控制寄存器USART_CR1 2.2控制寄存器USART_CR2​编辑 2.3串口寄存器USART_BRR 2.4 USART_ISR 2.5USART_TDR 2.6USART_RDR​编辑 三、实现串口数据的收发 一、串行通信的概念 u通信&#xff0c;最少要有两个对象&#xff0c;一个收…

强化学习、监督学习、无监督学习是什么

1 强化学习 1.1 定义 强化学习是机器学习学习方式的一种&#xff0c;是让计算机实现从一开始完全随机的进行操作&#xff0c;通过不断试错的方式去总结出每一步的最佳行为决策&#xff0c;基于环境给予的反馈&#xff0c;去调整自己的行为决策&#xff0c;从而对未来的行为给…