C++:set详解

文章目录

  • 前言
  • 一、set概念介绍
  • 二、set的使用
    • 1. 插入删除相关
    • 2. 查找相关
      • 1)find
      • 2)count
      • 3)lower_bound与upper_bound
      • 4)equal_range
  • 三、set的值是不能修改的原理
  • 四、基于哈希表的set
  • 总结


前言

根据应用场景的不同,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

首先是set相关:gogogo

在这里插入图片描述


一、set概念介绍

在这里插入图片描述

set就是key_tree的模型:

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

注意:

  1. 与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放 value,但在底层实际存放的是由<value, value>构成的键值对。
  2. set中插入元素时,只需要插入value即可,不需要构造键值对。
  3. set中的元素不可以重复(因此可以使用set进行去重)。
  4. 使用set的迭代器遍历set中的元素,可以得到有序序列
  5. set中的元素默认按照小于来比较
  6. set中查找某个元素,时间复杂度为: l o g 2 n log_2 n log2n
  7. set中的元素不允许修改,它的普通迭代器和const迭代器都是const迭代器
  8. set中的底层使用二叉搜索树(红黑树)

二、set的使用

1. 插入删除相关

在这里插入图片描述

首先,set的插入默认是排序 + 去重
在这里插入图片描述

set的删除:有就删,没有就不做为:
在这里插入图片描述


2. 查找相关

在这里插入图片描述

1)find

首先是find: 如果找到了就会返回对应结点的迭代器,没找到就会返回end()
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


2)count

然后是count:count的作用是返回当前值出现的次数:
对于set来说count并没有太大的作用,可以说和find的作用是一样的。

在这里插入图片描述

但是对于multiset来说就有意义了,因为set是默认去重的,因此插入相同的元素只有一个,但是multiset默认是不去重的,因此count可以统计个数。

在这里插入图片描述

3)lower_bound与upper_bound

lower_bound与upper_bound用来查找一段区间:[low, up)

是一段左闭右开的区间,因为只有这样,我们用迭代器访问的时候
itlow != itup才能不漏最后一个元素。

因此:对于lower_bound找的是>=x的迭代器,
在这里插入图片描述

对于upper_bound找的是>x的迭代器。
在这里插入图片描述

如果没找到就是end()。

对于等于的情况:
在这里插入图片描述

对于的所找的值 在set中找不到:
在这里插入图片描述

4)equal_range

equal_range作用是找到相同的值的一段迭代区间,同样是左闭右开的区间。
它的返回值是一个pair,pair是两个值做组成的一对,其中first是左区间,second是右区间。
在这里插入图片描述
因此我们接收返回值需要用pair<set::const_iterator, const set::const_iterator>,pair中每一个都是set类型的const_iterator,也可以用auto接收。

这里对于set来说,因为set会去重,所以其实equal_range对于set来说没什么意义。
在这里插入图片描述

但是对于multiset来说,就有意义了,nultiset不去重,equal_range就可以返回相同的值的区间,那么我们就可以对这个区间执行删除或者其他操作了。
在这里插入图片描述


三、set的值是不能修改的原理

set只是key的模型,set是不能修改的,它的原理是set的迭代器和const迭代器都是const迭代器。
在这里插入图片描述

在这里插入图片描述


四、基于哈希表的set

除了上述两个版本,还有两个基于哈希表的版本的set.
在这里插入图片描述

这张图展示了 C++ 中的四种无序关联容器(Unordered Associative Containers)。这些容器底层是基于哈希表实现的,所以元素是无序存储的。以下是每种容器的简要介绍:

  1. unordered_set

    • 用于存储唯一的元素集合,每个元素只能出现一次。
    • 适合用于快速查找一个元素是否存在的场景。
  2. unordered_multiset

    • unordered_set 类似,但允许存储重复的元素。
    • 适合用于需要存储非唯一元素的集合。
  3. unordered_map

    • 存储键值对(key-value pairs),每个键(key)是唯一的。
    • 可用于快速查找一个键对应的值。
  4. unordered_multimap

    • unordered_map 类似,但允许存储重复的键。
    • 适合用于需要一个键对应多个值的场景。

