【C++】vector的模拟实现
文章目录
- 1.查看STL源码
- 2.vector的模拟实现
- 1. 构造函数
- 无参构造
- 构造n个 val
- 迭代器模板
- 2. reserve
- 3. 迭代器
- 4.pop_back 尾删
- 5.resize
- 6.push_back
- 7.insert
- 迭代器失效—— pos为野指针
- 迭代器失效——修改迭代器位置
- 8. erase
- 对于VS和Linux环境测试
- 3.深浅拷贝问题
- 4. 整体代码实现
1.查看STL源码
start、finish、end_of_storage 都是指针
通过观察函数的实现过程,可以得知 start与begin等价 ,end与finish等价
2.vector的模拟实现
为了模拟实现vector,所以使用自己的名空间包含vector类
1. 构造函数
无参构造
vector()//构造函数:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}
只是将_start 、_finish 、_end_of_storage 初始化为nullptr
构造n个 val
vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);//扩容for (int i = 0; i < n; i++){push_back(val);}}
正常来说匿名对象生命周期只有这一行,因为这行之后没有会用它了
当调用完匿名对象后,会调用析构函数
引用会延长匿名对象的生命周期到引用对象域结束,因为后面用xx就是用匿名对象
由于匿名对象具有常性,所以需要用const修饰
此时调用完匿名对象,并不会调用析构函数释放
迭代器模板
template <class InputIterator>//随机迭代器vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){//[first,last)while (first != last){push_back(*first);first++;}}
template <class InputIterator>//随机迭代器vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){//[first,last)while (first != last){push_back(*first);first++;}}
提供迭代器模板,可以使用任意类型迭代器

调用vector本身迭代器
对于数组和string类型也同样适用
2. reserve
void reserve(size_t n)//开辟空间{if (n > capacity())//避免缩容{size_t sz = size();T* tmp = new T[n];if (_start != NULL)//为NULL时没有意义{memcpy(tmp, _start, sizeof(T)*size());//拷贝数据delete[]_start;//释放旧空间}_start = tmp;//指向新空间_finish = tmp + sz;_end_of_storage = tmp + n;//容量变大了}}
为了避免缩容的情况,所以使用 n>capacity() , 开辟一块空间tmp,将start中的数据拷贝到新空间,释放旧空间,指向新空间,同时更新_finish 和_end_of_storage
在计算_finish的大小时,由于size里面的_start改变了,所以需要提前储存原来的size
3. 迭代器
typedef T* iterator;
typedef const T* const_iterator;
iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const {return _start;}const_iterator end()const{return _finish;}
正向迭代器的应用
反向迭代器的应用
此时v由const修饰,所以需要const_iterator类型的迭代器
4.pop_back 尾删
为了防止没有数据继续删除,使用断言报错
bool empty(){return _start = _finish;}void pop_back()//尾删{assert(!empty());_finish--;}
5.resize
void resize(size_t n ,T val=T())//扩容+初始化{if (n < size())//删除数据{_finish = _start + n;}else{if (n > capacity()){reserve(n);//扩容}while (_finish != _start + n)//将剩余空间初始化{*_finish = val;_finish++;}}}
T val= T() ,T()是匿名对象,因为T模板泛型,所以有可能是内置类型int char,也有可能是自定义类型,为了两者都可以使用,所以使用匿名对象调用默认构造函数
内置类型也是有构造函数的
6.push_back
void push_back(const T& x)//尾插{if (_finish == _end_of_storage)//扩容{reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;}
需要考虑扩容问题,而若capacity本身为0的情况也要考虑
7.insert
void insert(iterator pos, const T& val)//在pos位置前插入n{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;//记录pos在旧空间所处位置reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos,解决pos失效的问题pos = _start +len;}iterator end = _finish-1;while (end >= pos){*(end+1) = *end ;end--;}*pos = val;_finish++;}
迭代器失效—— pos为野指针
扩容时出现了问题,由于pos指向原来的空间,但是扩容时将释放了旧空间,但是pos依旧指向原来的空间,所以pos变成了野指针
所以需要记录pos在旧空间所处位置,再更新pos在新空间的位置
迭代器失效——修改迭代器位置
加入修改迭代器位置后,会直接报错
形参pos位置的改变不会影响实参,所以pos依旧指向旧空间

