[C++] vector && list 等容器的迭代器失效问题

标签：iterator 迭代元素 list C++ v1 vector 失效

标题：[C++] 容器的迭代器失效问题

@水墨不写bug

正文开始：

什么是迭代器？

迭代器是STL提供的六大组件之一，它允许我们访问容器（如vector、list、set等）中的元素，同时提供一个遍历容器的方法。然而，在使用迭代器时，我们必须注意所谓的“迭代器失效”问题。

一、插入/删除元素：

（1）erase导致删除位置之后的迭代器失效

当我们在使用vector时，接收到了一组数据。然而这组数据的奇数具有实际意义，偶数需要被删除，这时候我们可能会写出这样的代码：

//删除偶数
vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10,22,1};

for (vector<int>::iterator it = v1.begin();it!= v1.end();)
{
	if (*it % 2 == 0)
	{
		v1.erase(it);
	}
	else
	{
		it++;
	}
}

乍一看，这段代码看似没有问题，并且在gcc上可以跑过，但是实际上这段代码是不符合C++标准的。

1.换一个编译器，比如VS2022，发现问题了：

报错翻译过来就是迭代器不兼容。其实VS2022是通过对vector的迭代器进行封装来达到这一功能的。

2.在gcc上可以跑过，本质上只是一个巧合。

迭代器失效本质

在STL标准中，vector的erase会返回一个修正后的迭代器，而这样的修正就是为了避免迭代器失效。

vector中的一组数据，{1,2,3,4,5,6,7,8,9}；假设有一个迭代器指向元素5：

在删除元素“5”后，由于会发生数据拷贝移动，于是这个迭代器就“顺势”指向了下一个元素“6”：

这一行为是未定义的！如果我们使用的容器不是连续线性的，比如链表，那么结果将不堪设想，会产生野指针！

void test7()
{
	list<int> v1 = { 1,2,3,4,5,6,7,8,9,10,22,1 };
	for (list<int>::iterator it = v1.begin(); it != v1.end();)
	{
		if (*it % 2 == 0)
		{
			v1.erase(it);
		}
		else
		{
			it++;
		}
	}
	cout << v1;
}
int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	//test6();
	test7();
	return 0;
}

vector的erase（）原型：

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);
STl的vector返回一个迭代器，指向被函数调用删除的最后一个元素后面元素的新位置。如果操作删除序列中的最后一个元素，则这是容器的末端。

所以标准的写法是：


	vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10,22,1};
	for (vector<int>::iterator it = v1.begin();it!= v1.end();)
	{
		if (*it % 2 == 0)
		{
			it = v1.erase(it);
		}
		else
		{
			it++;
		}
	}
	cout << v1;

这样就实时更新了迭代器。

（2）insert导致的迭代器失效

i,插入元素之后位置的迭代器失效

与删除元素之后位置的迭代器失效的问题本质上是一致的：

vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };
vector<int>::iterator it = v1.begin() + 5;
cout << *it << endl;

v1.insert(v1.begin(), 4);
cout << *it << endl;

在运行时报错：

由于无法保留原来的迭代器，所以直接更新为指向插入元素的迭代器：

vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };
vector<int>::iterator it = v1.begin() + 5;
cout << *it << endl;

it = v1.insert(v1.begin(), 0);
cout << *it << endl;

ii，扩容移动导致的迭代器失效

我们看一段insert（）的原型：

//在pos位置插入对象
iterator insert(iterator pos, const T& t)
	//由于可能需要扩容，会发生迭代器失效，对内部而言
	//迭代器pos在扩容前后指向的对象不再相同，对外部也是同样的会发生
{
	if (size() == capacity())
		//需要扩容
	{
		int len = pos - _start;
		int Newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(Newcapacity);
		//改变capacity,不改变size

		//记录len，解决迭代器失效的问题
		pos = _start + len;
	}

通过分析，我们发现：在insert之前，会有一个是否需要扩容的检验，如果需要扩容，则释放旧空间，开辟新空间，然后拷贝数据。

在这个过程中，如果需要扩容那么原来指向原旧空间的迭代器就失效了，如果访问失效的迭代器，会出现意想不到的结果。

这个就解释了VS2022封装为什么迭代器。也许VS将迭代器封装为一个类，并且有这个类内部有一个判断迭代器是否失效的方法，如果我们访问了失效的迭代器就会报错。

二、容器重新分配内存

其实，只要是导致容器的重新开辟这一动作时，就伴随着迭代器失效。

比如：

（1）std::vector 插入元素导致的重新分配

#include <iostream>  
#include <vector>  
  
int main() {  
    std::vector<int> v{1, 2, 3};  
    auto it = v.begin(); // 假设 it 指向第一个元素 1  
  
    // 插入元素，如果导致重新分配内存，it 将失效  
    v.push_back(4); // 如果 v 的容量不足以容纳新元素，它将重新分配内存  
  
    // 下面的代码在重新分配后可能会导致未定义行为  
    // *it = 0; // 如果 it 已失效，这是未定义行为  
  
    // 更好的做法是重新获取迭代器  
    it = v.begin(); // 现在 it 指向新的第一个元素（可能是原来的 1，也可能是新内存位置上的 1）  
  
    std::cout << *it << std::endl; // 输出：1  
    return 0;  
}

（2）std::vector resize 导致的重新分配

#include <iostream>  
#include <vector>  
  
int main() {  
    std::vector<int> v{1, 2, 3};  
    auto it = v.begin(); // 假设 it 指向第一个元素 1  
  
    // resize 到一个更大的大小，如果导致重新分配内存，it 将失效  
    v.resize(10); // 如果 v 的容量不足以容纳 10 个元素，它将重新分配内存  
  
    // 下面的代码在重新分配后会导致未定义行为  
    // *it = 0; // 如果 it 已失效，这是未定义行为  
  
    // 更好的做法是重新获取迭代器  
    it = v.begin(); // 现在 it 指向新的第一个元素（原来的 1 或新内存位置上的元素）  
  
    std::cout << *it << std::endl; // 输出：1  
    return 0;  
}

这两个操作都导致了容器的重新开辟也就是释放旧空间，开辟新空间进行容量调整的过程，所以造成迭代器失效。