【C++进阶04】STL中map、set、multimap、multiset的介绍及使用

在这里插入图片描述

一、关联式容器

vector/list/deque…
这些容器统称为序列式容器
因为其底层为线性序列的数据结构
里面存储的是元素本身

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

二、键值对

“键值对”用来表示具有一一对应关系的一种结构
该结构中一般只包含两个成员变量key和value
key代表键值，value表示与key对应的信息
比如：

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

SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

三、set

3.1 树形结构的关联式容器

根据应用场景的不同
C++STL总共实现了
两种不同结构的管理式容器：树型结构与哈希结构
树型结构的关联式容器主要有四种：
map、set、multimap、multiset
底层都是使用平衡搜索树(红黑树)来实现
容器中的元素是一个有序的序列

3.2 set的介绍

  1. set是按照一定次序存储元素的容器
    与map/multimap不同的是
    map/multimap中存储的是真正的键值对<key, value>
    set中只放value，但在底层实际存放的是由<value, value>构成的键值对

  2. 在set中，元素是唯一的
    元素的value就是key，类型为T
    set元素可以插入或删除，但不能修改
    map不能修改key，但可以修改value值
    set中插入元素时，只需要插入value即可，不需要构造键值对

  3. set中的元素总是按内部比较对象(类型比较)
    默认按照小于来比较
    所指示的特定“严格弱排序”准则进行排序
    使用set的迭代器遍历set中的元素，可以得到有序序列

  4. set容器通过key访问单个元素的速度通常比
    unordered_set容器慢，但它们允许根据顺序对
    子集进行直接迭代

  5. set中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2​n

set中的元素之所以不允许修改是怕破坏搜索规则

3.3 set的定义及使用

set的定义

set<int> s1; // 构造int类型的空容器

set<int> s2(s1); // 拷贝构造

string str("abcd");
set<char> s3(str.begin(), str.end()); // 迭代器构造某段区间

set<int, greater<int>> s4; // 比较方式改为大于

set的各个接口跟之前学的vector、list差不多
就不多介绍
set的使用

void test_set()
{
	set<int> s;
	// 插入元素并去重
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(3);

	// 搜索树不允许修改key，可能会破坏搜索的规则
	// 1. 迭代器遍历容器
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	// 2. 范围for遍历容器
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 删除元素
	s.erase(1);
	
	// 查找删除
	set<int>::iterator pos = s.find(2);
	if (pos != s.end())
		s.erase(pos);

	// 计算容器中值为3的元素
	cout << s.count(3) << endl;

	// 清空容器
	s.clear();

	// 交换两个容器的数据
	set<int> tmp{ 5, 7, 9 };
	s.swap(tmp);
}

// 输入一个值，查找在不在
void test_set2()
{
	set<int> s;
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(3);
	s.insert(3);

	int x;
	while (cin >> x)
	{
		/*
		set<int>::iterator it = s.find(x);
		if (it != s.end())
		{
			cout << "在" << endl;
		}
		else
		{
			cout << "不在" << endl;
		}
	*/
		if (s.count(x))
		{
			cout << "在" << endl;
		}
		else
		{
			cout << "不在" << endl;
		}
	}
}

multiset 允许冗余，其他跟set还是一样的

void test_set3()
{
	multiset<int> s;
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(3);
	s.insert(3);

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 有多个key，find找中序的第一个key
}

四、map

4.1 map的介绍

  1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元
    素，使用迭代器遍历map中的元素，可以得到一个有序序列

  2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的
    内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型
    value_type绑定在一起，为其取别名称为pair：typedef pair<const key, T> value_type;

  3. map容器中的键值key不能修改，但元素值value可以修改
    因为map底层是根据每个元素的键值key构建的

  4. 在内部，map中的元素总是按照键值key进行比较排序的
    不传内部比较对象时，map中元素键值key默认按小于比较

  5. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序
    对元素进行直接迭代

  6. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value

  7. map的底层是平衡二叉搜索树(红黑树)
    map查找某个元素时间复杂度为 l o g N log N logN

4.2 map的定义及使用

map的定义

// 构造一个key为string，value为char的容器
map<string, char> m1; 

// 构造一个跟m1一样的容器
map<string, char> m2(m1);

// 迭代器构造m2的某段区间的容器
map<string, char> m3(m2.begin(), m2.end());

// key的比较方式改成大于
map<string, char, greater<string>> m4;

map的插入和删除
在这里插入图片描述
value_type是pair的别名

typedef pair<const key, T> calue_type;

因此插入时需要构造一个pair的匿名对象

