[C++]vector模拟实现

news/2024/4/19 0:18:35

目录

前言:

1. vector结构

2. 默认成员函数

2.1 构造函数

无参构造:

有参构造:

有参构造重载:

2.2 赋值运算符重载、拷贝构造(难点)

2.3 析构函数:

3. 扩容

3.1 reserve

3.2 resize

4. 插入删除

5. 迭代器操作


前言:

        本篇文章模仿的vector与STL源码并不完全一致,例如本文直接通过new来开辟空间,但是源码中通过内存池分配,但是这并不影响彼此之间的关系,所以本篇文章还是有一定的学习意义的。

1. vector结构

模板:

template<class T>

class vector

{

public:

        typedef T* iterator;

        typedef const T* const_iterator;

private:

        iterator _start;

        iterator _finish;

        iterator _end_of_storage;

        我相信如果大家用过vector的话,一定是知道每一次使用vector都需要标注清楚这个类是用来存储什么样的数据的,例如:

vector<int> vv1;                存整型数据

vector<double> vv2;         存浮点型数据

vector<vector<int>> vv3;  存存整型数据的vector数据

        所以,我们模拟的vector类就不能单独面向某一种数据,而是应该考虑到所有的类型,就算是一直自定义类型嵌套也能实例化出来,如下:

vector<vector<vector<vector<vector<int>>>>>  vv4;

         虽然上述的类型对于我们来说估计这辈子都不会遇到,但是我们总不能防止某些好奇心重的小伙伴搞事,所以是必须要能够支持这种写法的,就像是为了满足到酒吧点炒饭的帅小伙。

        所以首先得出结论:我们的类需要被构建成模板类。

成员变量:

        上面代码中可以看到我们的成员变量的类型是自定义类型重定义iterator,也就是平时我们熟知的迭代器,我们的迭代器实现又是指针的方式,所以可以将这三个变量理解为我们存储数据空间的三个位置。_start对应开头,_finish对应数据结尾,_end_of_storage对应空间容量的最后位置。也即是对应我们顺序表的size和capacity。

2. 默认成员函数

        每当我们实现一个类,默认成员函数是必不可少的,特别是像是我们vector这样需要向堆申请空间的类。

2.1 构造函数

无参构造:

        无参构造可以说是非常简单了,我们甚至连空间都不需要开辟,只需要通过初始化列表为我们的三个迭代器变量初始化即可,如下:

//默认构造方式,全指针都置空值,后续无论怎么插入都有扩容为指针赋值
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}

        可能有朋友要问,那用这种方式,不就表示了自己之后不能插入数据之类的吗?事实不是,因为我们还有其它的函数接口为我们服务,大家看下去就明白了。

有参构造:

        有参构造咱们就与库保持一次,既然它不支持通过一个值直接去初始化,而支持通过n个T类型数据去构造,那么我们也这样学习它这样:

         看不懂上面的库实现方式没事,看我的也是一样:

