C++ 7
vector 底层原理和扩容过程
- 底层原理
● vector 是 C++ 标准库中的一个容器,可以看作是一个动态数组,它的大小可以根据元素的增加而增长。它通过在堆上分配一段连续的内存空间存放元素,支持时间复杂度为 O(1 ) 的随机访问。
● vector 底层维护了三个迭代器和两个变量,这三个迭代器分别指向对象的起始字节位置,最后一个元素的末尾字节和整个 vector 分配空间的末尾字节。两个变量分别是 size 和 capacity ,Size 表示当前存储元素的数量,capacity 表示当前分配空间的大小。当创建一个 vector 对象时,会分配一个初始化大小的空间存放元素,初始化空间可以通过构造函数的参数指定,缺省情况下为 0。当对 vector 容器进行增加和删除元素时,只需要调整末尾元素指针,而不需要移动整个内存块。 - 扩容机制
● 当添加元素的数量达到当前分配空间的大小时,vector 会申请一个更大的内存块,然后将元素从旧的内存块拷贝到新的内存块中,并释放旧的内存块。 扩容可能导致原有迭代器和指针失效,扩容完成后,容器返回指向新内存区域的迭代器或指针。
● vector 扩容的机制分为固定扩容和加倍扩容。
○ 固定扩容就是在每次扩容时在原容量的基础上增加固定容量。但是固定扩容可能会面临多次扩容(扩容的不够大)的情况,时间复杂度较高。
○ 加倍扩容就是在每次扩容时原容量翻倍,优点是使得正常情况下扩容的次数大大减少,时间复杂度低,缺点是空间利用率低。
push_back()和emplace_back()的区别
push_back()和emplace_back()都是C++标准库容器(如std::vector)中用来添加元素的方法,但它们在添加元素的方式上有所不同:
- push_back():
○ 语法是container.push_back(value);,传入的是一个值或对象的副本/移动版本。
○ 它接受一个元素的副本或移动该元素,然后将其添加到容器的末尾。
○ 这个方法需要先构造一个元素的副本或移动构造一个临时对象,然后再将其添加到容器中。 - emplace_back():
○ 语法是container.emplace_back(args…);,传入的是构造新元素所需的参数列表。
○ 它使用就地构造(emplace)的方式,直接在容器的内存空间中构造新元素。
○ 这个方法避免了元素的复制或移动操作,因为它直接在容器的末尾空间构造新元素。 - 性能:
○ emplace_back()通常比push_back()更高效,因为它避免了额外的复制或移动操作。
○ 当构造函数需要大量资源时,emplace_back()的优势更加明显。
map dequeu list的实现原理
- std:: map
● 基于红黑树:std::map 基于一种自平衡的二叉搜索树——红黑树实现。
● 有序容器:元素按照键的顺序自动排序,通常是按照小于(<)运算符定义的顺序。
● 唯一键:每个键都是唯一的,不允许有重复的键。
● 时间复杂度:提供对数时间复杂度 (O(log n)) 的查找、插入和删除操作。
● 迭代器:由于 std::map 是基于树的,迭代器在遍历时是有序的。 - std::list
● 基于双向链表:std::list 是一个双向链表,每个元素都持有指向前一个和后一个元素的指针。
● 无序容器:元素在容器中没有特定的顺序。
● 插入和删除:提供高效的插入和删除操作,特别是当需要在容器中间插入或删除元素时。
● 时间复杂度:提供线性时间复杂度 (O(n)) 的查找操作,但插入和删除可以在 O(1) 时间内完成,前提是已经拥有指向待插入或删除元素的迭代器。
● 迭代器:由于 std::list 是线性结构,迭代器在遍历时是顺序的,但不支持随机访问。 - std::deque
● 基于动态数组:std::deque 是一个基于动态数组的序列容器,可以高效地从两端添加或删除元素。
● 允许序列操作:可以快速地在队列的前端和后端添加或删除元素。
● 时间复杂度:提供常数时间复杂度 (O(1)) 的前端和后端插入和删除操作。中间插入或删除操作可能需要 O(n) 时间。
map && unordered_map的区别和实现机制
- map
● 基于红黑树:std::map 基于一种自平衡的二叉搜索树(通常是红黑树)实现,可以保持元素有序。
● 有序容器:元素按照键的顺序自动排序,可以通过键值进行有序遍历。
● 元素访问:提供对元素的快速查找、插入和删除操作,时间复杂度为 O(log n)。
● 唯一键:每个键都是唯一的,不允许有重复的键。
● 迭代器稳定性:由于基于树结构,迭代器在遍历时是稳定的,即使容器发生插入或删除操作,迭代器指向的元素也不会改变,除非该元素被删除。 - unordered_map
● 基于哈希表:std::unordered_map 基于哈希表实现,通过哈希函数将键分布到数组的槽位中。
● 无序容器:元素在容器中是无序的,不能按键的顺序进行遍历。
● 元素访问:理想情况下,提供平均时间复杂度为 O(1) 的快速查找、插入和删除操作。最坏情况下,性能可能下降到 O(n)。
● 允许重复键:实际上,std::unordered_map 不允许有重复的键,因为哈希表的设计不允许两个元素具有相同的哈希值。如果发生哈希冲突,会通过某种方式(如链表或开放寻址)解决。
● 迭代器稳定性:由于基于哈希表,迭代器的稳定性不如 std::map。在发生哈希表的重新哈希 (rehashing) 时,迭代器可能会失效。
● 遍历顺序与创建该容器时输入元素的顺序是不一定一致的,遍历是按照哈希表从前往后依次遍历的。 - 使用场景
● 当需要元素有序且对性能有较高要求时,应选择std::map。
● 当元素的顺序不重要,且需要快速访问元素时,应选择std::unordered_map。 - 实现机制
● std::map 的实现依赖于红黑树的旋转和颜色变换来保持树的平衡,确保操作的时间复杂度。
● std::unordered_map 的实现依赖于一个良好的哈希函数来最小化冲突,并通过解决冲突的机制(如链表或开放寻址)来存储具有相同哈希值的元素。
相关文章:
C++ 7
vector 底层原理和扩容过程 底层原理 ● vector 是 C 标准库中的一个容器,可以看作是一个动态数组,它的大小可以根据元素的增加而增长。它通过在堆上分配一段连续的内存空间存放元素,支持时间复杂度为 O(1 ) 的随机访问。 ● vec…...
论文阅读(七):贝叶斯因果表型网络解释遗传变异和生物学知识
1.论文链接:Bayesian Causal Phenotype Network Incorporating Genetic Variation and Biological Knowledge 摘要: 在分离群体中,数量性状基因座(QTL)定位可以确定对表型有因果效应的QTL。这些方法的一个共同特点是Q…...
数据库之PostgreSQL详解
一、PostgreSQL介绍 PostgreSQL是一个功能强大的 开源 的关系型数据库。底层基于C实现。 PostgreSQL的开源协议和Linux内核版本的开源协议是一样的。。BDS协议,这个协议基本和MIT开源协议一样,说人话,就是你可以对PostgreSQL进行一些封装&a…...
计算机毕业设计Python+CNN卷积神经网络高考推荐系统 高考分数线预测 高考爬虫 协同过滤推荐算法 Vue.js Django Hadoop 大数据毕设
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
可被electron等调用的Qt截图-录屏工具【源码开放】
1. 工具功能简介: (1)、QT5.15.2截图工具(exe)可单独使用或嵌入IM(嵌入方法参照:https://gitee.com/lykiao/yfscreenshot_release) (2)、支持通过Windows消息通知截图成功或取消 (3)、支持圆形、矩形、线条…...
【Python蓝桥杯备赛宝典】
文章目录 一、基础数据结构1.1 链表1.2 队列1.3 栈1.4 二叉树1.5 堆二、基本算法2.1 算法复杂度2.2 尺取法2.3 二分法2.4 三分法2.5 倍增法和ST算法2.6 前缀和与差分2.7 离散化2.8 排序与排列2.9 分治法2.10贪心法1.接水时间最短问题2.糖果数量有限问题3.分发时间最短问题4.采摘…...
.cc扩展名是什么语言?C语言必须用.c为扩展名吗?主流编程语言扩展名?Java为什么不能用全数字的文件名?
.cc扩展名是什么语言? .cc是C语言使用的扩展名,一种说法是它是c with class的简写,当然C语言使用的扩展名不止.cc和.cpp, 还包含.cxx, .c, .C等,这些在不同编译器系统采用的默认设定不同,需要区分使用。当然,编译器提…...
基于 Redis GEO 实现条件分页查询用户附近的场馆列表
🎯 本文档详细介绍了如何使用Redis GEO模块实现场馆位置的存储与查询,以支持“附近场馆”搜索功能。首先,通过微信小程序获取用户当前位置,并将该位置信息与场馆的经纬度数据一同存储至Redis中。利用Redis GEO高效的地理空间索引能…...
项目练习:重写若依后端报错cannot be cast to com.xxx.model.LoginUser
文章目录 一、情景说明二、解决办法 一、情景说明 在重写若依后端服务的过程中 使用了Redis存放LoginUser对象数据 那么,有存就有取 在取值的时候,报错 二、解决办法 方法1、在TokenService中修改如下 getLoginUser 方法中:LoginUser u…...
Python算法详解:贪心算法
贪心算法(Greedy Algorithm)是一种通过选择当前最优解以期望达到全局最优解的算法思想。它在每一步选择时只考虑当前状态下的局部最优,而不关心全局问题的复杂性。这种算法简单高效,适用于某些特定问题,尤其是存在贪心…...
5.3.2 软件设计原则
文章目录 抽象模块化信息隐蔽与独立性衡量 软件设计原则:抽象、模块化、信息隐蔽。 抽象 抽象是抽出事物本质的共同特性。过程抽象是指将一个明确定义功能的操作当作单个实体看待。数据抽象是对数据的类型、操作、取值范围进行定义,然后通过这些操作对数…...
sublime_text的快捷键
sublime_text的快捷键 向下复制, 复制光标所在整行并插入到下一行:通过 CtrlShiftD 实现快速复制当前行的功能。 可选多行, 不选则复制当前行 ctrl Shift D 删除当前行:通过 CtrlShiftK 实现快速删除当前行的功能。 可选多行, 不选则删当前行 ctrl S…...
【项目集成Husky】
项目集成Husky 安装初始化 Husky在.husky → pre-commit文件中添加想要执行的命令 安装 使用 Husky 可以帮助你在 Git 钩子中运行脚本,例如在提交代码前运行测试或格式化代码pnpm add --save-dev husky初始化 Husky npx husky init这会在项目根目录下创建一个 .hu…...
本地运行大模型效果及配置展示
电脑上用ollama安装了qwen2.5:32b,deepseek-r1:32b,deepseek-r1:14b,llama3.1:8b四个模型,都是Q4_K_M量化版。 运行过程中主要是cpu和内存负载比较大,qwen2.5:32b大概需要22g,deepseek-r1:32b类…...
数据结构与算法 —— 常用算法模版
数据结构与算法 —— 常用算法模版 二分查找素数筛最大公约数与最小公倍数 二分查找 人间若有天堂,大马士革必在其中;天堂若在天空,大马士革必与之齐名。 —— 阿拉伯谚语 算法若有排序,二分查找必在其中;排序若要使用…...
进阶数据结构——高精度运算
目录 前言一、高精度运算的定义与背景二、高精度运算的实现方式三、高精度运算的算法实现四、高精度运算的应用场景五、代码模版(c)六、经典例题1.[高精度加法](https://www.lanqiao.cn/problems/1516/learning/?page1&first_category_id1&name…...
第一届“启航杯”网络安全挑战赛WP
misc PvzHE 去这个文件夹 有一张图片 QHCTF{300cef31-68d9-4b72-b49d-a7802da481a5} QHCTF For Year 2025 攻防世界有一样的 080714212829302316092230 对应Q 以此类推 QHCTF{FUN} 请找出拍摄地所在位置 柳城 顺丰 forensics win01 这个软件 云沙盒分析一下 md5 ad4…...
前端八股CSS:盒模型、CSS权重、+与~选择器、z-index、水平垂直居中、左侧固定,右侧自适应、三栏均分布局
一、盒模型 题目:简述CSS的盒模型 答:盒模型有两种类型,可以通过box-sizing设置 1.标准盒模型(content-box):默认值,宽度和高度只包含内容区域,不包含内边距、边框和外边距。 2.边框盒模型&a…...
使用 Tauri 2 + Next.js 开发跨平台桌面应用实践:Singbox GUI 实践
Singbox GUI 实践 最近用 Tauri Next.js 做了个项目 - Singbox GUI,是个给 sing-box 用的图形界面工具。支持 Windows、Linux 和 macOS。作为第一次接触这两个框架的新手,感觉收获还蛮多的,今天来分享下开发过程中的一些经验~ 为啥要做这个…...
Windows程序设计10:文件指针及目录的创建与删除
文章目录 前言一、文件指针是什么?二、设置文件指针的位置:随机读写,SetFilePointer函数1.函数说明2.函数实例 三、 目录的创建CreateDirectory四、目录的删除RemoveDirectory总结 前言 Windows程序设计10:文件指针及目录的创建与…...
Rk3588芯片介绍(含数据手册)
芯片介绍:RK3588是一款低功耗,高性能的处理器,适用于基于arm的PC和边缘计算设备,个人移动互联网设备和其他数字多媒体应用,集成了四核Cortex-A76和四核Cortex-A55以及单独的NEON协处理器 视频处理方面:提供…...
golang 使用双向链表作为container/heap的载体
MyHeap:container/heap的数据载体,需要实现以下方法: Len:堆中数据个数 Less:第i个元素 是否必 第j个元素 值小 Swap:交换第i个元素和 第j个元素 Push:向堆中追加元素 Pop:从堆…...
HTML DOM 修改 HTML 内容
HTML DOM 修改 HTML 内容 引言 HTML DOM(文档对象模型)是浏览器内部用来解析和操作HTML文档的一种机制。通过DOM,我们可以轻松地修改HTML文档的结构、样式和行为。本文将详细介绍如何使用HTML DOM来修改HTML内容,包括元素的增删改查、属性修改以及事件处理等。 1. HTML …...
基于51单片机和WS2812B彩色灯带的流水灯
目录 系列文章目录前言一、效果展示二、原理分析三、各模块代码四、主函数总结 系列文章目录 前言 用彩色灯带按自己想法DIY一条流水灯,谁不喜欢呢? 所用单片机:STC15W204S (也可以用其他1T单片机,例如,S…...
React第二十八章(css modules)
css modules 什么是 css modules 因为 React 没有Vue的Scoped,但是React又是SPA(单页面应用),所以需要一种方式来解决css的样式冲突问题,也就是把每个组件的样式做成单独的作用域,实现样式隔离,而css modules就是一种…...
瑞芯微方案:RV1126定制开发板方案定制
产品简介 RV1126 核心板是常州海图电子科技有限公司推出的一款以瑞芯微 RV1126处理器为核心的通用产品,其丰富的设计资源、稳定的产品性能、强力的设计支持,为客户二次开发快速转化产品提供强有力的技术保障。RV1126 核心板集多种优势于一身,…...
吴恩达深度学习——有效运作神经网络
内容来自https://www.bilibili.com/video/BV1FT4y1E74V,仅为本人学习所用。 文章目录 训练集、验证集、测试集偏差、方差正则化正则化参数为什么正则化可以减少过拟合Dropout正则化Inverted Dropout其他的正则化方法数据增广Early stopping 归一化梯度消失与梯度爆…...
ollama改模型的存盘目录解决下载大模型报c:盘空间不足的问题
使用Ollama和Open WebUI快速玩转大模型:简单快捷的尝试各种llm大模型,比如DeepSeek r1,非常简单方便,参见:使用Ollama和Open WebUI快速玩转大模型:简单快捷的尝试各种llm大模型,比如DeepSeek r1…...
springboot集成钉钉,发送钉钉日报
目录 1.说明 2.示例 3.总结 1.说明 学习地图 - 钉钉开放平台 在钉钉开放文档中可以查看有关日志相关的api,主要用到以下几个api: ①获取模板详情 ②获取用户发送日志的概要信息 ③获取日志接收人员列表 ④创建日志 发送日志时需要根据模板规定日志…...
Day49:添加字典元素
在 Python 中,字典是一个可变的数据类型,这意味着你可以随时添加新的键值对。今天我们将学习如何向字典中添加元素。 1. 使用方括号 ([]) 添加新元素 最简单的方法是通过字典的键,使用方括号 [] 来添加新的键值对。如果该键已经存在&#x…...
Keepalived 安装
环境介绍 操作系统Kylin Linux Advanced Server V10 (Lance)Kylin Linux Advanced Server V10 (Lance)Kylin Linux Advanced Server V10 (Lance)内核版本Linux 4.19.90-52.22.v2207.ky10.aarch64Linux 4.19.90-52.22.v2207.ky10.aarch64Linux 4.19.90-52.22.v2207.ky10.aarch64…...
AI应用部署——streamlit
如何把项目部署到一个具有公网ip地址的服务器上,让他人看到? 可以利用 streamlit 的社区云免费部署 1、生成requirements.txt文件 终端输入pip freeze > requirements.txt即可 requirements.txt里既包括自己安装过的库,也包括这些库的…...
C++中vector追加vector
在C中,如果你想将一个vector追加到另一个vector的后面,可以使用std::vector的成员函数insert或者std::copy,或者简单地使用std::vector的push_back方法逐个元素添加。这里我将展示几种常用的方法: 方法1:使用insert方…...
普通人可以从DeepSeek工具获得什么帮助?
普通人可以从DeepSeek工具获得多方面的帮助,具体如下: 学习与教育 DeepSeek可以为学生提供作业辅导、知识点整理、论文思路生成等服务,帮助他们更好地理解和掌握学习内容。例如,学生可以通过DeepSeek获得详细的解题步骤和思路&…...
EtherCAT-快速搭建
EtherCAT-快速搭建 快速简介 快速简介 EtherCAT现场总线协议是由德国倍福公司在2003年提出的,该通讯协议拓扑结构十分灵活,数据传输速度快,同步特性好,可以形成各种网络拓扑结构。倍福公司推出了自己的ASIC专用芯片有ET1100和ET1…...
[Collection与数据结构] B树与B+树
🌸个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 🏵️热门专栏: 🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 🍕 Collection与…...
《大数据时代“快刀”:Flink实时数据处理框架优势全解析》
在数字化浪潮中,数据呈爆发式增长,实时数据处理的重要性愈发凸显。从金融交易的实时风险监控,到电商平台的用户行为分析,各行业都急需能快速处理海量数据的工具。Flink作为一款开源的分布式流处理框架,在这一领域崭露头…...
【AIGC专栏】AI在自然语言中的应用场景
ChatGPT出来以后,突然间整个世界都非常的为之一惊。很多人大喊AI即将读懂人类,虽然这是一句夸大其词的话,但是经过未来几十年的迭代,ChatGPT会变成什么样我们还真的很难说。在当前生成式内容来说,ChatGPT毫无疑问在当前…...
神经网络|(七)概率论基础知识-贝叶斯公式
【1】引言 前序我们已经了解了一些基础知识。 古典概型:有限个元素参与抽样,每个元素被抽样的概率相等。 条件概率:在某条件已经达成的前提下,新事件发生的概率。实际计算的时候,应注意区分,如果是计算综…...
数科OFD证照生成原理剖析与平替方案实现
数科OFD证照生成原理剖析及C#平替方案实现 1. OFD证照生成原理 OFD(Open Fixed-layout Document)是一种基于XML的固定版式文档格式,广泛应用于电子发票、电子证照等领域。数科OFD证照生成工具的核心原理包括以下几个方面: OFD文…...
未来无线技术的发展方向
未来无线技术的发展趋势呈现出多样化、融合化的特点,涵盖速度、覆盖范围、应用领域、频段利用、安全性等多个方面。这些趋势将深刻改变人们的生活和社会的运行方式。 传输速度提升:Wi-Fi 技术迭代加快,如 Wi-Fi7 理论峰值速率达 46Gbps&#…...
验证二叉搜索数(98)
98. 验证二叉搜索树 - 力扣(LeetCode) 解法: /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* …...
Day51:type()函数
在 Python 中,type() 是一个内置函数,用于返回对象的类型。它可以用于检查变量的类型,也可以用于动态创建新的类型。今天,我们将深入了解 type() 函数的使用方法。 1. 使用 type() 获取变量的类型 最常见的使用方式是将一个对象…...
DeepSeek-R1大模型本地部署及简单测试
目录 DeepSeek-R1大模型本地部署及简单测试背景我的测试环境模型参数选择适用场景参数规模 本地部署安装 DeepSeek-R1大模型本地部署及简单测试 背景 最近deepseek非常火, 要说2025年震惊科技圈的事件要数DeepSeek这个国产AI的横空出世,这是一款免费、开源且隐私优…...
【OpenGL】OpenGL游戏案例(二)
文章目录 特殊效果数据结构生成逻辑更新逻辑 文本渲染类结构构造函数加载函数渲染函数 特殊效果 为提高游戏的趣味性,在游戏中提供了六种特殊效果。 数据结构 PowerUp 类只存储存活数据,实际逻辑在游戏代码中通过Type字段来区分执行 class PowerUp …...
AI学习指南Ollama篇-使用Ollama构建自己的私有化知识库
一、引言 (一)背景介绍 随着企业对数据隐私和效率的重视,私有化知识库的需求日益增长。私有化知识库不仅可以保护企业数据的安全性,还能提供高效的知识管理和问答系统,提升企业内部的工作效率和创新能力。 (二)Ollama和AnythingLLM的结合 Ollama和AnythingLLM的结合…...
灵芝黄金基因组注释-文献精读109
The golden genome annotation of Ganoderma lingzhi reveals a more complex scenario of eukaryotic gene structure and transcription activity 灵芝(Ganoderma lingzhi)的黄金基因组注释揭示了更复杂的真核基因结构和转录活性情况 摘要 背景 普遍…...
【Proteus仿真】【51单片机】多功能计算器系统设计
目录 一、主要功能 二、使用步骤 三、硬件资源 四、软件设计 五、实验现象 联系作者 一、主要功能 1、LCD1602液晶显示 2、矩阵按键 3、加减乘除,开方运算 4、带符号运算 5、最大 999*999 二、使用步骤 基于51单片机多功能计算器 包含:程序&…...
MySQL数据类型转换应注意什么?
文章目录 1. **隐式转换**2. **显式转换**3. **数据截断**4. **字符集与排序规则**5. **日期和时间转换**6. **数值转换**7. **NULL 处理**8. **性能影响**9. **错误处理**10. **函数选择**示例总结 在 MySQL 中进行数据类型转换时,需要注意以下几个关键点ÿ…...
【LLM-agent】(task1)简单客服和阅卷智能体
note 一个完整的agent有模型 (Model)、工具 (Tools)、编排层 (Orchestration Layer)一个好的结构化 Prompt 模板,某种意义上是构建了一个好的全局思维链。 如 LangGPT 中展示的模板设计时就考虑了如下思维链:Role (角色) -> Profile(角色…...