【C++】vector模拟实现、迭代器失效问题(超详解)

        vector会使用之后我们来模拟实现一下,通过对vector的模拟实现,我们来说一下迭代器失效问题。

 1.准备工作

在头文件vector.h里声明和实现函数,然后在test.cpp里测试代码的正确性。

vector.h用命名空间分隔一下,因为c++库里面也有vector,避免冲突。vector.h里面写一些会用到的头文件,vector的成员变量类型都是T*,为了和vector源码保持一致,我们也把T*换个名字,换成iterator,然后定义成员变量。

namespace lyj
{template<class T> class vector{public:typedef T* iterator;private:iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; };
}

2.size、capacity、reserve

全都在vector.hvector类里面声明和实现,目前不做声明和定义分离。

size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
void reserve(size_t n)
{if (n > capacity()) //n大于capacity扩容{T* t = new T[n];//开辟新空间memcpy(t, _start, size * sizeof(T));//拷贝旧空间的数据到新空间delet[] _start; //释放旧空间_start = t; //指向新空间_finish = _start + size();//更新数据_end_of_storage = _start + n;//更新数据}//其他不变
}

3.operator[]、push_back、pop_back、empty

全都在vector.hvector类里面声明和实现,目前不做声明和定义分离。

//普通版本
T& operator[](size_t i)
{assert(i < size());return _start[i];
}
//const版本
const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}
//尾插
void push_back(const T& x)
{if (_finish == _end_of_storage)//空间不够{reserve(capacity() == 0 ? 4 : capacity() * 2);//2倍扩}*_finish = x;++_finish;
}
//判空
bool empty() const
{return _start == _finish;
}
//尾删
void pop_back()
{assert(!empty());--_finish;
}

test.cpp中对前面的所有代码进行测试。

#include "vector.h"
namespace lyj
{void test1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;}
}int main()
{lyj::test1();return 0;
}

运行发现程序崩溃了。

因为我们前面的reserve逻辑有问题。

 所以_finish 不是我们想要的值。

解决方法1:先更新_finish

void reserve(size_t n)
{if (n > capacity()) //n大于capacity扩容{T* t = new T[n];//开辟新空间memcpy(t, _start, size() * sizeof(T));//拷贝旧空间的数据到新空间delete[] _start; //释放旧空间_finish = t + size();//先更新_finish的数据_start = t; //再指向新空间_end_of_storage = _start + n;//更新数据}//其他不变
}

解决方法2:用old_size存值。 

void reserve(size_t n)
{if (n > capacity()) //n大于capacity扩容{size_t old_size = size();//存值T* t = new T[n];//开辟新空间memcpy(t, _start, size() * sizeof(T));//拷贝旧空间的数据到新空间delete[] _start; //释放旧空间_start = t; //指向新空间_finish = t + old_size;//用old_size更新数据_end_of_storage = _start + n;//更新数据}//其他不变
}

再运行代码,就可以通过了。

4.迭代器和范围for

4.1 普通正向迭代器

全都在vector.hvector类里面声明和实现,目前不做声明和定义分离。

iterator begin()
{return _start;
}
iterator end()
{return _finish;
}

test.cpp中进行测试。

void test1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}
}

4.2 普通范围for

支持迭代器就支持了范围for

for (auto e : v)
{cout << e << " ";
}
cout << endl;

 

4.3 const迭代器

const迭代器就要用const的iterator,所以我们typedef一个const_iterator,原类型是const T*

typedef const T* const_iterator;

const迭代器的实现就是把普通正向迭代器返回值类型换一下。

const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

当迭代器换成const迭代器后,范围for也要是const的。

test.cpp中进行测试。

void test1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;
}

5.拓展知识

我们把迭代器和范围for打印数据单独写成一个函数。

void vector_print(const vector<int>& v)
{vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;
}

但是我们写的这个函数只能打印vector<int>类型的数据,我如果想打印vector<double>呢?

有人肯定想到了,写成函数模板。

template<class T>
void vector_print(const vector<T>& v)
{vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;
}

 这样想打印什么就打印什么。

但是这样写,编译器会编译报错,因为:没有实例化的类模板里面取东西,编译器不能区分这里的const_iterator是类型还是静态成员变量

解决方法1:在vector<T>::const_iterator it = v.begin();这句代码前面加上typename,就是我们告诉编译器,这里是类型

解决方法2:类型直接写成auto

 6.insert和迭代器失效问题

vector.hvector类里面声明和实现,insert代码如下。

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start; //记录距离reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//更新pos}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;++_finish;
}

 6.1 失效情况1

按照我们写string的insert的思路写vector的insert。

void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;++_finish;
}

test.cpp中进行测试。

void test2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.vector_print(v);v.insert(v.begin() + 2, 30);v.vector_print(v);
}