由于这些容器基于哈希表,因此它们的查找、插入和删除操作通常具有常数时间复杂度(O(1))。
但是他们是无序的。


总结

到这里set的内容就结束啦,创作不易,求各位大大多多支持~~~😘😘😘
在这里插入图片描述

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

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

相关文章

【静态页面】尚品汇 1、设计稿分析及资源准备

目录 1. 准备工作2. 理解设计3. 规划项目结构 1. 准备工作 安装必要的工具&#xff1a;确保你的开发环境已经准备好&#xff0c;包括文本编辑器&#xff08;如 VSCode&#xff09;、浏览器等。获取设计文件&#xff1a;获取UI设计稿或者设计文件链接&#xff0c;并确保可以访问…

小时收入:衡量工作效率与个人自由的标准

小时收入&#xff0c;就是按照小时来计算一个人的收入。比如&#xff0c;一个月一共工作200小时&#xff0c;获得的总收入是20000元&#xff0c;那么小时收入就是100元/小时。 小时收入可以反应一个人的赚钱效率。 可能两个人的月收入一样&#xff0c;但是付出的总工作时间不…

RFID文件柜在文件管理中的作用

一、RFID文件柜系统概述 1.1 RFID技术简介 RFID&#xff08;Radio Frequency Identification&#xff0c;无线射频识别&#xff09;技术是一种非接触式的自动识别技术&#xff0c;它通过无线电讯号识别特定目标并读写相关数据&#xff0c;无需识别系统与特定目标之间建立机械…

mysql代码生成器

项目 pom 文件内容 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/…

域控操作二十四:主域故障辅域接替

模拟环境&#xff1a;上海DC1故障无法开机&#xff0c;导致只有一个DNS的电脑无法上网&#xff08;实际可以添加DC2但是为了实验就不说了&#xff09; FSMO还在DC1上 使用powershell把角色迁移到DC2 ntdsutil roles connections connect to server DC2SHA.whbk.cn quitSeize …

Redis(2):内存模型

一、Redis内存统计 工欲善其事必先利其器&#xff0c;在说明Redis内存之前首先说明如何统计Redis使用内存的情况。 在客户端通过redis-cli连接服务器后&#xff08;后面如无特殊说明&#xff0c;客户端一律使用redis-cli&#xff09;&#xff0c;通过info命令可以查看内存使用情…

数据分析:宏基因组DESeq2差异分析筛选差异物种

禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍原理:计算步骤:结果:加载R包准备画图主题数据链接导入数据Differential abundance (No BP vs 2BP TA)构建`countData`矩阵过滤低丰度物种构建DESeq数据对象DESeq2差异分析画图Di…

泷羽sec学习打卡-shodan扫描4

声明 学习视频来自B站UP主 泷羽sec,如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 关于shodan的那些事儿-4 一、shodan4如何查看公网ip&#xff1f;如何查看自己的ip&#xff1f;如何查看出…

abap 可配置通用报表字段级日志监控

文章目录 1.功能需求描述1.1 功能1.2 效果展示2.数据库表解释2.1 表介绍3.数据库表及字段3.1.应用日志数据库抬头表:ZLOG_TAB_H3.2.应用日志数据库明细表:ZLOG_TAB_P3.3.应用日志维护字段配置表:ZLOG_TAB_F4.日志封装类5.代码6.调用方式代码7.调用案例程序demo1.功能需求描述 …

Spark中的shuffle

Shuffle的本质基于磁盘划分来解决分布式大数据量的全局分组、全局排序、重新分区【增大】的问题。 1、Spark的Shuffle设计 Spark Shuffle过程也叫作宽依赖过程&#xff0c;Spark不完全依赖于内存计算&#xff0c;面临以上问题时&#xff0c;也需要Shuffle过程。 2、Spark中哪…

