Cpp::set map 的理解与使用(22)

文章目录

  • 前言
  • 一、预备知识
    • 关联式容器
    • 键值对
  • 二、set
    • 何为set?
    • set的使用
    • set的特点
    • multiset
  • 三、map
    • 何为map?
    • map中的operator[ ]
    • multimap
  • 总结


前言

  刚学完二叉搜索树,我们马上来感受一下直接与它相关的两个容器吧!


一、预备知识

关联式容器

  在以往的 STL 容器学习中,我们接触到的都是 序列式容器,比如 string、vector、list、deque 等,序列式容器的特点就是 底层为线性序列的数据结构,就比如 list,其中的节点是 线性存储 的,一个节点存储一个元素,其中存储的元素都可序,但未必有序

  关联式容器 则比较特殊,其中存储的是 <key, value> 的 键值对,这就意味着可以按照 键值大小 key 以某种特定的规则放置于适当的位置,关联式容器 没有首尾的概念,因此没有头插尾插等相关操作,本文中学习的 set 和 map 就属于 关联式容器

在这里插入图片描述

键值对

  键值对是 一种用来表示具有一一对应关系的结构,该结构中一般只包含两个成员变量:key 和 value,前者表示 键值,后者表示 实值

  关联式容器的实现离不开键值对

//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) {}

#ifdef __STL_MEMBER_TEMPLATES
  template <class U1, class U2>
  pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};

  pair 中的 first 表示 键值,second 则表示 实值,在给 关联式容器 中插入数据时,可以构建 pair 对象
比如下面就构建了一个 键值 key 为 string,实值 value 为 int 的匿名 键值对 pair 对象

pair<string, int>("hehe", 123);

  可以将此匿名对象传入 关联式容器 中,当然这样写未免过于麻烦了,于是库中设计了一个函数模板 make_pair,可以根据传入的参数,去调用 pair 构建对象并返回

make_pair("hehe", 123);	//构建出的匿名对象与上面的一致

二、set

何为set?

  set 其实就是之前在 二叉搜索树 中的K模型

也就是用来解决“在不在”问题的模型

在这里插入图片描述
  其中的 T 就是 set 的实值(键值),参数2 Compare 为存储依据,默认为升序,即符合 二叉搜索树 中序遍历的结果:升序,参数3 Alloc 是空间配置器,现在不必深究

  作为 STL 中的容器,set 当然少不了迭代器,树型关联式容器迭代器的遍历结果为有序,所以迭代器遍历的本质是 中序遍历,同时 set 的迭代器还是一个 双向迭代器,支持 ++ 和 – 操作

set的使用

  set 的构造函数如下图所示:
在这里插入图片描述
  可以直接创建一个空 set 使用,也可以根据迭代器区间创建 set

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 8,5,6,7,3,1,1,3 };

	set<int> s1;	//创建一个空的 set
	set<int> s2(arr.begin(), arr.end());	//创建包含数据的 set

	cout << "s1: ";
	for (const auto& e : s1)
		cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (const auto& e : s2)
		cout << e << " ";
	cout << endl;

	return 0;
}

在这里插入图片描述
  就像 二叉搜索树 一样,set 是不支持数据冗余的,如果出现冗余的数据插入时,会失败,如果想存储冗余的数据,可以使用 multiset

set 中的常用功能

功能用途
empty判断容器是否为空
size当前容器中的元素数
insert元素插入,根据特定条件插入至合适位置
erase删除指定元素
swap交换两个容器
clear清空容器中的所有元素
find查找实值是否存在并返回迭代器位置
count统计容器中指定键值的数量
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 7,3,6,9,3,1,6,2 };
	set<int> s1(arr.begin(), arr.end());

	//迭代器遍历
	cout << "迭代器遍历结果: ";
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//判空、求大小
	cout << "===================" << endl;
	cout << "empty(): " << s1.empty() << endl;
	cout << "size(): " << s1.size() << endl;

	//插入元素
	cout << "===================" << endl;
	cout << "insert(5): ";
	s1.insert(5);
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	//删除元素
	cout << "===================" << endl;
	cout << "erase(6): ";
	s1.erase(6);
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	//交换、查找、清理
	cout << "===================" << endl;
	set<int> s2(arr.begin() + 5, arr.end());
	s1.swap(s2);
	
	cout << "s1: ";
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (const auto& e : s2) cout << e << " ";
	cout << endl;

	cout << "s1.find(9): ";
	cout << (s1.find(9) != s1.end()) << endl;

	cout << "s2.clear(): " << endl;
	s2.clear();

	cout << "s1: ";
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (const auto& e : s2) cout << e << " ";
	cout << endl;

	// 查询数量
	cout << "s1.count(2):" << " " << s1.count(2) << endl;

	return 0;
}