void test_map()
{
	map<string, string> dict;
	
	// 构造一个pair的匿名对象去插入
	dict.insert(pair<string, string>("int", "整型")); 
	
	// 用pair代码会很长，更常用的是make_pair
	// make_pair是一个函数模板,能通过传参自动推导类型
	dict.insert(make_pair("sort", "排序")); 
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("count", "计数"));

	// 已经有的key,会插入失败
	dict.insert(make_pair("count", "(计数)")); 
	
	// map<string, string>::iterator dit = dict.begin();
	auto dit = dict.begin();
	while (dit != dict.end())
	{
		// 直接*dit无法通过编译.C++不支持返回两个值
		// dit解引用后是一个pair的结构体,里面有两个值,并不支持流插入
		// cout << (*dit).first << ":" << (*dit).second << endl;
		cout << dit->first << ":" << dit->second << endl; // 结构体里的指针一般用箭头
		dit++;
	}
	cout << endl;

	// 根据key值删除
	dict.erase(string);
	
	//迭代器删除
	map<string, string>::iterator pos = dict.find(sort);
	if (pos != dict.end())
		dict.erase(pos);
}

insert的返回值是pair
pair第一个成员是map的迭代器类型
第二个成员是bool类型

  • 若插入元素的键值key在map中不存在
    insert插入成功，并返回插入后元素的迭代器和true
  • 若插入元素的键值key在map中已存在
    则insert插入失败，并返回map中键值为key元素的迭代器和false

map的operator[ ]
在这里插入图片描述
operator[ ] 的返回值
在这里插入图片描述
[ ]operator实现的逻辑分为以下3个步骤：

  1. 调用insert函数插入键值对
  2. 拿出从insert函数获取到的迭代器
  3. 返回该迭代器位置元素的值value

代码分解

mapped_type& operator[] (const key_type& k)
{
	//1. 调用insert函数插入键值对
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2. 拿出从insert函数获取到的迭代器
	iterator it = ret.first;
	//3. 返回该迭代器位置元素的值value
	return it->second;
}

[ ]的插入、修改、查找、插入+修改
以及统计水果出现的次数

void test_map2()
{
	string arr[] = { "苹果", "香蕉", "西瓜", "梨子", "香蕉", "西瓜", "西红柿", "香蕉", "西瓜", "苹果", "西红柿" };
	map<string, int> countMap;

	//for (auto e : arr) // 统计水果出现次数
	//{
	//	map<string, int>::iterator it = countMap.find(e);
	//	if (it == countMap.end())
	//	{
	//		countMap.insert(make_pair(e, 1));
	//	}
	//	else
	//	{
	//		it->second++;
	//	}
	//}

	for (auto& e : arr) // 方括号统计水果出现次数
	{
		countMap[e]++; // [] 的三个功能: 插入、修改、查找、插入+修改
	}

	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl; // 结构体里的指针一般用箭头
	}
	cout << endl;

}

// countMap[e]++; 这段代码底层实现
// V& operator[](const K& key)
// {
// 	pair<iterator, bool> ret = insert(make_pair(key, V()));
// 	return ret.first->second;
//}

void test_map3()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("count", "计数"));
	dict.insert(make_pair("count", "(计数)"));

	dict["left"]; // 插入
	dict["right"] = "右"; // 插入+修改
	dict["string"] = "(字符串)"; // 修改
	cout << dict["string"] << endl; // 查找
	cout << dict["endl"] << endl; // 查找

	auto dit = dict.begin();
	while (dit != dict.end())
	{
		cout << dit->first << ":" << dit->second << endl; 
		dit++;
	}
	cout << endl;
}

[ ]operator的返回值是key的value的引用
所以我们对该函数返回值的修改
实际就是对键值key的value的修改

multimap
multimap跟map基本一样
只是multimap允许键值冗余
find返回值是返回搜索树中序第一个键值
为key的元素的迭代器

由于冗余，调用operator[ ]时
返回键值应为哪个key的value引用
而存在歧义，因此multimap没有operator[ ]接口

如果支持迭代器就一定支持范围for
因为范围for的底层就是迭代器

五、map和set的区别

  1. map元素是key-value(关键字-值)对
    set元素是关键字
    map和set都不允许插入重复关键字

  2. set迭代器是const
    所以不允许修改元素值
    map可以修改value，但不能修改key
    map和set底层红黑树依靠关键字保持有序性
    所以不允许修改关键字

  3. map支持下标操作，set则不支持
    注意：map下标通过insert实现
    也就是尝试插入一个查询键值对
    如果存在则返回该键值对

✨✨✨✨✨✨✨✨
本篇博客完，感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见
✨✨✨✨✨✨✨✨

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

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

