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

C++源码剖析——vector和array

  前言:之前看过侯老师的《STL源码剖析》但是那已经是多年以前的,现在工作中有时候查问题和崩溃都需要了解实际工作中使用到的STL的实现。因此计划把STL的源码再过一遍。
  摘要:本文描述了llvm中libcxx的std::vector的实现。
  关键字vector
  其他:参考代码LLVM-libcxx

  vector是标准库中的连续存储的容器,也就是容器中说任意两个索引上相邻的元素的地址也是相邻的,可以通过索引随机访问。vector中的元素默认是通过堆内存管理的,在进行空间分配时一般会比时机需求的空间要大,即capacity_size,这样能够避免在插入元素时频繁申请内存导致的性能问题(如果频繁申请内存导致页置换的话还是很耗时的)。

1 vector

  先看下容器的定义,和其他容器一样都是一个模板类。_Tp就是类型,而_Allocator是进行内存管理的分配器,默认分配器就是通过::operator new::operator delete申请和释放内存的。

template <class _Tp, class _Allocator /* = allocator<_Tp> */>
class _LIBCPP_TEMPLATE_VIS vector

  vector的内存布局比较简单如下图,有三个指针分别指向了对应的开始地址,已使用部分的尾地址,申请到的内存的尾地址,[__begin_, __end_)之间是已经使用的内存部分,[__end_, __end_cap_)是申请了但是未使用的部分(保留这一部分是为了避免插入元素时频繁allocate而可能出现的性能问题。)
在这里插入图片描述

private:pointer __begin_ = nullptr;pointer __end_ = nullptr;__compressed_pair<pointer, allocator_type> __end_cap_ =__compressed_pair<pointer, allocator_type>(nullptr, __default_init_tag());

构造和销毁
  vector的构造比较简单,就是先通过allocator申请一块内存,然后通过for循环逐个构造对象。构造时通过for循环实现,由于没有利用CPU的一些SMID指令的优化,必然效率不是很好。

vector(size_type __n, const value_type& __x, const allocator_type& __a) : __end_cap_(nullptr, __a){std::__debug_db_insert_c(this);if (__n > 0){__vallocate(__n);__construct_at_end(__n, __x);}
}vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x){_ConstructTransaction __tx(*this, __n);const_pointer __new_end = __tx.__new_end_;for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {__alloc_traits::construct(this->__alloc(), std::__to_address(__pos), __x);}
}

  销毁就比较直接,通过一个包装器__destroy_vector,先clear再调用deallocate释放内存。

__vec_.__clear();
__alloc_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.capacity());;

clear
  clear函数只会针对析构容器中的每一个函数并不会释放当前容器中的内存。因此在进行容器释放时需要注意,如果期望释放内存的话可以通过vector().swap(vec)的方式或者在调用clear之后调用shrink_to_fit 调整内存大小。

void clear() _NOEXCEPT{size_type __old_size = size();__clear();__annotate_shrink(__old_size);  //看源码里面什么也不会做std::__debug_db_invalidate_all(this);
}void __clear() _NOEXCEPT {__base_destruct_at_end(this->__begin_);}
void __base_destruct_at_end(pointer __new_last) _NOEXCEPT {pointer __soon_to_be_end = this->__end_;while (__new_last != __soon_to_be_end)          //依然是一个完整的循环析构__alloc_traits::destroy(__alloc(), std::__to_address(--__soon_to_be_end));this->__end_ = __new_last;
}

push_back
  push_back时,如果当前有足够的的大小则会在尾部构建一个对象,扩容的大小是按照现有大小的2倍来,即std::min(max_size(), std::max(current_cap + 1, 2 * current_cap)),简单的理解就是在条件允许的情况下扩容2倍。

void vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x){allocator_type& __a = this->__alloc();//__split_buffer就是一个包装器__split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);// __v.push_back(std::forward<_Up>(__x));__alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Up>(__x));__v.__end_++;__swap_out_circular_buffer(__v);//这个函数没有干什么就是将__v中的size设置给当前的vector
}

emplace_back
  emplace_backpush_back基本相同都是向容器中插入元素,如果对于插入vector::value_type类型的对象二者是没有区别的,push_back也实现了右值的重载,不存在push_back对于右值会多次拷贝的情况。主要的区别是emplace_back通过可变参数模板将参数直接传递给了构建器也就意味着同样的代码emplace_back直接在对应的内存上构建对象,而相比之下push_back是先构建再拷贝。

void vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)

