[ C++ ] STL_vector -- 迭代器失效问题

问题引入：

        在上篇文章中，包含vector的定义和重要接口的模拟实现，大家可点击下方链接自行查阅：[ C++ ] STL _ Vector使用及其模拟实现。在模拟实现过程中我们发现，我们在实现insert和erase的过程中会引发一个问题：迭代器失效。本篇文章我们解决vector有关的迭代器失效原因及其解决方案。

目录

1. 迭代器定义及其作用

2. 底层空间改变的操作，可能会引发迭代器失效 

3.指定位置元素被删除引发迭代器失效

4.Linux下， g++编译器对迭代器失效的检查与处理

4.1 空间扩容

4.2 erase删除任意位置代码(非尾删)

4.3 erase 删除最后一个元素(尾删)

5. 结论

---

1. 迭代器定义及其作用

        我们学习使用STL库前，大家一定知道STL库的六大组件，分别是：仿函数、算法、迭代器、空间配置器、容器、配接器。其中，迭代器的底层实际就是一个指针。比如：在之前我们总结的string类的迭代器我们知道string类的迭代器底层是一个char*；vector的迭代器是一个原生指针T*。因此，迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（如果继续使用已经失效的迭代器，程序可能崩溃）。

         在了解迭代器定义及其作用之后，我们对于vector可能会导致的迭代器失效进行分析。

2. 底层空间改变的操作，可能会引发迭代器失效 

        这类的接口有：resize，reserve，insert，assign，push_back 等。
出错原因：

以上的接口，都有可能会导致vector扩容，也就是说vector底层原理中旧空间已经被释放掉，而在遍历打印时，it迭代器所指向的仍然是已经被释放的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

解决方案：

在扩容等操作完成之后，如果想要继续通过迭代器操作vector中的元素，则需要对it重新赋值即可。

案例说明：

insert 插入时可能引发迭代器失效：

我们在下图中，如果想要在3之前插入一个新数据20，我们发现旧空间满了，此时要扩容，由于it是一个指针，指向的仍然是旧空间中3的地址，但是如果扩容会导致旧空间被释放，则会引发迭代器失效。因此我们需要对it的指向也进行改变，我们要将it也指向新空间中的3,。因此我们使用相对位置来计算确定pos的新位置。

解决方法： 我们计算pos位置和_start的位置差n，待新空间开辟好后，使用新的_start 加上 n 就是新空间pos的位置。

 代码实现：

		iterator insert(iterator pos, const T& x)
		{
			//检查
			assert(pos >= _start && pos <= _finish);
			//空间不够  扩容
			//扩容以后 pos就失效了
			if (_finish == _endofstoage)
			{
				//使用相对距离来计算确定pos位置
				size_t n = pos - _start;
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + n; //相对位置求pos
			}
 
			//挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
 
			return pos;
		}

3.指定位置元素被删除引发迭代器失效

        vector中还有一个接口erase，也会引发迭代器失效，那么他是如何引发的呢？怎么解决呢？

        实际上，erase删除pos位置元素之后，pos位置之后的元素会往前移动，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos位置刚好是最后一个元素（尾删），删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上的元素时，vs就认为该位置迭代器失效了。

		#include 
		using namespace std;
		#include 
		int main()
		{
			int a[] = { 1, 2, 3, 4 };
			vector<int> v(a, a + sizeof(a) / sizeof(int));
 
			// 使用find查找3所在位置的iterator
			vector<int>::iterator pos = find(v.begin(), v.end(), 3);
 
			// 删除pos位置的数据，导致pos迭代器失效。
			v.erase(pos);
 
			cout << *pos << endl; // 此处会导致非法访问
			return 0;
		}

解决方案：

由于erase在尾删时才会导致迭代器失效，因此我们只需要对erase删除时的逻辑进行简单调整，即可避免该问题。我们每次删除pos位置时，我们it指向pos位置的下一个元素，每次让it覆盖it-1位置的元素，当it走到_finish时，说明pos位置后面的元素已经全部往前走了一步，此时只需要将_finish位置--即可，此方法仍在解决尾删时，也不会导致迭代器失效。

代码实现：

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos <= _finish);
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;
 
			return pos;
		}

4.Linux下， g++编译器对迭代器失效的检查与处理

在Linux下，g++编译器对迭代器失效的检测并不是很严格，处理也没有vs极端。

4.1 空间扩容

#include 
#include 
using namespace std;
 
int main()
{
  vector<int> v{1,2,3,4};
  for(size_t i = 0; isize();++i)
    cout << v[i] << " ";
  cout << endl;
  auto it = v.begin();
  cout << "Before expansion:vector.capacity():"<capacity()<
  
  v.reserve(100);
  cout<<"After expansion:vector.capacity():"<capacity()<
  
  while(it != v.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
 
  return 0;
}

反观vs下：程序崩溃

结论：g++编译器下，扩容之后，迭代器已经失效了，程序虽然可以运行，但是结果已经不对了。而vs编译器下，直接程序崩溃。

4.2 erase删除任意位置代码(非尾删)

#include 
#include 
#include 
using namespace std;
 
int main()
{
  vector<int> v{1,2,3,4,5};
  vector<int>::iterator it = find(v.begin(),v.end(),3);
 
  v.erase(it);
  cout<< *it << endl;
  
  while(it != v.end())
  {
    cout<< *it << " ";
    ++it;
  }
  cout<
 
  return 0;
}

 反观vs下：程序崩溃

 

结论：erase删除任意位置代码后，linux下迭代器并没有失效，因为空间还是原来的空间，后续元素往前搬移了，it位置还是有效的；vs下erase统一认定为迭代器失效。

4.3 erase 删除最后一个元素(尾删)

模拟实现删除数组中的偶数

#include 
#include 
#include 
using namespace std;
 
int main()
{ 
  vector<int> v{1,2,3,4,5,6};
  vector<int>::iterator it = v.begin();
 
  while(it != v.end())
  {
    if(*it % 2 == 0)
    {
      v.erase(it);
    }
    ++it;
  }
 
  for(auto e : v )
  {
    cout << e << " ";
  }
  
  cout << endl;
  return 0;
}

 

vs下肯定也是崩溃

结论：erase删除的迭代器如果是最后一个元素，删除之后it已经超过了end，此时迭代器是无效的，++it导致程序崩溃。

5. 结论

在上述3个大例子中，我们从vs编译器到linux下g++编译器中可以看到：SGI版本的STL库中，迭代器失效后，vs下代码一定会崩溃，g++下代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。

因此迭代器失效时一定要对迭代器重新赋值。

(本篇完)