C++容器的迭代器失效情况总结

 
Category: C++

写在前面

序列式容器

vector

动态数组的迭代器失效本质上是扩容机制引起的, 看下面的实例代码:

#include <vector>
#include <format> // c++20
#include <iostream>
using namespace std;

vector<int> arr{1, 2, 3};
auto IFS = string(20, '=');
auto it1 = arr.begin();
auto it2 = arr.begin() + 1;


void get_info() { // 输出容器信息和迭代器是否失效
    cout << format("size={}, capacity={}\n", arr.size(), arr.capacity());
    if (*it1 != 1 or *it2 != 2) {
        cout << "iterator expired\n";
    }
    cout << "now arr is: ";
    for (auto i : arr) {
        cout << i << " ";
    }
    cout << format("\niter1={}, iter2={}\n", *it1, *it2);
}

void t1() {
    get_info();
    cout << format("{} after operating {}\n", IFS, IFS);
    // 只要涉及了内存的重新分配, 一定会导致迭代器失效,
    // expired: 失效的情况
    // arr.resize(5);
    // arr.reserve(5);
    // arr.push_back(4);
    arr.insert(arr.end(), 12);
    // arr.insert(arr.begin(), 12);
    // arr.erase(arr.begin());

    // non-expired: 未失效情况
    // arr.erase(arr.end()); // gcc 未做边界检查, 所以导致删除了最后一个元素
    // arr.erase(arr.end() - 1);

    // vector<int> v{4, 5, 6};
    // arr.swap(v);
    get_info();
}

int main(int argc, char *argv[]) {
    t1();
    return 0;
}

也就是说, 下面这些代码涉及到了数组的扩容(三个阶段, 申请新内存, Copy, 释放旧内存), 所以失效了

  // arr.resize(5);
  // arr.reserve(5);
  // arr.push_back(4); // 引发扩容
  arr.insert(arr.end(), 12);
  // arr.insert(arr.begin(), 12);
  // arr.erase(arr.begin()); // erase 之后迭代器指向的元素变了(后移), 其实不能算失效
  // 所以 Effective STL 中提到解决迭代器失效的方法: vector 的话erase 之后迭代器后移, 关联式容器不变.