相关文章

MongoDB高级集群架构设计

MongoDB高级集群架构设计

两地三中心集群架构设计 容灾级别 RPO & RTO RPO&#xff08;Recovery Point Objective&#xff09;&#xff1a;即数据恢复点目标&#xff0c;主要指的是业务系统所能容忍的数据丢失量。RTO&#xff08;Recovery Time Objective&#xff09;&#xff1a;即恢复时间目标&…
阅读更多...
赋能软件开发：生成式AI在优化编程工作流中的应用与前景

赋能软件开发：生成式AI在优化编程工作流中的应用与前景

随着人工智能&#xff08;AI&#xff09;技术的快速发展&#xff0c;特别是生成式AI模型如GPT-3/4的出现&#xff0c;软件开发行业正经历一场变革&#xff0c;这些模型通过提供代码生成、自动化测试和错误检测等功能&#xff0c;极大地提高了开发效率和软件质量。 本文旨在深入…
阅读更多...
ArcGIS中style文件的导入及lyr的文件的使用

ArcGIS中style文件的导入及lyr的文件的使用

地图是地理信息的重要载体&#xff0c;科学的配色方案可以有效地传递地理信息&#xff0c;而美观协调的配色方案也是我们进行地图符号化设计的重要内容。在日常工作中&#xff0c;我们常常苦恼于自带颜色不能满足需要或是希望使用现成的颜色模板&#xff0c;自定义配色方案导入…
阅读更多...
一文详解VScode 的远程开发

一文详解VScode 的远程开发

VS code登录服务器后进行编码和调试&#xff0c;VS code上的所有功能都可以使用&#xff0c;和在本地开发基本无区别。 一、配置免密远程登录 因为是要远程登录&#xff0c;那么需要通过使用ssh进行密钥对登录&#xff0c;这样每次登录服务器就可以不用输入密码了。 先来一句官…
阅读更多...
Python综合数据分析_RFM用户分层模型

Python综合数据分析_RFM用户分层模型

文章目录 1.数据加载2.查看数据情况3.数据合并及填充4.查看特征字段之间相关性5.聚合操作6.时间维度上看销售额7.计算用户RFM8.数据保存存储(1).to_csv(1).to_pickle 1.数据加载 import pandas as pd dataset pd.read_csv(SupplyChain.csv, encodingunicode_escape) dataset2…
阅读更多...
Qt - QML框架

Qt - QML框架

文章目录 1 . 前言2 . 框架生成3 . 框架解析3.1 qml.pro解析3.2 main.cpp解析3.3 main.qml解析 4 . 总结 【极客技术传送门】 : https://blog.csdn.net/Engineer_LU/article/details/135149485 1 . 前言 什么是QML&#xff1f; QML是一种用户界面规范和编程语言。它允许开发人员…
阅读更多...
C++类与对象基础(6)

C++类与对象基础(6)

