写在前面
序列式容器
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 之后迭代器后移, 关联式容器不变.