【c++丨STL】vector模拟实现

🌟🌟作者主页:ephemerals__
🌟🌟所属专栏:C++、STL

目录

前言

一、vector底层刨析

二、模拟实现

1. 属性、迭代器以及函数声明

2. 功能实现

交换两个容器的内容

构造函数

拷贝构造

赋值重载

析构函数 

下标引用operator[ ]

容量接口

迭代器接口

判空

resize

reserve

插入和删除

insert和push_back

erase和pop_back

3. 程序全部代码

总结


前言

        之前我们学习了vector的常用接口及其使用方法:

【c++丨STL】vector的使用-CSDN博客

本篇文章,我们将深入探讨vector的底层实现原理,并尝试模拟实现其结构以及一些常用接口。 

一、vector底层刨析

        之前已经提到,vector的底层是动态顺序表,我们使用c语言实现顺序表的结构时赋予了它三个成员变量:

typedef int SLDataType;//动态顺序表
typedef struct SeqList
{SLDataType* arr;//定义起始指针,后续动态开辟内存空间int size;//有效数据的个数int capacity;//数组的空间大小
}SL;

可以看到,我们定义了一个起始指针指向分配的内存,然后用size和capacity两个变量分别记录元素个数和空间容量。接下来,我们再看看SGI版本的STL源码:

为了提高程序的兼容性和灵活性,源码并没有使用size和capacity等属性,而是使用了三个迭代器(指针)来维护数组。这三个迭代器分别指向数组的不同位置:

start:指向首元素

finish:指向末尾元素的“后一位”

end_of_storage:指向可用空间的末尾

图示:

那么,接下来我们在模拟实现vector时,将仿照SGI版本的做法,通过定义相应的成员变量(即三个迭代器)来构建其内部结构

        另外,由于vector本质上是一个类模板允许我们存储任意类型的数据元素,因此在接下来模拟实现vector的过程中,我们也将采用类模板来进行定义。由于类模板成员函数的定义和声明分离到两个文件会造成链接错误,我们选择在头文件中同时完成这些成员函数的声明与定义

二、模拟实现

1. 属性、迭代器以及函数声明

        首先是属性、迭代器的声明以及我们需要实现的接口:

#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;template<class T>
class Vector
{
public://vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;//迭代器接口iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;//无参构造Vector();//初始化器构造Vector(initializer_list<T> l);//迭代器区间构造template<class InputIterator>Vector(InputIterator first, InputIterator last);//n个val值构造Vector(size_t n, const T& val = T());//拷贝构造Vector(const Vector<T>& v);//赋值重载Vector<T>& operator=(Vector<T> v);//析构~Vector();//下标引用T& operator[](size_t i);const T& operator[](size_t i) const;//容量接口size_t size() const;size_t capacity() const;//判空bool empty() const;//交换void swap(Vector<T>& tmp);//调整大小void resize(size_t n, const T& val = T());//增容void reserve(size_t n);//插入和删除void push_back(const T& x);void pop_back();iterator insert(iterator pos, const T& x);iterator erase(iterator pos);
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
};

      由于vector和string的数据元素都是采用顺序存储的方式,它们在功能实现上存在相似之处。因此,建议先阅读string模拟实现之后,再来阅读本文,否则其中的一些实现过程可能会较难理解。

2. 功能实现

        接下来,我们将正式开始实现上述接口的功能。

交换两个容器的内容

        与之前实现string时相同,直接交换它们的成员变量就可以完成数据的交换,无需重新开辟空间。

代码实现:

//交换
void swap(Vector<T>& tmp)
{std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);
}

构造函数

        这里我们实现了四个构造函数的重载:分别是:无参构造、初始化器构造、迭代器区间构造和n个val值构造