(注&#xff1a;本篇文章介绍部分内容时&#xff0c;需要用到上盘文章中日期类的代码&#xff0c;文章链接如下&#xff1a;C类与对象基础(5)——日期类的实现-CSDN博客​​​​​​&#xff09; 目录 1. 运算符重载的相关补充&#xff1a; 1.1流运算符重载出现的问题&#x…
阅读更多...
C语言爬虫程序采集58商铺出租转让信息

C语言爬虫程序采集58商铺出租转让信息

为了找到一个好店铺好位置&#xff0c;往往要花费很大精力和财力过去寻找&#xff0c;就有有某些出租平台但是一个个查找下来也是十分麻烦&#xff0c;所以我利用我们的C语言基础&#xff0c;给大家写个商品转租的爬虫程序&#xff0c;让找店铺不在那么费时费力&#xff0c;至少…
阅读更多...
图像去噪——CBDNet网络训练自己数据集及推理测试，模型转ONNX模型（详细图文教程）

图像去噪——CBDNet网络训练自己数据集及推理测试，模型转ONNX模型（详细图文教程）

CBDNet 主要由两个子网络组成&#xff1a;噪声估计子网络和去噪子网络。噪声估计子网络用于估计图像的噪声水平&#xff0c;而去噪子网络用于去除图像中的噪声。 CBDNet 的优势在于&#xff1a; 它采用了更真实的噪声模型&#xff0c;既考虑了泊松-高斯模型&#xff0c;还考虑…
阅读更多...
37-数据类型，一元运算符typeof，字符串string，布尔Boolean，未定义undefined,空null，数组Array

37-数据类型，一元运算符typeof，字符串string，布尔Boolean，未定义undefined,空null，数组Array

<body><script>// 0.1加0.2不等于0.3&#xff0c;正确的运算方法如下console.log(0.10.2);var x 0.1;var y 0.2;console.log((x*10y*10)/10);</script> </body> 简单数据类型&#xff08;5种&#xff09;&#xff1a;数字number&#xff0c;字符串s…
阅读更多...
MFC Socket和合信CTMC M266ES 运动控制型PLC通信进行数据交换

MFC Socket和合信CTMC M266ES 运动控制型PLC通信进行数据交换

前言 1、前两篇文章通过对Snap7和S7-1200/S7-1500PLC的通信进行了详细的介绍。Snap7的优点开源性强、使用方便易于上手&#xff0c;跨平台和可移植性性强。但是Snap7也有个缺点就是只能访问PLC的DB、MB、I、Q区进行数据读写&#xff0c;不能对V区进行读写,有人说可以读写V区&am…
阅读更多...
【Java 设计模式】23 种设计模式

【Java 设计模式】23 种设计模式

文章目录 设计模式是什么计算机行业里的设计模式创建型模式&#xff08;共 5 种&#xff09;结构型模式&#xff08;共 7 种&#xff09;行为型模式&#xff08;共 11 种&#xff09; 总结 设计模式是什么 “每一个模式描述了一个在我们周围不断重复发生的问题&#xff0c;以及…
阅读更多...
docker打包介绍

docker打包介绍

最近在做一个开源项目&#xff0c;遇到开发者问各种问题&#xff0c;发现都是系统和软件版本的差异引起的。于是了解了一下docker的使用&#xff0c;发现docker真是个好东东&#xff0c;基本解决了各种版本差异的问题&#xff0c;真正做到了一键部署使用。 先熟悉一下docker里…
阅读更多...
c++学习：容器stack栈+queue+map（简易输入法）+deque

c++学习：容器stack栈+queue+map（简易输入法）+deque

目录 stack 模板原型 头文件 模板的成员类型和成员对象和成员函数 栈类模板的容器对象 实例 queue 模板原型 头文件 模板的成员类型和成员对象和成员函数 队列类模板的容器对象 实例 map 模板原型 头文件 模板的成员类型和成员对象和成员函数 关联类模板的容器…
阅读更多...
debian cups 打印机共享

debian cups 打印机共享

apt update apt install -y cups localhost:631 add printer root 密码 添加打印机 然后在windows上设置 http://ip:631/printers/HP_LaserJet_1022
阅读更多...
Vue3---安装路由

Vue3---安装路由

介绍 在Vue3项目中安装路由 示例 第一步&#xff1a;执行npm命令安装路由 npm install vue-router4第二步&#xff1a;在项目的src文件夹下创建router子文件夹 第三步&#xff1a;创建index.js和routes.js文件&#xff0c;以下为文件的代码 //通过vue-router插件实现模板…
阅读更多...
Elementui Radio单选框取消选中

Elementui Radio单选框取消选中

问题&#xff1a; 最近开发一个后台项目的时候用到了单选框&#xff0c;而客户的要求是默认选择一个选项&#xff0c;然后点击可以取消选中。不想自己在手写一个Radio组件&#xff0c;只能在elementui的单选框上修改一下下啦。 1. .native的作用 .native的作用是在给组件添加修…
阅读更多...
Typecho 最新XC主题 去除域名授权全解密源码

Typecho 最新XC主题 去除域名授权全解密源码

Typecho 最新XC主题 去除域名授权全解密源码 这是一款多样式主题&#xff0c;首页支持六种主题样式&#xff0c;支持Pjax优化访问速度&#xff0c;多种单页&#xff0c;如友链、说说等。评论支持表情&#xff0c;自定义编辑器&#xff0c;支持其他样式功能。该主题功能性挺高&…
阅读更多...
代码随想录算法训练营第二十五天 | 216.组合总和III、17.电话号码的字母组合

代码随想录算法训练营第二十五天 | 216.组合总和III、17.电话号码的字母组合

216.组合总和III 题目&#xff1a; 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次&#xff0c;组合可以以任何顺序返回。 思路&…
阅读更多...
3D Surface Subdivision Methods 3D 曲面细分方法

3D Surface Subdivision Methods 3D 曲面细分方法

文章目录 1 介绍2 细分法3 一个简单的例子&#xff1a;Catmull-Clark 细分4 Catmull-Clark 细化5 Refinement Host6 Geometry Policy7 四种细分方法8 示例&#xff1a;自定义细分方法9 实施历史 原文地址: https://doc.cgal.org/latest/Subdivision_method_3/index.html#Chapte…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站