【C++】:C++中的STL序列式容器vector源码剖析
⛅️一 vector概述
vector的使用语法可以参考文章:
总的来说:vector是可变大小数组
特点:
支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
元素保存在连续的内存空间中,因此通过下标取值非常快
在容器中间位置添加或删除元素非常耗时
一旦vector内存不足,重新申请内存之后,和原vector相关的指针,引用,迭代器都失效。内存重分配耗时很长
通常,使用vector是最好的选择,如果没有什么特殊要求,最好使用vector
与其他容器的比较:
⛅️二、vector定义摘要
vector定于与<stl_vector.h>头文件中
//alloc是SGI STL的空间配置器
template <class T, class Alloc = alloc>
class vector {
public:// vector 的嵌套类型定义typedef T value_type;typedef value_type* pointer;typedef value_type* iterator;typedef value_type& reference;typedef size_t size_type;typedef ptrdiff_t difference_type;protected:// simple_alloc是SGI STL的空间配置器,见前面空间适配器文章的介绍typedef simple_alloc<value_type, Alloc> data_allocator;iterator start; // 表示目前使用空间的头iterator finish; // 表示目前使用空间的尾iterator end_of_storage; // 表示目前可用空间的尾void insert_aux(iterator position, const T& x);void deallocate() {if (start)data_allocator::deallocate(start, end_of_storage - start);}void fill_initialize(size_type n, const T& value) {start = allocate_and_fill(n, value);finish = start + n;end_of_storage = finish;}public:iterator begin() { return start; }iterator end() { return finish; }size_type size() const { return size_type(end() - begin()); }size_type capacity() const {return size_type(end_of_storage - begin()); }bool empty() const { return begin() == end(); }reference operator[](size_type n) { return *(begin() + n); }vector() : start(0), finish(0), end_of_storage(0) {}vector(size_type n, const T& value) { fill_initialize(n,value); } vector(int n, const T& value) { fill_initialize(n,value); } vector(long n, const T&value) { fill_initialize(n,value); } explicit vector(size_type n) { fill_initialize(n,T()); }~vector()destroy(start, finish); //全局函式,见前面文章destroy函数的介绍deallocate(); //这是 vector的㆒个 member function}reference front() { return *begin(); } // 第一个元素reference back() { return *(end() - 1); } // 最后一个元素void push_back(const T& x) { // 将元素安插至最尾端if (finish != end_of_storage) {construct(finish, x); //全局函式,见前面文章construct函数的介绍++finish;}elseinsert_aux(end(), x); //这是 vector的一个member function}void pop_back() { // 将最尾端元素取出--finish;destroy(finish); // 全局函式,见前面文章destroy函数的介绍}iterator erase(iterator position) { // 清除某位置上的元素if (position + 1 != end())copy(position + 1, finish, position); // 后续元素往前搬移--finish;destroy(finish); // 全局函式,见前面文章destroy函数的介绍return position;}void resize(size_type new_size, const T& x) {if (new_size < size())erase(begin() + new_size, end());elseinsert(end(), new_size - size(), x);}void resize(size_type new_size) { resize(new_size, T()); }void clear() { erase(begin(), end()); }protected:// 配置空间并填满内容iterator allocate_and_fill(size_type n, const T& x) {iterator result = data_allocator::allocate(n);uninitialized_fill_n(result, n, x); // 全局函式,见前面uninitialized_fill_n函数的介绍return result;}
⛅️三、vector的迭代器
vector维护的是一个连续线性空间,所以不论其元素类别是什么,普通指针都可以作为vector的迭代器而满足所有必要条件
vector迭代器支持有操作有(普通指针也具备):
operator*、operator->、operator++、operator–、operator+、operator-、operator+=、operator-=
vector支持随机存取,而普通指针正有着这样的能力,所以,vector提供的是随机访问迭代器(Random Access iterators)
vector的迭代器定义如下:
template <class T, class Alloc = alloc>
class vector {
public:typedef T value_type;typedef value_type* iterator; //vector的迭代器是原生指标...
};
例如:
vector<int>::iterator ivite; //等同于int* ivite;
vector<Shape>::iterator svite; //等同于Shape* svite;
⛅️四、vector的数据结构
vector的数据结构非常简单:一个线性连续空间
下面介绍vector的3个数据结构:
start:表示目前使用空间的头
finish:表示目前使用空间的尾
end_of_storage:表示目前可用空间的尾
template <class T, class Alloc = alloc>
class vector {
...
protected:iterator start; //表示目前使用空间的头iterator finish; //表示目前使用空间的尾iterator end_of_storage; //表示目前可用空间的尾...
};
说明:为了降低空间配置时的速度成本,vector实际配置的大小可能比客户端需求量更大一些,以备将来可能的扩充。这便是容量的概念。也就是说,一个vector的容量永远大于或等于其大小。一旦容量等于大小,下次再新增元素时就需要新开辟一块空间。如下图所示
运用start、finish、end_of_storage三个迭代器,vector提供了首尾标示、大小、容量、空容器判断、注标[]运算符、最前端元素值、最后端元素值…等机能,如下:
template <class T, class Alloc = alloc>
class vector {
...
public:iterator begin() { return start; }iterator end() { return finish; }size_type size() const { return size_type(end() - begin()); }size_type capacity() const {return size_type(end_of_storage - begin()); }bool empty() const { return begin() == end(); }reference operator[](size_type n) { return *(begin() + n); }reference front() { return *begin(); }reference back() { return *(end() - 1); }...
};
⛅️五、vector的构造与内存管理(constructor、push_back)
vector的内存管理:vector默认使用alloc做为空间配置器,并据此另外定义了一个data_allocator,为的是更方便以元素大小为配置单位:
template <class T, class Alloc = alloc>
class vector {
protected:// simple_alloc<>见前面文章介绍typedef simple_alloc<value_type, Alloc> data_allocator;...
};
于是,data_allocator::allocate(n) 表示配置n个元素空间
构造函数:vector提供许多构造函数,其中一个允许我们指定空间大小及初值:
//构造函数,允许指定vector大小n和初值value
vector(size_type n, const T& value) { fill_initialize(n, value); }// 充填并予初始化
void fill_initialize(size_type n, const T& value) {start = allocate_and_fill(n, value);finish = start + n;end_of_storage = finish;
}// 配置而后充填
iterator allocate_and_fill(size_type n, const T& x) {iterator result = data_allocator::allocate(n); //配置n个元素空间uninitialized_fill_n(result, n, x); //全局函式,会根据第1个参数类型特性决定使用算法fill_n()或反复调用construct()来完成任务return result;
}
push_back()函数:当我们以push_back() 将新元素安插入于vector尾端时,该函式首先检查是否还有备用空间,如果有就直接在备用空间上建构元素,并调整迭代器finish,使vector变大。如果没有备用空间了,就扩充空间(重新配置、搬移数据、释放原空间)。push_back()原型如下:
void push_back(const T& x) {if (finish != end_of_storage) { //还有备用空间construct(finish, x); //全局函式++finish; //调整水位高度}else //已无备用空间insert_aux(end(), x); // vector member function,见下
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {if (finish != end_of_storage) { //还有备用空间// 在备用空间起始处建构一个元素,并以 vector 最后一个元素值为其初值。construct(finish, *(finish - 1));// 调整水位。++finish;T x_copy = x;copy_backward(position, finish - 2, finish - 1);*position = x_copy;}else { // 已无备用空间const size_type old_size = size();const size_type len = old_size != 0 ? 2 * old_size : 1;// 以上配置原则:如果原大小为0,则配置 1(个元素大小)// 如果原大小不为 0,则配置原大小的两倍,// 前半段用来放置原数据,后半段准备用来放置新数据iterator new_start = data_allocator::allocate(len); // 实际配置iterator new_finish = new_start;try {// 将原 vector 的内容拷贝到新vectornew_finish = uninitialized_copy(start, position, new_start);// 为新元素设定初值 xconstruct(new_finish, x);// 调整水位++new_finish;// 将原vector的备用空间中的内容也忠实拷贝过来new_finish = uninitialized_copy(position, finish, new_finish);}catch(...) {// "commit or rollback" semantics.destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}//析构并释放原vectordestroy(begin(), end());deallocate();// 调整迭代器,指向新vectorvector start = new_start;finish = new_finish;end_of_storage = new_start + len;}
}
⛅️六、vector内存重分配策略
vector的内存重分配策略:
vector是以数组的形式存储的,当往vector中增加元素时,如果vector的容量不足,那么vector就会进行扩容
扩容的规则是:并不是在原空间之后接续新空间(因为无法保证原空间之后尚有可供配置的空间),而是申请一块比现在大的新的内存空间(gcc和vc申请规则不同,见下面介绍),然后原来内存中的内容拷贝到新内存中,然后释放原来的内存
重点:在gcc和vc的环境下,vector的扩容规则是不一样的
注意(重点):对vector 的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误,务需小心
#include <iostream>
#include <vector>using namespace std;int main()
{std::vector<int> iv;iv.push_back(1);cout << iv.capacity() << endl; //1iv.push_back(1);cout << iv.capacity() << endl; //2iv.push_back(1);cout << iv.capacity() << endl; //3iv.push_back(1);cout << iv.capacity() << endl; //4iv.push_back(1);cout << iv.capacity() << endl; //6iv.push_back(1);iv.push_back(1);cout << iv.capacity() << endl; //9return 0;
}
⛅️七、vector的元素操作(pop_back、erase、clear、insert)
所提供的元素操作动作很多,不就在此文章中一一说明
pop_back:
//将尾端元素拿掉,并调整大小
void pop_back() {--finish; //将尾端标记往前移一格,表示将放弃尾端元素destroy(finish); // destroy是全局函式
}
erase:
// 清除[first,last)中的所有元素
iterator erase(iterator first, iterator last) {iterator i = copy(last, finish, first); //copy是全局函式destroy(i, finish); //destroy是全局函式finish = finish - (last - first);return first;
}
下图是上面这个erase函数的版本
// 清除某个位置上的元素
iterator erase(iterator position) {if (position + 1 != end())copy(position + 1, finish, position); //copy是全局函式--finish;destroy(finish); //destroy是全局函式return position;
}
clear:
//清除容器内所有元素
void clear() { erase(begin(), end()); }
insert:
//从position开始,插入n个元素,元素初值为x
template<class T,class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x)
{if (n != 0) { //当n!= 0才进行以下所有动作if (size_type(end_of_storage - finish) >= n){//备用空间大于等于“新增元素个数”T x_copy = x;// 以下计算插入点之后的现有元素个数const size_type elems_after = finish - position;iterator old_finish = finish;if (elems_after > n){//“插入点之后的现有元素个数”大于“新增元素个数”uninitialized_copy(finish - n, finish, finish);finish += n; // 将vector尾端标记后移copy_backward(position, old_finish - n, old_finish);fill(position, position + n, x_copy); //从插入点开始填入新值}}else {//“插入点之后的现有元素个数”小于等于“新增元素个数”uninitialized_fill_n(finish, n - elems_after, x_copy);finish += n - elems_after;uninitialized_copy(position, old_finish, finish);finish += elems_after;fill(position, old_finish, x_copy);}}else {// 备用空间小于“新增元素个数”(那就必须配置额外的内存)// 首先决定新长度:旧长度的两倍,或旧长度+新增元素个数const size_type old_size = size();const size_type len = old_size + max(old_size, n);// 以下配置新的vector空间iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;STL_TRY {// 以下首先将旧vector的安插点之前的元素复制到新空间new_finish = uninitialized_copy(start, position, new_start);// 以下再将新增元素(初值皆为n)填入新空间new_finish = uninitialized_fill_n(new_finish, n, x);// 以下再将旧 vector 的插入点之后的元素复制到新空间new_finish = uninitialized_copy(position, finish, new_finish);}
# ifdef STL_USE_EXCEPTIONScatch(...) {// 如有异常发生,实现"commit or rollback" semantics.destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
# endif /* STL_USE_EXCEPTIONS */// 以下清除并释放旧的vectordestroy(start, finish);deallocate();// 以下调整水位标记start = new_start; finish =new_finish; end_of_storage =new_start + len;}
}
注意,插入完成后,新节点将位于哨兵迭代器(即上缪按的position,标示出插入点) 所指之节点的前方——这是STL对于“插入操作”的标准规范。下面的图片展示了insert(position,n,x)的操作
备用空间>=新增元素个数的情况:
①备用空间2>=新增元素个数2
②插入点之后的现有元素个数3>新增元素个数2
③插入点之后的现有元素个数2<=新增元素个数3
备用空间>=新增元素个数的情况:例如下面备用空间2<新增元素个数n==3
相关文章:

【C++】:C++中的STL序列式容器vector源码剖析
⛅️一 vector概述 vector的使用语法可以参考文章: 总的来说:vector是可变大小数组 特点: 支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢 元素保存在连续的内存空间中,因此通过下标取值非常快 在容器中间位置添加…...
final
//用final修饰的成员变量,必须在声明时或代码块中或构造函数中进行赋值 //但是在声明同时赋值或者代码块中赋值,赋值后不能改变,如果想改变 需要在构造方法中赋值...
【AI】ObjectCenteredSensing
1. 物体检测 .1. 流体 D. V. Q. Rodrigues, D. Rodriguez and C. Li, “Liquid Aerosol Detection Based on Sub-THz Portable Doppler Radars,” 2020 IEEE Asia-Pacific Microwave Conference (APMC), 2020, pp. 504-506, doi: 10.1109/APMC47863.2020.9331483. [pdf] Bala …...

一阶低通滤波器
一阶低通滤波器 X为输入,Y为滤波后得到的输出值;本次的输出结果主要取决于上次的滤波输出值,其中a是和滤波效果有关的一个参数,称为滤波系数;它决定新采样值在本次滤波结果中所占的权重; 滤波系数a越小&a…...

【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?
文章目录 🚀前言🚀插入排序(insertsort)✈️原理✈️代码实现(coding) 🚀总结🚀希尔排序(shellsort)✈️代码实现(coding)✈️为啥希尔…...

Unity中向量的点乘、叉乘区别和作用以及经典案例
文章目录 点乘(Dot Product)叉乘(Cross Product)向量归一化(Normalize)其他作用 unity开发中我们要计算角度,判断位置,常用点乘、叉乘、归一化等等,我们看看他们的使用案…...

(26)Linux 进程通信之共享内存(共享储存空间)
共享内存是System V版本的最后一个进程间通信方式。共享内存,顾名思义就是允许两个不相关的进程访问同一个逻辑内存,共享内存是两个正在运行的进程之间共享和传递数据的一种非常有效的方式。不同进程之间共享的内存通常为同一段物理内存。进程可以将同一…...
体感游戏开发体感互动游戏
体感健身游戏是一种利用特定技术来跟踪和响应玩家身体动作的互动式电子游戏。这种游戏类型的目的是通过有趣、动态的方式鼓励用户进行身体活动和健康锻炼。下面是有关体感健身游戏的一些重要信息: 体感游戏技术背景 体感技术:这些游戏通常使用运动传感…...

vulnhub靶场之DC-5
一.环境搭建 1.靶场描述 DC-5 is another purposely built vulnerable lab with the intent of gaining experience in the world of penetration testing. The plan was for DC-5 to kick it up a notch, so this might not be great for beginners, but should be ok for p…...

为什么选择CRM系统时,在线演示很重要?
想要知道一款CRM管理系统是否满足企业的需求,操作是否简单,运行是否流畅,最直观的方式就是远程演示。否则,光凭厂商的销售人员介绍一下产品,企业就盲目下单,最后发现功能不匹配,还要赔钱赔时间重…...
专业实习day3、4(路由器做内网访问公网)
专业实习 代码 display ip interface brief 显示当前设备下所有接口IP undo IP地址支持覆盖,但是正常的命令不能覆盖必须undo(删除)掉 un in en 在做配置的过程中,设备系统一般都会出现一些提示或者告警之类的东西,从…...

H264码流进行RTP包封装
一.H264基本概念 H.264从框架结构上分为视频编码层(VCL)和网络抽象层(NAL),VCL功能是进行视频编解码,包括运动补偿预测,变换编码和熵编码等功能;NAL用于采用适当的格式对VCL视频数据…...

基于多智能体点对点转换的分布式模型预测控制
matlab2020正常运行 基于多智能体点对点转换的分布式模型预测控制资源-CSDN文库...

性能分析与调优: Linux 实现 缺页剖析与火焰图
目录 一、实验 1.环境 2.缺页(RSS增长)剖析与火焰图 一、实验 1.环境 (1)主机 表1-1 主机 主机架构组件IP备注prometheus 监测 系统 prometheus、node_exporter 192.168.204.18grafana监测GUIgrafana192.168.204.19agent 监测 主机 node_exporter…...

代码随想录算法训练营第17天 | 110.平衡二叉树 + 257. 二叉树的所有路径 + 404.左叶子之和
今日内容 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和 110.平衡二叉树 - Easy 题目链接:. - 力扣(LeetCode) 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为࿱…...

ubuntu20.04网络问题以及解决方案
1.网络图标消失,wired消失,ens33消失 参考:https://blog.51cto.com/u_204222/2465609 https://blog.csdn.net/qq_42265170/article/details/123640669 原始是在虚拟机中切换网络连接方式(桥接和NAT), 解决…...

Java面试题(java高级面试题)
线程池的核心线程数设置为多大比较合理? Worker线程在执行的过程中,有一部计算时间需要占用CPU,另一部分等待时间不需要占用CPU,通过量化分析,例如打日志进行统计,可以统计出整个Worker线程执行过程中这两…...

【MIdjourney】关于图像中人物视角的关键词
本篇仅是我个人在使用过程中的一些经验之谈,不代表一定是对的,如有任何问题欢迎在评论区指正,如有补充也欢迎在评论区留言。 1.全景镜头(panorama) 全景镜头是一种广角镜头,可以捕捉到比普通镜头更广阔的视野范围。全景镜头&…...
433. 最小基因变化(Queue使用ArrayList和LinkedList进行声明)
这道题可以看成一个24叉树。 因为基因序列长度固定为8,且每个位置的字母固定是AGCT,可以选择改变的只有3个字母,所以一次最多24种情况。 然后检查变化后的结果是否存在bank中(使用hashSet来存储),同时设置…...

MYSQL双主节点–更换ip
MYSQL双主节点–更换ip 一、更换双主节点ip 1.停止mysql服务 #安装了supervisor supervisorctl stop mysql #未安装 systemctl stop mysqld2.修改网卡配置信息 注:ens33是网卡名称,可能网卡不叫ens33 vi /etc/sysconfig/network-scripts/ifcfg-ens333…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...