C++ vector 模拟实现

vector的底层也是一个动态数组,他与 string 的区别就是,string 是专门用来存储字符类数据的,为了兼容C语言,使用C语言的接口,在string的动态数组内都会都开一块空间用来存 \0  ,而vector则不会。

首先我们要知道的就是,vector是一个类模板,他的内存管理是使用空间配置器,我们就简单点直接使用new和delete来管理内存。其他的一些接口什么的,vector与string差别不大,vector有的string基本都有,实现起来我们也挑一些重点来实现。而对于vector的成员变量,我们则不是采用string的一个指针两个整型的实现,而是使用三个迭代器,_start,_finish,_end_of_storage,这是参考Linux的库的实现,而我们实现vector时迭代器就直接使用的原生的指针。

_start 迭代器是数组的开头,_finish是最后一个数据的下一个位置,_end_of_storage指向的是申请的内存块的下一个位置。

使用三个迭代器的实现,在后续需要挪数据的时候会很方便。

无参构造函数与析构

无参构造不用说,很简单也没什么含量,都初始化为空指针就行了

		vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

完成了无参构造函数之后,我们先去实现其他的一些基本的函数,最后再来解决其他的三个构造

析构函数就是释放_start指向的空间

        //析构~vector(){delete[]_start;_start = _finish = _end_of_storage = nullptr;}

size与capacity和判空

size与capacity的实现其实很简答,我们之前学过数组中同类型指针相减,得到的是这两个指针之间的该类型的数据的个数,于是我们就可以用这三个迭代器来得到size和capacity

	    //sizesize_t size()const{return _finish - _start;}//capacitysize_t capacity()const{return _end_of_storage - _start;}//判空bool empty()const{return _start == _finish;}

方括号的重载与at

vector由于还是动态数组实现的,所以我们还是支持直接是用下标访问的方式,所以方括号重载的实现还是有必要的,方括号重载的越界检查我们直接使用assert暴力检查,库里面实现的就是assert。同时at的功能虽然和方括号一样,但是他和方括号的区别在于 : 1 方括号是运算符重载,而at是普通的成员函数。2 越界的检查不一样,方括号的越界检查使用assert,而at是抛异常,我们可使用vs的库试一下

由于我们还没学习异常。也直接用assert判断就行了。同时,由于有普通对象和const对象的访问,返回的引用的权限不一样,所以我们需要实现两个版本

		//普通对象  [ ]reference operator[](size_t pos){assert(pos < size());return _start[pos];}//const对象 [ ] const_reference operator[](size_t pos)const{assert(pos < size());return _start[pos];}//普通对象 atreference at(size_t pos){assert(pos < size());return _start[pos];}//const对象 atconst_reference at(size_t pos)const{assert(pos < size());return _start[pos];}

对于下标为pos位置的数据的访问,我们可以直接使用 _start[pos]来访问,等价于*(_start+pos)

由于vector也就是普通的数组的比较是没有意义的,所以一般只重载[ ] 和=

swap

为什么要实现swap呢?

首先vector的库里面是有swap的,用于交换两个对象的数据,但是算法库里面也有swap,

他们的区别在于,算法库里的swap有三次拷贝构造,如果要交换的是两个自定义类型的对象,代价很大,而我们的类里面的成员函数swap,我们可以使用算法库的swap对对象里的成员变量进行交换,避免了深拷贝。

//swapvoid swap(rvector<T>& v){//要使用算法库里面的swap要指定命名空间域,否则会优先匹配当前命名空间的swap函数std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}

同时我们实现swap也是为了下面的拷贝构造和赋值重载做准备

赋值重载

vector的赋值重载显然是深拷贝,我们有一种很简洁的代码写法来完成这个深拷贝,就是利用拷贝构造,我们可以传值传参,将我们的this与生成的临时的形参进行交换