//无参构造
Vector()
{}
//初始化器构造
Vector(initializer_list<T> l)
{reserve(l.size());for (auto& e : l){push_back(e);}
}
//迭代器区间构造
template<class InputIterator>
Vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}
//n个val值构造
Vector(size_t n, const T& val = T())
{reverse(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

不难发现,由于我们在成员变量声明时已经赋初值,所以无参构造中什么都不用做。这样无参构造也可以写成如下形式:

Vector() = default;//强制生成无参构造

我们显示写了构造函数后,编译器就不会默认生成无参构造函数。我们用这条语句就可以强制让编译器生成一个无参的构造函数

        其余的构造函数都是通过遍历来访问每个元素,并将它们依次尾插到数组中的。push_back、reverse等函数我们之后实现。这里特别注意一下n个val值构造函数,如果我们不传val参数,则会调用T类型的默认构造函数,生成一个匿名对象并赋值给val。

拷贝构造

        与初始化器构造的原理相似,我们遍历被拷贝数组的每个元素,并将它们逐一尾插到当前数组中。

//拷贝构造
Vector(const Vector<T>& v)
{reverse(v.capacity());for (auto& e : v){push_back(e);}
}

赋值重载

        这里我们使用新式写法(string使用过),构造新对象然后交换,完成赋值操作。

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

析构函数 

//析构
~Vector()
{if (_start)//避免多次释放{delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}

下标引用operator[ ]

        下标引用重载可以让我们像访问数组元素一样访问容器内容。

//下标引用
T& operator[](size_t i)
{assert(i < size());//防止越界return _start[i];
}
const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

容量接口

        使用指针减指针的方式来实现容量接口size和capacity功能。

//容量接口
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}

迭代器接口

        由于string和vector底层都是顺序存储,所以它们的迭代器相对简单,都是直接使用指针实现。之后我们学习list(链表)时,就会接触到更加复杂的迭代器实现。

//迭代器接口
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

判空

        当start与finish指向同一处时,容器即为空。 

//判空
bool empty() const
{return _start == _finish;
}

resize

        如果参数n的值小于当前size,则该函数会将size调整为n值,并且删除超出的元素。

        如果参数n的值大于当前size,则会在末尾插入元素至size等于n值。

//调整大小
void resize(size_t n, const T& val = T())
{if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}
}

reserve

        reserve的实现原理与string相似,当参数n值大于当前容量时,我们才会进行增容操作。这里需要注意:由于容量大小由三个迭代器控制,所以我们重新开辟空间之前需要记录原来的size,便于确定增容之后三个迭代器指向的位置

//增容
void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();//记录原来的sizeT* tmp = new T[n];if (_start)//如果start是空,说明数组为空,不拷贝数据{for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}

插入和删除

insert和push_back

        insert和push_back负责插入操作。这里需要注意:insert实现时的迭代器失效问题。 

什么是迭代器失效呢?简单的讲,由于vector是使用三个迭代器来维护的,那么如果它们指向的空间被释放,那么就会出现野指针的情况,这三个迭代器的相关操作就是无效的,这就是迭代器失效。迭代器失效的本质就是你管理的内存已经不属于你了

insert出现迭代器失效的原因:很简单,我们在插入数据时,如果空间已满就会增容,此时分配新的空间,然后把内容拷贝过去并释放旧空间。原本我们传入的参数pos(指定的插入位置)是一个指向旧空间的迭代器旧空间被释放后,该迭代器就会失效,从而无法插入数据

解决办法 记录迭代器pos与start的相对距离,当增容完成之后,根据相对距离更新pos即可

        为什么string在进行插入的时候不会发生迭代器失效呢?因为参数pos本身是一个整形,代表要插入的下标,只要该下标不越界,就不会出现失效的情况。当然,这只是插入时不会,并不是一定不会。如果你在外部定义了一个迭代器,当字符串空间被释放后,该迭代器也会失效。此时我们对迭代器重新赋值即可。

接下来我们实现insert和push_back的代码:

iterator insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= finish);//确保插入位置合法if (_finish == _end_of_storage)//空间已满,增容{size_t len = pos - _start;//记录相对位置reserve(capcaity() == 0 ? 4 : 2 * capacity());//增容pos = _start + len;//更新pos}iterator i = _finish - 1;while (i >= pos)//pos之后元素全体向后移动一位{*(i + 1) = *i;i--;}*pos = x;_finish++;return pos;//返回指向新元素的迭代器
}
void push_back(const T& x)
{insert(_finish, x);//直接调用insert
}
erase和pop_back

        erase和pop_back负责删除操作。与insert相同,erase也会发生迭代器失效的问题。但是erase不会造成空间容量的改变,理论上是不会使迭代器失效的。不过,如果有一个迭代器指向末尾元素,删除数据之后,finish前移,该迭代器指向的数据就是非法的,就会造成迭代器失效。所以删除vector的任意元素后,vs编译器就会认为指向该元素的迭代器失效,无法继续使用

        对于这种问题的解决方法也很简单:如果我们只是删除一次数据,迭代器失效也没关系;如果要连续删除,则需要更新迭代器。对此,我们在erase函数中删除元素后,将指向该元素位置的迭代器作为返回值,函数外部需要使用该返回值更新迭代器

