vector迭代器失效问题

目录

leetcode

一. insert

springmvc

二. erase

CEEMDAN算法


自定义异常

简单模拟实现实现vector时,发现犯的一个错误:迭代器失效

自动化测试框架

起因是在是实现insert和erase时,出现的报错。

去中心化

一. insert

        void insert(iterator pos, const T& x)
		{
			//位置合法化
			assert(pos <= _finish && pos >= _start);
			//扩容
			if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			//末尾
			iterator end = _finish - 1;
			while (pos <= end)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
		}

然后就出现问题:

软件测试工程师

软技能

然后,经过调试发现:

redis分片集群

ios解锁大师

原来是pos没有更新,导致迭代器失效,于是就有了以下代码:

第一人称射击游戏

        void insert(iterator pos, const T& x)
		{
			//位置合法化
			assert(pos <= _finish && pos >= _start);
			//扩容
			if (_finish == _endofstorage)
			{
				//注意迭代器失效,需要更新pos
				size_t oldsize = pos - _start;

				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);

				pos = _start + oldsize;
			}
			//末尾
			iterator end = _finish - 1;
			while (pos <= end)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;

		}

但是,再进行测试的时候,会发现,如果一旦扩容了,由于是传值传参,即使内部的pos更改了,外部的pos仍然指向旧i空间,外部的pos仍然失效,仍然无法通过外部的pos去访问元素

火车票查询系统

机械

而且,不仅如此,假设当我们想要在偶数前插入20,就会出现问题,如下:

以太坊r s v

    myvector::vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.insert(it, 20);
		}
		++it;
	}

 

线性布局

我们会惊奇发现,在2的前面不断插入20,这其实是一种指向意义的迭代器失效,由此,应对这两个解决方法,参考stl库可以发现:使用的是返回值来解决该问题,于是乎,再次进行修改:

配置文件

        iterator insert(iterator pos, const T& x)
		{
			//位置合法化
			assert(pos <= _finish && pos >= _start);
			//扩容
			if (_finish == _endofstorage)
			{
				//注意迭代器失效,需要更新pos
				size_t oldsize = pos - _start;

				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);

				pos = _start + oldsize;
			}
			//末尾
			iterator end = _finish - 1;
			while (pos <= end)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;

			return pos;
		}

我们可以发现,解决方式是:

文件结构

虽然即使在内部实现时针对迭代器失效做了处理,但是外部仍然会有迭代器失效的问题

adb

由于使用的是值传递,一旦发生了扩容,由于pos(it)没有改变仍然指向旧空间,仍然会出现越界的野指针迭代器失效的问题

安卓音乐播放器

即使空间足够仍然会出现由于it指向位置意义改变导致重复插入-1,出现迭代器失效

数据链路层

通过使用使用返回值解决,既解决了位置的最新的问题,又能防止意义改变导致迭代器失效的问题,引用在会出现数据常性的问题 

mybatis使用

至此,insert的两个问题解决完,关于迭代器失效的问题也就解决了。

python数据分析

二. erase

erase由于和不同于insert,insert是由于扩容会导致野指针失效,而在erase中erase一般是不会出现野指针导致的迭代器失效的问题,erase的失效都是指向意义变了,或者不在有效访问数据有效范围(因为一般不会使用缩容方案)

dumpbin

一开始实现方式是:

舵机

        void erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;
		}

然后用以下方式去测试:

浏览器内核

    //找到pos位置删除并修改
    cout << "size:capacity = " << v.size() << ":" << v.capacity() << endl;
	auto pos = find(v.begin(), v.end(), 4);
	if (pos != v.end())
	{
		v.erase(pos);
	}
	cout << "size:capacity = " << v.size() << ":" << v.capacity() << endl;
	cout << *pos << endl;
	*pos = 10;
	cout << *pos << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
    
    //删除偶数
    myvector::vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
	}
	cout << "size:capacity = " << v.size() << ":" << v.capacity() << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

很快就发现问题了:

接口管理

区别

然而,与此同时,如果我们使用Linux系统,我们就会发现一个挺有意思的现象:

软件著作权

不仅没报错,反而还打印出来了,由此也可以发现:erase(pos)以后pos失效了,pos的意义变了,但是不同平台对于访问pos的反应是不一样的,但是如果在Linux中运行以下代码:

行转列

    myvector::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	myvector::vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
	}
	cout << "size:capacity = " << v.size() << ":" << v.capacity() << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

mingw

 然后就出现了段错误,事实上,在实际应用场景中,迭代器意义变了,还是会出现各种问题。

再次针对这些问题查看stl库对erase进行优化:

        iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;

			return pos;
		}

再次进行测试:

    myvector::vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.erase(it);
		}
		else
		{
			++it;
		}
	}
	cout << "size:capacity = " << v.size() << ":" << v.capacity() << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

发现问题已经解决,由此可知:

通过使用使用返回值解决,既解决了位置的最新的问题,又能防止意义改变导致迭代器失效的问题,这里需要注意使用引用传参在会出现数据常性的问题

综合以上的迭代器失效发现:

vector迭代器失效有两种:

1、扩容、缩容,导致野指针失效

2、迭代器指向的位置意义变了

需要注意的是:对于越界的野指针检查,系统越界机制检查不一定能检查到,编译实现机制检查相对靠谱。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注