从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