resize
  resize的实现比较直接,内存小了就扩容,大了就析构但是并不释放内存。

void vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x){size_type __cs = size();if (__cs < __sz)this->__append(__sz - __cs, __x);else if (__cs > __sz)this->__destruct_at_end(this->__begin_ + __sz);//只会析构对象,不会释放内存
}

shrink_to_fit
  

vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT{if (__external_cap_to_internal(size()) > __cap()){vector(*this, allocator_type(__alloc())).swap(*this);}
}

vector<bool>基本上被建议放弃使用了,所以就不深入了。

2 array

  array的实现比较简单就是一个简单的栈数组的包装器。就不详细描述了。

template <class _Tp, size_t _Size>
struct _LIBCPP_TEMPLATE_VIS array
{// types:typedef array __self;typedef _Tp                                   value_type;typedef value_type&                           reference;typedef const value_type&                     const_reference;typedef value_type*                           iterator;typedef const value_type*                     const_iterator;typedef value_type*                           pointer;typedef const value_type*                     const_pointer;typedef size_t                                size_type;typedef ptrdiff_t                             difference_type;typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;_Tp __elems_[_Size];
};

3 参考文献

  • stackoverflow——push_back vs emplace_back
  • Proposed Wording for Placement Insert

相关文章:

C++源码剖析——vector和array

前言&#xff1a;之前看过侯老师的《STL源码剖析》但是那已经是多年以前的&#xff0c;现在工作中有时候查问题和崩溃都需要了解实际工作中使用到的STL的实现。因此计划把STL的源码再过一遍。   摘要&#xff1a;本文描述了llvm中libcxx的std::vector的实现。   关键字&…...

学习linux编程(一)

本文导航一. Linux基础知识杂记0. terminal操作快捷键等1. 为什么vfork的子进程里用return&#xff0c;整个程序会挂掉&#xff0c;而且exit不会(zz)2. 进程内存管理详解3. 关于堆和自由存储区概念的区别4. cache和buffer的区别5. C实现线程池6. 静态函数和虚函数的区别7. C里是…...

pt-query-digest_详细使用方法

pt-query-digest_详细使用方法1. pt介绍1.1. 说明1.2. 安装2 语法选项2.1 所有参数2.2 常见参数2.3 事件和属性2.4 分组2.5 过滤2.6 排序2.7 输出选项2.8 DSN(数据源)选项3. 慢日志3.1 事件属性3.2 分析报告3.2.1 第一部分&#xff1a;总体概况说明3.2.2 第二部分&#xff1a;查…...

基于MATLAB编程的萤火虫FA优化BP神经网络的回归分析

目录 BP神经网络的原理 BP神经网络的定义 BP神经网络的基本结构 BP神经网络的神经元 BP神经网络激活函数及公式 SVM应用实例,基于fa-svm分类预测 代码 结果分析 展望 BP神经网络的原理 BP神经网络的定义 人工神经网络无需事先确定输入输出之间映射关系的数学方程,仅通过…...

leetcode 消失的数字(面试题)

题目 数组nums包含从0到n的所有整数&#xff0c;但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗&#xff1f; 注意&#xff1a;本题相对书上原题稍作改动 示例 1&#xff1a; 输入&#xff1a;[3,0,1] 输出&#xff1a;2 示例 2&#xff1a; 输入&…...

Spring入门篇6 --- AOP

目录1.核心概念AOP(Aspect Oriented Programming)面向切面编程&#xff1a;一种编程范式&#xff0c;指导开发者如何组织程序结构作用&#xff1a;在不惊动原始设计的基础上为其进行功能增强。连接点(JoinPoint)&#xff1a;程序执行过程中的任意位置切入点(PointCut)&#xff…...

linux 配置java环境

1、上传jdk包到/usr/local/java目录下 2、解压jdk的tar包 tar -zxvf jdk-8u291-linux-x64.tar.gz 3、添加配置&#xff08;环境变量&#xff09; 注意&#xff1a;JAVA_HOME值为实际jdk路径 打开配置文件 vi /etc/profile 最下面添加: #set java environment JAVA_HOME/usr/…...

分布式事务基础入门

分布式事务基础入门 什么是分布式事务 什么是分布式事务&#xff1f; 首先理解什么是本地事务&#xff1f; 平常我们在程序中通过spring去控制事务是利用数据库本身的事务特性来实现的&#xff0c;因此叫数据库事务&#xff0c;由于应用主要靠关系数据库来控制事务&#xff0…...