//有参构造n个T类型的数据进入vector<int>
vector(size_t n, const T& va = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{T* temp = new T[n];for (size_t i = 0; i < n; ++i){//这里赋值操作是<T>和<T>之间的操作temp[i] = va;}_start = temp;_finish = _start + n;_end_of_storage = _finish;
}

        这里的构造也是一样,需要通过初始化列表先将三个迭代器变量初始化空指针,因为我们不能保证有没有小聪明蛋给n赋值为0去初始化,其次就是我这里使用了T()这样的匿名对象作为缺省参数。

        有同学在这里就要问了:T()这样的匿名对象生命周期不是只有一行吗?你这代码都多少行了,还在用不是错的吗?

        其实不是,在C++当中,当我们用const加引用类型的变量去接收匿名对象,会改变匿名对象的生命周期为这个变量的生命周期长度,如下:

const int& ret = T();        改变T()的生命周期为ret

T();                                生命周期只有一行

         值得注意的是上面的const是必须加的,因为我们的T()属于本身是属于临时对象的,而临时对象又有常量属性,也就是不可更改属性。如果不用const接收,那么就会导致错误。

        有点意思的是,不加const在vs2013及其之前的版本都是不报错的,后续版本我不清楚,但是到了vs2019这个BUG就被修复了。

函数设计:

        这里的代码我用了最全面的写法,后面可以通过函数复用的方式直接究极简化。

        首先通过new向堆申请n个T类型的空间,这里不能使用malloc这种C语言的申请方式,原因我相信大家也明白,就是因为我们要实现模板类,那必然有可能使用自定义类型,有自定义类型要就要去调用它的构造函数,只有new才能实现,malloc不行。

T* temp = new T[n];

        然后通过循环不断的赋值,最后为三个迭代器变量定位即可,这里循环体中的赋值操作涉及了很复杂的嵌套操作,绝不是简单的一行代码,等到下一小节重载赋值运算符我再来讲。

有参构造重载:

vector(int n, const T& va = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (n--){push_back(va);}
}

        该重载的函数体就是我所说的究极优化的方式,通过尾插函数,不断的复用,就实现了函数功能,但是重点不在这里,我重载这个函数的意义在于为我们的迭代器区间构造函数服务。 

        为什么这么说?请先看迭代器区间构造函数。

template<class InputIterator>
vector(InputIterator start,InputIterator end):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (start != end){push_back(*start);++start;}
}

         首先我们得知道一个点,那就是C++为我们提供了函数重载,那么编辑器就会通过传入的参数类型为我们匹配最适合的函数

        举例:当我们通过下列方式传参:

vector<int> vv1(5,5);

        编辑器会将我们的传参类型认为是int,int,而不是size_t,int,也就是说,编辑器就会找到迭代器区间构造函数中去了,这并不是我们想要的结果,而编辑器却认为这是最合适的函数,为了避免这种情况的出现,所以需要重载int型的构造函数。

        当然,有的小伙伴可能不太理解为什么我们需要再写一个模板出来,这理解起来真难受。这确实让人很难受,但是他带来的好处也是很大的,因为这样实现的功能,让我们的构造方式做种多样的起来,无论是何种形式的迭代器去构造,我们都有对应的方式去构造出来,这就是牛逼之处。

2.2 赋值运算符重载、拷贝构造(难点)

代码:

vector<T>& operator=(const vector<T>& va)
{if (_start != va._start){//只能通过new的方式实现,因为要调用自定义类型的构造函数T* temp = new T[va.capacity()];//保留数据//memcpy(temp, va._start, sizeof(T)* va.size());int len = va.size();for (int i = 0; i < len;++i){//嵌套temp[i] = va[i];}//释放掉原来空间,如果有的话delete[] _start;_start = temp;_finish = _start + va.size();_end_of_storage = _start + va.capacity();}return *this;
}

        赋值需要相同类型才能成功,这里用const vector<T>&相信大家也能理解,我就直接切入重点了。

        为什么我代码中要用循环一个一个的赋值,为什么不直接调用库函数memcpy()呢?简单又方便,而是通过循环一个一个的赋值,感觉写得好搓哦。其实呢,也不是博主不想用memcpy(),而是现实给了博主一巴掌,让我认清,写模板类的深拷贝有多令人头疼。

        举一个例子:如果我们构建的vector<vector<int>>类型的类,那么我们开辟了一片空间用于存n个vector<int>,然后这些vector<int>被我们直接用memcpy直接拷贝过来了,但是我们呢,又不能直接为单独写一个函数,因为这是模板,要是单独写了,又不满足vector<int>类型了。下图:

         原本我们是希望赋值出来的对象能有一个新的空间去承载这些数据,如上图,但是如果我们通过memcpy来实现能够成功吗?请看下图:

         很明显,如果通过memcpy实现了一个什么功能?我们确实实现了一层深拷贝,将vector<int>用新的空间承载起来了,但是还有更里面的空间呢?这些空间也是需要new出来的哇。用memcpy还能行吗?能行,但不完全行,除非你保证你以后不会用自定义类型模板。

        所以决定采用循环的方式,一次一次的赋值,其中有一句话非常重要,那就是:

temp[i] = va[i];

         这一句话没有你想象的那么简单,你想,如果是内置类型我们关不关心他申请空间?不关心,那么对于自定义类型它会怎么做?嵌套!!!,直到遇到内置类型嵌套就结束了,如下图:

        上图中,我们可以看到,每次我们赋值拷贝,如果遇到了一个赋值运算符,编辑器就回去检查是否是自定义类型,需要去调用赋值运算符重载函数,如此反复,直到没有赋值运算符重载函数,也就是没有需要申请空间的必要了

         下图的编译,运行,使用也不会报任何的错误了。

拷贝构造:

//拷贝构造
vector(const vector<T>& va)
{//赋值重载*this = va;
}

        拷贝构造直接复用赋值运算符重载函数就行,写法和逻辑思维差不多,博主也想偷懒。

2.3 析构函数:

//析构函数
~vector()
{//释放空指针不会出错,无论是什么方式delete[] _start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;
}

        析构函数也没有什么好讲的,看代码就行。

3. 扩容

3.1 reserve

代码:

void reserve(size_t n)
{if (n > capacity()){size_t len = size();T* temp = new T[n];if (_start != nullptr){//memcpy(temp, _start, sizeof(T) * size());for (size_t i = 0; i < len; ++i){temp[i] = _start[i];}delete[] _start;}_start = temp;_finish = _start + len;_end_of_storage = _start + n;}
}

        vector和其它string、顺序表或者说任何数据结构一样,能不缩容就不缩容,所以,当我们的n小于容量大小的时候,不做任何处理直接返回即可。

        同样,这里也涉及到了多次深拷贝的问题,也就不能用memcpy来实现,需要用循环依次赋值。还有,咱们需要考虑到当空间异地扩容之后是需要将原空间释放的,以防内存泄漏。

3.2 resize

代码:

void resize(size_t n,const T val& = T())
{//小于操作不需要缩容,只需要将_finish重定位即可if (n < size()){_finish = _start + n;}else if (n == size()){}		//无动作else{int len = n - size();//_finish和_end_of_storage的绝对位置之差与n的大小之比if (_finish + n > _end_of_storage){reserve(capacity() == 0 ? n : capacity()+n);}//补齐T类型数据while (len-- > 0){*_finish = val;_finish++;}}
}

        resize功能比reserve多一个,那就是能够实现重定size大小,大于size的部分通过数据val占位。然后复用reserve,如果是第一次扩容,那就需要用三目运算来判断给定大小。

4. 插入删除

        内容比较简单,相信大家配合注解能够看懂,直接上代码:

//尾插只需要考虑如果空间不够就应该扩容
//并且,还有空容量的情况也需要考虑
void push_back(const T& val)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//如果不需要reserve表示不用扩容,那么就是原地扩,不需要动_start和_end_of_storage//如果扩了容,reserve会为我们将这几个变量重定向*_finish = val;++_finish;
}//插入
iterator insert(iterator pos, const T& val)
{//检查插入位置的有效性assert(pos >= _start);assert(pos <= _finish);//提前保留绝对距离size_t len = pos - _start;//判断扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//通过绝对值偏移重定向pos = _start + len;//指向最后一个位置的下一个地址iterator end = _finish;//移动完pos位置的数据,结束while (end > pos){*(end) = *(end - 1);--end;}//因为有赋值运算符重载,那么不管是否是内置类型,都能满足*pos = val;//向后移动一位++_finish;return pos;
}//删除
void erase(iterator pos)
{//判断pos可行性assert(pos >= _start);assert(pos < _finish);//从pos下一个位置地址开始依次向前移动iterator start = pos + 1;//中途是没有任何扩容缩容的地方,所以迭代器不会更换while (start != _finish){*(start - 1) = *start;++start;}//删除会有机会产生结果不确定的意外情况//所以,任何一次删除,该迭代器都应该被销毁//该函数才不会设置返回值--_finish;
}//尾删,检查是否还有数据能删除
void pop_back()
{assert(_start != _finish);--_finish;
}

5. 迭代器操作

//迭代器
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}//求个数、容量
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}//重载[],需要区分const有无的区别和pos位置的准确性
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}

        迭代器是有失效的情况的,这部分根据不同的编辑器会有不同的实现方式,博主这里不太想多讲,不过我建议大家通过迭代器插入删除数据之后就别再使用这个迭代器了,或者是重新给他定位,防止非法越界。


        以上就是博主对vector模拟实现的全部理解了,希望能够帮到大家。


