重学C++ | std::set 的原理
std::set 是C++标准库中的容器之一,它基于红黑树实现。std::set 利用红黑树的特性来实现有序的插入、查找和删除操作,并且具有较好的平均和最坏情况下的时间复杂度。
当向 std::set 插入元素时,它会按照特定的比较函数(bool less<T>::operator() const(const T &lhs, const T & rhs))将新元素插入到红黑树的适当位置,以保持树的有序性质。插入操作的平均时间复杂度为 O ( log n ) O(\log n) O(logn),其中 n n n是 std::set 中元素的数量。查找操作(find())使用红黑树的性质,通过比较函数在树中进行二分查找,查找操作的平均时间复杂度为 O ( log n ) O(\log n) O(logn)。
但是当我们把 struct 放入 std::set 会有什么后果呢?因为 std::set 需要在插入到时候排序,所以需要重载 struct 的比较运算符,这个时候就出现问题了,首先我们定义一个结构体 Person :
struct Person {Person(int _ID, string _name, int _age) : ID(_ID), age(_age), name(_name) {}int ID;int age;string name;
};
当我们直接插入到 std::set<Person> 中时,会报 complier error 的错误,因此简单补写一个比较运算符重载,如下:
bool operator<(const Person &lhs, const Person &rhs) {return lhs.age < rhs.age;
}
OK,编译起来没有问题,但是我们运行测试一下下面的find操作就会发现问题
#include <iostream>
#include <set>using namespace std;struct Person {Person(int _ID, string _name, int _age) : ID(_ID), age(_age), name(_name) {}int ID;int age;string name;
};bool operator<(const Person &lhs, const Person &rhs) {return lhs.age < rhs.age;
}int main() {set<Person> person;for (int i = 0; i < 1000; ++i) {Person p_tmp(i, "sxj", 10);person.insert(p_tmp);}Person p(2000, "sxj", 10);auto it = person.find(p);if (it != person.end())cout << "Find Person --- ID: " << it->ID << " name: " << it->name << " age: " << it->age;elsecout << "Can't find" << endl;return 0;
}