白盒测试究竟怎么做

大家好&#xff0c;我是洋子 在进行日常测试的时候&#xff0c;我们大部分时间花在手动的功能测试上&#xff0c;功能测试又可称为手工测试&#xff0c;官方一点的学名叫黑盒测试&#xff0c;当然作为测试工程师&#xff0c;我们一般俗称点点点 黑盒测试是一种软件测试方法&am…...

EEG微状态的功能意义

导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构&#xff0c;这些结构能够最佳地解释自发EEG记录中随时间变化的差异。这四种结构被称为EEG微状态A、B、C和D类&#xff0c;分别与言语/语音、视觉、主观感受-自主加工和注意力重定…...

Python3 - Flask+swift实现单点登录

基于 Flask 和 Redis 实现单设备登录的服务端代码和客户端swift、oc代码&#xff1a; Python flask 实现服务端 from flask import Flask, jsonify, request from redis import Redisapp Flask(__name__) redis_db Redis()# 用户登录接口&#xff0c;验证用户名和密码&#…...

HTML URL

文章目录HTML URLURL - 统一资源定位器常见的 URL SchemeURL 字符编码URL 编码实例HTML URL URL 是一个网页地址。 URL可以由字母组成&#xff0c;如"csdn.net"&#xff0c;或互联网协议&#xff08;IP&#xff09;地址&#xff1a; 192.168.100.1。大多数人进入网站…...

带你了解ICCV、ECCV、CVPR三大国际会议

文章目录 前言 一、ICCV、ECCV、CVPR是什么? 1.ICCV 2.ECCV 3.CVPR 二、三大会链接及论文下载链接 前言  作为刚入门CV的新人,有必要记住计算机视觉方面的三大顶级会议:ICCV,CVPR,ECCV,统称为ICE。 与其它学术领域不同,计算机科学使用会议而不是期刊作为发表研究成果的主…...

常用的一些代码

今天菜鸟涨工资了&#xff0c;到手估计有8000左右了&#xff0c;有点开心&#xff0c;本来想上一篇就把这篇写了的&#xff0c;但是发现还是分开写比较好&#xff01; 文章目录自适应js禁止放大播放声音store的使用websocket封装echarts实现渐变swiper常用的陌生方法&#xff0…...

Python-df.pop()和np.array.shape()属性

1.df.pop() 删除某一列 可以使用这个来删除某一列&#xff08;不能是多列&#xff09;&#xff0c;只有一个参数&#xff0c;就是列名&#xff0c;可以是str类型&#xff0c;函数返回的是被删除的列&#xff0c;df直接是删除后的df&#xff0c;不需要我们处理。 我们建模时&a…...

多线程并发编程笔记03(小滴课堂)---线程安全性

原子性操作&#xff1a; 这样一段代码。 我们输出一下&#xff1a; 我们发现它的结果和我们想的不太一样。 正常应该输出1000. 这是因为没有保证原子性。 所以我们来加上原子性&#xff1a; 这样就保证了我们的原子性。 接下来我们来细说说这个关键字&#xff1a; 我发现我…...

提升代码质量,使用插件对 java 代码进行扫描检查分析

目录前言一、使用maven-checkstyle-plugin插件1. maven-checkstyle-plugin 介绍2.引入依赖3.使用二、使用 idea 插件1.安装2.使用前言 很多时候我们的代码写的不规范&#xff0c;比如没缩进、参数间没空格、导入的包没用到没删除、方法很长没有进行拆分、 直接对方法参数进行了…...

如何用秒验提升用户体验和转换率?

手机号验证是移动应用开发中常见的需求&#xff0c;它可以用于用户注册、登录、身份认证等场景。目前&#xff0c;市场上主要的手机号验证方式是短信验证码&#xff0c;但这种方式存在一些问题&#xff0c;例如&#xff1a; 延迟&#xff1a;短信验证码需要等待运营商发送和用…...

【新】(2023Q2模拟题JAVA)华为OD机试 - 机器人活动区域

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:机器人活动区域 题目 现有一…...

2023软件测试面试真题宝典大汇总,没收藏的都后悔了

下边是我根据工作这几年来的面试经验&#xff0c;加上之前收集的资料&#xff0c;整理出来350道软件测试工程师 常考的面试题。字节跳动、阿里、腾讯、百度、快手、美团等大厂常考的面试题&#xff0c;在文章里面都有提到。 虽然这篇文章很长&#xff0c;但是绝对值得你点击一…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...