在这里插入图片描述

其实因为set不允许键值重复,所以 count() 只会有 0 或者 1 两种可能,所以理论上来说你可以用它来判断数字是否在容器中

  另外请注意,二叉搜索树中的键值key是不允许改变的,如果改变了,会破坏二叉搜索树的结构导致失效

因此即使是 set 中的普通迭代器,本质上也是 const 迭代器

set的特点

  总得来说就是下图
在这里插入图片描述

multiset

在这里插入图片描述

multi前缀在英语中是为 “多” 的意思

  其实对比set,也就是多了支持数据冗余的功能

  另外当查询数字有多个的时候,返回的是 中序遍历中第一次出现的元素

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 3,5,3,4,5,9,2,3 };
	multiset<int> ms1(arr.begin(), arr.end());

	auto it = ms1.begin();
	while (it != ms1.end())
	{
		cout << *it << " | " << &*(it) << endl;
		++it;
	}

	cout << "================" << endl;
	cout << "ms1.find(3): " << &*(ms1.find(3)) << endl;

	return 0;
}

在这里插入图片描述
multiset 才是真正的排序,set 则是去重 + 排序

三、map

何为map?

  map 是 二叉搜索树 改造后的 key / value 模型,是一个真正意义上的 键值对

map其实就是一种映射关系

在这里插入图片描述

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
	vector<pair<string, int>> arr = { make_pair("G", 71), make_pair("A", 65), make_pair("F", 70) };

	map<string, int> m1;	//创建一个空的 map
	map<string, int> m2(arr.begin(), arr.end());	//创建包含数据的 map

	cout << "m1: " << endl;
	for (const auto& e : m1)
		cout << e.first << " | " << e.second << endl;
	cout << "========================" << endl;
	cout << "m2: " << endl;
	for (const auto& e : m2)
		cout << e.first << " | " << e.second << endl;

	return 0;
}

在这里插入图片描述
map 中的常用功能

功能用途
empty判断容器是否为空
size当前容器中的元素数
operator[ ]按照键值,访问实值,如果没有,则新插入
insert元素插入,根据特定条件插入至合适位置
erase删除指定元素
swap交换两个容器
clear清空容器中的所有元素
find查找实值是否存在并返回迭代器位置
count统计容器中指定键值的数量
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	vector<pair<string, int>> arr{ make_pair("z", 122), make_pair("a", 97),  make_pair("K", 75), make_pair("h", 104), make_pair("B", 66) };

	map<string, int> m1(arr.begin(), arr.end());

	//迭代器遍历
	cout << "迭代器遍历结果: ";
	map<string, int>::iterator it = m1.begin();
	while (it != m1.end())
	{
		cout << "<" << it->first << ":" << it->second << "> ";
		++it;
	}
	cout << endl;

	//判空、求大小、解引用
	cout << "===================" << endl;
	cout << "empty(): " << m1.empty() << endl;
	cout << "size(): " << m1.size() << endl;
	cout << "m1[""a""]: " << m1["a"] << endl;

	//插入元素
	cout << "===================" << endl;
	cout << "insert(""a"", 5): ";
	m1.insert(make_pair("a", 5));
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//删除元素
	cout << "===================" << endl;
	cout << "erase(""a""): ";
	m1.erase("a");
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//交换、查找、清理
	cout << "===================" << endl;
	map<string, int> m2(arr.begin() + 2, arr.end());
	m1.swap(m2);
	cout << "m1.swap(m2)" << endl;
	cout << "m1: ";
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m2: ";
	for (const auto& e : m2) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m1.find(""B""): ";
	cout << (m1.find("B") != m1.end()) << endl;

	cout << "m2.clear()" << endl;
	m2.clear();

	cout << "m1: ";
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m2: " << endl;
	for (const auto& e : m2) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	return 0;
}

在这里插入图片描述

map 不允许数据冗余,如果想插入重复的数据,可以使用 multimap

  map的插入函数比较有意思,因为既要返回插入是否成功,又要返回插入成功的迭代器,所以它的返回值其实是个pair

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<string, int> m1;
	auto ret = m1.insert(make_pair("a", 97));
	cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;

	ret = m1.insert(make_pair("a", 100));
	cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;

	return 0;
}

在这里插入图片描述

  至于 find 和 count 跟 set 中的一样,可以用来判断元素是否存在,不过 find 返回的是 迭代器,count 返回的则是 键值数

  map 是支持修改 实值 value 的,因此 可以根据普通迭代器修改实值

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<string, int> m1;
	m1.insert(make_pair("a", 97));
	auto it = m1.find("a");
	cout << "<" << it->first << ":" << it->second << ">" << endl;

	it->second = 100;
	cout << "<" << it->first << ":" << it->second << ">" << endl;

	return 0;
}

