vector迭代器失效问题

目录

一. insert

二. erase

---

简单模拟实现实现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;
		}

然后就出现问题：

然后，经过调试发现：

原来是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，就会出现问题，如下：

    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;
		}

我们可以发现，解决方式是：

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

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

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

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

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

二. erase

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

一开始实现方式是：

        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;

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

再次针对这些问题查看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、迭代器指向的位置意义变了

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