Ⅳ. 浅谈迭代器失效问题
0x00 引入：通过 insert / erase 了解迭代器失效问题
我们通过实现 vector 的 insert 和 erase，去顺带讲解迭代器失效的问题。
❓ 什么是迭代器失效？
" 迭代器失效是一种现象，由特定操作引发，这些特定操作对容器进行操作，使得迭代器不指向容器内的任何元素，或者使得迭代器指向的容器元素发生了改变。"
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，
或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T* 。
因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，
而使用一块已经被释放的空间，造成的后果是程序崩溃，
即，如果继续使用已经失效的迭代器，程序可能会出现崩溃。
0x01 实现 insert
插入可分为四个步骤：① 检查 pos 是否越界 ② 检查是否需要扩容 ③ 移动数据 ④ 插入数据
💬 insert
/* 插入 */ void insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); // 检查是否需要增容 if (_finish == _eos) { // 扩容 reserve(capacity() == 0 ? 4 : capacity() * 2); } // 移动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } // 插入数据 *pos = x; _finish++; }
💬 测试：在2的位置前插入一个20
void test_vector7() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); vector<int>::iterator pos = find(v1.begin(), v1.end(), 2); if (pos != v1.end()) { v1.insert(pos, 20); } for (auto e : v1) cout << e << " "; cout << endl; }
🚩 运行结果如下：
我们的 insert 似乎没什么问题？我们再 push_back 一个数据看看，让它出现扩容的情况：
void test_vector7() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector<int>::iterator pos = find(v1.begin(), v1.end(), 2); if (pos != v1.end()) { v1.insert(pos, 20); } for (auto e : v1) cout << e << " "; cout << endl; }
🚩 运行结果如下：
迭代器失效问题。扩容导致的 pos 失效，我们的 insert 没有去处理这个问题。
如果发生扩容，我们的 pos 是不是应该去更新一下？
💬 insert：
/* 插入 */ void insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); // 检查是否需要增容 if (_finish == _eos) { // 扩容会导致迭代器失效，扩容需要更新一下 pos size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } // 移动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } // 插入数据 *pos = x; _finish++; }
🚩 运行结果如下：
但是外面的 pos（实参） 还是失效的，这里是传值，pos（形参） 是 pos（实参） 的临时拷贝。
如果 insert 中发生了扩容，那么会导致 pos（实参）指向空间被释放。
pos（实参） 本身就是一个野指针，这种问题我们称之为 —— 迭代器失效
❓ 如何解决这里的迭代器失效问题？传引用？
传引用当然时不好的，有的 vector 还会缩容呢，传引用不能彻底解决所有问题。
🔍 我们来看看大佬是如何解决这一问题的：
然而它们是通过返回值去拿的，返回新插入的迭代器。
如果迭代器失效了，你想拿另一个迭代器去代替，就可以通过返回值去拿一下。
⚡ insert：
/* 插入 */ iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); // 检查是否需要增容 if (_finish == _eos) { // 扩容会导致迭代器失效，扩容需要更新一下 pos size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } // 移动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } // 插入数据 *pos = x; _finish++; return pos; }
0x02 实现 erase
💬 erase
void erase(iterator pos) { assert(pos >= _start); assert(pos <= _finish); iterator begin = pos + 1; while (begin < _finish) { *(begin - 1)* begin; begin++; } _finish--; }
💬 测试：删除2
void test_vector8() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector<int>::iterator pos = find(v1.begin(), v1.end(), 2); if (pos != v1.end()) { v1.erase(pos); } for (auto e : v1) cout << e << " "; cout << endl; }
🚩 运行结果如下：
思考：erase 有没有迭代器失效的问题？
当然了，erase 也会有失效的情况！
💬 比如我们要求删除 v1 所有的偶数：
void test_vector8() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); // 要求删除v1所有的偶数 vector<int>::iterator pos = find(v1.begin(), v1.end(), 2); while (pos != v1.end()) { if (*pos % 2 == 0) { v1.erase(pos); } pos++; } for (auto e : v1) cout << e << " "; cout << endl; }
❓ 删除会导致 pos 失效吗？
我们用三种场景去测试：
1 2 3 4 5 1 2 4 5 1 2 3 4
测试结果如下，如果数据是：
① 1 2 3 4 5 👉 正常（其实是个巧合）
② 1 2 3 4 👉 崩溃
③ 1 2 4 5 👉 结果不对（没删除完）
erase(pos) 以后，pos 指向的意义已经变了，直接 pos++ 可能会导致一些意料之外的结果。
对于情况 ③：比如连续的偶数，导致后一个偶数没有判断，导致没有删掉。
再其次，erase 的删除有些 vector 版本的实现，不排除它会缩容。
如果是这样，erase(pos) 以后，pos 也可能会是野指针，跟 insert 类似。
（SGI 和 PJ 版本 vector 都不会缩容）
对于情况 ②：如果最后一个数据是偶数，会导致 erase 以后，pos 意义变了。
再 ++ 一下，导致 pos 和 end 错过结束判断，出现越界问题。
而情况 ①： 之所以没有翻车，是因为被删除的偶数后面恰巧跟的是奇数，运气好逃过了一劫。
导致上述三种问题的本质：erase(pos) 以后，pos 的意义变了，再去 pos++ 是不对的。
为了解决这个问题，erase 是这么说明的：
最近 erase 的元素的后方位置。
⚡ 改进 erase：
/* 删除 */ iterator erase(iterator pos) { assert(pos >= _start); assert(pos <= _finish); iterator begin = pos + 1; while (begin < _finish) { *(begin - 1) = *begin; begin++; } _finish--; return pos; } void test_vector9() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); // 要求删除v1所有的偶数 vector<int>::iterator pos = find(v1.begin(), v1.end(), 2); while (pos != v1.end()) { if (*pos % 2 == 0) { pos = v1.erase(pos); // erase以后pos失效，会返回下一个位置的迭代器 } else { pos++; } } for (auto e : v1) cout << e << " "; cout << endl; }
🚩 运行结果如下：
0x03 可能导致迭代器失效的操作
对于 vector 可能会导致其迭代器失效的操作有：
① 会引起其底层空间改变的操作，都有可能存在迭代器失效。
比如：resize、reverse、insert、assign、push_back 等。
② 指定位置元素的删除操作：erase
#include <iostream> using namespace std; #include <vector> 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 删除 pos 位置元素后，pos 位置之后的元素就会往前搬移，
没有导致底层空间的改变，理论上讲迭代器不应该会失效。
但是 pos 刚好是最后一个元素，删完之后 pos 刚好在 end 的位置，
而 end 位置是没有元素的，那么 pos 就失效了。
因此删除 vector 中任意位置元素时，VS 就认为该位置迭代器失效了。
还有就是我们刚才讲解的奇偶数，删除 pos 位置的数据，导致 pos 迭代器失效。
当然，vector 迭代器的失效主要发生在 insert 和 erase。vector 的其他接口基本不碰迭代器，自然也就不涉及这些问题。
迭代器失效解决方法：在使用前，对迭代器重新赋值即可。
❓ string 的 insert 和 erase 迭代器是否会失效？string 有没有迭代器失效？
💡 当然会，只要使用迭代器的容器，都可能会涉及迭代器失效。
只是 string 一般很少涉及迭代器失效，因为它 insert 和 erase 时主要用下标。
Ⅴ. vector 深拷贝
0x00 拷贝构造
可以使用传统写法，也可以使用现代写法。
💬 传统写法：全都自己干，
/* v2(v1) */ vector(const vector<T>& v) { //_start = new T[v.capacity()]; //_finish = _start + v.size(); //_eos = _start + v.capacity(); reserve(v.capacity()); // 我们可以直接调用写好的reserve去开空间 // memcpy(_start, v._start, v.size() * sizeof(T)); // 会翻车 for (const auto& e : v) { push_back(e); } }
老老实实开空间，老老实实拷数据。
因为我们已经实现好了 reserve，所以我们这里可以直接调用 reserve 去开空间。
注意这里不能使用 memcpy，这个我们前面已经强调过了。
💬 现代写法：找工具人帮忙干活：
刚来，谁是工具人？ —— 让迭代器区间当工具人：
/* 现代写法：v2(v1) */ vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _eos(nullptr) { vector<T> tmp(v.begin(), v.end()); swap(_start, tmp._start); swap(_finish, tmp._finish); swap(_eos, tmp._eos); }
💬 测试一下：
void test_vector4() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector<int> v2(v1); for (auto e : v2) cout << e << " "; cout << endl; }
🚩 运行结果如下：
tmp 完成交换工作后，出了作用域要调用析构函数，
如果我们不对 _start、_finish 和 _eos 进行初始化，那么 tmp 将会是随机值。
所以我们用初始化列表给它们先初始化成 nullptr，这样交换后 tmp 就都是 nullptr 了。
根据经验，我们下面肯定还会用到 swap 的，我们不如把它封装成一个 Swap 函数。
💬 Swap：
void Swap(vector<T>& tmp) { swap(_start, tmp._start); swap(_finish, tmp._finish); swap(_eos, tmp._eos); }
⚡ 更新拷贝构造：
/* v2(v1) */ vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _eos(nullptr) { vector<T> tmp(v.begin(), v.end()); Swap(tmp); }
当然，不加模板参数的写法也是可以的：
vector(const vector& v) : _start(nullptr) , _finish(nullptr) , _eos(nullptr) { vector<T> tmp(v.begin(), v.end()); Swap(tmp); }
（这样语法上是支持的，但是还是推荐用加模板参数的写法，因为写类型会比较清楚）
0x01 赋值构造 operator=
传统写法就是把 v2 赋值给 v1，自己把 v1 释放了，再去深拷贝出 v2 一样大的空间……
太麻烦了，直接用现代写法，只要有了拷贝构造，赋值都可以用现代写法。
并且，这里还可以利用 "传参调用拷贝构造" 这一特性，做到真正的 "压榨" 工具人。
所以我们去掉 const 和引用传参，为的是让形参去充当临时变量 tmp ——
💬 现代写法：v1 = v3
/* v1 = v3 */ vector<T>& operator=(vector<T> v) { Swap(v); // 让形参v充当tmp工具人 return *this; } 这里也一样，不写模板参数也是可以的： /* v1 = v3 */ vector& operator=(vector v) { Swap(v); // 让形参v充当tmp工具人 return *this; }
想要 v1 跟 v3 有一样大的空间一样大的值，我们让传参的时候就顺便把这件事给办了。
现在 v 手上就有 v3 了，然后再用 Swap 函数夺取 v 的劳动成果，最后返回 *this 就大功告成了。
这里 v1 不仅把 v 从 v3 得到的东西，还让 v 帮忙把垃圾丢了（释放空间） ——
（画技烂轻喷）
"传参调用拷贝构造" 压榨工具人的方式，是我们第二次讲了。
第一次是在 string 模拟实现的时候讲的，当时我们称之为 —— 更简洁的写法：
正所谓一回生二回熟，相信到这里你应该理解，我们为什么可以这么做了。
❓ 现在请思考：既然有这种好事，为什么不在拷贝构造的时候用？
🔍 如果你答错了，建议复习一下：
【C++要笑着学】类的默认成员函数详解 | 构造函数 | 析构函数 | 构造拷贝函数
💬 测试一下：
void test_vector5() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); cout << "赋值前："; for (auto e : v1) cout << e << " "; cout << endl; vector<int> v3; v3.push_back(10); v3.push_back(20); v3.push_back(30); cout << "赋值后："; v1 = v3; for (auto e : v1) cout << e << " "; cout << endl; }
🚩 运行结果如下：
（不崩溃了）