erase和pop_back代码实现:

iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);//确保删除位置合法auto i = pos + 1;while (i < _finish)//pos之后元素全体前移一位{*(i - 1) = *i;i--;}_finish--;return pos;//返回删除位置迭代器
}
void pop_back()
{assert(!empty());//防止空删_finish--;
}

3. 程序全部代码

模拟实现vector的全部代码如下:

#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;template<class T>
class Vector
{
public://vector的迭代器是一个原生指针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;}//无参构造Vector(){}//初始化器构造Vector(initializer_list<T> l){reserve(l.size());for (auto& e : l){push_back(e);}}//迭代器区间构造template<class InputIterator>Vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}//n个val值构造Vector(size_t n, const T& val = T()){reverse(n);for (size_t i = 0; i < n; i++){push_back(val);}}//拷贝构造Vector(const Vector<T>& v){reverse(v.capacity());for (auto& e : v){push_back(e);}}//赋值重载Vector<T>& operator=(Vector<T> v){swap(v);return *this;}//析构~Vector(){if (_start)//避免多次释放{delete[] _start;_start = _finish = _end_of_storage = nullptr;}}//下标引用T& operator[](size_t i){assert(i < size());//防止越界return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}//容量接口size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}//判空bool empty() const{return _start == _finish;}//交换void swap(Vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}//调整大小void resize(size_t n, const T& val = T()){if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}}//增容void reserve(size_t n){if (n > capacity()){size_t old_size = size();//记录原来的sizeT* tmp = new T[n];if (_start)//如果start是空,说明数组为空,不拷贝数据{for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}//插入和删除void push_back(const T& x){insert(_finish, x);//直接调用insert}void pop_back(){assert(!empty());//防止空删_finish--;}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= finish);//确保插入位置合法if (_finish == _end_of_storage)//空间已满,增容{size_t len = pos - _start;//记录相对位置reserve(capcaity() == 0 ? 4 : 2 * capacity());//增容pos = _start + len;//更新pos}iterator i = _finish - 1;while (i >= pos)//pos之后元素全体向后移动一位{*(i + 1) = *i;i--;}*pos = x;_finish++;return pos;//返回指向新元素的迭代器}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);//确保删除位置合法auto i = pos + 1;while (i < _finish)//pos之后元素全体前移一位{*(i - 1) = *i;i--;}_finish--;return pos;//返回删除位置迭代器}
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
};

总结

        本篇文章,我们深入了解了vector的底层原理,并成功地模拟实现了它。与传统的动态顺序表不同,它采用了三个迭代器来维护数组,提高了程序灵活性。也正因如此,它的实现难度也有所增大,对于细节把控的要求也很高。之后博主会带领大家学习一个新容器--list。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤

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

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

