【C++私房菜】序列式容器的迭代器失效问题

一、list的迭代器失效

二、vector的迭代器失效

1、空间缩小操作

2、空间扩大操作

三、总结

在C++中，当对容器进行插入或删除操作时，可能会导致迭代器失效的问题。所谓迭代器失效指的是，原先指向容器中某个元素的迭代器，在容器发生结构性变化（比如插入、删除元素）后，可能不再指向之前预期的位置，甚至变得无效，不能再安全地使用。

迭代器失效通常会导致程序出现未定义行为，比如访问无效内存地址、产生崩溃等问题。这是因为在容器发生结构性变化时，迭代器所持有的指针或引用可能已经不再有效，但程序仍然试图通过这些失效的迭代器来访问容器中的内容，从而导致错误。

本文别以list和vector为例，给出代码示例并分析迭代器失效的情况。

一、list的迭代器失效

此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。下面我们来了解一下list的erase函数：

该函数用于从list容器中删除单个元素或者一个范围内的元素。删除元素会导致容器大小减少，并且被销毁。与其他标准序列容器不同，list和forward_list对象专门设计用于在任何位置高效地插入和删除元素，即使是在序列的中间位置。参数包括position（指向要从list中删除的单个元素的迭代器），以及[first, last)（指定要删除的范围的迭代器，包括first指向的元素但不包括last指向的元素）。返回值是一个迭代器，指向函数调用erase的最后一个元素之后的元素。如果操作erase了序列中的最后一个元素，则返回容器的末尾位置。迭代器类型iterator是一个双向迭代器类型，用于指向元素。

list的迭代器失效问题

先看一个正常使用迭代器的例子：

 #include <iostream>
 #include <list>
 
 int main() {
     std::list<int> myList = {1, 2, 3, 4, 5};
     auto it = myList.begin();
   
     // 在迭代器指向位置2之后插入一个元素
     ++it; // 移动到位置2
     myList.insert(it, 10);
 
     for (auto it = myList.begin(); it != myList.end(); ++it) {
         std::cout << *it << " ";
     }
     std::cout << std::endl;
     //1 10 2 3 4 5 
     return 0;
 }

在上面的代码中，我们在list中插入元素时，使用了insert方法来在迭代器指向的位置后面插入一个新的元素。这样做是安全的，因为insert方法会返回一个指向新插入元素的迭代器，原先的迭代器仍然有效。

接下来，再看一个list的迭代器失效问题：

 #include <iostream>
 #include <list>
 
 int main() {
     std::list<int> myList = {1, 2, 3, 4, 5};
     auto it = myList.begin();
 
     // 删除迭代器指向的位置2处的元素
     ++it; // 移动到位置2
     myList.erase(it);
     
     //cout << *it;  
     
     for (auto it = myList.begin(); it != myList.end(); ++it) {
         std::cout << *it << " ";
     }
     std::cout << std::endl;
 
     return 0;
 }

在这个例子中，我们删除了迭代器指向的位置2处的元素。此时，原先指向位置2的迭代器已经失效，应该避免继续使用它。即erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值。

如果我们在 myList.erase(it);后输入 cout << *it;，在vs下会报如下错误：

这个错误信息表明程序中出现了尝试对值初始化的list迭代器进行解引用的情况。当你试图对指向列表中无效元素的迭代器进行解引用时，会导致未定义的行为，并可能引发断言失败。

在调用 erase 函数之后，被删除元素的迭代器会失效，因此不能再安全地对它进行解引用操作。在这种情况下，尝试输出 *it 会导致错误，因为 it 已经不再指向有效的元素了。

要避免这个问题，我们可以在调用 erase 函数之后，更新你的迭代器，使其指向正确的位置，或者使用 it = myList.erase(it); 来获取指向下一个有效元素的迭代器。

我们要避免这个问题，应该始终在对迭代器进行解引用操作之前检查它是否有效。你可以将迭代器与 list.end() 进行比较，以确定它是否指向列表的末尾，然后再尝试访问它所指向的元素。

