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

问题记录——c++ sort 函数 和 严格弱序比较

引出

看下面这段cmp函数的定义


//按照vector第一个元素升序排序
static bool cmp(const vector<int>& a, const vector<int>& b){return a[0] < b[0];
}int eraseOverlapIntervals(vector<vector<int>>& intervals) {//按区间左端排序...sort(intervals.begin(), intervals.end(), cmp);...
}

问题

当我将比较函数中<换成<=时,会出现崩溃
在这里插入图片描述

原因

使用sort时需要遵循严格弱序,永远让等于的情况返回false

弱序定义

严格弱序比较指的是一种比较关系,具有以下性质:
反对称性:如果a小于b,那么b不可能小于a。但是a和b可以相等。
传递性:如果a小于b,并且b小于c,则a小于c。但是a和c可能相等。
反自反性:元素不能和自己比较。即a不小于a。

理解了一下,说人话就是:

反对称性:如果[a,b]满足你定义的规则(return了true),那么[b,a]就一定是不满足规则的,否则就得return false。
传递性:如果[a,b]满足规则,[b,c]满足规则,则[a,c]也一定满足规则。
反自反性:元素不能和自己比较。即[a,a]是不满足规则的。

显然,如果a=b时返回true的话,不满足反对称性反自反性

更进一步

看一部分c++sort原码

template<typename _RandomAccessIterator, typename _Compare>
void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {... while (__first != __last && __comp(*__first, __pivot)) ++__first;...
}

sort是用快排实现的,

在这段代码中,

__comp(*__first, __pivot) 

这个表达式的结果,决定了while循环是否继续进行,
如果这个表达式的结果为 true,那么 __first 就会向右移动,直到找到一个元素不再小于 __pivot。

a.如果表达式返回 true,那么意味着 __first 小于 __pivot,应该被放到左边分区;
b.如果返回 false,则意味着 __first 大于或等于__pivot,应该被放到右边分区
所以如果元素相等,那么 __comp(
__first, __pivot) 应该返回 false。

而stl判断相等是使用的 !Cmp(a,b) && !Cmp(b,a),cmp是你自己定义的函数,
如果cmp在a,b相等时返回true,那么在a,b相等时表达式可以简化成 !true && !true = false
最后,导致了输入两个相等的元素,在stl看来这两个元素既不是小于,也不是等于,也不是大于。

好了,最终会导致什么后果呢?(先去大概看下快排代码)
在从小到大遍历时(pivot左边),判断小于,相等的元素返回的是false,被扔到了右边,
右边判断相等时(pivot右边),返回也是false,又被扔了回来,
循环往复,以至无穷,最终导致程序崩溃。

结论

自定义sort的cmp时, 永远让等于的情况返回false!!!

相关文章:

问题记录——c++ sort 函数 和 严格弱序比较

引出 看下面这段cmp函数的定义 //按照vector第一个元素升序排序 static bool cmp(const vector<int>& a, const vector<int>& b){return a[0] < b[0]; }int eraseOverlapIntervals(vector<vector<int>>& intervals) {//按区间左端排序…...

《Go 简易速速上手小册》第9章:数据库交互(2024 最新版)

文章目录 9.1 连接数据库 - Go 语言的海底宝藏之门9.1.1 基础知识讲解安装数据库驱动数据库连接 9.1.2 重点案例&#xff1a;用户信息管理系统准备数据库Go 代码实现连接数据库添加新用户查询用户信息用户登录验证主函数 9.1.3 拓展案例 1&#xff1a;批量添加用户准备数据库Go…...

redis的hash数据结构底层简记

hash&#xff1a;k和v都是string的hash表。 HSET&#xff08;设置集合数据&#xff0c;4.0之前只能设置1个&#xff0c;之后可以设置多个&#xff09;&#xff0c;HSETNX(若k不存在则设置对应v)&#xff0c;HDEL&#xff08;删除指定kv&#xff0c;可以一次删除多个&#xff09…...

清除Django的管理员admin站点中“Recent Actions“最近活动面板上的所有信息

清除Django的管理员admin站点中"Recent Actions"最近活动面板上的所有信息 本文主要介绍了如何清除Django的管理员admin站点中"Recent Actions"最近活动面板上的所有信息 操作步骤如下 进入Django项目目录中运行代python manage.py shell进入Django shell…...

【JVM篇】ThreadLocal中为什么要使用弱引用

文章目录 &#x1f354;ThreadLocal中为什么要使用弱引用⭐总结 &#x1f354;ThreadLocal中为什么要使用弱引用 ThreadLocal可以在线程中存放线程的本地变量&#xff0c;保证数据的线程安全 ThreadLocal是这样子保存对象的&#xff1a; 在每个线程中&#xff0c;存放了一个…...

Stable Diffusion教程——stable diffusion基础原理详解与安装秋叶整合包进行出图测试

前言 在2022年&#xff0c;人工智能创作内容&#xff08;AIGC&#xff09;成为了AI领域的热门话题之一。在ChatGPT问世之前&#xff0c;AI绘画以其独特的创意和便捷的创作工具迅速走红&#xff0c;引起了广泛关注。随着一系列以Stable Diffusion、Midjourney、NovelAI等为代表…...