当我们已经扩容好的时候,这个程序是没问题的。但是如果空间不够,我们插入数据时正好要扩容呢?程序会出现崩溃

原因如下。

此时的pos已经找不到了类似野指针。这就是一个最基础的迭代器失效问题。

解决方法就是我们先记录pos到start的位置距离,在扩容的时候更新pos,代码如下。

void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){size_t len = pos - _start; //记录距离reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//更新pos}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;++_finish;
}

6.2 find

其实vector并没有像string那样实现find接口,如果我们想在vector用find,就要用算法库里面的find。

 这个find是个模板,所有的容器都可以使用,这也体现了封装的特点。这个函数在first和last-1的区间找,找到了就返回下标,没找到就返回last

比如说我们要找2,用法如下。

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);

然后呢在2的前面插入一个40.

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);
if (pos != v.end())
{v.insert(pos, 40);
}
v.vector_print(v);

6.3 失效情况2

访问pos,让pos位置的值加1。

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);
if (pos != v.end())
{v.insert(pos, 40);*pos += 1; //pos位置的值加1
}
v.vector_print(v);

pos地方的值毫无变化。 虽然pos在insert内部更新了,但是这种在外部访问的情况下,pos是局部变量,出了作用域就被销毁了,其实就是形参的改变不影响实参。参数pos加&是行不通的,因为这样就不支持别的迭代器了。

insert之后,pos已经失效了,前面画过图,所以,insert之后pos失效,不要访问

insert改写

如果我们非要访问,insert的写法就要发生变化。如下。

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start; //记录距离reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//更新pos}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;++_finish;return pos; //返回插入的位置
}

解决方法

然后我们记录pos的位置再访问pos

void test3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto pos = find(v.begin(), v.end(), 2);if (pos != v.end()){pos = v.insert(pos, 40);*pos += 1; //pos位置的值加1}v.vector_print(v);}

所以insert之后pos失效,不要直接访问,要访问就要更新这个失效的迭代器。

6.4 失效情况3

以前面的pos为例,pos原本指向的是2,我们插入一个数据之后,pos指向了新插入的那个数据。

这也是一种迭代器失效的情况。前两种失效情况我们可以理解为类似野指针这种失效情况就是位置的意义已经变了。 所以insert后我们认为迭代器也失效了,所以不要访问

如果使用vector,在vs下上述情况去访问pos,是会直接报错的,Linux下不会,这要看编译器。

7.erase和迭代器失效问题

7.1 erase

vector.hvector类里面声明和实现。

void erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}_finish--;
}

test.cpp中进行测试。比如我们要删除所有偶数

void test4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.vector_print(v);vector<int>::iterator i = v.begin();while (i != v.end()){if (*i % 2 == 0){v.erase(i);}++i;}v.vector_print(v);
}

看起来成功了,我们换一个测试样例,换成123445。

没删干净。 再换一个样例1234。

程序崩溃

7.2迭代器失效问题

erase这里的迭代器失效和前面的失效情况一样,此时的i已经不是原来的数据了,就是失效了。如果一定要访问,更新一下在访问

erase改写

所以我们这里的erase要有返回值,返回被删除元素的下一个元素

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}_finish--;return pos;
}

test.cpp中进行测试。

