【C++ STL】你真的了解string吗?浅谈string的底层实现
文章目录
- 底层结构概述
- 扩容机制
- 浅拷贝与深拷贝
- 插入和删除的效率
- 浅谈VS和g++的优化
- 总结
底层结构概述
string可以帮助我们很好地管理字符串,但是你真的了解她吗?事实上,string的设计是非常复杂的,拥有上百个接口,但最常用的就那几个。如果不了解string的底层,就很难优雅地写出高效的代码!
要想高效地管理一个string类,至少需要3个成员变量,分别是:
char* _str;
size_t _size;
size_t _capacity;
比如要存储字符串"abcde",那么_str指向了a,_size=5表示有5个有效字符(不包括’\0’),_capacity=8表示当前空间最多存储8个字符(实际上是9个,因为有’\0’)。此时,_str就是c_str的返回值,_size就是size的返回值,_capacity就是capacity的返回值;堆区上的空间总大小是9个字节,最多保存除了’\0’之外的8个字符,换句话说,当前再插入3个字符,空间就满了,需要扩容。
扩容机制
_str指向的空间是动态开辟出来的,当容量不够用时,会扩容。扩容的步骤是:
- 申请新空间。
- 把旧空间的数据拷贝到新空间中。
- 释放旧空间。
设想一下,当字符串很长时,第2步的拷贝代价就会非常大。所以,我们要想方设法地减少甚至避免扩容!
假设我们要反复地插入字符,插入100次,容量会怎么变化呢?
#include <iostream>
#include <string>
using namespace std;int main()
{string s;size_t capacity = s.capacity();cout << "init: capacity = " << capacity << endl;for (size_t i = 0; i < 100; i++){s.push_back('x');if (s.capacity() != capacity){capacity = s.capacity();cout << "new: capacity = " << capacity << endl;}}return 0;
}
VS2022运行结果:
可以观察到,一开始容量是15,第一次扩容为原来容量的2倍,后面每次扩容都为原来容量的1.5倍。
g++运行结果:
可以观察到,每次扩容都是原来容量的2倍。
如果我们能提前知晓,即将插入100个字符,就可以调用reserve,提前保留足够的空间,从而避免扩容的消耗!
#include <iostream>
#include <string>
using namespace std;int main()
{string s;// 提前开空间,从而避免扩容的消耗!s.reserve(100);size_t capacity = s.capacity();cout << "init: capacity = " << capacity << endl;for (size_t i = 0; i < 100; i++){s.push_back('x');if (s.capacity() != capacity){capacity = s.capacity();cout << "new: capacity = " << capacity << endl;}}return 0;
}
VS2022运行结果:
g++运行结果:
浅拷贝与深拷贝
string是如何拷贝的呢?
如果不写拷贝构造函数,编译器会生成默认的拷贝构造函数,对内置类型按照字节拷贝,这种拷贝称作浅拷贝!
举个例子,有一个string s1的结构如下:
此时来了另一个string s2,把s1的_str,_size和_capacity都拷贝过去,此时两个string的_str就指向了同一块空间!
此时,如果我们修改其中一个string,另一个string也会同时被修改!更可怕的是,当对象的生命周期结束时,会调用析构函数,由于两个string中的_str存储的是同一个地址,这个地址就会被delete两次,从而导致进程崩溃!
为了解决这个问题,string必须实现深拷贝!也就是说,我们需要重新申请一块空间,把"abcde"拷贝过去,让s2的_str指向新的空间!
这样,修改其中一个string就不会影响另一个string,而且两个string的_str指向不同的空间,不会出现同一块空间释放两次的问题了!
插入和删除的效率
如果要在字符串尾部插入一个字符,底层是如何实现的呢?只需要在_str[_size]的位置插入字符,再让_size++,最后再填一个’\0’即可!
当然,如果插入前,_size==_capacity,说明空间不够用了,要扩容!扩容的逻辑前面讲过,这里不再重复。
但是如果要在中间插入一个字符呢?甚至在头部插入呢?就要先挪动数据腾出空间,才能插入!
比起在尾部插入数据,多出了挪动数据的消耗,所以应尽可能地少在string的头部或中间插入数据!
同理,如果要删除头部或中间的数据,也要挪动数据覆盖删除,所以应尽可能地避免删除头部或中间的数据!
浅谈VS和g++的优化
VS2022的X86环境下,一个string类对象的大小是28字节;X64环境下,大小是40个字节。32位环境下,char*大小是4字节,size_t大小是4字节,那么_str,_size,_capacity的总大小是12字节;64位环境下,char*大小是8字节,size_t大小是8字节,那么_str,_size,_capacity的总大小是24字节。那么,剩下还有16字节去哪了呢?
观察一下监视窗口:
注意到有一个char[16]类型的数组_Buf。也就是说,VS在栈区上也申请了一块空间,长度是16个字节,当字符串的size<=15时,就存储在这个数组中;当size>15时,才会存储到堆区,这是为了减少堆区的内存碎片,因为字符串的长度一般不会超过15。
g++的X86环境下,一个string对象的大小是4字节;X64环境下,大小是8字节。这是由于底层只存储了一个指针,指针指向的空间中,存储了引用计数,_size和_capacity,以及C-string的数据。
这个引用计数又是啥玩意呢?这是g++对string做的优化,实现了写时拷贝(Copy On Write),创建对象时,把引用计数cnt初始化成1,拷贝的时候,cnt++。这样析构的时候,如果cnt不是1,就cnt--;如果cnt是1,再释放空间。当要对对象写入数据时,再进行深拷贝。这样极大地提升了拷贝的效率!
总结
- string的底层可以理解为一个指针和两个无符号整形变量,分别代表了c_str,size和capacity的返回值。
- 扩容是有代价的,尽可能使用reserve减少甚至避免扩容。
- string底层实现了深拷贝。
- 尽可能少地在string头部或者中间插入、删除数据。
- VS和g++对string做了一些优化。
相关文章:
【C++ STL】你真的了解string吗?浅谈string的底层实现
文章目录 底层结构概述扩容机制浅拷贝与深拷贝插入和删除的效率浅谈VS和g的优化总结 底层结构概述 string可以帮助我们很好地管理字符串,但是你真的了解她吗?事实上,string的设计是非常复杂的,拥有上百个接口,但最常用…...
17.3.1.3 灰度
版权声明:本文为博主原创文章,转载请在显著位置标明本文出处以及作者网名,未经作者允许不得用于商业目的。 灰度的算法主要有以下三种: 1、最大值法: 原图像:颜色值color(R,G,B&a…...
基于CAS操作的atomic原子类型
在上一节的卖票程序中,我们讲解了如何在多线程中保证临界资源的正确访问——使用互斥锁,即 lock_guard<mutex> lock(mtx); count;lock_guard<mutex> lock(mtx); count--; 从汇编角度解释线程间互斥-mutex互斥锁与lock_guard的使用-CSDN博客…...
Rust HashMap详解及单词统计示例
在Rust中,HashMap是一种非常有用的数据结构,用于存储键值对。本文将深入介绍HashMap的特性,以及通过一个单词统计的例子展示其用法。 HashMap简介 HashMap是Rust标准库提供的用于存储键值对的数据结构。它允许通过键快速查找对应的值&#…...
命令执行讲解和函数
命令执行漏洞简介 命令执行漏洞产生原因 应用未对用户输入做严格得检查过滤,导致用户输入得参数被当成命令来执行 命令执行漏洞的危害 1.继承Web服务程序的权限去执行系统命会或读写文件 2.反弹shell,获得目标服务器的权限 3.进一步内网渗透 远程代…...
外包实在是太坑了,划水三年,感觉人都废了
先说一下自己的情况,专科生,19年通过校招进入杭州某个外包软件公司,干了接近3年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了3年的功…...
代码随想录算法训练营第19天
77. 组合 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 class Solution:def combine(self, n: int, k: int) -> List[List[int]]:path []res []def dfs(n,k,index):if len(path) k:res.append(path[:])returnfor i in range(index,n1):…...
树莓派5 EEPROM引导加载程序恢复镜像
树莓派5不能正常启动,可以通过电源led灯的闪码来判断错误发生的大致情形。 LED警告闪码 如果树莓派由于某种原因无法启动,或者不得不关闭,在许多情况下,LED会闪烁特定的次数来指示发生了什么。LED会闪烁几次长闪烁,然…...
循序渐进-讲解Markdown进阶(Mermaid绘图)-附使用案例
Markdown 进阶操作 查看更多学习笔记:GitHub:LoveEmiliaForever Mermaid官网 由于CSDN对某些Mermaid或Markdown语法不支持,因此我的某些效果展示使用图片进行 下面的笔记内容全部是我根据Mermaid官方文档学习的,因为是初学者所以…...
寒假作业2月6号
第五章 静态成员与友元 一、填空题 1、一个类的头文件如下所示,num初始化值为5,程序产生对象T,且修改num为10,并使用show()函数输出num的值10。 #include <iostream.h> class Test { private: static int num; publi…...
ChatGPT绘图指南:DALL.E3玩法大全(一)
一、 DALLE.3 模型介绍 1、什么是 DALLE.3 模型? DALLE-3模型,是一种由OpenAI研发的技术,它是一种先进的生成模型,可以将文字描述转化为清晰的图片。这种模型的名称"DALLE"实际上是"Deep Auto-regressive Latent …...
计算机服务器中了_locked勒索病毒怎么办?Encrypted勒索病毒解密数据恢复
随着网络技术的不断发展,数字化办公已经成为企业生产运营的根本,对于企业来说,数据至关重要,但网络威胁无处不在,近期,云天数据恢复中心接到很多企业的求助,企业的计算机服务器遭到了_locked勒索…...
VueCLI核心知识3:全局事件总线、消息订阅与发布
这两种方式都可以实现任意两个组件之间的通信 1 全局事件总线 1.安装全局事件总线 import Vue from vue import App from ./App.vueVue.config.productionTip false/* 1.第一种写法 */ // const Demo Vue.extend({}) // const d new Demo()// Vue.prototype.x d // 把Dem…...
Redis中缓存问题
缓存预热 Redis缓存预热是一项关键任务,可帮助提升应用程序的性能和响应速度。在高流量的应用程序中,Redis缓存预热可以加速数据查询和读取,从而改善用户体验。本文将介绍一种快速、稳定的Redis缓存预热方案,并提供相应代码实现。…...
数码管扫描显示-单片机通用模板
数码管扫描显示-单片机通用模板 一、数码管扫描的原理二、display.c的实现1、void Display(void) 各模式界面定义数据2、void BackupRamToDisRam(void)从缓存区刷新显示映射Ram3、void FreshDisplay(void) 映射显示Ram到主控的IO口4、void LcdDisplay_8bit(void) 映射显示Ram到…...
IDEA中的神仙插件——Smart Input (自动切换输入法)
IDEA中的神仙插件——Smart Input (自动切换输入法) 设置 更多功能详见官方文档:Windows版SmartInput使用入门...
shell编程:求稀疏数组中元素的和(下标不连续)
#!/bin/basharr([2]3 [5]2 [6]2 [9]1)for i in "${!arr[]}" dosum$((sumarr[i])) doneecho $sumBash 脚本中,* 和 符号在数组上下文中有不同的用途。当使用它们来遍历数组时,必须了解它们之间的区别。 * (无前置感叹号 !): 在索引…...
Rust 学习笔记 - 详解数据类型
前言 任何一门编程语言几乎都脱离不了:变量、基本类型、函数、注释、循环、条件判断,这是一门编程语言的语法基础,只有当掌握这些基础语法及概念才能更好的学习 Rust。 标量类型(Scalar Types) 在 Rust 中ÿ…...
构建本地yum源
下载repo数据文件 根据需要修改下载路径和reposync参数 #!/bin/bashlocal_path/repo/remote/rhel9 enabled_repos$(yum repolist enabled | awk NR>3{print $1}) tempfile$(mktemp -t reposync.XXXX)check() {echo "目标目录剩余空间: $(df -h ${local_path} | awk …...
常用的正则表达式,收藏必备!!!
正则表达式是一种强大的文本模式匹配工具,用于在字符串中查找、替换和验证特定模式的文本。下面是一些常用的正则表达式示例: 匹配Email地址: ^[a-zA-Z0-9._%-][a-zA-Z0-9.-]\.[a-zA-Z]{2,}$匹配URL: ^(https?|ftp)://[^\s/$.?#…...
js---webAPI
01 声明变量 js组成: DOM:操作网页内容的,开发页面内容特效和实现用户交互 BOM: DOM树:将 HTML 文档以树状结构直观的表现出来,我们称之为文档树或 DOM 树 文档树直观的体现了标签与标签之间的关系 CSS获取元素的方法 document.querySele…...
git的常用命令有哪些?
Git 是一个流行的分布式版本控制系统,用于跟踪文件的变化、协作开发和管理代码。以下是一些常用的 Git 命令: 创建和克隆仓库: git init:在当前目录初始化一个新的 Git 仓库。git clone <仓库URL>:克隆一个远程仓…...
《动手学深度学习(PyTorch版)》笔记8.5
注:书中对代码的讲解并不详细,本文对很多细节做了详细注释。另外,书上的源代码是在Jupyter Notebook上运行的,较为分散,本文将代码集中起来,并加以完善,全部用vscode在python 3.9.18下测试通过&…...
【蓝桥杯单片机入门记录】LED灯(附多个例程)
目录 一、LED灯概述 1.1 LED发光原理 1.2电路原理图 1.3电路实物图 1.4 开发板LED灯原理图 1.4.1共阳极LED灯操控原理(本开发板) (非实际原理图,便于理解版本)由图可以看出,每个LED灯的左边…...
c语言简单json库
文章目录 写在前面头文件源代码使用示例 写在前面 用c语言实现的一个简单json库,极其轻量 仅1个四百多行源码的源文件,和1个头文件 支持对象、数组、数值、字符串类型 github仓库 头文件 对主要的json API的声明 #ifndef ARCOJSON_ARCOJSON_H #defin…...
Linux操作系统基础(七):Linux常见命令(二)
文章目录 Linux常见命令(二) 一、kill命令 二、ifconfig命令 三、clear命令 四、重启与关机命令 五、which命令 六、hostname命令 七、grep命令 八、|管道 九、useradd命令 十、userdel命令 十一、tar命令 十二、su命令 十三、ps命令 Linu…...
进程状态
广义概念: 从广义上来讲,进程分为新建、运行、阻塞、挂起、退出五个状态,其中新建和退出两个状态可以直接理解字面意思。 运行状态: 这里涉及到运行队列的概念,CPU在读取数据的时候,需要把内存中的进程放入…...
STM32固件库简介与使用指南
1. STM32官方标准固件库简介 STM32官方标准固件库是由STMicroelectronics(ST)提供的一套软件开发工具,旨在简化STM32微控制器的软件开发过程。该固件库提供了丰富的功能和模块,涵盖了STM32微控制器的各种外设,包括但不…...
【开源】SpringBoot框架开发智能教学资源库系统
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课程资源模块2.4 课程作业模块2.5 课程评价模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 课程档案表3.2.2 课程资源表3.2.3 课程作业表3.2.4 课程评价表 四、系统展示五、核心代…...
融资项目——获取树形结构的数据
如下图所示,下列数据是一个树形结构数据,行业中包含若干子节点。表的设计如下图,设置了一个id为1的虚拟根节点。(本树形结构带虚拟根节点共三层) 实现逻辑: 延时展示方法,先展现第二层的信息&a…...
Crypto-RSA2
题目:(BUUCTF在线评测 (buuoj.cn)) 已知e,n,dp/(dq),c求明文: 首先有如下公式: dp ≡ d mod (p-1) ,ed ≡ 1 mod φ(n) ,npq ,φ(n)(p-1)(q-1) python代码实现如下: import libnu…...
IEEE Internet of Things Journal投稿经验
期刊名:IEEE Internet of Things Journal 期刊分区:中科院一区 Top 影响因子:10.6 投稿状态 (1)2023.11.3,投稿成功,状态为:under review(大u大r)࿱…...
实例分割论文阅读之:FCN:《Fully Convolutional Networks for Semantica Segmentation》
论文地址:https://openaccess.thecvf.com/content_cvpr_2015/papers/Long_Fully_Convolutional_Networks_2015_CVPR_paper.pdf 代码链接:https://github.com/pytorch/vision 摘要 卷积网络是强大的视觉模型,可以产生特征层次结构。我们证明,…...
apk反编译修改教程系列---简单去除apk登陆 修改vip与一些反编译基础常识【十二】
往期教程: 安卓玩机-----反编译apk 修改apk 去广告 去弹窗等操作中的一些常识apk反编译修改教程系列-----修改apk应用名称 任意修改名称 签名【一】 apk反编译修改教程系列-----任意修改apk版本号 版本名 防止自动更新【二】 apk反编译修改教程系列-----修改apk中…...
网络安全习题集
第一章 绪论 4 ISO / OSI 安全体系结构中的对象认证安全服务使用( C ) 机制来完成。 A .访问控制 B .加密 C .数字签名 D .数据完整性 5 身份鉴别是安全服务中的重要一环,以下关于身份鉴别的叙述不正确的是…...
C++中的volatile:穿越编译器的屏障
C中的volatile:穿越编译器的屏障 在C编程中,我们经常会遇到需要与硬件交互或多线程环境下访问共享数据的情况。为了确保程序的正确性和可预测性,C提供了关键字volatile来修饰变量。本文将深入解析C中的volatile关键字,介绍其作用、…...
(07)Hive——窗口函数详解
一、 窗口函数知识点 1.1 窗户函数的定义 窗口函数可以拆分为【窗口函数】。窗口函数官网指路: LanguageManual WindowingAndAnalytics - Apache Hive - Apache Software Foundationhttps://cwiki.apache.org/confluence/display/Hive/LanguageManual%20Windowing…...
【开源图床】使用Typora+PicGo+Github+CDN搭建个人博客图床
准备工作: 首先电脑得提前完成安装如下: 1. nodejs环境(node ,npm):【安装指南】nodejs下载、安装与配置详细教程 2. Picgo:【安装指南】图床神器之Picgo下载、安装与配置详细教程 3. Typora:【安装指南】markdown神器之Typora下载、安装与无限使用详细教…...
阅读笔记(SOFT COMPUTING 2018)Seam elimination based on Curvelet for image stitching
参考文献: Wang Z, Yang Z. Seam elimination based on Curvelet for image stitching[J]. Soft Computing, 2018: 1-16. 注:SOFT COMPUTING 大类学科小类学科Top期刊综述期刊工程技术 3区 COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE 计算机…...
LinkedList数据结构链表
LinkedList在Java中是一个实现了List和Deque接口的双向链表。它允许我们在列表的两端添加或删除元素,同时也支持在列表中间插入或移除元素。在分析LinkedList之前,需要理解链表这种数据结构: 链表:链表是一种动态数据结构&#x…...
[计算机网络]---序列化和反序列化
前言 作者:小蜗牛向前冲 名言:我可以接受失败,但我不能接受放弃 如果觉的博主的文章还不错的话,还请点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、再谈协议…...
[前端开发] 常见的 HTML CSS JavaScript 事件
代码示例指路 常见的 HTML、CSS、JavaScript 事件代码示例 常见的 HTML CSS JavaScript 事件 事件HTML 事件鼠标事件键盘事件表单事件 JavaScript 事件对象事件代理(事件委托) 事件 在 Web 开发中,事件是用户与网页交互的重要方式之一。通过…...
H5/CSS 笔试面试考题(71-80)
简述哪种输入类型用于定义周和年控件(无时区)( ) A:date B:week C:year 面试通过率:67.0% 推荐指数: ★★★★★ 试题难度: 初级 试题类型: 选择题 答案:b 简述下列哪个元素表示外部资源?该元素可以被视为图像、嵌套的浏览上下文或插件要处理的资源。它包括各种属性…...
【Node.js】path 模块进行路径处理
Node.js 执行 JS 代码时,代码中的路径都是以终端所在文件夹出发查找相对路径,而不是以我们认为的从代码本身出发,会遇到问题,所以在 Node.js 要执行的代码中,访问其他文件,建议使用绝对路径 实例࿱…...
react+ts【项目实战一】配置项目/路由/redux
文章目录 1、项目搭建1、创建项目1.2 配置项目1.2.1 更换icon1.2.2 更换项目名称1.2.1 配置项目别名 1.3 代码规范1.3.1 集成editorconfig配置1.3.2 使用prettier工具 1.4 项目结构1.5 对css进行重置1.6 注入router1.7 定义TS组件的规范1.8 创建代码片段1.9 二级路由和懒加载1.…...
英文论文(sci)解读复现【NO.20】TPH-YOLOv5++:增强捕获无人机的目标检测跨层不对称变压器的场景
此前出了目标检测算法改进专栏,但是对于应用于什么场景,需要什么改进方法对应与自己的应用场景有效果,并且多少改进点能发什么水平的文章,为解决大家的困惑,此系列文章旨在给大家解读发表高水平学术期刊中的 SCI论文&a…...
第十五章 以编程方式使用 SQL 网关 - %SQLGatewayConnection 方法和属性
文章目录 第十五章 以编程方式使用 SQL 网关 - %SQLGatewayConnection 方法和属性FetchRows()GatewayStatus propertyGatewayStatusGet()GetConnection()GetGTWVersion()GetLastSQLCode() 第十五章 以编程方式使用 SQL 网关 - %SQLGatewayConnection 方法和属性 FetchRows() …...
【QTableView】
QTableView是Qt框架中用于显示表格形式数据的部件,通常用于显示数据库查询结果、数据集以及其他类似的结构化数据。 以下是一个使用QTableView的简单示例,假设我们有一个数据库表存储了学生的信息,我们可以使用QSqlTableModel将数据库表关联到QTableView上,并显示出来: …...
VS-Code-C#配置
C#开发环境配置 查看更多学习笔记:GitHub:LoveEmiliaForever 1. 安装 .NET SDK 官方下载网址按照安装程序指引安装即可 2. VS Code 安装插件 插件名:C#发布者是Microsoft 该插件是基础语法插件 插件名:C# Dev Kit发布者是Mic…...
第七篇【传奇开心果系列】Python微项目技术点案例示例:数据可视化界面图形化经典案例
传奇开心果微博系列 系列微博目录Python微项目技术点案例示例系列 微博目录一、微项目开发背景和项目目标:二、雏形示例代码三、扩展思路介绍四、数据输入示例代码五、数据分析示例代码六、排名统计示例代码七、数据导入导出示例代码八、主题定制示例代码九、数据过…...