【JavaEE】_线程与多线程的创建

目录 1. 线程的概念 2. 创建与使用多线程 2.1 方式1&#xff1a;继承Thread类 2.2 方式2&#xff1a; 实现Runnable接口 2.3 以上两种创建线程方式的对比 3. 多线程的优势-增加运行速度 1. 线程的概念 进程的存在是由于系统的多任务执行需求&#xff0c;这也要求程序员进…...

【前端工程化面试题】如何优化提高 webpack 的构建速度

使用最新版本的 Webpack 和相关插件: 每个新版本的 Webpack 都会带来性能方面的改进和优化&#xff0c;因此始终确保你在使用最新版本。同时&#xff0c;更新你的相关插件也是同样重要的。 使用DllPlugin动态链接库: 使用DllPlugin和DllReferencePlugin来将第三方库的代码进行…...

免费chatgpt使用

基本功能如下&#xff1a; https://go.aigcplus.cc/auth/register?inviteCode3HCULH2UD...

OpenCV识别人脸案例实战

使用级联函数 基本流程 函数介绍 在OpenCV中&#xff0c;人脸检测使用的是cv2.CascadeClassifier.detectMultiScale()函数&#xff0c;它可以检测出图片中所有的人脸。该函数由分类器对象调用&#xff0c;其语法格式为&#xff1a; objects cv2.CascadeClassifier.detectMul…...

VOSK——离线语音库

文章目录 识别函数调用添加自定义热词表1. SetWords2. SetLatticeWords3. SetPartialWords使用示例注意1. SetMaxAlternatives2. SetNLSML3. SetSpkModel4. SetGrammar使用示例注意SetLogLevel示例用法注意事项 识别函数调用 在使用Vosk库进行语音识别时&#xff0c;PartialRe…...

ELAdmin 隐藏添加编辑按钮

使用场景 做了一个监控模块&#xff0c;数据都是定时生成的&#xff0c;所以不需要手动添加和编辑功能。 顶部不显示 可以使用 true 或者 false 控制现实隐藏 created() {this.crud.optShow {add: false,edit: false,del: true,download: true,reset: true}},如果没有 crea…...

浅谈Websocket

由于 http 存在⼀个明显的弊端(消息只能有客户端推送到服务器端,⽽服务器端不能主动推送到客户端),导致如果服务器如果有连续的变化,这时只能使⽤轮询,⽽轮询效率过低,并不适合。于是 WebSocket 被发明出来 WebSocket 是⼀种在 Web 应⽤程序中实现双向通信的协议。与传…...

JavaScript闭包详细介绍

文章目录 什么是闭包优点&#xff1a;变量持久化&#xff1a;封装私有变量&#xff1a;模块化&#xff1a;函数工厂&#xff1a; 缺点&#xff1a;内存占用&#xff1a;调试困难&#xff1a;过度使用导致性能下降&#xff1a; 什么是闭包 闭包是指有权访问另一个函数作用域中的…...

pytorch神经网络入门代码

import torch import torch.nn as nn import torch.optim as optim import torchvision import torchvision.transforms as transforms# 定义神经网络结构 class SimpleNN(nn.Module):def __init__(self, input_size, hidden_size, num_classes):super(SimpleNN, self).__init_…...

代码随想录算法训练营第三十四天|860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球

860.柠檬水找零 链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 细节&#xff1a; 1. 首先根据题意就是只有5.的成本&#xff0c;然后就开始找钱&#xff0c;找钱也是10.和5. 2. 直接根据10 和 5 进行变量定义&#xff0c;然后去循环…...

Ditto:提升剪贴板体验的宝藏软件(复制粘贴效率翻倍、文本处理好助手)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录 一、什么是Ditto&#xff1f;二、下载安装三、如…...

【自然语言处理-工具篇】spaCy<2>--模型的使用

前言 之前已经介绍了spaCy的安装,接下来我们要通过下载和加载模型去开始使用spaCy。 下载模型 经过训练的 spaCy 管道可以作为 Python 包安装。这意味着它们是应用程序的一个组件,就像任何其他模块一样。可以使用 spaCy download的命令安装模型,也可以通过将 pip 指向路径或…...

Java之通过Jsch库连接Linux实现文件传输

Java之通过JSch库连接Linux实现文件传输 文章目录 Java之通过JSch库连接Linux实现文件传输1. JSch2. Java通过Jsch连接Linux1. poxm.xml2. 工具类3. 调用案例 1. JSch 官网&#xff1a;JSch - Java Secure Channel (jcraft.com) JSch是SSH2的纯Java实现。 JSch 允许您连接到 ss…...

Nginx七层负载均衡之动静分离

思路: servera:负载均衡服务器 serverb:静态服务器 serverc:动态服务器 serverd:默认服务器 servera(192.168.233.132): # 安装 Nginx 服务器 yum install nginx -y#关闭防火墙和selinux systemctl stop firewalld setenforce 0# 切换到 Nginx 配置文…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...