若将形参pos加入引用,会报错,当调用begin时,因为是传值返回,所以返回临时对象,而临时对象具有常性,所以不能直接传给引用

为了解决这个问题,将修改指向的pos返回
8. erase
void erase(iterator pos)//删除pos位置数据{assert(pos >= _start);assert(pos < _finish);iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;start++;}_finish--;}
对于VS和Linux环境测试
VS做了强制检查,只要使用了erase,迭代器就失效了,所以会报错
而同样的代码在Linux下会就能正常运行

遇到偶数就删除,并且每次结尾pos都会++,运行结束时正好pos位置等于finish

VS做了强制检查,使用erase后,迭代器失效了,所以会报错

同样的代码在Linux下就会发生段错误
假设为最后一个位置被删除,finish会移动到到最后到3位置的后面,同时pos++,此时pos位置已经在finish位置后面,就会造成一直循环下去
说明g++没有强制类型检查,具体问题具体分析,结果未定义
3.深浅拷贝问题

对内置类型调用默认拷贝构造函数会进行浅拷贝,所以需要我们自己来实现深拷贝
vector(const vector<T>& v)//拷贝构造{_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_end_of_storage = _start + v.capacity();}
若为上面内置类型,那报错的问题就可以解决了,但若为自定义类型依旧会报错

因为自己实现的拷贝构造中memcpy也是一种浅拷贝(按字节拷贝)
深拷贝是重新开辟一块与原空间大小相同的新空间,并将原空间的数据拷贝给新空间,但是若为string 类型,本身的_str指向字符串,而新空间只是将_str拷贝过去了,依旧指向同一字符串
v2先进行析构,会调用delete[ ] ,会对数组上每个成员依次调用析构函数,此时指向的字符串旧全部被析构了,
再次使v1析构,依旧会析构字符串,所以会报错
属于深拷贝内的浅拷贝

这样v1与v2中的_str都指向自己的字符串,不会发生析构两次的问题了
同样reserve也存在使用memcp造成浅拷贝的问题

将旧空间上的_str等拷贝到新空间上,释放旧空间就导致_str所指向的字符串析构
当新空间析构时,_str所指向的字符串就会造成二次析构,从而报错


