vector中的迭代器失效问题

一、insert引发的失效

【错误一】：底层空间改变后产生野指针

// 案例一：模拟实现vector中的insert接口
iterator insert(iterator p, const T& val)
{
	 assert(p >= start && p <= finish);

     if (finish == end_of_storage)
     {
         reserve(finish == nullptr ? 4 : 2 * capacity());
     }

     auto end = finish;
     while (end > p)        
     {
         *end = *(end - 1);
         --end;
     }
     finish++;
     *p = val;
     return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

[错因分析]：

​ 经扩容后，start指向一块新的空间，而p仍然指向原来的空间，从而出现野指针

[解决办法]：

​ 扩容后给p重新赋值使之仍然有效

if (finish == end_of_storage)
{
     size_t n = p - start;
     reserve(finish == nullptr ? 4 : 2 * capacity());
     p = start + n;
}
1
2
3
4
5
6

将insert代码修改无误后看接下来的案例：

【错误二】：迭代器指向空间的意义改变

// 案例二：在所有的偶数前插入数字0
void test()
{
	my::vector<int> v;  
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	my::vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.insert(it, 0); // 返回迭代器的作用就体现出了
         it++;
		}
		it++;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

[错因分析]：

• 如果发生了扩容，那么start会指向新的一块空间。而it仍然指向原来的空间，所以会造成如案例一中所示的野指针错误
• 如果没有发生扩容，那么假设在2前面插入0，it原本指向2变成指向0，it加加后it仍然指向2，从而陷入了死循环。迭代器指向空间的意义改变。

[解决办法]：

扩容后给it重新赋值使之仍然有效；保持迭代器指向空间的意义不变

while (it != v.end())
{
    if (*it % 2 == 0)
    {
        v.insert(it, 0);
		it++;
    }
    it++;
}
1
2
3
4
5
6
7
8
9

二、不同平台对其处理

1. 野指针错误

   void test()
   {
   	vector<int> v;
   	v.push_back(1);
   	v.push_back(2);
   	v.push_back(3);
   	v.push_back(4);
   	cout << v.size() << " " << v.capacity() << endl;
   	auto pos = v.begin();
   	v.insert(pos, 0); // 插入后发生扩容，但是没有修改pos的值（形参不影响实参）
   	*pos = 10;
   }
   
   int main()
   {
   	test();
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17

   VS: 抛出异常

   g++：检测不出

2. 意义改变

   void test()
   {
   	vector<int> v;
      	reserve(10);   //开好足够的空间就不会扩容了
   	v.push_back(1);
   	v.push_back(2);
   	v.push_back(3);
   	v.push_back(4);
   	cout << v.size() << " " << v.capacity() << endl;
   	auto pos = v.begin();
   	v.insert(pos, 0);
   	*pos = 10;
   }
   
   int main()
   {
   	test();
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18

   VS: 检测不出

   g++：检测不出

三、erase引发的失效

【概况】：

​  一般vector在删除数据的时候都不会考虑缩容的方案，因为缩容本质上就是用时间换空间，但显然时间是更加珍贵的。所以erase引发的迭代器失效问题基本上不会是由野指针导致的，而是由意义改变引起的。

​

• VS下使用erase后就不能再使用「p」了，因为它的意义改变了

  
  正确的方法是用erase的返回值来给p重新赋值
  

• g++检测不出

四、总结

对于insert和erase造成的迭代器失效问题：

• Liunx下的g++平台检查更佛系，基本依靠系统自身野指针越界检查机制（只是抽查，越界了不能保证百分百检测出）
• windows下VS系列检查更加严格，会使用一些强制检查机制，意义变了也可能会检查出来（例如erase）

套用在实际场景中，迭代器意义变了也可能会出现各种问题，值得重视：

同样的代码使用的数据不同带来的结果也是不同的，但都是迭代器意义改变造成的：

1. 代码逻辑错误导致2被直接略过

2. 凑巧

3. 删除4后it遇不到finish，陷入死循环

   

​ 类似的，string类也存在迭代器失效的问题，但是由于我们在使用string类相应接口的时候，使用下标的居多，所以问题不大