http://www.ppmy.cn/news/30123.html

相关文章

【C++】类和对象补充知识点

&#x1f3d6;️作者&#xff1a;malloc不出对象 ⛺专栏&#xff1a;C的学习之路 &#x1f466;个人简介&#xff1a;一名双非本科院校大二在读的科班编程菜鸟&#xff0c;努力编程只为赶上各位大佬的步伐&#x1f648;&#x1f648; 目录前言一、再谈构造函数1.1 构造函数体赋…

解析MySQL 8.0 OCP(1Z0-908)考试中一道大部分同学都会做错的题目

一个用户有下面的权限: mysql>SHOW GRANTS FOR jsmith;---------------------------------------------------------------------- | Grants for jsmith% | ----------------------------------------------------------…

【Linux】P4 Linux 权限 chmod chown

Linux 权限认知权限信息chmod 修改权限chown 修改用户与用户组认知权限信息 序号1&#xff1a;文件、文件夹权限控制信息&#xff1b; 权限控制信息一共有十位 第 1 位&#xff1a; - 表示文件&#xff0c;d 表示文件夹&#xff0c;l 表示软链接 第 2~4 位&#xff1a; 所属用…

MATLAB——数据及其运算

MATLAB数值数据数值数据类型的分类1&#xff0e;整型整型数据是不带小数的数&#xff0c;有带符号整数和无符号整数之分。表中列出了各种整型数据的取值范围和对应的转换函数。2&#xff0e;浮点型浮点型数据有单精度(single&#xff09;和双精度&#xff08;(double)之分&…