相关文章

C++中类的默认成员函数

默认成员函数 1.构造函数2.析构函数3.拷贝构造函数4.赋值运算符重载4.1运算符重载4.2赋值运算符重载 #mermaid-svg-oipiwg9stvONvYK0 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-oipiwg9stvONvYK0 .error-icon{f…

数据编排与ETL有什么关系?

数据编排作为近期比较有热度的一个话题&#xff0c;讨论度比较高&#xff0c;同时数据编排的出现也暗示着数字化进程的自动化发展。在谈及数据编排时&#xff0c;通常也会谈到ETL&#xff0c;这两个东西有相似点也有不同点。 数据编排和ETL&#xff08;提取、转换、加载&#x…

【SpringCloud】SpringBoot集成Swagger 常用Swagger注解

概述&#xff1a;SpringBoot集成Swagger 常用Swagger注解 导语 相信无论是前端还是后端开发&#xff0c;都或多或少地被接口文档折磨过。前端经常抱怨后端给的接口文档与实际情况不一致。后端又觉得编写及维护接口文档会耗费不少精力&#xff0c;经常来不及更新。其实无论是前…

革命性AI搜索引擎!ChatGPT最新功能发布,无广告更智能!

文章目录 零、前言一、ChatGPT最新AI搜索引擎功能操作指导实战1:搜索新闻实战2:搜索天气实战3:搜索体育消息 二、感受 零、前言 大人&#xff0c;时代变了。 最强 AI 助力下的无广告搜索引擎终于问世。我们期待已久的这一刻终于到来了&#xff0c;从今天起&#xff0c;ChatGPT…

基于 CMSIS-PACK 移植Bootloader

基于 CMSIS-PACK 移植 1.准备工作 准备一份基础的裸机源码 (可通过 STM32CubeMx 可视化软件创建也可按照工程项目所需文档手动创建) 工程&#xff0c;如一份 stm32 包含一个支持 printf 的串口初始化代码。 2.安装Pack包 在 MDK 中部署 **MicroBoot **的第一步是获取对应的…

苍穹外卖day09超出配送范围前端不提示问题

同学们在写苍穹外卖项目day09时调用了百度地图api来判断用户地址是否超出配送范围&#xff0c; 但是在黑马官方的课程或资料中&#xff0c;出现这样的问题时只会向用户端的控制台报错并不会提醒用户 如下图&#xff1a; 解决方法&#xff1a; 其实解决方法很简单只需要找到向…

嵌入式linux中PWM控制与实现

大家好,今天主要给大家分享一下,如何使用linux系统里面的PWM的功能,可以控制对应电机的转速。 第一:PWM驱动基本简介 PWM就是脉冲宽度调制。 PWM信号有两个关键术语:频率和占空比,频率指的是开关的速度。占空比就是一个周期内高电平和低电平时间的比例,一个周期内高电…

CUDA系统学习之一软件堆栈架构

一、CPU与GPU体系架构 计算单元分布 CPU: 少量强大的ALU(算术逻辑单元)&#xff0c;通常4-8个核心GPU: 大量小型ALU&#xff0c;成百上千个计算核心特点&#xff1a;GPU更适合并行计算&#xff0c;可以同时处理大量数据控制单元(Control) CPU: 较大的控制单元&#xff0c;复杂的…

「QT」几何数据类 之 QPoint 整型点类

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「QT」QT5程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasolid…

0x00基础算法 -- 0x01 位运算

资料来源&#xff1a;算法竞赛进阶指南活动 - AcWing 1、进制表示 二进制表示&#xff1a;m位二进制中&#xff0c;通常称最低位为第0位&#xff0c;从右到左以此类推&#xff0c;最高位为第m-1位。 常用十六进制表示的数字&#xff1a; 32位补码int&#xff08;十进制&#xf…

H5移动端预览PDF方法