明明不在set中的 ID-2000 的Person也可以被找到。造成这个结果的原因是我们所提供的 operator<() ,当Person p1、p2,在 p1<p2 与 p2<p2 都不成立时,find 就会判断 p1 和 p2 是同一个 Person ,因此会造成这样的错误结果。
解决方案就是补充完整我们的比较运算符重载,完整代码如下:
#include <iostream>
#include <set>using namespace std;struct Person {Person(int _ID, string _name, int _age) : ID(_ID), age(_age), name(_name) {}int ID;int age;string name;
};bool operator<(const Person &lhs, const Person &rhs) {if (lhs.ID < rhs.ID) return true;if (lhs.ID > rhs.ID) return false;if (lhs.name < rhs.name) return true;if (lhs.name > rhs.name) return false;return lhs.age < rhs.age;
}int main() {set<Person> person;for (int i = 0; i < 1000; ++i) {Person p_tmp(i, "sxj", 10);person.insert(p_tmp);}Person p(2000, "sxj", 10);auto it = person.find(p);if (it != person.end())cout << "Find Person --- ID: " << it->ID << " name: " << it->name << " age: " << it->age;elsecout << "Can't find" << endl;return 0;
}
相关文章:
重学C++ | std::set 的原理
std::set 是C标准库中的容器之一,它基于红黑树实现。std::set 利用红黑树的特性来实现有序的插入、查找和删除操作,并且具有较好的平均和最坏情况下的时间复杂度。 当向 std::set 插入元素时,它会按照特定的比较函数(bool less<…...
AnV-X6使用及总结
目录 1 简介2 安装3 基础概念3.1 画布Graph3.2 基类Cell3.3 节点Node3.4 边Edge 4 使用4.1 创建节点4.2 节点连线4.3 事件系统 5 总结 1 简介 AntV是一个数据可视化(https://x6.antv.antgroup.com/)的工具(https://antv.vision/zh/ …...
Go 围炉札记
文章目录 一、安装二、文档三、使用 一、安装 VSCode 和 CLion 为 Go 开发配置Visual Studio Code | Microsoft Learn VScode下配置Go语言开发环境【2023最新】 基础篇:新手使用vs code新建go项目 vscode里安装Go插件和配置Go环境 GO 笔记 Golang 配置代理 golang…...
数据分析回头看2——重复值检查/元素替换/异常值筛选
0、前言: 这部分内容是对Pandas的回顾,同时也是对Pandas处理异常数据的一些技巧的总结,不一定全面,只是自己在数据处理当中遇到的问题进行的总结。 1、当数据中有重复行的时候需要检测重复行: 方法:使用p…...
什么是OSPF?为什么需要OSPF
【微|信|公|众|号:厦门微思网络】 【微思网络www.xmws.cn,成立于2002年,专业培训21年,思科、华为、红帽、ORACLE、VMware等厂商认证及考试,以及其他认证PMP、CISP、ITIL等】 什么是OSPF? 开放式最短路径优…...
轻量级的日志采集组件 Filebeat 讲解与实战操作
文章目录 一、概述二、Kafka 安装三、Filebeat 安装1)下载 Filebeat2)Filebeat 配置参数讲解3)filebeat.prospectors 推送kafka完整配置1、filebeat.prospectors2、processors3、output.kafka 4)filebeat.inputs 与 filebeat.pros…...
C# 委托和事件
C# 委托和事件 委托匿名方法事件 委托 当要把方法传送给其他方法时,需要使用委托。首先定义要使用的委托,对于委托,定义它就是告诉编译器这种类型的委托代表了哪种类型的方法,然后创建该委托的一个或多个实例。编译器在后台将创建…...
数据结构与算法之字典: Leetcode 349. 两个数组的交集 (Typescript版)
两个数组的交集 https://leetcode.cn/problems/intersection-of-two-arrays/description/ 题目和解题参考 https://blog.csdn.net/Tyro_java/article/details/133279737 使用字典来解题的算法实现 字典:顾名思义,像新华字典一样可查找,基…...
day-56 代码随想录算法训练营(19)动态规划 part 16
538.两个字符串的删除操作 思路一: 1.dp存储:以word1[i-1]结尾,word2[j-1]结尾,最少进行dp[i][j]次操作2.动态转移方程: if(word1[i-1]word2[i-1]) dp[i][j]dp[i-1][j-1]; else dp[i][j]min(dp[i-1][…...
蓝桥等考Python组别四级005
第一部分:选择题 1、Python L4 (15分) 字符“0”的ASCII码值为48,则字符“5”的ASCII码值为( )。 3953120240正确答案:B 2、Python L4 (15分) 下面哪个是Python中正确的变量名?( ) ABC#sup01Trueif正确答案:B...
【Linux】diff 命令
【Linux】diff 命令——并排格式输出 功能 diff 以逐行的方式,比较文本文件的异同处。 如果指定要比较目录,则 diff 会比较目录中相同文件名的文件,但不会比较其中子目录 diff [参数] [文件A] [文件B]diff [参数] [目录A] [目录B]【参数】…...
【51单片机】9-定时器和计数器
1.定时器的介绍 1.什么是定时器 (1)SoC的一种内部的外设【在单片机里面,但是在CPU外面】 (2)定时器就是CPU的”闹钟“ 2.什么是计数器 (1)定时器就是用计数的原始实现的 (2…...
2023年海南省职业院校技能大赛(高职组)信息安全管理与评估赛项规程
2023年海南省职业院校技能大赛(高职组) 信息安全管理与评估赛项规程 一、赛项名称 赛项名称:信息安全管理与评估 英文名称:Information Security Management and Evaluation 赛项组别:高等职业教育 赛项归属产业&…...
大模型深挖数据要素价值:算法、算力之后,存储载体价值凸显
文 | 智能相对论 作者 | 叶远风 18.8万亿美元,这是市场预计2030年AI推动智能经济可产生的价值总和,其中大模型带来的AI能力质变无疑成为重要的推动力量。 大模型浪潮下,业界对AI发展的三驾马车——算力、算法、数据任何一个维度的关注都到…...
AI文章,AI文章生成工具
在互联网时代,随着信息爆炸式增长,文章的需求愈发旺盛。从博客、新闻、社交媒体到企业宣传,文字作为传达信息、吸引受众的工具变得愈发重要。但问题是,对于很多人来说,创作一篇高质量的文章并不容易。时间、创意、写作…...
mac有必要用清理软件吗?有哪些免费的清理工具
当我们谈到Mac电脑时,很多人都会觉得它比Windows系统更加稳定和高效,也更不容易积累垃圾文件。但实际上,任何长时间使用的操作系统都会逐渐积累不必要的文件和缓存。那么,对于Mac用户来说,有必要使用专门的清理软件吗&…...
React 全栈体系(十八)
第九章 React Router 6 二、代码实战 6. 路由的 params 参数 6.1 routes /* src/routes/index.js */ import About from "../pages/About"; import Home from "../pages/Home"; import Message from "../pages/Message"; import News from &q…...
TCP/UDP
TCP:可靠的有序传输 TCP是一种面向连接的协议,旨在提供可靠、有序的数据传输。它通过以下方式实现这一目标: 1. 连接建立和维护 在使用TCP传输数据之前,必须先建立连接。这个过程包括三次握手,即客户端和服务器之间…...
c++内存对齐
原文在这里。https://blog.csdn.net/WangErice/article/details/103598081 但是内容有错误。我在自己的这里修改并变成红色了。 内存在使用过程并不是单一的依次排列,而是按照某种既定的规则来进行对齐,以方便快速访问.内存的对齐原则有以下三条&#…...
leetcode 33. 搜索旋转排序数组
2023.9.26 本题暴力法可以直接A,但是题目要求用log n的解法。 可以想到二分法,但是一般二分法适用于有序数组的,这里的数组只是部分有序,还能用二分法吗? 答案是可以的。因为数组是经过有序数组旋转得来的,…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...
