[数据结构与算法]vector迭代器失效——insert模拟实现

vector支持通过输入迭代器实现插入数据，但是与此同时存在迭代器失效的问题

当我们查找某个数时，返回的位置结果是迭代器

所以这个时候我们可能需要通过迭代器插入数据

vector<int>::iterator it = find(v1.begin(),v1.end(),2);
v.insert(it,20);

?目录

一、什么是迭代器失效？

二、解决失效：insert模拟实现调整

一、什么是迭代器失效？

假设insert函数的声明如下，pos是一个迭代器，可以看作是指针

void insert(iterator& pos,const int& val);

如果现在要插入一个数，很显然需要扩容，我们的扩容方式是：

(1)? 先开辟更大的一个新空间 tmp，然后把数据拷贝到新空间

(2)? 把旧空间销毁，_start 指向新空间tmp，更新 _end、_endofstroage

?????????

此时问题出现了，旧空间被销毁，pos就成了野指针

这就是迭代器失效问题

二、解决失效：insert模拟实现调整

步骤一：判断是否要扩容，若扩容，同时需要更新迭代器pos

在插入之前，直接把迭代器转换成相对位置

int pos = it - _start;

扩容完毕后，更新pos的位置，因为即便是空间地址发生改变，相对位置不会发生变化

但是此时需要注意的一点是，原本的迭代器必须要被更新

?步骤二：从最后一个位置开始，逐个向后挪，空出pos指向的位置

函数声明如下

//这里的迭代器类型参数要设置为 引用
//形参pos被更新以后，实参的it 也会被更新
void insert(iterator& pos,const int& val);

函数定义如下

void insert(iterator& pos, const T val)
{
	if (pos >= _end || pos < 0)
	{
		return;                        //越界则不执行插入
	}

	if (_end == _endofstorage)
	{
		int len = pos - _start;        //计算相对位置
		reserve(capacity() * 2);
		pos = _start + len;            //更新pos
	}

	T* finish = _end - 1;
	while (finish>=pos)            
	{
		*(finish + 1) = *finish;
		finish--;
	}
	*pos = val;                        
	_end++;
}

代码测试：

由于这里没有实现find函数，所以使用一个简单的迭代器替代

push_back的实现详见下面的博客vector模拟实现之构造函数初始化_abs(ln(1+NaN))的博客-CSDN博客vector的构造函数模拟实现，其中另外包含扩容函数reserve、尾插函数push_back的模拟实现https://blog.csdn.net/challenglistic/article/details/124021966?spm=1001.2014.3001.5501

int main()
{
	xing::vector<int> v3;
	v3.push_back(1);
	v3.push_back(2);
	v3.push_back(3);
	v3.push_back(4);

    int* pos = v3.begin() + 2;        //简易迭代器
	v3.insert(pos, 20);            
    
	return 0;
}

?插入前

?插入后

?我们发现pos的值发生变化了

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读