golang安装,常用框架安装,记忆点

0.安装 虚拟机扩容 【Linux干货分享】LVM快速扩容虚拟机磁盘_哔哩哔哩_bilibili newvim 安装 sudo add-apt-repository ppa:neovim-ppa/stable sudo apt-get update sudo apt-get install -y neovim 最强Vim新手指南&#xff0c;手把手教你打造只属于自己的代码编辑器&am…

亚马逊旺季爆品攻略:如何利用旺季打造爆品?

随着假日季的脚步日益临近&#xff0c;亚马逊卖家们正摩拳擦掌&#xff0c;准备迎接这一年度的销售高峰。本文将为您揭示如何在旺季中抓住机遇&#xff0c;通过精心策划和执行一系列策略&#xff0c;让您的产品在众多竞争对手中脱颖而出&#xff0c;成为真正的爆品&#xff01;…

别卷Transformer了!时序卷积这么做,一样发顶会!

Transformer爆火之后&#xff0c;时间序列领域基本上算是被占领了&#xff0c;围绕此类相关的研究也是非常之卷。这种情况下&#xff0c;我们不妨了解一下时序卷积。 在大规模时间序列数据处理任务中&#xff0c;时序卷积是一种非常重要的方法&#xff0c;它结合了传统CNN的特…

【C++】STL中的list容器详解及常用函数用法

个人主页: 起名字真南的CSDN博客 个人专栏: 【数据结构初阶】 &#x1f4d8; 基础数据结构【C语言】 &#x1f4bb; C语言编程技巧【C】 &#x1f680; 进阶C【OJ题解】 &#x1f4dd; 题解精讲 目录 &#x1f4cc; 1 引言&#x1f4cc;2 list容器✨2.1 list容器简介✨2.2 li…

使用kalibr_calibration标定相机(realsense)和imu(h7min)

vslam-evaluation/VINS/Installation documentation/4.IMU和相机联合标定kalibr_calibration.md at master DroidAITech/vslam-evaluation GitHub 目录 1.kalibr安装 1.1安装依赖项 1.2创建工作空间 1.3下载kalibr并编译 1.4设置环境变量 2.准备标定板 3.配置驱动和打…

论文阅读:基于语义分割的非结构化田间道路场景识别

论文地址&#xff1a;DOI: 10.11975/j.issn.1002-6819.2021.22.017 概要 环境信息感知是智能农业装备系统自主导航作业的关键技术之一。农业田间道路复杂多变&#xff0c;快速准确地识别可通行区域&#xff0c;辨析障碍物类别&#xff0c;可为农业装备系统高效安全地进行路径规…

能识别黑烟的摄像头

能识别黑烟的摄像头主要应用于监测车辆尾气排放情况&#xff0c;特别是针对排放黑烟的车辆进行抓拍和识别。以下是朗观视觉对这类摄像头的详细介绍&#xff1a; 一、主要特点 智能识别&#xff1a;摄像头内置视频识别功能&#xff0c;能够实时分析视频中的车辆尾气排放情况&am…

Docker镜像分成

1. 镜像分层原理 1.1 镜像分层的定义与结构 Docker 镜像的分层存储机制是其核心特性之一&#xff0c;它允许 Docker 镜像由多个只读层组成&#xff0c;这些层叠加在一起形成一个完整的文件系统。每个层代表 Dockerfile 中的一个指令&#xff0c;并且每一层都是不可变的&#…

2020年美国总统大选数据分析与模型预测

数据集取自&#xff1a;2020年&#x1f1fa;&#x1f1f8;&#x1f1fa;&#x1f1f8;美国大选数据集 - Heywhale.com 前言 对2020年美国总统大选数据的深入分析&#xff0c;提供各州和县层面的投票情况及选民行为的可视化展示。数据预处理阶段将涉及对异常值的处理&#xff0…