你不会工作1年了连枚举都还不知道吧?

&#x1f497;推荐阅读文章&#x1f497; &#x1f338;JavaSE系列&#x1f338;&#x1f449;1️⃣《JavaSE系列教程》&#x1f33a;MySQL系列&#x1f33a;&#x1f449;2️⃣《MySQL系列教程》&#x1f340;JavaWeb系列&#x1f340;&#x1f449;3️⃣《JavaWeb系列教程》…

2023年Wireshark数据包分析——wireshark0051.pcap

Wireshark数据包分析 任务环境说明: 服务器场景:FTPServer220223服务器场景操作系统:未知(关闭连接)FTP用户名:wireshark0051密码:wireshark0051从靶机服务器的FTP上下载wireshark0051.pcap数据包文件,找出黑客获取到的可成功登录目标服务器FTP的账号密码,并将黑客获…

mysql普通索引与唯一索引怎么选择

学习mysql普通索引与唯一索引选择记录总结&#xff0c;学习链接&#xff1a;http://gk.link/a/11YG8从mysql查询操作分析&#xff1a;普通索引&#xff1a;查到满足条件的第一条记录后&#xff0c;还会继续查找下一条记录&#xff0c;直到出现满足条件的记录出现后停止检索唯一…

经典分类模型回顾5—DenseNet实现图像分类(matlab)

DenseNet&#xff0c;全称为Densely Connected Convolutional Networks&#xff0c;中文名为密集连接卷积网络&#xff0c;是由李沐等人在2017年提出的一种深度神经网络架构。 DenseNet旨在解决深度神经网络中的梯度消失问题和参数数量过多的问题&#xff0c;通过构建密集连接…

滚蛋吧,正则表达式!

大家好&#xff0c;我是良许。 不知道大家有没有被正则表达式支配过的恐惧&#xff1f;看着一行火星文一样的表达式&#xff0c;虽然每一个字符都认识&#xff0c;但放在一起直接就让人蒙圈了~ 你是不是也有这样的操作&#xff0c;比如你需要使用「电子邮箱正则表达式」&…

vue简介与环境搭建

该栏目会非定期出教学视频&#xff0c;文档一般与视频关联&#xff0c;感谢观看。b站搜索博主同名&#xff0c;可观看教学视频。 一、Node.js 什么是node&#xff1f;是一个基于Chrome V8引擎的JavaScript运行环境&#xff0c;使用了一个事件驱动、非阻塞式I/O模型&#xff0c…

时序预测 | MATLAB实现IWOA-BiLSTM和BiLSTM时间序列预测(改进的鲸鱼算法优化双向长短期记忆神经网络)

