【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.h的vector类里面声明和实现，目前不做声明和定义分离。

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.h的vector类里面声明和实现，目前不做声明和定义分离。

//普通版本
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.h的vector类里面声明和实现，目前不做声明和定义分离。

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.h的vector类里面声明和实现，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.h的vector类里面声明和实现。

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.h的vector类里面声明和实现。

这里的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.h的vector类里面声明和实现。

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.xdnf.cn/news/10956.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

基于SpringBoot的渔具管理系统【附源码】

基于SpringBoot的渔具管理系统【附源码】

基于SpringBoot的渔具管理系统 效果如下&#xff1a; 系统主页面 系统登陆页面 管理员主页面 用户管理页面 渔具信息管理页面 租赁信息管理页面 归还信息管理页面 渔具信息页面 用户登陆页面 个人中心页面 研究背景 随着社会的发展&#xff0c;渔具销售企业之间的竞争与合作…
阅读更多...
string

string

文章目录 一. STL1.概念2.版本 二. string类2.1 为什么学习string类2. 标准库中的string类2.2.1 构造&#xff08;7个&#xff09;2.2.2 对string类对象进行访问和修改&#xff08;1&#xff09;operator[]&#xff08;2&#xff09;迭代器1.迭代器的使用2.迭代器的价值&#x…
阅读更多...
B2B订货系统功能设计与代码开发（PHP + MySQL）

B2B订货系统功能设计与代码开发（PHP + MySQL）

在B2B&#xff08;Business to Business&#xff09;电子商务中&#xff0c;企业之间的商品订购、交易和供应链管理是核心功能。一个高效的B2B订货系统可以帮助企业管理库存、订单、采购等业务流程。本文将介绍一个基于PHP与MySQL技术栈的B2B订货系统的功能设计与开发流程。 一…
阅读更多...
【2024】前端学习笔记17-Vue初体验

【2024】前端学习笔记17-Vue初体验

学习笔记 1.什么是vue2.vue初体验3.代码拆分释义4.本文新内容1.什么是vue Vue是一个用于构建用户界面的渐进式JavaScript框架。 它专注于视图层，易于集成或与现有项目结合使用，也可以通过其生态系统实现更复杂的单页应用（SPA）。 Vue的核心特点包括响应式数据绑定、组件化开…
阅读更多...
java动态代理

java动态代理

静态代理和动态代理 1、代理模式2、静态代理2.1 定义接口2.2 被代理对象实现2.3 代理对象2.4 客户端 3、JDK动态代理3.1 JDK动态代理例子3.1.1 定义接口3.1.2 被代理对象实现3.1.3 实现InvocationHandler接口3.1.4 创建代理对象 3.2 动态代理底层原理3.3 查看生成的代理类 4、C…
阅读更多...
多线程的创建方式以及及Thread类详解

多线程的创建方式以及及Thread类详解

目录 一.线程的创建方法&#xff1a;&#xff08;重点&#xff09; 一&#xff1a;继承Thread类 写法一&#xff1a;正常写法 写法二&#xff1a;匿名内部类 二.实现Runnable接口 写法一&#xff1a;正常写法 写法二&#xff1a;匿名内部类 三. 实现 Callable 接口 ​…
阅读更多...
408最后冲刺阶段，怎么做题才能考到120+？

408最后冲刺阶段，怎么做题才能考到120+？

C哥专业提供——计软考研院校选择分析专业课备考指南规划 重要性排序如下&#xff1a;真题占据首位&#xff0c;紧随其后的是王道模拟题&#xff0c;王道书与题目则紧随其后&#xff0c;而408统考配套习题&#xff08;高教版&#xff09;与之大致相当。 真题&#xff0c;无疑…
阅读更多...
如何对接低价又稳定的影视会员渠道？

如何对接低价又稳定的影视会员渠道？

对接低价折扣影视会员渠道通常涉及到与影视内容提供商或第三方分销商的合作。以下是一些基本步骤和注意事项&#xff0c;帮助你顺利对接这类渠道&#xff1a; 1. 市场调研 了解市场&#xff1a;研究市场上现有的影视会员服务提供商&#xff0c;包括价格、服务、用户反馈等。确…
阅读更多...
crond 任务调度 （Linux相关指令：crontab）

crond 任务调度 （Linux相关指令：crontab）

相关视频链接 crontab 进行 定时任务 的设置 概述 任务调度&#xff1a;是指系统在某个时间执行的特定的命令或程序 任务调度的分类&#xff1a; 1.系统工作&#xff1a;有些重要的工作必须周而复始地执行。如病毒扫描等。 2.个别用户可能希望执行某些程序&#xff0c;比如…
阅读更多...
顺序表+ArrayList

顺序表+ArrayList

