关于vector的迭代器失效

目录

关于迭代器失效的判定

1 迭代器指向的位置是野指针（全部迭代器失效）

原因：

解决

2 erase或者insert之后迭代器被更改了（部分迭代器失效）

原因

迭代器失效的场景：

改进之后

部分迭代器失效之越界访问

原因

 解决

关于平台问题

总结

---

关于迭代器失效的判定

（在windows平台下）

1 迭代器指向的位置是野指针（全部迭代器失效）

原因：

容量的改变导致空间的重新分配

比如insert或者push_back这种往原先的vector中插入元素的操作，会进行一个容量的判断，如果容量满了就会扩容：扩容是深拷贝，扩容(reserve)的具体操作是这样子的

① 先判断当前空前和reserve之后空间的大小，如果reserve之后的空间大于现在的capacity会扩容

②新开辟一块reserve之后大小的tmp的空间

③将原先空间的值拷贝到新的空间

④将原先的空间释放

因此如果不对迭代器进行更新的话，迭代器仍然指向的是之前被释放的空间，会导致迭代器失效

图解

 

如果erase采取以时间换空间的做法：缩容

这种导致容量的改变的，并且迭代器没有及时更新的，就会导致对应的迭代器失效

解决

这种由于容量的改变引起的，只能在设计reserve的时候，同时更新迭代器的值才可以

void reserve(size_t newcapacity)
	{
		if (newcapacity > capacity())
			size_t sz = size();
			T* tmp = new T[newcapacity];
			if (_start)
			{
				memcpy(tmp, _start, sizeof(T) * size());
				delete[]_start;
			}
			_start = tmp;
			_end = _start + sz;
			_endofstorage = _start + newcapacity;
 
		
	}

2 erase或者insert之后迭代器被更改了（部分迭代器失效）

原因

在erase或者insert之后capacity并没有发生改变的一个情况

erase的底层实现：erase当前位置之后的值都会往前移动一个位置并且返回在erase之前的下一个位置的迭代器的值

insert的底层实现：insert当前位置之后的值都会往后移动一个位置，并且返回insert的pos位置的迭代器的值。 

不管是erase和insert和之前相比，pos和pos位置之后的迭代器都发生了变化，在windows下的vs判定下，就判定了对应的迭代器失效了。

 

 他是这样判定的：原先每个位置的迭代器分别指向1,2,3,4,5,6,7,8，在4的位置插入之后，原先4的位置变成了新插入的10，并且之后所有的元素都发生了移位，这样子的话，原先的迭代器指向的值就发生了改变，vs判定迭代器失效

erase也是同理的，erase 4位置的值之后，其后的元素会往前挪动覆盖，这样子的话，原先4的位置变成了5，并且之后的值都发生了改变，因此原先迭代器和之后的迭代器都失效了

解决：这种情况下，erase和insert的pos位置和之后的迭代器会失效，不去访问这些位置就可以了。

如果非得访问，记得更新一下迭代器的值

迭代器失效的场景：

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
	int ar[] = { 1,2,3,4,0,5,6,7,8,9 };
	int n = sizeof(ar) / sizeof(int);
	vector<int> v(ar, ar + n);
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it != 0)
			cout << *it;
		else
			v.erase(it);
 
		it++;
	}
	return 0;
}

改进之后

 

部分迭代器失效之越界访问

删除的值在这一组值的末尾

原因

为什么会导致迭代器失效呢？

最根本的原因是迭代器erase掉最后一个值之后返回的是最后一个元素下一个位置的迭代器，而非最后一个元素！

这样子的话返回的位置是没有元素的，属于非法访问。导致了迭代器的失效

 解决

如何避免呢？

可以将返回的迭代器重新赋值，将末尾的元素给它

 

关于平台问题

在windows的vs下，和在Linux下对比，由于底层实现和检查机制的不同，因此对于上述情况的运行是否报错也不尽相同

上述的情况都是在windows下进行讨论的，如果在Linux平台下的话，erase和insert一个位置，并且如果不是末尾的元素或者中间出现的连续的偶数，并且不引起底层空间的改变的情况下，是不报错的

如果是末尾的元素，和vs下的情况一样，也是属于一个非法访问，是会报错的

如果是删除连续的数字的话，结果是不太一样的，vs下是会直接报错，但是Linux下的话，运行是没问题的，就是结果会出错，会只能删除一个对应的元素，因为返回的是删除元素的下一个位置的迭代器，这样子的话，如果正常情况下迭代进行访问，会直接错过这个位置的值（不更新迭代器的话）

总结：

迭代器失效最根本是因为指向原先位置的迭代器在erase和insert的作用下发生了改变。但是对于不同的场景迭代器失效的原因也不尽相同：

涉及到容量的改变引起的全部迭代器失效

涉及到erase和insert的部分迭代器失效，erase的值如果在末尾的话的一种特殊的情况

避免迭代器失效的做法也差不多，就是重新更改迭代器的值，让他指向正确的值。

因此如果要避免迭代器失效的话，我们需要对reserve，insert和erase的底层实现非常了解才可以采取对应的措施。

并且在不同的平台下，迭代器是否失效以及失效带来的影响也是不同的。

所以我们平时对迭代器的使用，如果无法判断的话，最好就不要去访问删除之后的迭代器了，或者如果要解决迭代器失效的问题的话，一定要注意更新！