在这里插入图片描述

map中的operator[ ]

  operator[ ] 返回的是当前 键值 对应的 实值,如果当前 键值 不存在,则会插入新的 键值对

这很强大,值得我们单独介绍一下它

在这里插入图片描述
  operator[ ] 的返回值为 mapped_type,即 实值 value 的引用,参数 key_type 是 键值 key

(*((this->insert(make_pair(k, mapped_type()))).first)).second

在这里插入图片描述

  1. 插入一个新的键值对 this->insert( make_pair(k, mapped_type()) )
  2. 获取 insert 返回值中的 键值 返回值.first 即迭代器 iterator
  3. 最后通过迭代器获取 实值 (*iterator).second

所以说,这个operator[ ]包含了插入、修改、插入+修改、查找等功能

在这里插入图片描述

multimap

在这里插入图片描述

既然允许冗余数据插入,自然也就没有了operator[ ]


总结

  复杂链表的复制
  前K个高频单词

  两道很有意思的题目,大家可以尝试运用本篇文章的内容来尝试一下

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

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

相关文章

PostgreSQL 学习笔记:PostgreSQL 主从复制

PostgreSQL 笔记&#xff1a;PostgreSQL 主从复制 博客地址&#xff1a;TMDOG 的博客 在现代应用程序中&#xff0c;数据库的高可用性和扩展性是至关重要的。PostgreSQL 提供了主从复制功能&#xff0c;可以在多个数据库实例之间复制数据&#xff0c;以实现冗余和负载均衡。本…

SQL,力扣题目1225,报告系统状态的连续日期【窗口函数】

一、力扣链接 LeetCode_1225 二、题目描述 表&#xff1a;Failed ----------------------- | Column Name | Type | ----------------------- | fail_date | date | ----------------------- 该表主键为 fail_date (具有唯一值的列)。 该表包含失败任务的天数.表…

晶台施密特触发器光耦KLH11LX,1MHz高传输速率

晶台推出KLH11LX系列由一个砷化镓红外发光二极管和一个高速集成电路检测器组成&#xff0c;该输出检测器包含了一个施密特触发器&#xff0c;利用其回滞特性&#xff0c;便于脉冲整形&#xff0c;提高抗噪性能。 功能图Functional Diagram 产品特点Product Features •高传输…

Mac在Typora配置PicGo图床,以github为例

Mac配置PicGo图床 0.准备阶段&#xff1a;下载PicGo https://picgo.github.io/PicGo-Doc/zh/guide/ 根据这个链接选择自己的安装方式 1.PicGo已损坏&#xff0c;无法打开 解决方法 打开iTerm,把sudo xattr -d com.apple.quarantine 输入命令行 然后把软件拖入命令行 sudo xa…

「Mac畅玩鸿蒙与硬件23」鸿蒙UI组件篇13 - 自定义组件的创建与使用

自定义组件可以帮助开发者实现复用性强、逻辑清晰的界面模块。通过自定义组件,鸿蒙应用能够提高代码的可维护性,并简化复杂布局的构建。本篇将介绍如何创建自定义组件,如何向组件传递数据,以及如何在不同页面间复用这些组件。 关键词 自定义组件复用组件属性传递组件通信组…

redis模板的应用:自定义redisTemplate序列化规则 (RedisTemplate和StringRedisTemplate)

文章目录 引言I 基础知识redis对key和value使用序列化方式RedisTemplate<Object, Object>自定义redisTemplate序列化规则RedisTemplate<String, String>II 存储自定义对象redisTemplate存储自定义对象StringRedisTemplate存储自定义对象引言 StringRedisTemplate只…

二叉苹果树

AcWing 1074. 二叉苹果树【有依赖背包DP】 - AcWing 问题描述 在一棵有权无向树中&#xff0c;从某个节点&#xff08;这里假设为节点 1&#xff09;出发&#xff0c;遍历树的子节点&#xff0c;每经过一条边会获得对应的权重值。在访问节点数的限制下&#xff08;即体积限制…

Linux基础命令(八) 之 alias ,history,stat,type,特殊符号及命令行快捷键

目录 一&#xff0c;命令别名 alias 常见用法 二&#xff0c;命令历史 history 参数及其作用 常见用法 三.显示文件或文件系统的详细信息 stat 参数及其作用 常见用法 四&#xff0c;显示命令的类型 type 参数及其作用 常见用法 五&#xff0c;特殊符号及命令行快捷…

省级-知识产权保护指数(2012-2022年)