4. 整体代码实现
#include<iostream>
#include<vector>
#include<assert.h>
#include<algorithm>
#include<functional>
using namespace std;
namespace yzq
{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector()//构造函数:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);//扩容for (int i = 0; i < n; i++){push_back(val);}}vector(const vector<T>& v)//拷贝构造{reserve(v.capacity());for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}void push_back(const T& x)//尾插{if (_finish == _end_of_storage)//扩容{reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;}size_t capacity()const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t n)//开辟空间{if (n > capacity())//避免缩容{size_t sz = size();T* tmp = new T[n];if (_start != NULL)//为NULL时没有意义{for (size_t i = 0; i < sz; i++)//深拷贝{tmp[i] = _start[i];}delete[]_start;//释放旧空间}_start = tmp;//指向新空间_finish = tmp + sz;_end_of_storage = tmp + n;//容量变大了}}T& operator[](size_t pos){assert(pos < size());//防止越界return _start[pos];}iterator begin(){return _start;}iterator end(){return _finish;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}int main()
{yzq::vector<std::string> v1(3, "111111111111111111111111");for (auto e : v1){cout << e << " ";}cout << endl;yzq::vector<std::string>v2(v1);v2.push_back("333333333"); v2.push_back("333333333");v2.push_back("333333333");for (auto e : v2){cout << e << " ";}cout << endl;
}相关文章:
【C++】vector的模拟实现
文章目录1.查看STL源码2.vector的模拟实现1. 构造函数无参构造构造n个 val迭代器模板2. reserve3. 迭代器4.pop_back 尾删5.resize6.push_back7.insert迭代器失效—— pos为野指针迭代器失效——修改迭代器位置8. erase对于VS和Linux环境测试3.深浅拷贝问题4. 整体代码实现1.查…...
THUPC-2023 游记
清华校赛,战火重燃 原文链接 宣传图 上周四同学在洛谷无意间看到了宣传图,当时很有感触。不知觉间,又是一年春,又是一场触动心弦的 THUPC 了。 周五的团建过于有趣,致使我完全将 THUPC 抛之脑后了。 周日上午被省选…...
Linux - 磁盘I/O性能评估
文章目录概述RAID文件系统与裸设备的对比磁盘I/O性能评判标准常用命令“sar –d”命令组合“iostat –d”命令组合“iostat –x”单独统计某个磁盘的I/O“vmstat –d”命令组合小结概述 RAID 可以根据应用的不同,选择不同的RAID方式 如果一个应用经常有大量的读操…...
计算机网络--网络基础
目录 一.互联网的组成 编辑 1.互联网的边缘部分 1.1客户-服务器方式 1.2对等连接方式 编辑 2.互联网的核心部分 2.1电路交换 2.2分组交换 2.3报文交换 二.计算机网络的类别 1.按网络的作用范围进行分类 2.按网络的使用者进行分类 3.用来把用户接入互联…...
Gin 接口超时控制
文章目录1.Gin 的 Middleware2.gin-contrib/timeout3.小结参考文献API 是现代应用程序中的重要组成部分,可以用于提供数据和功能,供客户端应用程序访问。由于网络不稳定、服务器负载、网络拥堵等因素,API 请求可能会花费较长时间。这可能导致…...
1.C#与.NET简介
目录 一、C#语言及其特点 二、C#与.NET Framework/.NET Core关系 三、C#应用开发 四、案例展示 五、学习环境 一、C#语言及其特点 C#是美国微软公司发布的一种面向对象的,运行于 .NET Framework 和 .NET Core (完全开源,跨平台ÿ…...
OpenAI CTO、吴恩达夫人……AI 领域值得关注的「她」力量,个个都是女强人
内容一览: 「她时代」来临,一些有着强大信念与热情的女性,纷纷投身至 AI 领域,成为不可或缺的存在与力量。值此国际妇女节到来之际,HyperAI超神经盘点了领域内令人印象深刻的杰出的女性代表。 关键词:国际妇…...
[ 网络 ] 应用层协议 —— HTTP协议
目录 1.HTTP协议 1.1URL urlencode和urldecode 2. HTTP协议格式 HTTP请求 HTTP响应 3.告知服务器意图的HTTP方法 GET:获取资源 POST:传输实体主体 GET和POST的区别 使用Cookie的状态管理 4.返回结果的HTTP状态码 状态码告知从服务器端返回的…...
Spring Boot 整合 Redisson 缓存性能客户端(2023-03-06)
Spring Boot 整合 Redisson 缓存 (官网) 介绍: Redisson是一个在Redis的基础上实现的Java驻内存数据网格(In-Memory Data Grid)。它不仅提供了一系列的分布式的Java常用对象,还提供了许多分布式服务。其中包括(BitSet, Set, Multimap, Sorte…...
【C和C++】输出100内能够被13整除的数,取模判断方法
目录 前言基础概念重温整除例子小知识点收尾前言 在软件行业已经有快十年,技术虽然一般般,但是足够应付和解决编程入门的相关问题! 都说十年磨一剑,积累到一定经验,是时候发挥自己的价值,给予入门的同行些许的帮助! 为什么要写收费专栏,其实原因很简单,时间就是金钱(…...
STC8单片机基于开源库读取DS18B20数据例程
STC8单片机基于开源库读取DS18B20数据例程 📍开源库FwLib_STC8 Github地址:https://github.com/IOsetting/FwLib_STC8📌STC官方STC8库函数资源:https://www.stcai.com/khs🎉本次利用FwLib_STC8库读取DS18B20,由于该开源库是基于VSCode编写,默认使用的是SDCC编译器,在…...
计算机专业毕业设计基于Spring Boot 学生在线考试系统
目录 一、学生端 1.1 登录 1.2 注册 1.3 学生首页 1.4 学生查看任务中心的试卷(已答卷/未答卷) 1.5 学生查看固定试卷以及开始做题 1.6 学生查看时段试卷以及开始做题 1.7 学生查看试卷中心 1.8 学生查看考试记录以及查看试卷 1.9 学生查看…...
【读书笔记】《深入浅出数据分析》第八章 启发法
目录一,什么是启发法?1,那什么是启发法?2,心理学上对启发法定义二,活动分析1,如何去分析活动效果呢?1.1 活动前期(活动前1-2周)1.2 活动中期1.3 活动结束一&a…...
英飞凌Tricore实战系列导读
本文框架 1.系列概述1.1 外设理论及应用介绍1.2 基于TC3xx的MCAL各外设配置开发1.3 基于TC3xx的Davinci工程开发1.4 项目中问题排查经验分享1.5 其他相关话题分享2. 目前已发布系列文章汇总1.系列概述 英飞凌TC3xx以其强大的性能,扩展性,存储及安全性能在汽车电子中扮演着越…...
做数据分析有前景吗?
当然有前景的。 每个行业都有发展前景,只是看你自身的技能情况或者关系人脉、软实力方面是否到位,不同的行业要求不一样。作为数据分析领域而言,属于IT行业,看的是你的专业技能;只要你技能过硬,就能在行业…...
Rust Web入门(六):服务器端web应用
本教程笔记来自 杨旭老师的 rust web 全栈教程,链接如下: https://www.bilibili.com/video/BV1RP4y1G7KF?p1&vd_source8595fbbf160cc11a0cc07cadacf22951 学习 Rust Web 需要学习 rust 的前置知识可以学习杨旭老师的另一门教程 https://www.bili…...
1.特定领域知识图谱知识融合方案(实体对齐):金融产业产业知识图谱-基于内容匹配和图模型的品牌知识链指
1 引言 供应链金融是一种围绕经营关系,以核心企业为依托,针对中小企业的新型金融服务。如何精准地还原企业间的经营关系,是供应链金融的关键所在。知识图谱是描绘实体间关系的网络结构,对于挖掘企业关系有重要意义。在真实场景中,仅有企业与用户的微观知识对于还原经营关系…...
前端基础语法合集
JS语法基础1-注释//单行注释/*......*/多行注释2-分号;用作分割javascript语句,可以省略。3-变量定义定义变量使用varvar a;//声明变量 var a100;//声明变量并赋值 var b,c;//声明多个变量 var d20;bd1;cb1;//一行多条语句要用;分割4-数据类型判断该变量…...
百亿补贴,京东的自卫反击战
“百亿补贴”这个词大家有没有很熟悉?大部分人应该是在看拼多多投放广告的时候,知道这个词的吧。而京东APP也于近日在升级11.6.2版本时,在更新日志中明确提到:“京东3.8节,百亿补贴上线”。至此,发酵数日的…...
融云入选中国信通院《高质量数字化转型产品及服务全景图》
企业数字化转型正在进入“深水区”。 3 月 3 日,“中国信息通信研究院(以下简称中国信通院)高质量数字化转型创新发展大会暨中国信通院‘铸基计划’年度峰会”在京召开,深度展示了中国信通院在数字化转型领域的工作成果ÿ…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
高分辨率图像合成归一化流扩展
大家读完觉得有帮助记得关注和点赞!!! 1 摘要 我们提出了STARFlow,一种基于归一化流的可扩展生成模型,它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流(TARFlow&am…...
负载均衡器》》LVS、Nginx、HAproxy 区别
虚拟主机 先4,后7...
医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