新建页面 新建一个页面以便去预览对应的pdf 新建完后在 pages.json 文件内去新增对应路由 页面内容 <template><view class"page"><view class"pdf"><view id"demo"></view></view><view class"b…

嵌入式开发之线程

进程 vs 线程 进程在切换时系统开销大很多操作系统引入了轻量级进程LWP同一进程中的线程共享相同地址空间Linux不区分进程、线程(都会创建:task_strcut)线程特点: 通常线程指的是共享相同的地址空间的多个任务,使用多线程的好处 大大提高了任务切换的效率避免了额外的TLB…

【SQL实验】更新操作

完整代码在文章末尾【代码是自己的解答&#xff0c;并非标准答案&#xff0c;也有可能写错&#xff0c;文中可能会有不准确或待完善之处&#xff0c;恳请各位读者不吝批评指正&#xff0c;共同促进学习交流】 将素材“图书管理”文件下载到本地&#xff0c;并将其还原到SQL SER…

Hadoop(HDFS)

Hadoop是一个开源的分布式系统架构&#xff0c;旨在解决海量数据的存储和计算问题&#xff0c;Hadoop的核心组件包括Hadoop分布式文件系统&#xff08;HDFS&#xff09;、MapReduce编程模型和YARN资源管理器,最近需求需要用到HDFS和YARN。 文章目录 HDFS优缺点HDFS的读写原理 常…

Spire.PDF for .NET【页面设置】演示:获取 PDF 文件中的页数

计算 PDF 文件中的页数对于各种目的都至关重要&#xff0c;例如确定文档长度、组织内容和评估打印要求。除了使用 PDF 查看器了解页数信息外&#xff0c;您还可以通过编程自动执行该任务。在本文中&#xff0c;您将学习如何使用C#通过Spire.PDF for .NET获取 PDF 文件中的页数。…

stm32不小心把SWD和JTAG都给关了,程序下载不进去,怎么办?

因为想用STM32F103的PA15引脚&#xff0c;调试程序的时候不小心把SWD和JTAD接口都给关了&#xff0c;先看下罪魁祸首 GPIO_PinRemapConfig(GPIO_Remap_SWJ_JTAGDisable,ENABLE);//关掉JTAG&#xff0c;不关SWGPIO_PinRemapConfig(GPIO_Remap_SWJ_Disable, ENABLE);//关掉SW&am…

vue3使用element-plus,树组件el-tree增加引导线

vue3使用element-plus&#xff0c;树组件el-tree增加引导线 vue3项目element-plus&#xff0c;树组件el-tree增加引导线 element-plus组件库的el-tree样式 因为element的样式不满足当前的的需求&#xff0c;UI图&#xff0c;所以对el-tree进行增加了引导线 修改样式如下&am…

pytest简单使用

一&#xff1a;Mark 1.注册标记 在项目根目录下创建固定名为 pytest.ini 的配置文件&#xff0c;文件格式需要加上 [pytest] &#xff0c;然后通过 markers 注册自定义标记 2.贴上标记 通过pytest加上装饰器&#xff0c;然后pytest.mark.XX配置自定义的标记&#xff0c;一个…

【C++】——多态

一.多态的概念 1.多态 多态(polymorphism)的概念&#xff1a;通俗的来说&#xff0c;就是多种形态。多态分为静态多态(编译时多态)和动态多态(运行时多态)&#xff0c;而我们讲的多态大部分都是动态多态。 静态多态主要就是我们前面了解过的函数模板和函数重载&#xff0c;它…

Linux基础4-进程4(环境变量,命令行参数详解)

上篇文章:Linux基础4-进程3(进程优先级&#xff0c;竞争&#xff0c;独立&#xff0c;并行&#xff0c;并发&#xff0c;进程切换)-CSDN博客 本章重点: Linux中环境变量的理解和使用 目录 一. 环境变量概念和查看环境变量 1.1 环境变量概念 1.2 查看环境变量 二. 获取环境变…