【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模拟实现大概结构以及迭代器失效问题就介绍完了,拜拜~

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

前端CSS3 渐变详解

文章目录 CSS3 渐变详解一、引言二、CSS3 渐变基础1、线性渐变1.1、基本线性渐变1.2、改变渐变方向 2、径向渐变2.1、基本径向渐变2.2、设置径向渐变的中心 三、高级渐变技巧1、重复渐变1.1、重复线性渐变1.2、重复径向渐变 四、总结 CSS3 渐变详解 一、引言 在现代网页设计中…

Docker学习—Docker的安装与使用

Docker安装 1.卸载旧版 首先如果系统中已经存在旧的Docker&#xff0c;则先卸载&#xff1a; yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine2.配置Docker的yum库 首先…

M1M2 MAC安装windows11 虚拟机的全过程

M1/M2 MAC安装windows11 虚拟机的全过程 这两天折腾了一下windows11 arm架构的虚拟机&#xff0c;将途中遇到的坑总结一下。 1、虚拟机软件&#xff1a;vmware fusion 13.6 或者 parallel 19 &#xff1f; 结论是&#xff1a;用parellel 19。 这两个软件都安装过&#xff0…

蓝桥杯备考——算法

一、排序 冒泡排序、选择排序、插入排序、 快速排序、归并排序、桶排序 二、枚举 三、二分查找与二分答案 四、搜索&#xff08;DFS&#xff09; DFS&#xff08;DFS基础、回溯、剪枝、记忆化&#xff09; 1.DFS算法&#xff08;深度优先搜索算法&#xff09; 深度优先搜…

‘conda‘ 不是内部或外部命令,也不是可运行的程序或批处理文件,Miniconda

下载了conda&#xff0c;但是在cmd里执行conda --version会显示’conda’ 不是内部或外部命令&#xff0c;也不是可运行的程序或批处理文件。 原因是环境变量里没有添加conda&#xff0c;无法识别路径。 需要在系统环境变量里添加如下路径&#xff1a; 保存之后重新打开cmd&am…

UE5 随机生成地牢关卡

参考视频&#xff1a;【UE5 | 教程 | 地编】虚幻引擎5 中创建史诗级 程序化 地下城_哔哩哔哩_bilibili 首先创建一个父项Actor 这个BOX碰撞提是和地板重叠的 这三个是场景组件&#xff0c;这个ExitsFolder下面的箭头等会会在子蓝图中添加 接下来创建BP_MasterRoom的子蓝图&…

Qt信号和槽-->day04

Qt信号和槽 标准的信号和槽函数Qt中的槽函数Qt中的信号 connect案例 自定义信号和槽案例分析 信号槽的拓展信号连接信号案例 信号槽的两种连接方式Qt5中的处理方式Qt4中的处理方式Qt5处理信号槽重载问题案例 lambda表达式简单案例Qt中的应用 补充知识点 标准的信号和槽函数 QW…

十大经典排序算法-冒泡算法详解介绍

1、十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序&#xff0c;内部排序是数据记录在内存中进行排序&#xff0c;而外部排序是因排序的数据很大&#xff0c;一次不能容纳全部的排序记录&#xff0c;在排序过程中需要…

ASMR助眠声音视频素材去哪找 吃播助眠素材网站分享

在快节奏的现代生活中&#xff0c;越来越多的人感到压力山大&#xff0c;许多人开始寻求助眠和放松的方式。而ASMR&#xff08;自发性知觉经络反应&#xff09;助眠声音视频&#xff0c;凭借其独特的声音刺激和放松效果&#xff0c;成为了睡前的“神器”。如果你是一位内容创作…

【Linux】常用命令(2.6万字汇总)

文章目录 Linux常用命令汇总1. 基础知识1.1. Linux系统命令行的含义1.2. 命令的组成 2. 基础知识2.1. 关闭系统2.2. 关闭重启2.3. 帮助命令&#xff08;help&#xff09;2.4. 命令说明书&#xff08;man&#xff09;2.5. 切换用户&#xff08;su&#xff09;2.6.历史指令 3.目录…

量化分析工具日常操作日记-5-通合科技

使用量化分析微信小程序工具“梦想兔企业智能风险分析助手”日常操作日记-5-军工-通合科技&#xff08;300491&#xff09;。 周末国家新政策&#xff0c;要大力支持军工行业&#xff0c;我用工具挖掘了两个低位股&#xff0c;供大家参考。通合科技&#xff08;300491&#xff…

4D施工奇迹:废弃码头变身地标体育场

SYNCHRO 促进协同和战略性施工&#xff0c;完成大型项目交付 改造举世闻名的海滨城市 为了提升球迷的比赛日体验&#xff0c;英国足球俱乐部埃弗顿足球俱乐部正在利物浦默西河畔废弃的布拉姆利摩尔码头建造一座新的现代化体育场。该体育场是利物浦城市总体规划的一部分&#xf…

图神经网络(GNN)入门笔记(1)——图信号处理与图傅里叶变换

一、信号处理&#xff1a;时域与频域 时域&#xff08;Time Domain&#xff09;是我们生活中常见的信号表示方式&#xff0c;以横轴为时间&#xff0c;纵轴为信号该时刻的强度&#xff08;幅度&#xff09;&#xff0c;就可以得到一张时域图。打个比方&#xff0c;通过每时每刻…

【八百客CRM-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

【AIGC】如何在ChatGPT中制作个性化GPTs应用详解

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AIGC | GPTs应用实例 文章目录 &#x1f4af;前言&#x1f4af;什么是GPTsGPTs的工作原理GPTs的优势GPTs的应用前景总结 &#x1f4af;创建GPTS应用的基本流程进入GPTs创建界面方式一&#xff1a;按照引导完成生成创建GPTs方式二…

读书笔记--Java与线程

并发不一定要依赖多线程&#xff08;如PHP中很常见的多线程并发&#xff09;&#xff0c;但是Java里面谈论并发&#xff0c;大多数都与线程脱不了关系。 线程的实现 我们都知道&#xff0c;线程是比进程更轻量级的调度执行单位&#xff0c;线程的引入&#xff0c;可以把一个进程…

PICO+Unity 用手柄点击UI界面

如果UI要跟随头显&#xff0c;可将Canvas放置到XR Origin->Camera Offset->Main Camera下 1.Canvas添加TrackedDeviceGraphicRaycaster组件 2.EventSystem移动默认的Standard Input Module&#xff0c;添加XRUIInputModule组件 3.&#xff08;可选&#xff09;设置射线可…

三十六、Python基础语法(JSON操作)

JSON&#xff08;JavaScript Object Notation&#xff09;是一种基于文本&#xff0c;轻量级的数据交换格式。它易于人阅读和编写&#xff0c;同时也易于机器解析和生成&#xff0c;在自动化测试中经常用来存放测试数据。 JSON的特点&#xff1a; 基于文本&#xff0c;不包含图…

产品设计理念:10个案例分享

在互联网时代&#xff0c;企业通过在线产品为用户提供服务。要在众多竞争产品中脱颖而出并吸引更多用户&#xff0c;企业不仅要提供优质的服务&#xff0c;还要在产品设计上给用户带来卓越的体验。互联网产品设计包括页面布局、服务内容、流程逻辑、色彩搭配、图标、按钮等多个…

智能社区服务小程序+ssm

智能社区服务小程序 摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了智能社区服务小程序的开发全过程。通过分析智能社区服务小程序管理的不足&#xff0c;创建了一个计算机管理智能社区服务小程序的方案。文…