二、vector的迭代器失效

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（(即如果继续使用已经失效的迭代器，程序可能会崩溃）。vector导致迭代器失效的情景是引起其底层空间改变的函数或操作。

在C++的STL中，vector容器可以动态地增长和收缩，以适应元素数量的变化。当向vector容器中插入元素时，如果元素数量超过了当前容器的大小，vector会进行空间扩展操作；而当从vector容器中删除元素时，如果元素数量变少到一定程度，vector可能会进行空间收缩操作。

我们从两个方面来谈：

1、空间缩小操作

当使用pop_back()函数删除元素，且元素数量减少到一定程度以下时，vector可能会执行空间收缩操作。具体的收缩条件和实现细节因编译器和STL库的不同而有所差异。一般来说，vector并不会在每次删除元素后立即收缩内存空间，而是在适当的时机进行调整以提高性能。

使用erase()函数删除元素，同样可能触发空间收缩操作。

下面我们来了解一下vector的erase函数，我们仅使用erase函数来描述空间缩小的情况：

该函数用于从vector中删除单个元素或者一个范围内的元素。删除元素会导致容器大小减少，并且被销毁。由于vector使用数组作为其底层存储，因此在除了末尾位置之外的位置上擦除元素会导致容器重新定位被擦除段之后的所有元素到它们的新位置。与其他类型的序列容器（如list或forward_list）相比，这通常是一种低效的操作。参数包括position（指向要从vector中删除的单个元素的迭代器）和[first, last)（指定要删除的范围的迭代器，包括first指向的元素但不包括last指向的元素）。返回值是一个迭代器，指向函数调用erase的最后一个元素之后的新位置。如果操作erase了序列中的最后一个元素，则返回容器的末尾位置。

 #include <iostream>
 #include <vector>
 
 int main() {
     std::vector<int> myVector = {1, 2, 3, 4, 5};
     auto it = myVector.begin();
 
     // 删除迭代器指向的位置2处的元素
     it = it + 2; // 移动到位置2
     myVector.erase(it);
 
     for (auto it = myVector.begin(); it != myVector.end(); ++it) {
         std::cout << *it << " ";
     }
     std::cout << std::endl;
 
     return 0;
 }

在这个例子中，我们删除了迭代器指向的位置2处的元素。与list类似，删除操作后原先的迭代器已经失效，应该避免继续使用它。

再例如如下案例：

 #include <iostream>
 #include <vector>
 using namespace std;
 int main(){
     vector<int> v{ 1, 2, 3, 4 };
     auto pos = v.begin();
     while (pos != v.end()){
         if (*pos % 2 == 0)
             v.erase(pos);
         ++pos;
     }
     return 0;
 }

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

根据上面的内容，我们应在删除元素后，对迭代器进行赋值，使操作合法化：

 #include <iostream>
 #include <vector>
 using namespace std;
 int main(){
     vector<int> v{ 1, 2, 3, 4 };
     auto it = v.begin();
     while (it != v.end()){
         if (*it % 2 == 0)
             it = v.erase(it);
         else 
             ++it;
     }
     return 0;
 }

2、空间扩大操作

当使用push_back()函数向vector末尾添加元素，并且当前元素数量已经达到了vector的容量上限时，vector会执行空间扩大操作。通常情况下，vector会重新分配更大的内存空间，将原有元素拷贝到新的内存空间中，并释放原来的内存空间。

使用insert()函数在任意位置插入元素，如果导致vector超出容量上限，也会触发空间扩大操作。

下面我们来了解一下vector的erase函数，我们仅使用erase函数来描述空间缩小的情况：

 #include <iostream>
 #include <vector>
 int main() {
     std::vector<int> myVector = {1, 2, 3, 4, 5};
     auto it = myVector.begin();
   
     // 在迭代器指向位置2之后插入一个元素
     it = it + 2; // 移动到位置2
     myVector.insert(it, 10);
 
     for (auto it = myVector.begin(); it != myVector.end(); ++it) {
         std::cout << *it << " ";
     }
     std::cout << std::endl;
   
     return 0;
 }

我们在vector中插入元素时，使用了insert方法并通过迭代器移动到指定位置。以上操作可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，而在打印时，如cout << *it;，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效。本文不再赘述，请读者结合vector理解。

需要注意的是，不同的编译器有不同的处理方式，Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对。或者erase删除任意位置代码后，Linux下迭代器并没有失效，因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的。