C++vector模拟实现
vector模拟实现
- 1.构造函数
- 2.拷贝构造
- 3.析构+赋值运算符重载
- 4.iterator
- 5.modifiers
- 5.1push_back
- 5.2pop_back
- 5.3empty
- 5.4insert
- 5.5erase
- 5.6swap
- 6.Capacity
- 6.1size
- 6.2capacity
- 6.3reserve
- 6.4resize
- 6.5empty
- 7.Element access
- 7.1operator[]
- 7.2at
- 8.在谈reserve
vector官方库实现的是一个模板类,因此我们也写个模板类。
在前面模拟实现过string类,string和vector都是动态增长的数组,有点类似。
vector把这个三个成员变量都换成了指针。
template<class T>
class Vector
{
public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;iterator _finish;iterator _endofstorage;
};
1.构造函数
//第一种无参构造Vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}
//第二种构造Vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size,capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}while (n--){push_back(val);}}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + size();_endofstorage = _start + n;}}size_t size() const{//指针减指针等于元素个数return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void push_back(const T& val = T()){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size,capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = val;++_finish;}
写完一段代码先测试测试,看看有没有错误。
这里的_finish报错了,调试一下找原因。如果不能确定到底是哪里错误,就一段一段屏蔽代码,这里我们最终确定是扩容出现了问题。
我们开辟空间之后,_finish还指向nullptr,也就是根本没有更新_finish的位置。
void reserve(size_t n){if (n > capacity()){//记录_finish的相对位置int Oldsize = size();T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;//对_finish特殊处理。//_finish=_start+_finish-_start导致的错误。//_finish = _start + size();_finish = _start + Oldsize;_endofstorage = _start + n;}}
这样写,也防止了_start本身有空间,然后异地扩容,_finish位置不对的情况。
这里的reserve内部memcpy还有一个浅拷贝的问题,等最后说到这个成员函数再具体谈。
//第三种扩容template <class InputIterator>Vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){while (first != last){push_back(*first);++first;}}iterator begin() const{return _start;}iterator end() const{return _finish;}
注意看图片的对比,右边没有屏蔽第二种构造函数,竟然报错了。
把1换成字符‘c’就不报错了。
其原因是因为10,1都是int类型,走的是模板参数的构造。
不是走的Vector(size_t n, const T& val = T()),因为int转换成size_t涉及算术转换。
而Vector(InputIterator first, InputIterator last) 这里都是同一类型,所以编译器会选择模板。
这里和库的解决方法一样,在加一个Vector(int n, const T& val = T())。
这样由于由现成的,编译器就不再会走模板了。
Vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size,capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}while (n--){push_back(val);}}
2.拷贝构造
在string模拟实现,拷贝构造实现了现代写法,是比较方便的,我们这里就继续用起来。
void swap(Vector<T> x){//这里调用的是库里面swap,关于这里可以看看string类模拟实现std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofstorage, x._endofstorage);}Vector(const Vector<T>& val):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){Vector<T> tmp(val.begin(), val.end());//这里调用的是自己写的swap,如果直接用库里面的就会调用构造和拷贝构造。swap(tmp);}
3.析构+赋值运算符重载
~Vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}//赋值运算符重载现代写法//v1=v2//v1=v1 虽然这里没有判断,但是很少有人会自己给自己赋值//即使赋值了,也是使用了一次拷贝构造Vector<T>& operator=(Vector<T> val){swap(val);return *this;}
4.iterator
iterator begin() const{return _start;}const_iterator begin() const{return _start;}iterator end() const{return _finish;}const_iterator end() const{return _finish;}
5.modifiers
5.1push_back
void push_back(const T& val = T()){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size,capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = val;++_finish;}
5.2pop_back
void pop_push(){assert(!empty());--_finish;}
5.3empty
bool empty(){return _start == _finish;}
5.4insert
void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);//扩容if (_finish == _endofstorage){int newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}iterator begin = end();while (begin > pos){*begin = *(begin - 1);--begin;}*pos = val;++_finish;}
这样写就没有问题了吗?
测试一下看看。
发现和我们预想的结果不一样,分析一下,找原因
请问pos,在扩容之后应该在哪里呢?
这里是迭代器失效:野指针问题。
扩容导致,插入pos位置还是原空间的位置。
解决方法:
更新pos的位置。
void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);//扩容if (_finish == _endofstorage){//记录pos的相对位置size_t n = pos - _start;int newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);//更新pospos = _start + n;}iterator begin = end();while (begin > pos){*begin = *(begin - 1);--begin;}*pos = val;++_finish;}
5.5erase
void erase(iterator pos){assert(pos >= _start)assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;}
在来测试一下。
发现自己实现的vector没报错,库里面的vector,删除it位置,然后再读it位置,就报错了。这是也是因为迭代器失效问题。
再看看linux环境下同样代码是上面情况。
linux环境下读it位置可以再次读,说明这个位置没有失效。
那么erase删除位置到底失效不失效呢?
erase删除it位置,失效不失效,由编译器自己决定。
再看这样一种情况。
两个平台出现不一样的结果,为了代码能够再不同平台都能正常运行。所以,
erase,删除it位置元素,统一认为it失效了。it就不能再读写访问了,更新it才能继续访问,所以erase返回被删元素的下一个位置
更新了lt位置,就不会报错了。
正确写法。
iterator erase(iterator pos){assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}
5.6swap
void swap(Vector<T>& x){std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofstorage, x._endofstorage);}
6.Capacity
6.1size
size_t size() const{//指针减指针等于元素个数return _finish - _start;}
6.2capacity
size_t capacity() const{return _endofstorage - _start;}
6.3reserve
void reserve(size_t n){if (n > capacity()){//记录_finish的相对位置int Oldsize = size();T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;//对_finish特殊处理。//_finish=_start+_finish-_start导致的错误。//_finish = _start + size();_finish = _start + Oldsize;_endofstorage = _start + n;}}
6.4resize
resize有三种情况;
n<size();删除元素
size()<n<capacity();插入元素
n>capacity();扩容+插入元素
void resize(size_t n, const T& val=T()){if (n > size()){//这里在reserve已经判断过了是否扩容reserve(n);//插入数据while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}
6.5empty
bool empty(){return _start == _finish;}
7.Element access
7.1operator[]
T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}
7.2at
T& at(size_t pos){assert(pos < size());return _start[pos];}const T& at(size_t pos) const{assert(pos < size());return _start[pos];}
剩下接口比较简单,这里就不再模拟实现了。
8.在谈reserve
在谈reserve之前,做一道LeetCode的题
118. 杨辉三角
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows);for(int i=0;i<vv.size();++i){vv[i].resize(i+1);//放数据for(int j=0;j<vv[i].size();++j){if(j == 0 || j == vv[i].size()-1){vv[i][j]=1;}else{vv[i][j]=vv[i-1][j-1]+vv[i-1][j];}}}return vv;}
};
注意这道题,vector < T > ,T是自定义类型,不是内置类型;我们用自己写的vector来跑一下类似的代码,看看有没有什么问题。
void test_Vector4()
{Vector<Vector<int>> vv;Vector<int> v(5, 1);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){cout << vv[i][j] << " ";}cout << endl;}}
为什么会有随机值的出现呢?
画图分析。
原因在于,reserve中memcpy拷贝的时候是浅拷贝,delete[ ] _start会把原有空间给释放掉了,所以出现随机值问题,
解决方法:浅拷贝换成深拷贝。
void reserve(size_t n){if (n > capacity()){//记录_finish的相对位置int Oldsize = size();T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){//浅拷贝//memcpy(tmp, _start, sizeof(T) * size());//深拷贝for (size_t i = 0; i < Oldsize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;//对_finish特殊处理。//_finish=_start+_finish-_start导致的错误。//_finish = _start + size();_finish = _start + Oldsize;_endofstorage = _start + n;}}
自此关于vector类模拟实现结束了。里面有很多值得多多思考的东西,希望能给你带来一份收获,喜欢的小伙伴,点赞,评论,收藏+关注!下篇博文再见!
相关文章:

C++vector模拟实现
vector模拟实现 1.构造函数2.拷贝构造3.析构赋值运算符重载4.iterator5.modifiers5.1push_back5.2pop_back5.3empty5.4insert5.5erase5.6swap 6.Capacity6.1size6.2capacity6.3reserve6.4resize6.5empty 7.Element access7.1operator[]7.2at 8.在谈reserve vector官方库实现的是…...

《DATASET DISTILLATION》
这篇文章提出了数据浓缩的办法,在前面已有的知识浓缩(压缩模型)的经验上,提出了不压缩模型,转而压缩数据集的办法,在压缩数据集上训练模型得到的效果尽可能地接近原始数据集的效果。 摘要 模型蒸馏的目的是…...
GDPU 数据结构 天码行空1
1. 病历信息管理 实现病历查询功能。具体要求如下: 定义一个结构体描述病人病历信息(病历号,姓名,症状);完成功能如下: 输入功能:输入5个病人的信息; 查询功能:输入姓名,在5个病历中进行查找,如果找到则显示该人的信息,…...

【C++】红黑树的模拟实现
🌇个人主页:平凡的小苏 📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风…...

【多线程】Thread 类 详解
Thread 类 详解 一. 创建线程1. 继承 Thread 类2. 实现 Runnable 接口3. 其他变形4. 多线程的优势-增加运行速度 二. Thread 类1. 构造方法2. 常见属性3. 启动线程-start()4. 中断线程-interrupt()5. 线程等待-join()6. 线程休眠-sleep()7. 获取当前线程引用 三. 线程的状态1. …...

LINUX 网络管理
目录 一、NetworkManager的特点 二、配置网络 1、使用ip命令临时配置 1)查看网卡在网络层的配置信息 2)查看网卡在数据链路层的配置信息 3)添加或者删除临时的网卡 4)禁用和启动指定网卡 2、修改配置文件 3、nmcli命令行…...

