C++中vector迭代器失效问题以及删除所有带有某值的元素

1.迭代器的失效

C++标准库（第2版）中提到：

• 如果删除某个元素，所有容器（除了vector和deque）保证迭代器以及用以指向其他元素的引用继续保持有效。
  对于vector而言，只有被删除元素之前的迭代器、指针和引用有效，被删除元素以及被删除元素之后的迭代器、指针和引用均会失效。

• 如果插入某个元素，只有list、forward_list和关联式容器（map/multimap、set/multiset）可以保证原本的迭代器和指向元素的引用继续保持有效。
  对于vector而言，只有当插入操作不会造成内存的重新分配（也就是元素的个数不会超过vector的容量capacity），插入位置之前的迭代器依然有效，插入位置之后的迭代器失效

vector<int> v{ 2,4,6,8 };
auto p = find(v.begin(), v.end(), 6); //p是指向第三个元素6的迭代器
auto q = find(v.begin(), v.end(), 4); //p是指向第二个元素4的迭代器
q=v.erase(q); //删除第二个元素，并返回下一个元素(也就是第三个元素）的迭代器

cout << *q << endl; //ok,输出6
cout << *(v.begin())<< endl; //ok,输出2,首元素的迭代器依然有效,这就验证了被删除元素之前的迭代器继续有效
cout << *p << endl; //错误，此时指向原先第三个元素的迭代器p已经失效，也验证了被删除元素之后的迭代器会失效

2.删除容器特定元素

由于之前讨论的迭代器失效的问题，我们在删除特定元素的时候必须注意：

比如我们试图删除容器中所有值为9的元素

下面是常见的错误写法1

vector<int>v{4,3,9,9,2,5,9};


	for (auto it = v.begin(); it != v.end(); ++it)
	{
		if (*it == 9)
			v.erase(it); //删除it指向的元素，导致it不再是容器v的有效迭代器
			             //如果不重新对it进行赋值，像这样直接就使用导致不明确的行为
	}

下面是常见的错误写法2

vector<int>v{4,3,9,9,2,5,9};

auto iter = find(v.begin(), v.end(), 9);//iter指向vector容器的第三个元素，即第一个9
	for (auto it = v.begin(); it != v.end();)
	{
		if (*it == 9)
			v.erase(it++); //首先it递增，递增后的新it指向第一个9后面的那个元素（也就是第二个9）
			               //接着开始执行erase，传入erase的是递增前的it的一个副本，这个副本就等同于上面的迭代器iter
			               //erase导致it的副本迭代器失效，也会导致后续的迭代器失效。因此上面it递增得到的新it也失效了
			               //那么回到for循环判断 it!=v.end();  这一步必然出错
	    else 
	       it++;
			             
	}

下面是常见的错误写法3
先暂停一下，在说明第三个错误之前，回顾以下文章一开头的那个例子

vector<int> v{ 2,4,6,8 };
auto p = find(v.begin(), v.end(), 6); //p是指向第三个元素6的迭代器
auto q = find(v.begin(), v.end(), 4); //p是指向第二个元素4的迭代器
q=v.erase(q); //删除第二个元素，并返回下一个元素(也就是6）的迭代器
--q;//ok，q现在指向了元素6前面的那个元素2（因为元素4已经被删除了）
++q;//ok,现在指向了元素2后面的元素6

cout << *q << endl; //ok,输出6

好，以上述为基础，有些人开始编写以下代码

vector<int>v{4,3,9,9,2,5,9};

	for (auto it = v.begin(); it != v.end(); ++it)
	{
		if (*it == 9){
			it=v.erase(it); //依赖erase总是返回指向被删除元素的后继元素的迭代器
			--it;//for循环中有个++it，所以这里进行--it
			}			
	}
	copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));//没问题，输出 4，3，2，5

上述代码的运行和输出都是ok的，但是真的没问题吗？答案是否定的
试想一下，如果容器的第一个元素就是9，比如

vector<int>v2{9,4,3,9,9,2,5,9};

	for (auto it = v2.begin(); it != v2.end(); ++it)
	{
		if (*it == 9){
			it=v2.erase(it); //现在it指向了首元素9后面的元素4
			--it;//现在it指向元素4，由于元素9被删了，现在4变成了首元素
			     //那么--it，相当于--v2.begin(); 怎么能够对指向首元素的迭代器进行递减呢！！！
			}			
	}

因此，一旦容器首元素就是我们要删除的元素，写法2必将导致这样的运行时库错误

can’t decrement vector iterator before begin
翻译： 不能在begin的前面递减vector的迭代器

正确写法

vector<int>v{4,3,9,9,2,5,9};

	for (auto it = v.begin(); it != v.end();)
	{
		if (*it == 9)
			it=v.erase(it); 
		else
		   ++it;	
	}

还有种写法，利用STL中的算法remove

vector<int>v{4,3,9,9,2,5,9};

v.erase(remove(v.begin(),v.end(),9),  v.end());//容器中元素变为4，3，2，5

关于remove算法：

vector<int>v{4,3,9,9,2,5,9};
remove(v.begin(),v.end(),9);//现在容器中的元素变为4，3，2，5，2，5，9