【探索C++容器：vector的使用和模拟实现】（三）：https://developer.aliyun.com/article/1425783
3.vector 迭代器失效问题。（重点）
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器， 程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有：
3.1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、 push_back等。
#include <iostream> using namespace std; #include <vector> int main() { vector<int> v{ 1,2,3,4,5,6 }; auto it = v.begin(); // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容 // v.resize(100, 8); // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变 // v.reserve(100); // 插入元素期间，可能会引起扩容，而导致原空间被释放 // v.insert(v.begin(), 0); // v.push_back(8); // 给vector重新赋值，可能会引起底层容量改变 v.assign(100, 8); /* 出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉， 而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的 空间，而引起代码运行时崩溃。 解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新 赋值即可。 */ while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; }
这里我们着重来介绍一下插入函数的迭代器失效问题。
在上面我们函数内部的迭代器失效的问题得到了解决，但是外部的迭代器失效问题依然没有解决，因为pos是形参，我们只在函数内部对pos位置进行了更新，而形参得改变是不会影响实参的，外部的it依然指向原始释放的旧空间，因此外部的迭代器失效问题依然没有解决。
3.2. 指定位置元素的删除操作--erase
#include <iostream> #include <vector> using namespace std; 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就认为该位置迭代器失效了。
以下代码的功能是删除vector中所有的偶数，请问那个代码是正确的，为什么？
void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); ++it; } }
运行结果：
我们来调式一下程序
我们发现当程序删除最后一个元素后，此时就应该停止，但是我们的程序还执行了++it，导致it向后访问了，由于我们的程序是不缩容的，导致我们的程序删除最后一个元素仅仅是--finish，并没有将之前_finish的元素进行销毁，所以此时还是6，导致程序又进去了，然后程序判断为偶数，于是执行删除，但是此时pos位置不再小于_finish，于是程序就触发断言了。我们来看看图解
如果我们再尾插一个奇数呢？
void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); ++it; } print_vector(v); }
运行结果：
这是因为在删除6之后，it然后执行++，*it为7经过判断不为偶数就再次执行++it，然后it就到了end位置，程序不满足循环调教，于是就退出了，我们再看看下面的情况
void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(5); v.push_back(6); v.push_back(7); auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); ++it; } print_vector(v); }
运行结果：
我们发现我们的程序没有做到有效的偶数删除，这是因为erase删除是从后先前覆盖的，删除了第一个元素2后，第二个2就把第一个2覆盖掉了，但是此时我们的程序执行了++it，就跳过了第二个元素2，所以我们程序的逻辑还是有一点问题，所以我们来修改一下我们的代码
void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(5); v.push_back(6); v.push_back(7); auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); else ++it; } print_vector(v); }
运行结果：
如果最后一个元素是偶数呢？
void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(5); v.push_back(6); auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); else ++it; } print_vector(v); }
运行结果：
我们发现将++it放入到else里面，我们的程序就能正常去掉偶数值。这是因为我们erase的实现逻辑是覆盖操作，删除数据没有对it进行改变。但是这里能正常去掉偶数值是偶然性，我们来使用一下库里面的vector，看看结果是怎样？
void test_vector6() { std::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(5); v.push_back(6); auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); else ++it; } for (auto e : v) { cout << e << " "; } cout << endl; }
运行结果：
我们来调式一下，看看问题在哪？
我们发现我们的程序在332就出错了，这是因为vs进行了强制的检查验证，vs认为erase(it)之后，它就认为it此时已经失效了，就不允许再次访问了。所以我们上面的程序也是错误的，面对erase缩容和vs极端检查验证情况下都是错误的。
3.3. 注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。
// 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了 int main() { vector<int> v{ 1,2,3,4,5 }; for (size_t i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; auto it = v.begin(); cout << "扩容之前，vector的容量为: " << v.capacity() << endl; // 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效 v.reserve(100); cout << "扩容之后，vector的容量为: " << v.capacity() << endl; // 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux下不会 // 虽然可能运行，但是输出的结果是不对的 while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; } 程序输出： 1 2 3 4 5 扩容之前，vector的容量为: 5 扩容之后，vector的容量为 : 100 0 2 3 4 5 409 1 2 3 4 5
// 2. erase删除任意位置代码后，linux下迭代器并没有失效 // 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的 #include <vector> #include <algorithm> 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 << endl; return 0; } 程序可以正常运行，并打印： 4 4 5
// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end // 此时迭代器是无效的，++it导致程序崩溃 int main() { vector<int> v{ 1,2,3,4,5 }; // vector<int> v{1,2,3,4,5,6}; auto 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; } ======================================================== // 使用第一组数据时，程序可以运行 [sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11 [sly@VM - 0 - 3 - centos 20220114]$ . / a.out 1 3 5 ======================================================== = // 使用第二组数据时，程序最终会崩溃 [sly@VM - 0 - 3 - centos 20220114]$ vim testVector.cpp [sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11 [sly@VM - 0 - 3 - centos 20220114]$ . / a.out Segmentation fault
从上述三个例子中可以看到：SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。
3.4. 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效
#include <string> void TestString() { string s("hello"); auto it = s.begin(); // 放开之后代码会崩溃，因为resize到20会string会进行扩容 // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了 // 后序打印时，再访问it指向的空间程序就会崩溃 //s.resize(20, '!'); while (it != s.end()) { cout << *it; ++it; } cout << endl; it = s.begin(); while (it != s.end()) { it = s.erase(it); // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后 // it位置的迭代器就失效了 // s.erase(it); ++it; } }
迭代器失效解决办法：在使用前，对迭代器重新赋值即可。我们发现库中inser和erase是有返回值的。
当我们用返回值接收对迭代器重新赋值，就解决了上面的问题。所以我们上面实现的erase函数和insert函数也要修改一下。
iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it ; ++it; } --_finish; return pos; } // 在pos位置插入 iterator insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish); // 检查扩容 if (_finish == _end_of_storage) { //记录pos到_start的距离 size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); //如果发生扩容 pos = _start + len; } // 把pos后面的数据移走，再把x放到pos位置 memmove(pos + 1, pos, sizeof(T) * (_finish - pos)); *pos = x; ++_finish; return pos; }
再次用我们自己实现的vector就也可以正常运行。
结论：insert和erase形参pos都可能失效，原则是insert和erase过的迭代器都不要再使用。
4.vector深拷贝的相关问题
4.1 使用memcpy拷贝问题
假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？
void test_vector8() { vector<string> v; v.push_back("1111"); v.push_back("2222"); v.push_back("3333"); v.push_back("4444"); v.push_back("5555"); for (auto e : v) { cout << e << " "; } cout << endl; }
运行结果：
我们来调式一下
我们发现我们的程序在扩容之后就出现了错误。
问题分析：
- 1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
- 2. 如果拷贝的是基本类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
我们的delete会做两件事，首先是调用析构函数，然后再是释放空间，由于memcpy的拷贝实际是浅拷贝，再使用delete后，_str就会被析构函数情况，导致tmp里面的_str就是野指针，从而导致程序出错，所以要想解决这里的问题，就要对每一个string去做深拷贝。
void reserve(size_t n) { if (n > capacity()) { T* temp = new T[n]; size_t oldsize = size();//保存旧空间有效元素的个数 if (_start) //memcpy(temp, _start, n * sizeof(T)); for (size_t i = 0; i < oldsize; i++) { temp[i] = _start[i];//赋值操作符 } delete[] _start; _start = temp; _finish = _start + oldsize; _end_of_storage = _start + n; } }
通过赋值操作符实现上面的深拷贝，temp[i]就是我们的string类型，进行赋值操作，它就会去调用string类的赋值操作符重载去实现深拷贝。结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是 浅拷贝，否则可能会引起内存泄漏甚至程序崩溃，我们的我insert里面有memmove，它也是浅拷贝，我们也要修改一下
// 在pos位置插入 iterator insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish); // 检查扩容 if (_finish == _end_of_storage) { //记录pos到_start的距离 size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); //如果发生扩容 pos = _start + len; } // 把pos后面的数据移走，再把x放到pos位置 //memmove(pos + 1, pos, sizeof(T) * (_finish - pos)); iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; }
这里也是如此，当T是string类型的时候，此时就是string赋值给string，此时调用的就是string的赋值了。
5.动态二维数组理解
// 以杨慧三角的前n行为例：假设n为5 void test2vector(size_t n) { // 使用vector定义二维数组vv，vv中的每个元素都是vector<int> yu::vector<yu::vector<int>> vv(n); // 将二维数组每一行中的vecotr<int>中的元素全部设置为1 for (size_t i = 0; i < n; ++i) vv[i].resize(i + 1, 1); // 给杨慧三角出第一列和对角线的所有元素赋值 for (int i = 2; i < n; ++i) { for (int j = 1; j < i; ++j) { vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1]; } } }
yu::vector<yu::vector<int>> vv(n);构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类 型的，每行没有包含任何元素，如果n为5时如下所示：
vv中元素填充完成之后，如下图所示：
使用标准库中vector构建动态二维数组时与上图实际是一致的。
