当前位置: 首页 > news >正文

重学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 nstd::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-2000Person也可以被找到。造成这个结果的原因是我们所提供的 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标准库中的容器之一&#xff0c;它基于红黑树实现。std::set 利用红黑树的特性来实现有序的插入、查找和删除操作&#xff0c;并且具有较好的平均和最坏情况下的时间复杂度。 当向 std::set 插入元素时&#xff0c;它会按照特定的比较函数&#xff08;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是一个数据可视化&#xff08;https://x6.antv.antgroup.com/&#xff09;的工具&#xff08;https://antv.vision/zh/ &#xf…...

Go 围炉札记

文章目录 一、安装二、文档三、使用 一、安装 VSCode 和 CLion 为 Go 开发配置Visual Studio Code | Microsoft Learn VScode下配置Go语言开发环境【2023最新】 基础篇&#xff1a;新手使用vs code新建go项目 vscode里安装Go插件和配置Go环境 GO 笔记 Golang 配置代理 golang…...

数据分析回头看2——重复值检查/元素替换/异常值筛选

0、前言&#xff1a; 这部分内容是对Pandas的回顾&#xff0c;同时也是对Pandas处理异常数据的一些技巧的总结&#xff0c;不一定全面&#xff0c;只是自己在数据处理当中遇到的问题进行的总结。 1、当数据中有重复行的时候需要检测重复行&#xff1a; 方法&#xff1a;使用p…...

什么是OSPF?为什么需要OSPF

【微|信|公|众|号&#xff1a;厦门微思网络】 【微思网络www.xmws.cn&#xff0c;成立于2002年&#xff0c;专业培训21年&#xff0c;思科、华为、红帽、ORACLE、VMware等厂商认证及考试&#xff0c;以及其他认证PMP、CISP、ITIL等】 什么是OSPF&#xff1f; 开放式最短路径优…...

轻量级的日志采集组件 Filebeat 讲解与实战操作

文章目录 一、概述二、Kafka 安装三、Filebeat 安装1&#xff09;下载 Filebeat2&#xff09;Filebeat 配置参数讲解3&#xff09;filebeat.prospectors 推送kafka完整配置1、filebeat.prospectors2、processors3、output.kafka 4&#xff09;filebeat.inputs 与 filebeat.pros…...

C# 委托和事件

C# 委托和事件 委托匿名方法事件 委托 当要把方法传送给其他方法时&#xff0c;需要使用委托。首先定义要使用的委托&#xff0c;对于委托&#xff0c;定义它就是告诉编译器这种类型的委托代表了哪种类型的方法&#xff0c;然后创建该委托的一个或多个实例。编译器在后台将创建…...

数据结构与算法之字典: Leetcode 349. 两个数组的交集 (Typescript版)

两个数组的交集 https://leetcode.cn/problems/intersection-of-two-arrays/description/ 题目和解题参考 https://blog.csdn.net/Tyro_java/article/details/133279737 使用字典来解题的算法实现 字典&#xff1a;顾名思义&#xff0c;像新华字典一样可查找&#xff0c;基…...

day-56 代码随想录算法训练营(19)动态规划 part 16

538.两个字符串的删除操作 思路一&#xff1a; 1.dp存储&#xff1a;以word1[i-1]结尾&#xff0c;word2[j-1]结尾&#xff0c;最少进行dp[i][j]次操作2.动态转移方程&#xff1a; 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 以逐行的方式&#xff0c;比较文本文件的异同处。 如果指定要比较目录&#xff0c;则 diff 会比较目录中相同文件名的文件&#xff0c;但不会比较其中子目录 diff [参数] [文件A] [文件B]diff [参数] [目录A] [目录B]【参数】…...

【51单片机】9-定时器和计数器

1.定时器的介绍 1.什么是定时器 &#xff08;1&#xff09;SoC的一种内部的外设【在单片机里面&#xff0c;但是在CPU外面】 &#xff08;2&#xff09;定时器就是CPU的”闹钟“ 2.什么是计数器 &#xff08;1&#xff09;定时器就是用计数的原始实现的 &#xff08;2&#xf…...

2023年海南省职业院校技能大赛(高职组)信息安全管理与评估赛项规程

2023年海南省职业院校技能大赛&#xff08;高职组&#xff09; 信息安全管理与评估赛项规程 一、赛项名称 赛项名称&#xff1a;信息安全管理与评估 英文名称&#xff1a;Information Security Management and Evaluation 赛项组别&#xff1a;高等职业教育 赛项归属产业&…...

大模型深挖数据要素价值:算法、算力之后,存储载体价值凸显

文 | 智能相对论 作者 | 叶远风 18.8万亿美元&#xff0c;这是市场预计2030年AI推动智能经济可产生的价值总和&#xff0c;其中大模型带来的AI能力质变无疑成为重要的推动力量。 大模型浪潮下&#xff0c;业界对AI发展的三驾马车——算力、算法、数据任何一个维度的关注都到…...

AI文章,AI文章生成工具

在互联网时代&#xff0c;随着信息爆炸式增长&#xff0c;文章的需求愈发旺盛。从博客、新闻、社交媒体到企业宣传&#xff0c;文字作为传达信息、吸引受众的工具变得愈发重要。但问题是&#xff0c;对于很多人来说&#xff0c;创作一篇高质量的文章并不容易。时间、创意、写作…...

mac有必要用清理软件吗?有哪些免费的清理工具

当我们谈到Mac电脑时&#xff0c;很多人都会觉得它比Windows系统更加稳定和高效&#xff0c;也更不容易积累垃圾文件。但实际上&#xff0c;任何长时间使用的操作系统都会逐渐积累不必要的文件和缓存。那么&#xff0c;对于Mac用户来说&#xff0c;有必要使用专门的清理软件吗&…...

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&#xff1a;可靠的有序传输 TCP是一种面向连接的协议&#xff0c;旨在提供可靠、有序的数据传输。它通过以下方式实现这一目标&#xff1a; 1. 连接建立和维护 在使用TCP传输数据之前&#xff0c;必须先建立连接。这个过程包括三次握手&#xff0c;即客户端和服务器之间…...

c++内存对齐

原文在这里。https://blog.csdn.net/WangErice/article/details/103598081 但是内容有错误。我在自己的这里修改并变成红色了。 内存在使用过程并不是单一的依次排列&#xff0c;而是按照某种既定的规则来进行对齐&#xff0c;以方便快速访问.内存的对齐原则有以下三条&#…...

leetcode 33. 搜索旋转排序数组

2023.9.26 本题暴力法可以直接A&#xff0c;但是题目要求用log n的解法。 可以想到二分法&#xff0c;但是一般二分法适用于有序数组的&#xff0c;这里的数组只是部分有序&#xff0c;还能用二分法吗&#xff1f; 答案是可以的。因为数组是经过有序数组旋转得来的&#xff0c;…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...