省级知识产权保护指数&#xff08;以下简称“指数”&#xff09;正是衡量各省份在知识产权保护方面表现的一个综合指标&#xff0c;它涵盖了立法、执法、审查和监督等多个维度&#xff0c;全面反映了各省份在知识产权保护方面的综合实力。 2012年-2022年省级-知识产权保护指数…

GraphQL 与 Elasticsearch 相遇:使用 Hasura DDN 构建可扩展、支持 AI 的应用程序

作者&#xff1a;来自 Elastic Praveen Durairaju GraphQL 提供了一种高效且灵活的数据查询方式。本博客将解释 Hasura DDN 如何与 Elasticsearch 配合使用&#xff0c;以实现高性能和元数据驱动的数据访问。 此示例的代码和设置可在此 GitHub 存储库 - elasticsearch-subgraph…

filebeat+elasticsearch+kibana日志分析

1 默认配置 1.1 filebeat filebeat-7.17.yml,从网关中下载k8s的配置&#xff0c;指定es和kibana的配置 通过kibana查询可以查询到日志了&#xff0c;但此时还不知道具体怎么用。 1.2 kibana 在Discover中创建索引格式&#xff1a;filebeat-*&#xff0c;得到如下图&#xf…

Rust 力扣 - 2090. 半径为 k 的子数组平均值

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 半径为 k 的子数组平均值 等价于 子数组长度为2 * k 1的总和 除于 2 * k 1 我们遍历长度为2 * k 1的窗口&#xff0c;我们只需要记录窗口内的平均值即可 题解代码 impl Solution {pub fn get_averages(num…

uniapp的video视频属性打包app后层级过高

问题&#xff1a;在使用uniapp开发APP时&#xff0c;使用video标签显示视频发现H5可以正常展示&#xff0c;但是打包到APP后&#xff0c;它的层级过高&#xff0c;把底部导航都盖住了。 官网说明&#xff1a;uni-app官网 官网给了cover-view组件或plus.nativeObj.view、subNVue…

浅谈UI自动化

⭐️前言⭐️ 本篇文章围绕UI自动化来展开&#xff0c;主要内容包括什么是UI自动化&#xff0c;常用的UI自动化框架&#xff0c;UI自动化原理等。 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f349;博主将持续更新学习记录收获&#xff0c;友友们有任何问题…

Vue3+Data-V实现可视化大屏页面布局

目录 一、前言 二、环境准备 1.Vue3安装npm create vuelatest 2.Data-V配置 项目Data-v安装 main.js中注册Data-v到全局 ​编辑可使用按需引入 3.测试 三、导航栏路由跳转配置 1.子组件mainNav组件准备 2.父组件准备导航栏参数传递 3.子组件接收父组件参数 4.导航…

Python 使用 LSTM 进行情感分析:处理文本序列数据的指南

使用 LSTM 进行情感分析&#xff1a;处理文本序列数据的指南 长短期记忆网络&#xff08;LSTM&#xff09;是一种适合处理序列数据的深度学习模型&#xff0c;广泛应用于情感分析、语音识别、文本生成等领域。它通过在训练过程中“记住”过去的数据特征来理解和预测序列数据的…

树莓派5实时时钟(RTC)

树莓派5板载一个实时时钟模块。它可以通过 USB-C 电源插口右侧板上的 J5(BAT) 插口进行电池供电。如果没有互联网连接来通过 NTP 获取时间&#xff0c;RTC 可能会很有用。 可以设置唤醒警报&#xff0c;将树莓派5切换到非常低功耗的状态&#xff08;大约3mA&#xff09;。当到达…

保姆级教程!!教你通过【Pycharm远程】连接服务器运行项目代码

小罗碎碎念 这篇文章主要解决一个问题——我有服务器&#xff0c;但是不知道怎么拿来写代码&#xff0c;跑深度学习项目。确实&#xff0c;玩深度学习的成本比较高&#xff0c;无论是前期的学习成本&#xff0c;还是你需要具备的硬件成本&#xff0c;都是拦路虎。小罗没有办法…

Chrome与夸克的安全性对比

在当今数字化时代&#xff0c;浏览器的安全性对于用户来说至关重要。Chrome和夸克作为两款流行的浏览器&#xff0c;各有其特点和优势。本文将对这两款浏览器的安全性进行详细对比&#xff0c;帮助用户更好地了解它们之间的差异。&#xff08;本文由https://www.chromegw.com/的…

ZFC in LEAN 之 前集(Pre-set)

前集&#xff08;Pre-set&#xff09;的概念是相对于集合&#xff08;Set&#xff09;&#xff0c;由数学家 Bishop 提出的。Bishop 认为定义一个集合需要三个步骤&#xff1a; 1. 定义该集合的元素是如何构建的&#xff08;Construction&#xff09;。 2. 定义集合中的两元素的…