refresh rate
1920 x 1080 显卡刷新率 60...
使用 NGINX Unit 实施应用隔离
原文作者:Artem Konev - Senior Technical Writer 原文链接:使用 NGINX Unit 实施应用隔离 转载来源:NGINX 中文官网 NGINX 唯一中文官方社区 ,尽在 nginx.org.cn NGINX Unit 特性集的最新动态之一是支持应用隔离,该特…...

2023/09/12 qtc++
实现一个图形类(Shape) ,包含受保护成员属性:周长、面积, 公共成员函数:特殊成员函数书写 定义一个圆形类(Circle) ,继承自图形类,包含私有属性:半径 公共成员函数:特殊成员函数…...

全科医学科常用评估量表汇总,建议收藏!
根据全科医学科医生的量表使用情况,笔者整理了10个常用的全科医学科量表,可在线评测直接出结果,可转发使用,可生成二维码使用,可创建项目进行数据管理,有需要的小伙伴赶紧收藏! 日常生活能力量表…...

了解消息中间件的基础知识
为什么要使用消息中间件? 解耦:消息中间件可以使不同的应用程序通过解耦的方式进行通信,减少系统间的依赖关系提供异步通信:消息中间件可以实现异步消息传递,提高系统的响应性能。流量削峰:消息中间件可以…...