void test4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.vector_print(v);vector<int>::iterator i = v.begin();while (i != v.end()){if (*i % 2 == 0){i = v.erase(i);//erase返回的是被删除数据的下一个数据}else++i;}v.vector_print(v);
}

都能正确处理。

8.resize

先回顾一下std里面中resize的结构。

vector.hvector类里面声明和实现。

这里的value_type其实就是模板参数T。所以我们在模拟实现resize的时候参数如下。

void resize(size_t n, T val = T())
{}

这里T val = T()就是先通过后面的T默认构造去构造一个匿名对象,然后再拷贝构造给前面的val,自定义类型要缺省的话,就是像这样,给相应的默认构造。当然这里默认构造+拷贝构造我们说过编译器可能会做优化,直接就是一个构造。

拓展

 但是,但是,如果T不是自定义类型呢?我们说过,内置类型没有构造这样的概念。针对这一情况,内置类型也有了构造函数的概念

int i = int();//初始化为0
iny j = int(1);//初始化为1
int k(2); //初始化为2

 

通过前面对resize的了解,我们知道,resize会出现三种情况。如下。

如果忘记了,请看【C++】vector使用详解_vector c++ 用法-CSDN博客 5.resize  。

我们模拟实现的时候也分两个情况就可以了,n<size和其他情况。

void resize(size_t n, T val = T())
{if (n < size()){_finish = _start + n;}else{reserve(n);//reserve内部会对n判断while (_finish < _start + n){_finish = val;++_finish;}}
}

test.cpp中进行测试。

void test5()
{vector<int> v;v.resize(6, 5);v.vector_print(v);
}

 

9.构造函数和析构函数

9.1 析构函数

~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}

9.2 构造函数

//vector() //默认构造
//{}//C++11支持,强制生成默认构造
vector() = default; //默认构造
vector(const vector<T>& v)//拷贝构造
{reserve(v.size());for (auto& e : v){push_back(e);}
}

 

10.swap、clear和operator=

vector.hvector类里面声明和实现。

10.1 传统写法

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
void clear()
{_finish = _start;
}
vector<T>& operator=(const vector<T>& v)
{if (this != &v){clear();reserve(v.size());for (auto& e : v){push_back(e);}}return *this;
}

上面写的是传统写法

 在test.cpp中进行测试一下传统写法。

vector<int> v1, v2;
v1.resize(5, 1);
v1.vector_print(v1);
v2.resize(5, 2);
v2.vector_print(v2);
v2 = v1;
v2.vector_print(v2);

10.2 现代写法

现代写法的具体内容在【C++拓展】深拷贝的传统写法vs现代写法,你更喜欢哪个?-CSDN博客

vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

测试用例和上面一样。

vector模拟实现大概结构以及迭代器失效问题就介绍完了,拜拜~

 

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

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

相关文章

前端学习八股资料CSS(一)

&#x1f914;&#x1f914;宝子们&#xff0c;好久不见啊&#xff01;今日继续分享前端八股笔记&#xff0c;好多友友们觉得笔记对于自己学习复习或面试复习或平时加强知识非常有用&#xff0c;收到了大家的好评&#xff0c;谢谢大家的喜欢&#xff0c;我会坚持继续更新的&…

【进阶】Stable Diffusion 插件 Controlnet 安装使用教程(图像精准控制)

Stable Diffusion WebUI 的绘画插件 Controlnet 最近更新了 V1.1 版本&#xff0c;发布了 14 个优化模型&#xff0c;并新增了多个预处理器&#xff0c;让它的功能比之前更加好用了&#xff0c;最近几天又连续更新了 3 个新 Reference 预处理器&#xff0c;可以直接根据图像生产…

小程序源码-模版 100多套小程序(附源码)

一、搭建开发环境 搭建环境可以从这里开始&#xff1a; 微信小程序从零开始开发步骤&#xff08;一&#xff09;搭建开发环境 - 简书 二、程序示例 1、AppleMusic https://download.csdn.net/download/m0_54925305/89977187 2、仿B站首页 https://download.csdn.net/downlo…

【Python-AI篇】K近邻算法(KNN)

0. 前置----机器学习流程 获取数据集数据基本处理特征工程机器学习模型评估在线服务 1. KNN算法概念 如果一个样本在特征空间中的K个最相似&#xff08;即特征空间中最邻近&#xff09;的样本中大多数属于某一个类别&#xff0c;则该样本也属于这一个类别 1.1 KNN算法流程总…

Deepin 系统中安装Rider和Uno Platform

1、在系统的中断命令行中输入如下命令&#xff0c;安装.NET 8环境。 wget https://packages.microsoft.com/config/ubuntu/20.04/packages-microsoft-prod.deb -O packages-microsoft-prod.debsudo dpkg -i packages-microsoft-prod.debsudo apt-get updatesudo apt-get insta…

[OpenGL]使用OpenGL实现硬阴影效果

一、简介 本文介绍了如何使用OpenGL实现硬阴影效果&#xff0c;并在最后给出了全部的代码。本文基于[OpenGL]渲染Shadow Map&#xff0c;实现硬阴影的流程如下&#xff1a; 首先&#xff0c;以光源为视角&#xff0c;渲染场景的深度图&#xff0c;将light space中的深度图存储…

反序列化漏洞浅析

Apache InLong 是开源的高性能数据集成框架&#xff0c;支持数据接入、数据同步和数据订阅&#xff0c;同时支持批处理和流处理&#xff0c;方便业务构建基于流式的数据分析、建模和应用。浅析Apache InLong < 1.12.0 JDBC反序列化漏洞&#xff08;CVE-2024-26579&#xff0…

基于微信小程序的移动学习平台的设计与实现+ssm(lw+演示+源码+运行)

摘 要 由于APP软件在开发以及运营上面所需成本较高&#xff0c;而用户手机需要安装各种APP软件&#xff0c;因此占用用户过多的手机存储空间&#xff0c;导致用户手机运行缓慢&#xff0c;体验度比较差&#xff0c;进而导致用户会卸载非必要的APP&#xff0c;倒逼管理者必须改…

SQL中的内连接(inner join)、外连接(left|right join、full join)以及on关键字中涉及分区筛选、null解释

一、简介 本篇幅主要介绍了&#xff1a; SQL中内连接&#xff08;inner join&#xff09;、外连接&#xff08;left join、right join、full join&#xff09;的机制;连接关键字on上涉及表分区筛选的物理执行及引擎优化&#xff1b;null在表关联时的情况与执行&#xff1b; …

【Linux】软硬链接和动静态库

&#x1f525; 个人主页&#xff1a;大耳朵土土垚 &#x1f525; 所属专栏&#xff1a;Linux系统编程 这里将会不定期更新有关Linux的内容&#xff0c;欢迎大家点赞&#xff0c;收藏&#xff0c;评论&#x1f973;&#x1f973;&#x1f389;&#x1f389;&#x1f389; 文章目…

Orleans集群及Placement设置

服务端界面使用相同的clusterid和serviceid&#xff0c;相同ip地址&#xff0c;不同网关端口号和服务端口号&#xff0c;启动两个silo服务&#xff0c;并使用MySql数据库做Silo间信息同步&#xff0c;实现集群。 silo服务启动代码如下&#xff08;从nuget下载Microsoft.Orleans…

iphone怎么删除重复的照片的新策略

Phone用户常常面临存储空间不足的问题&#xff0c;其中一个主要原因是相册中的重复照片。这些重复项不仅占用了大量的存储空间&#xff0c;还会影响设备的整体性能。本文将向您展示iphone怎么删除重复的照片的方法&#xff0c;包括一些利用工具来自动化这个过程的创新方法。 识…

C++ 的第一个程序

目录 一 . C的第一个程序 二 . 命名空间 2.1 namespace的价值 2.1 namespace 的定义 7.3 命名空间的使用 三 . C输入&输出 四 . 缺省参数 五 . 函数重载 六 . 引用 6.1 引用的概念和定义 6.2 引用的特性 6.3 引用的使用 6.4 const 引用 6.5 指针和引用的关系&…

C#开发基础:WPF和WinForms关于句柄使用的区别

1、前言 在 Windows 应用程序开发中&#xff0c;WPF&#xff08;Windows Presentation Foundation&#xff09;和 WinForms&#xff08;Windows Forms&#xff09;是两种常见的用户界面&#xff08;UI&#xff09;框架。它们各自有不同的架构和处理方式&#xff0c;其中一个显…

WPS Office手机去广高级版

工具介绍功能特点 WPS Office是使用人数最多的移动办公软件&#xff0c;独有手机阅读模式&#xff0c;字体清晰翻页流畅&#xff1b;完美支持文字&#xff0c;表格&#xff0c;演示&#xff0c;PDF等51种文档格式&#xff1b;新版本具有海量精美模版及高级功能 安装环境 [名称…

【Three.js基础学习】21.Realistic rendering

前言 课程回顾 渲染器 1.色调映射 值意在将高动态范围](HDR)值转换为低动态范围(LDR) Three.is中的色调映射实际上会伪造将LDR转换为HDR的过程&#xff0c;即使颜色不是HDR&#xff0c; 结果会产生非常逼真的渲染效果 THREE .NoToneMapping (default) 无色调映射 THREE.Linear…

