从C语言到C++_15(vector的模拟实现)+迭代器失效问题(上）：https://developer.aliyun.com/article/1521287
3. vector的其它接口函数
3.1 修改后的reserve
我们刚才实现了 reserve，reserve 搬元素的时候也是 memcpy去进行拷贝的，又让 push_back 复用了 reserve， 其实这里存在一个非常严重的问题！
现在给出一个测试用例：
void Test3() { vector<string> v; // 在vector里放string v.push_back("1"); v.push_back("2"); v.push_back("3"); v.push_back("4"); v.push_back("5"); v.push_back("6"); v.push_back("7"); v.push_back("8"); v.push_back("9"); for (const auto& e : v) { cout << e << " "; } cout << endl; }
这里发现程序崩掉了。
为什么会这样？原因在于我们在扩容和深拷贝时，用了一个 memcpy！
push_back 调用 reserve 扩容时就会出问题，根本原因是 memcpy 是浅拷贝。
问题分析：
memcpy 是内存的二进制格式拷贝，
将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
如果拷贝的是自定义类型的元素，memcpy 既高效又不会出错，
但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，
就会出错，因为memcpy的拷贝实际是浅拷贝。
（这里新的三个指针还是指向原来的空间，然后原来的空间又被释放了）
所以：如果对象中涉及到资源管理时，不能使用 memcpy 进行对象之间的拷贝，我们手动去拷：
修改后的 reserve：
void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if(_start) { //memcpy(tmp, _start, sizeof(T) * sz); 浅拷贝，不行 for (size_t i = 0; i < sz; i++)// 如果T是int，一个一个拷贝没问题 { tmp[i] = _start[i];// 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。 } delete[] _start; } _start = tmp; _finish = tmp + sz; _end_of_storage = tmp + n; } }
成功运行：
3.2 resize
vector 的 resize 如果不给第二个参数，默认给的是其对应类型的缺省值作为 "填充值"。
由于这里我们不知道具体类型是什么，这里缺省值我们使用匿名对象 T() ，
此外因为匿名对象的生命周期仅在当前一行，这里必须要用 const 引用匿名对象，
可以理解为延长其生命周期：
void resize(size_t n, const T& val = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish != _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } }
3.3 pop_back
pop_back 很简单，只需要 - -finish 就可以了。
但是需要考虑删完的情况，我们这里采用暴力的处理方式 —— 断言。
void pop_back() { assert(_finish > _start); --_finish; }
测试一下上面的函数：
void Test3() { vector<string> v; // 在vector里放string v.push_back("1"); v.push_back("2"); v.push_back("3"); v.push_back("4"); v.push_back("5"); v.push_back("6"); v.push_back("7"); v.push_back("8"); v.push_back("9"); for (const auto& e : v) { cout << e << " "; } cout << endl; cout << v.size() << " " << v.capacity() << endl; v.resize(50,"x"); cout << v.size() << " " << v.capacity() << endl; v.pop_back(); v.pop_back(); v.pop_back(); for (const auto& e : v) { cout << e << " "; } cout << endl; cout << v.size() << " " << v.capacity() << endl; } }
4. insert和erase迭代器失效问题
什么是迭代器失效？
" 迭代器失效是一种现象，由特定操作引发，这些特定操作对容器进行操作，使得迭代器不指向容器内的任何元素，或者使得迭代器指向的容器元素发生了改变。"
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，
或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T* 。
因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，
而使用一块已经被释放的空间，造成的后果是程序崩溃，
即，如果继续使用已经失效的迭代器，程序可能会出现崩溃。
4.1 insert
插入可分为四个步骤：① 检查 pos 是否越界 ② 检查是否需要扩容 ③ 移动数据 ④ 插入数据
void insert(iterator pos, const T& val) { assert(pos >= _start);// ①检查pos是否越界 assert(pos <= _finish); if (_finish == _end_of_storage)// ②检查是否需要扩容 { reserve(capacity() == 0 ? 4 : capacity() * 2); } iterator right = _finish - 1;// ③移动数据 while (right >= pos) { *(right + 1) = *right; --right; } *pos = val;// ④插入数据 ++_finish; }
测试：在2的位置前插入一个20
void Test4() { 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 (const auto& e : v1) { cout << e << " "; } cout << endl; }
继续在2的位置前插入一个20：
void Test4() { 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 (const auto& e : v1) { cout << e << " "; } cout << endl; pos = find(v1.begin(), v1.end(), 2); if (pos != v1.end()) { v1.insert(pos, 20); } for (const auto& e : v1) { cout << e << " "; } cout << endl; }
是什么问题出现了随机值？机智的童鞋已经想到：
迭代器失效问题。扩容导致的 pos 失效，我们的 insert 没有去处理这个问题。
如果发生扩容，我们的 pos 是不是应该去更新一下？：
void insert(interator pos, const T& val) { assert(pos >= _start);// ①检查pos是否越界 assert(pos <= _finish); if (_finish == _end_of_storage)// ②检查是否需要扩容 { size_t len = pos - _start;// 记录一下pos到_start的距离 reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos， } interator right = _finish - 1;// ③移动数据 while (right >= pos) { *(right + 1) = *right; --right; } *pos = val;// ④插入数据 ++_finish; }
但是外面的 pos（实参） 还是失效的，这里是传值，pos（形参） 是 pos（实参） 的临时拷贝。
如果 insert 中发生了扩容，那么会导致 pos（实参）指向空间被释放。
pos（实参） 本身就是一个野指针，这种问题我们称之为 —— 迭代器失效
如何解决这里的迭代器失效问题？传引用？
传引用当然时不好的，如果我传给你一个begin呢，传引用不能彻底解决所有问题。
我们来看看巨佬是如何解决这一问题的：
是通过返回值去拿的，返回新插入的迭代器。
如果迭代器失效了，你想拿另一个迭代器去代替，就可以通过返回值去拿一下：
iterator insert(iterator pos, const T& val) { assert(pos >= _start);// ①检查pos是否越界 assert(pos <= _finish); if (_finish == _end_of_storage)// ②检查是否需要扩容 { size_t len = pos - _start;// 记录一下pos到_start的距离 reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos， //而且形参不会影响实参，传引用的话begin等就传不了，所以用返回解决 } iterator right = _finish - 1;// ③移动数据 while (right >= pos) { *(right + 1) = *right; --right; } *pos = val;// ④插入数据 ++_finish; return pos; }
从C语言到C++_15(vector的模拟实现)+迭代器失效问题(下）：https://developer.aliyun.com/article/1521305