【linux】Linux wps字体缺失、加粗乱码解决
解决wps字体缺失问题 1、下载字体包 git clone https://github.com/iamdh4/ttf-wps-fonts.git2、创建单独放置字体的目录 mkdir /usr/share/fonts/wps-fonts3、复制字体到系统目录下 cp ttf-wps-fonts/* /usr/share/fonts/wps-fonts4、修改字体权限 chmod 644 /usr/share/f…...
每日两题 103二叉树的锯齿形层序遍历(数组) 513找树左下角的值(队列)
103 题目 103 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 示例 1: 输入:root [3,9,…...
ROS2报错:ImportError: cannot import name ‘Log‘ from ‘rosgraph_msgs.msg‘
在使用ros2的bag命令查看数据集信息时报错 Traceback (most recent call last):File "/opt/ros/noetic/bin/rosbag", line 34, in <module>import rosbagFile "/opt/ros/noetic/lib/python3/dist-packages/rosbag/__init__.py", line 33, in <mo…...
【Vue】Vue中的代码分为哪几种类型?
在 Vue 中的代码可以分为以下几种类型: 1.模板代码 模板代码是 Vue 中用来生成 HTML 的一种语法,可以通过 Vue 的模板语法和指令来动态渲染页面。模板代码一般写在 Vue 组件的 template 标签中。 2.JavaScript 代码 JavaScript 代码是 Vue 组件中用来…...
es6中includes用法
js中的includes用法 1.数组 includes 可以判断一个数组中是否包含某一个元素,并返回true 或者false [a,b,c].includes(a) true [a,b,c].includes(1) false includes可以包含两个参数,第二个参数表示判断的起始位置 起始位置第一个数字是0。 2.字符串 …...
QT中QRadioButton实现分组C++
通过对QRadioButton组件进行分组可解决QRadioButton组件的互斥性 实现如下。 假设已设计好UI并且有UI代码情况: 头文件引用: #include <QButtonGroup> 分组功能 ,cpp文件代码实现: Your_Project::Your_Project(QWidge…...

kafka实战报错解决问题
需求 在一个在线商城中,用户下单后需要进行订单的处理。为了提高订单处理的效率和可靠性,我们使用Kafka来实现订单消息的异步处理。当用户下单后,订单信息会被发送到Kafka的一个Topic中,然后订单处理系统会从该Topic中消费订单消…...

vite+react 使用 react-activation 实现缓存页面
对应的版本 "react": "^18.2.0", "react-activation": "^0.12.4", "react-dom": "^18.2.0", "react-router-dom": "^6.15.0",react-activation 这是一个npm包,在react keep alive…...
【android 蓝牙开发——蓝牙耳机】
【android 蓝牙开发——传统蓝牙】 【android 蓝牙开发——BLE(低功耗)蓝牙 2021-10-09更新】 总结一下蓝牙开发的基本使用以及蓝牙耳机的断开和链接。 所以需权限: <uses-permission android:name"android.permission.ACCESS_FIN…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...