C++ 容器查找效率
C++ 容器查找效率
只要选对容器,多写几行代码就能让程序“飞”起来。下面用生活化的比喻 + 足够多的带注释示例,帮你弄懂常用 STL 容器的查找特性。
读完你应该能快速判断:“我的场景该用哪一个?”
0. 先把“查找复杂度”聊明白
记号 | 含义 | 举个🌰 |
---|---|---|
O(1) | 常数时间 | 像从冰箱门口拿饮料——一下就到手 |
O(log n) | 对数时间 | 折半查电话簿——越找越快 |
O(n) | 线性时间 | 排队买奶茶——要挨个等 |
只要记住:数字越小越快,O(1)
最爽,O(n)
最慢。
1. std::vector
—— “排排坐”的长桌子
- 特点:元素一字排开,内存连续,跟操场跑道一样直。
- 查找
- 没排序:只能一个个比——
O(n)
- 排好序:可折半查——
O(log n)
- 没排序:只能一个个比——
#include <vector>
#include <algorithm> // std::sort, std::binary_search
#include <iostream>int main() {std::vector<int> nums{5, 1, 4, 3, 2}; // 连续摆放的「长桌子」std::sort(nums.begin(), nums.end()); // ① 排序一次,之后查找快// nums 变成 {1,2,3,4,5}bool has3 = std::binary_search( // ② 折半查找 3nums.begin(), nums.end(), 3); // O(log n)std::cout << (has3 ? "找到了" : "没找到") << '\n';
}
什么时候用
- 数据量可控、想要下标随机访问。
- 插入删除不多(尤其不是在中间插)。
2. std::list
—— “珍珠项链”
- 特点:每颗珠子(节点)用线(指针)串起来,插拔容易。
- 查找:得一颗颗摸——
O(n)
,而且分散指针不利于 CPU 缓存。
#include <list>
#include <algorithm>
#include <iostream>int main() {std::list<int> lst{1, 2, 3, 4, 5}; // 一串节点auto it = std::find(lst.begin(), lst.end(), 3); // ① 线性查找std::cout << (it != lst.end() ? "找到了" : "没找到") << '\n';
}
什么时候用
插入 / 删除动作特别频繁、但不太在意查找速度,比如任务队列需要随时插入或移走元素。
3. std::set
—— 自动排序的“有序字典”
- 底层:红黑树,像一个能自动平衡的家谱图。
- 查找 / 增删:都
O(log n)
。
#include <set>
#include <iostream>int main() {std::set<int> s{4, 1, 3, 2}; // 元素自动有序:{1,2,3,4}bool has2 = s.contains(2); // C++20 起可直接 containsstd::cout << (has2 ? "有 2" : "没 2") << '\n';
}
什么时候用
既想要“去重”又想要“元素排好序”,而且单个元素查找要快。
4. std::unordered_set
—— “散列表”小黑屋
- 底层:哈希表,把元素按哈希值分到不同“桶”里。
- 平均查找:
O(1)
,最坏冲突多时O(n)
。 - 元素无序:放进去啥顺序不管。
#include <unordered_set>
#include <iostream>int main() {std::unordered_set<std::string> words; // 小黑屋摞桶words.insert("hello");words.insert("world");if (words.contains("hello")) { // 平均 O(1)std::cout << "嘿~ 找到了 hello\n";}
}
什么时候用
不需要顺序,只想“秒查秒存”,典型如去重、统计次数。
5. std::map
vs std::unordered_map
—— 键值对“双子星”
容器 | 底层 | 查找 | 是否有序 |
---|---|---|---|
map | 红黑树 | O(log n) | ✅ |
unordered_map | 哈希表 | O(1) 平均 | ❌ |
#include <map>
#include <unordered_map>
#include <iostream>int main() {std::map<int, std::string> ordered; // 有序ordered[2] = "B"; ordered[1] = "A";std::unordered_map<int, std::string> hash; // 无序hash[2] = "B"; hash[1] = "A";std::cout << ordered[1] << ' ' << hash[1] << '\n';
}
什么时候用
- 需要按键遍历且保持有序:
map
。- 只关心查、增、删速度:
unordered_map
。
6. std::deque
—— 可以从两头装菜的“长盘子”
- 特点:首尾插入 / 删除都是
O(1)
;中间操作比vector
慢点。 - 查找:线性
O(n)
;随机访问语法与vector
一样。
#include <deque>
#include <algorithm>
#include <iostream>int main() {std::deque<int> q{1, 2, 3};q.push_front(0); // 头部 O(1)q.push_back(4); // 尾部 O(1)bool has3 = std::find(q.begin(), q.end(), 3) != q.end();std::cout << (has3 ? "有 3" : "没 3") << '\n';
}
什么时候用
既想要随机访问,又要在首尾频繁加减元素,比如滑动窗口算法。
7. “多索引”技巧 —— 一份数据,多把钥匙
如果你既想按 ID 查,又想按 名字 查,可以:
#include <vector>
#include <unordered_map>struct User { int id; std::string name; };std::vector<User> users; // 主数组
std::unordered_map<int, User*> id_index; // id → 指针
std::unordered_map<std::string, User*> name_index; // name → 指针
- 插入一个用户时,三处都要更新。
- 查找时,从对应索引直接拿到指针,速度飞快。
8. 记忆卡片(纯中文朗朗上口)
小而随机选 vector
插删中间选 list
要有序就 set/map
求极致快 unordered_*
两头忙活用 deque
多条件查 自建索引
最后一句话
先写代码,测一次性能——复杂度只给方向,真快还是得跑数据。祝你写得顺、跑得飞!
相关文章:
C++ 容器查找效率
C 容器查找效率 只要选对容器,多写几行代码就能让程序“飞”起来。下面用生活化的比喻 足够多的带注释示例,帮你弄懂常用 STL 容器的查找特性。 读完你应该能快速判断:“我的场景该用哪一个?” 0. 先把“查找复杂度”聊明白 记号…...
汽车可变转向比系统的全面认识
一、什么是转向比? 转向比又叫转向传动比,是指方向盘转向角度与车轮转向角度之比。 例如,方向盘向左转动了60角,而车轮则向左转动了30角,转向比就是2:1。 转向比越大,意味着要使车轮转向达到指…...
知识储备-后仿
仿真环境设定 mem、constant input(scan/test)等设非x初值无复位ff通过force-release处理vcs timing_check、optconfigfile (自定义配置,如指定模块timing check与否)设置运行核数、仿真精度不要过小设置、根据测试目的选择性关闭、dump范围(时间/空间)…...
C# AutoResetEvent 详解
一、简介 AutoResetEvent 是 .NET 中一个重要的线程同步原语,用于线程间的信号通知。下面我将从多个方面详细讲解 AutoResetEvent。 AutoResetEvent 是 System.Threading 命名空间下的一个类,它表示一个线程同步事件,在等待线程被释放后会自…...
【水印图片文字识别】水印相机拍摄的照片提取重要的信息可以批量改名,批量识别水印文字内容批量给图片改名,基于QT和腾讯OCR的识别方案
应用场景 在日常工作和生活中,人们使用水印相机拍摄的照片往往包含重要的信息,如拍摄地点、时间、事件等。这些信息以水印的形式存在于照片中。当需要对大量照片进行管理时,手动为每张照片重命名是一项繁琐且容易出错的工作。通过批量识别水印文字内容并为图片改名,可以提…...
【架构】Armstrong公理系统通俗详解:数据库设计的基本法则
关系数据库就像一本精心设计的通讯录,而Armstrong公理系统则是帮我们整理这本通讯录的基本规则。本文将用简单易懂的语言和生活实例,带你理解这套看似复杂的理论。 1. 什么是函数依赖? 想象你有一个学生信息表,包含学号、姓名、…...
Redis高频核心面试题
1.阐述Redis的主要的特性和优势 ? 【Redis 的主要特性】 (1)Redis 是完全开源免费的,遵守 BSD 协议,是一个高性能的 key-value 数据库 (2)Redis 与其他 key - value 缓存产品有以下三个特点&a…...
Vue3-原始值的响应式方案ref
一、原始类型的值 原始类型的指的是: boolean、number、string、symbol、undefind和null等类型的值. 一、初识ref 为什么vue3需要对原始值的响应式做单独处理?因为Javascript中的Proxy只能代理对象类型的数据, 如普通对象、数组、Set、Map等。 为了解决Proxy不能代理原始类…...
VUE的创建
Vue Vue的创建脚手架创建Vue的解析setup函数:插值表达式数据响应式 ⽬录和⽂件解读指令 Vue的创建 下载VScode https://code.visualstudio.com/download 加入拓展包 点击 然后输入代码 <!DOCTYPE html> <html lang"en"><head><meta charset&…...
第51讲:AI在农业政策支持系统中的应用——用人工智能点亮科学决策的新范式
目录 🧠 开篇引导:农业决策,如何更科学? 🤖 什么是“AI驱动的农业政策支持系统”? 🧪 案例解析:AI如何助力农业政策? 🌾 案例一:政策补贴的智能匹配 🌍 案例二:土地利用规划支持 🛠 AI在农业政策建模中的常用技术 📈 可视化与接口建议 🌟 未来…...
开关电源LM5160-Q1 在 Fly-Buck 电路中的硬件设计与 PCB Layout 优化
一、LM5160-Q1 规格书深度解读与硬件设计参数提取 核心功能 宽输入范围:4.5V~65V,支持汽车级输入电压波动(AEC-Q100 标准,温度等级 1:-40C~125C)。 集成度:内置高侧 / 低侧 MOSFET,无需外部肖特基二极管,同步降压 / Fly-Buck 双模式。 控制架构:自适应恒定导通时间…...
面向 C# 初学者的完整教程
🧱 一、项目结构说明 你的项目大致结构如下: TaskManager/ ├── backend/ │ ├── TaskManager.Core/ // 实体类和接口 │ ├── TaskManager.Infrastructure/ // 数据库、服务实现 │ └── TaskManager.API/ // We…...
Python实现孔填充与坐标转换
一、问题背景 在工业自动化、材料加工等领域,常需要在图像识别的闭合区域内生成等间距的孔位坐标。本文基于OpenCV库,提出一种从图像边界提取到物理坐标生成的完整解决方案,实现以下核心功能: 像素坐标到实际尺寸的转换安全间距…...
精益数据分析(16/126):掌握关键方法,探寻创业真谛
精益数据分析(16/126):掌握关键方法,探寻创业真谛 大家好!在创业与数据分析的学习道路上,每一次的探索都让我们离成功更近一步。今天,我带着和大家共同进步的初心,继续深入解读《精…...
pytorch(gpu版本安装)
Pytorch官网下载很慢 选择以下方法,关于版本对应从pytorch官网查看 官网方法 pip install torch2.2.0 torchvision0.17.0 torchaudio2.2.0 --index-url https://download.pytorch.org/whl/cu121 其他方法 pip install torch2.2.0cu121 torchvision0.17.0cu121 t…...
day001
文章目录 1. 常用Linux发行版本2. 常用的Linux系统及版本3. Linux系统运行在哪?4. 安装kylin虚拟机4.1 环境准备4.2 新建虚拟机4.3 配置虚拟机参数4.4 同意系统使用协议4.5 登录系统,查看ip4.6 保存系统快照 5. 远程连接5.1 连接类型对比5.2 使用Xshell连…...
k8s 证书相关问题
1.重新生成新证书 kubeadm init phase certs apiserver-etcd-client --config ~/kubeadm.yaml这个命令表示生成 kube-apiserver 连接 etcd 使用的证书,生成后如下 -rw------- 1 root root 1.7K Apr 23 16:35 apiserver-etcd-client.key -rw-r--r-- 1 root root 1.2K Apr 23 …...
Spring JDBC 的开发步骤(注解方式)
Spring JDBC 的开发步骤主要包括以下关键环节,结合代码示例说明如下: 1. 添加依赖 在 pom.xml 中引入 Spring JDBC 和数据库驱动依赖(以 HikariCP 连接池和 MySQL 为例): <!-- Spring JDBC --> <dependency…...
蓝桥杯 15.小数第n位
小数第n位 原题目链接 题目描述 我们知道,整数做除法时,有时会得到有限小数,有时会得到无限循环小数。 如果我们把有限小数的末尾加上无限多个 0,它们就具有了统一的形式。 本题的任务是:在上述约定下,…...
[计算机科学#1]:计算机的前世今生,从算盘到IBM的演变之路
【核知坊】:释放青春想象,码动全新视野。 我们希望使用精简的信息传达知识的骨架,启发创造者开启创造之路!!! 内容摘要:在我们的日常生活中,计算机无处不在——…...
【LangChain4j】AI 第一弹:LangChain4j 的理解
一、LangChain4j 的简介 1.1 LangChain4j的背景 LangChain4j(LangChain for java) 的目标是简化将大语言模型(LLM - Large Language Model)集成到 Java 应用程序中的过程。 官网: https://docs.langchain4j.dev 202…...
深入解析C++ STL Stack:后进先出的数据结构
一、引言 在计算机科学中,栈(Stack)作为一种遵循后进先出(LIFO)原则的数据结构,是算法设计和程序开发的基础构件。C STL中的stack容器适配器以简洁的接口封装了底层容器的操作,为开发者提供了…...
3.2 Agent核心能力:感知、规划、决策与执行
智能代理(Agent)是一种能够在复杂环境中自主运作的计算实体,其智能行为依赖于四大核心能力:感知(Perception)、规划(Planning)、决策(Decision-making)和执行…...
(即插即用模块-特征处理部分) 四十一、(2024) MSAA 多尺度注意力聚合模块
文章目录 1、Multi-Scale Attention Aggregation Module2、代码实现 paper:CM-UNet: Hybrid CNN-Mamba UNet for Remote Sensing Image Semantic Segmentation Code:https://github.com/XiaoBuL/CM-UNet 1、Multi-Scale Attention Aggregation Module 传…...
【速写】hook与fx
文章目录 问题方法方法 1:使用 PyTorch 的 register_forward_hook方法 2:自定义前向传播(修改 forward 方法)方法 3:使用 output_attentions 或 output_hidden_states方法 4:使用 torch.fx 进行动态追踪总结…...
基于javaweb的SpringBoot扶农助农平台管理系统设计与实现(源码+文档+部署讲解)
技术范围:SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...
用户模块-SpringEvent观察者模式
1. 背景与需求 在很多系统中,我们常常需要对用户的行为进行处理,比如发放奖励、处理通知等。在这个例子中,我们希望在两个场景下发放“改名卡”这个奖励: 用户注册时:当一个新用户注册成功时,我们希望立即发…...
三目云台转动性能稳定性
三目云台是一种具备三个摄像头或观测窗口的云台设备,其转动性能对于实现全方位、多角度的监控或观测至关重要。以下是对三目云台转动的详细分析: 一、转动原理 云台本身是一种摄像机稳定器,通过内置的电机和控制系统实现转动。三目云台则在…...
Python基础语法3
目录 1、函数 1.1、语法格式 1.2、函数返回值 1.3、变量作用域 1.4、执行过程 1.5、链式调用 1.6、嵌套调用 1.7、函数递归 1.8、参数默认值 1.9、关键字参数 2、列表 2.1、创建列表 2.2、下标访问 2.3、切片操作 2.4、遍历列表元素 2.5、新增元素 2.6、查找元…...
45、子类需要重写父类的构造函数嘛,子类自己的构造函数呢?
45、子类需要重写父类的构造函数嘛,子类自己的构造函数呢? 一、子类是否需要重写父类的构造函数? 1. 不需要重写的场景 基类有无参构造函数 若父类(基类)显式或隐式定义了无参构造函数,子类无需重写构造函…...
C语言 ——— 分支循环语句
目录 分支循环语句 单分支 多分支 switch 分支语句 牛刀小试 判断一个数是否是奇数 输出 1-100之间 的奇数 计算 n 的阶乘 计算 1! 2! 3! ... n! 在一个有序数组中查找具体的某一个数字 打印 100-200 之间的素数 求两个整数的最大公约数 getchar函数 和 putc…...
解耦旧系统的利器:Java 中的适配器模式(Adapter Pattern)实战解析
在现代软件开发中,我们经常需要与旧系统、第三方库或不一致接口打交道。这时候,如果能优雅地整合这些不兼容组件,又不破坏原有结构,就需要一位“翻译官” —— 适配器模式。本文将通过 Java 实例,详细讲解适配器模式的…...
C++学习之游戏服务器开发十五QT登录器实现
目录 1.界面搭建 2.登录客户端步骤分析 3.拼接登录请求实现 4.发送http请求 5.服务器登录请求处理 6.客户端处理服务器回复数据 7.注册页面启动 8.qt启动游戏程序 1.界面搭建 2.登录客户端步骤分析 3.拼接登录请求实现 CGI 程序处理流程 程序员自己写程序处理各种业务 …...
搭建Stable Diffusion图像生成系统实现通过网址访问(Ngrok+Flask实现项目系统公网测试,轻量易部署)
目录 前言 背景与需求 🎯 需求分析 核心功能 网络优化 方案确认 1. 安装 Flask 和 Ngrok 2. 构建 Flask 应用 3. 使用 Ngrok 实现内网穿透 4. 测试图像生成接口 技术栈 实现流程 优化目标 实现细节 1. 迁移到Flask 2. 持久化提示词 3. 图像下载功能 …...
第五章:5.3 ESP32物联网应用:阿里云IoT平台与腾讯云IoT平台的数据上传与远程控制
一、阿里云IoT平台接入 1. 准备工作 注册阿里云账号 访问阿里云官网,注册并完成实名认证。创建产品和设备 进入物联网平台控制台 → 公共实例 → 创建产品(例如产品名称“ESP32_Sensor”,节点…...
【AI News | 20250423】每日AI进展
AI Repos 1、suna Suna是一款完全开源的AI助手,旨在通过自然对话帮助用户轻松完成现实世界的任务。它作为您的数字伙伴,提供研究、数据分析和日常问题解决等功能,并结合强大的能力与直观的界面,理解您的需求并交付成果。Suna的工…...
3.1 Agent定义与分类:自主Agent、协作Agent与混合Agent的特点
随着人工智能技术的快速发展,智能代理(Agent)作为一种能够感知环境、自主决策并采取行动的计算实体,已成为人工智能领域的重要研究对象和应用工具。特别是在大模型(Large Models)的赋能下,Agent…...
stack和queue的学习
stack的介绍 stack的文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,…...
leetcode-位运算
位运算 371. 两整数之和 题目 给你两个整数 a 和 b ,不使用 运算符 和 - ,计算并返回两整数之和。 示例 1: 输入: a 1, b 2 输出: 3 示例 2: 输入: a 2, b 3 输出: 5 提示&am…...
《浔川AI翻译v6.1.0问题已修复公告》
《浔川AI翻译v6.1.0问题已修复公告》 尊敬的浔川AI翻译用户: 感谢您对浔川AI翻译的支持与反馈!我们已针对 **v6.1.0** 版本中用户反馈的多个问题进行了全面修复,并优化了系统稳定性。以下是本次修复的主要内容: 已修复问题 ✅…...
Unity 创建、读取、改写Excel表格数据
1.导入EPPlus.dll、Excel.dll、Mysql.Data.dll、System.Data.dll;(我这里用的是:Unity2017.3.0) 2.代码如下: using System.Data; using System.IO; using UnityEngine; using OfficeOpenXml; using UnityEditor; us…...
【阿里云大模型高级工程师ACP习题集】2.3 优化提示词改善答疑机器人回答质量
练习题: 【单选题】在使用大模型进行意图识别时,通过设计特定提示词引导模型生成符合预期回答的方法,其本质是( )。 A. 修改模型本身参数 B. 依靠构造输入激发模型内部已有知识 C. 对模型进行微调 D. 改变模型的训练数据 【多选题】以下哪些属于提示词框架中的要素( )。…...
富文本编辑器实现
🎨 富文本编辑器实现原理全解析 📝 基本实现路径图 #mermaid-svg-MO1B8a6kAOmD8B6Y {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-MO1B8a6kAOmD8B6Y .error-icon{fill:#552222;}#mermaid-s…...
海量粒子特效解决方案:VEG
Unity 官方除了一个 GPU 粒子特效的解决方案:Visual Effect Graph,即 VEG,能支持百万级粒子特效的播放。在性能要求高的使用场景中,这个解决方案就能完美解决原本 Particle System 性能低下的问题。关于 VEG 的基本使用方法参考官…...
Java高频面试之并发编程-06
hello啊,各位观众姥爷们!!!本baby今天来报道了!哈哈哈哈哈嗝🐶 面试官:线程上下文切换是什么? 线程上下文切换(Thread Context Switching)是操作系统中 CPU…...
Windows 同步技术-一次性初始化
组件通常设计为在首次调用时执行初始化任务,而不是加载它们时。 一次性初始化函数可确保此初始化仅发生一次,即使多个线程可能尝试初始化也是如此。 Windows Server 2003 和 Windows XP: 应用程序必须使用 互锁函数 或其他同步机制提供自己的…...
Transformer起源-Attention Is All You Need
这篇笔记主要讲解Attention Is All You Need论文。《Attention Is All You Need》由 Ashish Vaswani 等人撰写,于 2017 年发表在 NIPS(Neural Information Processing Systems)会议上。它提出了一种全新的神经网络架构——Transformer&#x…...
被裁20240927 --- 视觉目标跟踪算法
永远都像初次见你那样使我心荡漾 参考文献目前主流的视觉目标跟踪算法一、传统跟踪算法1. 卡尔曼滤波(Kalman Filter)2. 相关滤波(Correlation Filter,如KCF、MOSSE)3. 均值漂移(MeanShift/CamShift&#x…...
每日学习Java之一万个为什么(JUC)
文章目录 Git复习synchronized介绍基本概念特点 使用模板1. 同步方法格式特点 2. 同步代码块格式特点 常见面试题1. synchronized的实现原理?2. synchronized与ReentrantLock的区别?3. synchronized的缺点?4. 死锁的四个必要条件?…...
代码分享:python实现svg图片转换为png和gif
import cairosvg import imageio from PIL import Image import io import osdef svg_to_png(svg_path, png_path):try:cairosvg.svg2png(urlsvg_path, write_topng_path)print(f"成功将 {svg_path} 转换为 {png_path}")except Exception as e:print(f"转换为 P…...