而当v2不为空时也是一样的,无非就是将这临时对象与当前对象的空间换了一下,出作用域之后,临时对象指向的空间就被释放了,不会影响外面等号右边的变量。

        //赋值重载vector<T>& operator=(vector<T> v){swap(v);return *this;}

push_back和pop_back

尾插的实现就很简单了,首先检查是否扩容,然后直接在 _finish位置插入数据并且更新 _finish就行了。而尾删的操作则是判断是否为空,然后直接 -- _finish 就行了。

		void push_back(const_reference x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;;++_finish;//insert(beign(),x);//复用insert}void pop_back(){assert(size()>0);--_finish;}

拷贝构造

我们需要考虑当 T 为需要深拷贝的自定义类型这种情况,要做深层次的深拷贝。

如果数据只是内置类型或者只需要浅拷贝的自定义类型的话,我们就只需要memcpy就行了,但是如果是需要深拷贝的数据的话,比如 vector<vector<int>> ,数据类型是 vector<int> ,需要深拷贝,如果只是简单的memcpy

	//如果只是内置类型或者浅拷贝自定义类型//先扩容reserve(v.capacity());//函数内部会修改_end_of_storage//直接内存拷贝memcpy(_start,v._start,v.size()*sizeof(T));_finish = _start + v.size();

我们发现这时候两个对象虽然是不同的空间,但是里面的 vector<int> 数据指向的空间是同一块,这其实还没有达到我们想要的深拷贝。

对于我们来说目前也没有什么更好的解决方法,可以利用上面实现的赋值重载,赋值重载去对每一个数据都深拷贝,

//拷贝构造vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//先扩容reserve(v.capacity());//或者先扩size,再使用赋值重载进行深拷贝_finish = _start + v.size();for (size_t i = 0; i < size(); ++i){_start[i] = v[i];}}

同时,拷贝构造完成之后,不管再多层,他们都有对应的拷贝构造,但是可能有人会对这里的赋值重载产生疑惑,认为赋值重载的前提是实现拷贝构造,而我们这里的拷贝构造又用了赋值重载,会不会递归死循环了,其实是不会的,就比如这里的vector<vector<int>> ,会生成 vector<int> 和vector<vector<int>>的模板,而在vector<vector<int>>中拷贝构造的赋值重载是属于 vector<int>实例出来的赋值重载,而这个赋值重载调用的是 int 的拷贝构造,也就是内置类型的传值调用,所以这里的逻辑是没有问题的,拷贝构造和赋值重载的互相调用会在内置类型(或者浅拷贝的自定义类型)停下来,然后回归。总之就是 赋值重载的深拷贝是调用 T 类型的拷贝构造

reserve

reserve函数与string一样,只会扩容,不会缩容,同时不会改变size。但是扩容之后需要解决将原空间的数据拷贝到新空间的问题,我们可以直接使用指针来进行边界控制。

但是同时,我们也要考虑 数据类型是需要深拷贝的自定义类型的情况,比如 vector<vector<int>> ,如果只是单纯的memcpy,也会造成浅拷贝的问题,也就是原空间的 vector<int>对象与新空间的vector<int>对象指向相同的内存空间,当时放掉原空间之后,新空间指向的内存也被释放掉了。

解决方法还是跟上面的深拷贝一样,使用数据自身的赋值重载来拷贝,虽然效率低了点,但是能确保不会出问题。

迭代器相关

		//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const iterator cbegin(){return _start;}const iterator cend(){return _finish;}

insert和erase

		iterator insert(iterator pos, const_reference x=val_type())//缺省值{//检查越界assert(pos >= _start);assert(pos <= _finish);//第一次插入pos==_finish  同时要支持尾插//检查是否扩容if (_finish == _end_of_storage){//扩容之后pos就失效了,所以要记录pos的相对位置size_t pos_index = pos - _start;size_t newcapacity = (capacity() == 0 ? 4 : 2 * capacity());reserve(newcapacity);//更新pospos = _start + pos_index;}//挪动数据 从后往前,往后挪数据iterator end = _finish;while (end != pos){*end = *(end - 1);--end;}//更新_finish++_finish;//插入新数据*pos = x;//返回插入的数据的迭代器return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);//挪数据覆盖iterator begin = pos+1;while (begin < _finish){*(begin - 1) = *begin;begin++;}//返回删除的下一个数据return pos;}

insert和erase都要注意迭代器失效的问题,比如insert的时候,如果扩容了,那么传过来的pos指向的空间就可能已经被释放了,所以要更新pos指向新空间的该元素的位置,同时,正常来说insert之后,函数外面的pos就不能用了,因为我们是传值的,函数内更新了pos不会影响函数外的pos,这时候如果我们要更新函数外面的pos,可以insert返回心得pos的值。  erase也是一样的,因为erase可能是删除最后一个数据,这时候pos的位置就是_finish 了,虽然pos没有出我们开辟的内存空间,但是在我们看来,它指向finish就已经算是越界了,不能继续使用,同样,要在函数外面更新pos也是用erase的返回值更新。

resize

		//resizevoid resize(size_t n, val_type x = val_type())//缺省参数{//扩容检查if (n > capacity()){reserve(n);}//是否需要加数据if (n > size()){while (_finish < _start + n){*_finish=x;++_finish;}}}

剩下的两个构造函数

一个是迭代器区间来构造初始化。为什么这里的构造函数是模板呢? 因为我们可能不是使用vector<T>的数据结构来初始化我们的对象,也可能是用其他的数据结构比如链表等的数据来初始化vector,这也是可以的,只要传迭代器区间就可以

		template<typename InputIterator>vector(InputIterator begin, InputIterator end){//push_back就行了while (begin != end){push_back(*begin);++begin;}}

还有n个val初始化,这里我们需要注意的是,我们不能做到跟库里一样,n的参数类型要用int,为什么呢? 

		//n个val初始化vector(int n, T val){for (int i = 0; i < n; ++i){push_back(val);}}

比如我们可以这样构造 vector<int> v(10,5) 这时候,如果我们的n的类型是size_t 的话,由于编译器会把 10 和5 识别为 int 类型,这时候传给构造函数的两个参数都是 int ,如果去匹配这个构造函数的话, n 还需要进行整型提升。而如果去匹配上面的迭代器区间的模板,因为模板的只有一个参数类型,两个迭代器区域间都是一样的类型,所以不用进行隐式类型转换,因此他与迭代器区间的构造函数更加匹配,编译器就会去调用迭代器区间的构造函数,这时候就会出问题。 有两种解决方法,一种就是我们上面写的,但是这样做就与库不一致了 。另外一种就是我们不要使用原生的指针作为迭代器的类型,这种方法我们目前还不会用

完整代码


namespace MY_vector
{template<typename T>class vector{public:typedef T val_type;typedef T& reference;typedef const T& const_reference;typedef T* iterator;//无参构造vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//析构~vector(){delete[] _start;_start = _finish = _end_of_storage=nullptr;}//sizesize_t size()const{return _finish - _start;}//capacitysize_t capacity()const{return _end_of_storage-_start;}//emptybool empty()const{return _start == _finish;}//尾插void push_back(val_type x){ /*//检查扩容if (_finish== _finish){size_t newcapacity = (capacity() == 0 ? 4 : 2 * capacity());reserve(newcapacity);}//插入数据*_finish = x;++_finish;*/insert(begin(), x);}//尾删void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos, const_reference x=val_type())//缺省值{//检查越界assert(pos >= _start);assert(pos <= _finish);//第一次插入pos==_finish  同时要支持尾插//检查是否扩容if (_finish == _end_of_storage){//扩容之后pos就失效了,所以要记录pos的相对位置size_t pos_index = pos - _start;size_t newcapacity = (capacity() == 0 ? 4 : 2 * capacity());reserve(newcapacity);//更新pospos = _start + pos_index;}//挪动数据 从后往前,往后挪数据iterator end = _finish;while (end != pos){*end = *(end - 1);--end;}//更新_finish++_finish;//插入新数据*pos = x;//返回插入的数据的迭代器return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);//挪数据覆盖iterator begin = pos+1;while (begin < _finish){*(begin - 1) = *begin;begin++;}//返回删除的下一个数据return pos;}//[ ] 重载reference operator[](size_t pos){assert(pos < size());return _start[pos];}const_reference operator[](size_t pos)const{assert(pos < size());return _start[pos];}//atreference at(size_t pos){assert(pos<size());return _start[pos];}const_reference at(size_t pos)const{assert(pos < size());return _start[pos];}//swapvoid swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//= 重载vector<T>& operator=(vector<T> v){swap(v);return *this;}//扩容 reservevoid reserve(size_t n){if (n > capacity()){iterator tmp = new val_type[n];//记录原来的数据个数,用来更新_finishsize_t oldsize = size();//判断是否需要挪数据if(_start) //_start!=nullptr{for (size_t i = 0; i < oldsize; ++i){tmp[i] = _start[i];}//释放原空间 delete[]_start;}//更新迭代器_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}}//拷贝构造vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//先扩容reserve(v.capacity());//或者先扩size,再使用赋值重载进行深拷贝_finish = _start + v.size();for (size_t i = 0; i < size(); ++i){_start[i] = v[i];}}//resizevoid resize(size_t n, val_type x = val_type())//缺省参数{//扩容检查if (n > capacity()){reserve(n);}//是否需要加数据if (n > size()){while (_finish < _start + n){*_finish=x;++_finish;}}}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const iterator cbegin(){return _start;}const iterator cend(){return _finish;}template<typename InputIterator>vector(InputIterator begin, InputIterator end){//push_back就行了while (begin != end){push_back(*begin);++begin;}}//n个val初始化vector(int n, T val){for (int i = 0; i < n; ++i){push_back(val);}}private:iterator _start;iterator _finish;iterator _end_of_storage;};//测试一维void test1(){vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2(v1);vector<int>v3;v3.resize(8);v3 = v1;v3.reserve(10);v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();//v2.pop_back();//v2.pop_back();//v2.pop_back();v3.insert(v3.begin(), 6);v3.insert(v3.begin(), 6);v3.insert(v3.end()-1, 6);v3.insert(v3.end() - 1, 6);v3.insert(v3.end(), 6);v3.insert(v3.end(), 6);for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}cout << endl;for (auto e : v3){cout << e << " ";}cout << endl;}//测试二维void test2(){vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<vector<int>> vv1;vv1.push_back(v);vv1.push_back(v);vv1.push_back(v);vv1.push_back(v);vv1.push_back(v);vector<vector<int>> vv2(vv1);vv2.pop_back();vv2.pop_back();vector<vector<int>> vv3;vv3.resize(2);vv3.reserve(6);vv3.push_back(v);vv3.push_back(v);vv3 = vv1;vv3.push_back(v);vv3.push_back(v);cout << "vv1" << endl;for (auto ev : vv1){for (auto e : ev){cout << e << " ";}cout << endl;}cout << "vv2" << endl;for (auto ev : vv2){for (auto e : ev){cout << e << " ";}cout << endl;}cout << "vv3" << endl;for (auto ev : vv3){for (auto e : ev){cout << e << " ";}cout << endl;}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/336605.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】TCP协议【上】{协议段属性:源端口号/目的端口号/序号/确认序号/窗口大小/紧急指针/标记位}

文章目录 1.引入2.协议段格式4位首部长度16位窗口大小32位序号思考三个问题【demo】标记位URG: 紧急指针是否有效提升某报文被处理优先级【0表示不设置1表示设置】ACK: 确认号是否有效PSH: 提示接收端应用程序立刻从TCP缓冲区把数据读走RST: 对方要求重新建立连接; 我们把携带R…

《QT实用小工具·六十八》基于QMenu开发的炫酷菜单栏

1、概述 源码放在文章末尾 该项目基于QMenu实现了炫酷的菜单栏效果&#xff0c;包含了如下功能&#xff1a; 1、实现了类似word菜单栏的效果&#xff0c;可以在菜单栏中横向添加不同的菜单 2、鼠标点击菜单可以展开菜单栏&#xff0c;再次点击菜单可以收起菜单栏 3、鼠标点击笑…

C++ wasm 使用教程

环境搭建 git clone https://github.com/emscripten-core/emsdk.gitgit pull./emsdk install latest./emsdk activate latestsource ./emsdk_env.sh./emcc -v && ./emcc c11__Thread_local.c -s WASM_WORKERS --threadprofiler --memoryprofiler -v -o test.html &…

鸿蒙OS开发:【一次开发,多端部署】(分栏控件)

一多分栏控件 介绍 本示例分别展示了多场景下&#xff0c;一多分栏控件的响应式变化效果。 本示例分别用到了[SideBarContainer]组件与[Navigation]组件&#xff0c;对应使用场景如下&#xff1a; ABC&#xff1a;即SideBarContainer组件组合Navigation组件AC&#xff1a;S…

AI企业需要“联盟营销”?一文带你探索AI企业营销新玩法!

为什么联盟营销对AI业务有较大优势 联盟营销在电商领域、saas领域与其他产品领域同样有效。在AI业务中&#xff0c;它有效的原因与其他领域大不相同。 高好奇心和试用率 AI领域是创新的热点。它吸引了一群渴望探索和尝试每一项新技术的人群。这种蓬勃的好奇心为聪明的AI企业提…

Linux 编译器gcc/g++使用

gcc/g同理 编译器运行过程 1. 预处理&#xff08;进行宏替换) gcc -E a.c -o a.i 预处理后还是c语言 -E 只激活预处理,这个不生成文件,你需要把它重定向到一个输出文件里面 告诉gcc&#xff0c;从现在开始进行程序的翻译&#xff0c;将预处理工作做完停下 2. 编译&#x…

【因果推断python】2_因果关系初步2

目录 偏差 关键思想 偏差 偏差是使关联不同于因果关系的原因。幸运的是&#xff0c;我们的直觉很容易理解。让我们在课堂示例中回顾一下我们的平板电脑。当面对声称为孩子提供平板电脑的学校会获得更高考试成绩的说法时&#xff0c;我们可以反驳说&#xff0c;即使没有平板电…

新疆 | 金石商砼效率革命背后的逻辑

走进标杆企业&#xff0c;感受名企力量&#xff0c;探寻学习优秀企业领先之道。 本期要跟砼行们推介的标杆企业是新疆砼行业的龙头企业&#xff1a;新疆兵团建工金石商品混凝土有限责任公司&#xff08;以下简称&#xff1a;新疆金石&#xff09;。 从年产80万方到120万方&am…

Go 和 Delphi 定义可变参数函数的对比

使用可变参数函数具有灵活性、重用性、简化调用等优点&#xff0c;各个语言有各自定义可变参数函数的方法&#xff0c;也有通用的处理方法&#xff0c;比如使用数组、定义参数结构体、使用泛型等。 这里总结记录一下 go、delphi 的常用的定义可变参数函数的方式&#xff01; 一…

数据挖掘与机器学习——回归分析

目录 回归分析定义&#xff1a; 案例&#xff1a; 线性回归 预备知识&#xff1a; 定义&#xff1a; 一元线性回归&#xff1a; 如何找出最佳的一元线性回归模型&#xff1a; 案例&#xff1a; python实现&#xff1a; 多元线性回归 案例&#xff1a; 线性回归的优缺点…

基于xilinx FPGA的 FFT IP使用例程说明文档(可动态配置FFT点数,可计算信号频率与幅度)

目录 1 概述2 IP examples功能3 IP 使用例程3.1 IP设置3.2 fft_demo端口3.3 例程框图3.4 仿真结果3.5 仿真验证得出的结论4 注意事项5例程位置 1 概述 本文用于讲解xilinx IP 的FFT ip examples的功能说明&#xff0c;方便使用者快速上手。 参考文档&#xff1a;《PG109》 2 …

如何配置才能连接远程服务器上的 redis server ?

文章目录 Intro修改点 Intro 以阿里云服为例。 首先&#xff0c;我在我买的阿里云服务器中以下载源码、手动编译的方式安装了 redis-server&#xff0c;操作流程见&#xff1a;Ubuntu redis 下载解压配置使用及密码管理 && 包管理工具联网安装。 接着&#xff0c;我…

Atlas 血缘分析-hive/spark

Apache Atlas部署安装 这里需要注意&#xff0c;需要从官网下载Atlas的源码&#xff0c;不要从git上分支去checkout&#xff0c;因为从分支checkout出来的代码&#xff0c;无法正常运行&#xff0c;这里小编使用针对Atlas-2.3.0源码进行编译. mvn clean -DskipTests package …

2024 京麟ctf -MazeCodeV1

文章目录 检查代码思路一个字节的指令注意附上S1uM4i佬们的exp https://www.ctfiot.com/184181.html 检查 代码 __int64 __fastcall check_solve(char *a1) {__int64 result; // rax__int64 v2; // rax__int64 index_step; // rax__int64 v4; // rax__int64 v5; // rax__int64…

MySQL索引与事务

1. 索引 &#xff08;1&#xff09;概念 索引是一种特殊的文件&#xff0c;包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引&#xff0c; 并指定索引的类型&#xff0c;各类索引有各自的数据结构实现。 &#xff08;2&#xff09;利弊 利&#xff1a; 数…

基于51单片机的温湿度控制系统

一.硬件方案 本设计采用51单片机每2秒钟从DHT11温湿度传感器中读入温度和湿度&#xff0c;在液晶屏上即时显示。液晶屏上同时显示温湿度上限值&#xff0c;该上限值保存外外部EEPROM存储器中&#xff0c;掉电不失&#xff0c;并且可以通过四只按键上调或下调。当温度或湿度值超…

车机壁纸生成解决方案,定制化服务,满足个性化需求

在数字化与智能化浪潮的推动下&#xff0c;汽车内部设计已不再仅仅满足于基本功能的需求&#xff0c;更追求为用户带来前所未有的视觉享受与沉浸式体验。美摄科技&#xff0c;凭借其在图像生成与处理领域的深厚积累&#xff0c;推出了一款创新的车机壁纸生成解决方案&#xff0…

LORA微调,让大模型更平易近人

技术背景 最近和大模型一起爆火的&#xff0c;还有大模型的微调方法。 这类方法只用很少的数据&#xff0c;就能让大模型在原本表现没那么好的下游任务中“脱颖而出”&#xff0c;成为这个任务的专家。 而其中最火的大模型微调方法&#xff0c;又要属LoRA。 增加数据量和模…

VMware ESXi 7.0 U3q 发布 - 领先的裸机 Hypervisor

VMware ESXi 7.0 U3q 发布 - 领先的裸机 Hypervisor VMware ESXi 7.0 Update 3 Standard & All Custom Image for ESXi 7.0U3 Install CD 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-esxi-7-u3/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出…

[pdf,epub]《软件方法》2024版电子书共290页(202405更新)

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 已上传本账号CSDN资源。 或者到以下链接下载&#xff1a; http://www.umlchina.com/url/softmeth2024.html&#xff0c;或点击“阅读原文”。 如果需要提取码&#xff1a;umlc 已排…