文章目录 一、基础知识1.1 数据结构类的继承图1.2 List 介绍1.3 线性表 二、数据结构 -- 顺序表2.1 什么是顺序表以及优缺点2.2 用数组实现顺序表细节解析代码 三、ArrayList3.1 Java中如何使用ArrayList3.2 ArrayList源码无参构造方法add方法扩容方法指定初始容量构造利用其他…
阅读更多...
【工具变量】排污权交易政策试点DID（2000-2023）

【工具变量】排污权交易政策试点DID（2000-2023）

数据简介&#xff1a;在过去几十年间的“高增长、高能耗、高污染”的经济发展背景下&#xff0c;随着社会各界不断反应高经济增长背后付出的巨大环境代价&#xff0c;中国ZF将节能环保减排纳入长期规划治理中。在2007年&#xff0c;我国开始启动了二氧化硫&#xff08;SO2&…
阅读更多...
通用特效Shader

通用特效Shader

一、通用特效Shader介绍 1.1 什么是通用特效材质 Unity支持SRP Batcher后&#xff0c;使用UberShader的优势非常明显。所谓&#xff0c;UberShader&#xff0c;即一个超级Shader&#xff0c;覆盖一类功能&#xff0c;而不是多个分散的小Shader&#xff0c;比如一个通用特效Sh…
阅读更多...
网络安全SQL初步注入2

网络安全SQL初步注入2

六.报错注入 mysql函数 updatexml(1,xpath语法,0) xpath语法常用concat拼接 例如: concat(07e,(查询语句),07e) select table_name from information_schema.tables limit 0,1 七.宽字节注入(如果后台数据库的编码为GBK) url编码:为了防止提交的数据和url中的一些有特殊意…
阅读更多...
Golang--面向对象

Golang--面向对象

Golang语言面向对象编程说明&#xff1a; Golang也支持面向对象编程(OOP)&#xff0c;但是和传统的面向对象编程有区别&#xff0c;并不是纯粹的面向对象语言。所以我们说Golang支持面向对象编程特性是比较准确的。Golang没有类(class)&#xff0c;Go语言的结构体(struct)和其…
阅读更多...
英国留学论文写作中复合句式基础知识讲解

英国留学论文写作中复合句式基础知识讲解

从句子的结构出发&#xff0c;复合句式是将两个以上的独立、完整的字句子通过coordinating conjunction或者分号连接在一起。因此&#xff0c;复合句式可以理解成为两个以上的简单句子组合在一起。下面英国翰思教育通过举例的方式&#xff0c;来介绍如何将独立的句子连接在一起…
阅读更多...
从奇富科技，QQ钱包看信贷服务、贷款超市的的客户注册认证流程有什么不同

从奇富科技，QQ钱包看信贷服务、贷款超市的的客户注册认证流程有什么不同

概览 奇富科技作为港股信贷第一企业&#xff0c;目前已服务2.4亿用户&#xff0c;是国内头部信贷科技服务平台。 QQ钱包&#xff0c;作为8亿用户的贷款超市&#xff0c;拥有其他贷款超市产品梦寐以求的流量入口。 产品模式 奇富科技作为信贷科技服务平台&#xff0c;主要提…
阅读更多...
寻找伤感短视频素材 这些网站帮你轻松下载无水印资源

寻找伤感短视频素材 这些网站帮你轻松下载无水印资源

无论是制作情感类短视频&#xff0c;还是为抖音视频寻找合适的素材&#xff0c;伤感视频素材一直是创作者们关注的重点。如果你正在为如何找到高质量的伤感素材而困扰&#xff0c;那么今天我将推荐一些非常实用的素材网站&#xff0c;帮助你快速找到适合的伤感视频素材&#xf…
阅读更多...
Java项目实战II基于Spring Boot的大学生智能消费记账系统的设计与实现（开发文档+数据库+源码）

Java项目实战II基于Spring Boot的大学生智能消费记账系统的设计与实现（开发文档+数据库+源码）

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在当今社会…
阅读更多...
Linux 抓包工具 --- tcpdump

Linux 抓包工具 --- tcpdump

序言 在传输层 Tcp 的学习中&#xff0c;我们了解了 三次握手和四次挥手 的概念&#xff0c;但是看了这么多篇文章&#xff0c;我们也只是停留在 纸上谈兵。  欲知事情如何&#xff0c;我们其实可以尝试去看一下具体的网络包的信息。在这篇文章中将向大家介绍&#xff0c;在 L…
阅读更多...
基于Spring Boot+Vue的养老院管理系统【原创】

基于Spring Boot+Vue的养老院管理系统【原创】

一.系统开发工具与环境搭建 1.系统设计开发工具 后端使用Java编程语言的Spring boot框架 项目架构&#xff1a;B/S架构 运行环境&#xff1a;win10/win11、jdk17 前端&#xff1a; 技术&#xff1a;框架Vue.js&#xff1b;UI库&#xff1a;ElementUI&#xff1b; 开发工具&…
阅读更多...
最新文章

Copyright @ 2022~2023