时序预测 | MATLAB实现IWOA-BiLSTM和BiLSTM时间序列预测(改进的鲸鱼算法优化双向长短期记忆神经网络) 目录时序预测 | MATLAB实现IWOA-BiLSTM和BiLSTM时间序列预测(改进的鲸鱼算法优化双向长短期记忆神经网络)预测效果基本介绍程序设计参考资料预测效果 基本介绍 MATLAB实现IWO…

【算法】DFS与BFS

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法篇 &#x1f43e;题目的模拟很重要&#xff01;&#xff01;&#x1f43e; 文章目录1.区别2.DFS2.1 排列数字2.2 n-皇后问题3.BFS3.1走迷宫1.区别 搜索类型数据结构空间用途过程DFSstackO( n )不能用于最短路搜索到最深处&a…

基于Java的某石材公司货物管理系统的设计与实现

技术&#xff1a;Java、JSP等摘要&#xff1a;随着信息化技术的发展&#xff0c;计算机的应用已迅速扩展到企事业管理与办公自动化领域&#xff0c;而数据库技术也被广泛应用。电脑操作及管理日趋简化&#xff0c;电脑知识日趋普及&#xff0c;同时市场经济快速多变、竞争激烈&…

Spark使用Log4j将日志发送到Kafka

文章目录自定义KafkaAppender修改log4j.properties配置启动命令配置添加参数启动之后可以在Kafka中查询发送数据时区问题-自定义实现JSONLayout解决自定义JSONLayout.java一键应用可能遇到的异常ClassNotFoundException: xxx.KafkaLog4jAppenderUnexpected problem occured dur…

软工2023个人作业二——软件案例分析

项目内容这个作业属于哪个课程2023年北航敏捷软件工程这个作业的要求在哪里个人作业-软件案例分析我在这个课程的目标是学习并掌握现代软件开发和项目管理技术&#xff0c;体验敏捷开发工作流程这个作业在哪个具体方面帮助我实现目标从软件工程角度分析比较我们所熟悉的软件&am…

做程序界中的死神,锻造合适的斩魂刀

标题解读&#xff1a;标题中的死神&#xff0c;是源自《死神》动漫里面的角色&#xff0c;斩魂刀是死神的武器&#xff0c;始解是斩魂刀的初始解放形态&#xff0c;卐解是斩魂刀的觉醒解放形态&#xff0c;也是死神的大招。意旨做程序界中程序员的佼佼者&#xff0c;一步一步最…

实验一 Python编程基础

目录 一、实验目标 二、实验内容 1.绘制如下图形 &#xff0c;一个正方形&#xff0c;内有三个红点&#xff0c;中间红点在正方形中心。 2.使用turtle库绘制如下图形&#xff1a; 3.绘制奥运五环图 4.回文问题 5.身份证性别判别 6.数据压缩 7.验证哥德巴赫猜想 8.使…

【汇编】三、寄存器(一只 Assember 的成长史)

嗨~你好呀&#xff01; 我是一名初二学生&#xff0c;热爱计算机&#xff0c;码龄两年。最近开始学习汇编&#xff0c;希望通过 Blog 的形式记录下自己的学习过程&#xff0c;也和更多人分享。 上篇系列文章链接&#xff1a;【汇编】二、预备知识&#xff08;一只 Assember 的…

react入门篇

react入门篇前言一、目标二、项目环境三、实现过程&#xff08;干货满满&#x1f4a5;&#x1f4a5;&#x1f4a5;&#xff09;1.创建react项目2.arco design UI库3.路由模块化4. 状态管理zustand5. axios6. 路由守卫前言 提示&#xff1a;这里可以添加本文要记录的大概内容&a…

超全的命令(代码)执行漏洞无回显的姿势总结(附带详细代码和测试分析过程)

目录 漏洞代码 突破方式 重定向 dnslog外部通信 burpsuite burpcollaborator外部通信 日志监听 netcat监听 反弹shell的各种姿势 漏洞代码 <?php shell_exec($_GET[a]); ?>这里使用了无回显的shell执行函数shell_exec&#xff0c;给html目录的权限是777 突破方…