TeamTalk知识点梳理一(单聊)

文章目录 db_proxy_serverdb_proxy_server reactor响应处理流程连接池redis连接池MySQL连接池 单聊消息消息如何封装&#xff1f;如何保证对端完整解析一帧消息&#xff1f;协议格式&#xff1f;单聊消息流转流程消息序号&#xff08;msg_id &#xff09;为什么使用redis生成&a…

LLaMA-Factory学习笔记(1)——采用LORA对大模型进行SFT并采用vLLM部署的全流程

该博客是我根据自己学习过程中的思考与总结来写作的&#xff0c;由于初次学习&#xff0c;可能会有错误或者不足的地方&#xff0c;望批评与指正。 1. 安装 1.1 LLaMA-Factory安装 安装可以参考官方 readme &#xff08;https://github.com/hiyouga/LLaMA-Factory/blob/main/…

Linux -- 进程初印象

目录 预备知识 切入点 PCB 看见进程 pid getpid 函数 预备知识 Linux -- 冯诺依曼体系结构&#xff08;硬件&#xff09;-CSDN博客https://blog.csdn.net/2301_76973016/article/details/143598784?spm1001.2014.3001.5501 Linux -- 操作系统&#xff08;软件&#xf…

342--358作业整理(错误 + 重点)

目录 1. 在需要运行的类中 定义 main 方法 2. this 。访问逻辑&#xff1a;先访问本类中&#xff0c;再访问父类中可以访问的成员&#xff08;不包括和本类中重名的成员&#xff09; 3. super 。访问逻辑&#xff1a;super&#xff08;父类对象&#xff09;直接访问父类及以…