| 【C++】vector迭代器失效与深浅拷贝问题 | 您所在的位置：网站首页 › erase迭代器收容 › 【C++】vector迭代器失效与深浅拷贝问题 |
【C++】vector迭代器失效与深浅拷贝问题
|
vector迭代器失效与深浅拷贝问题
上文我们写了insert的模拟实现，最开始的版本是有许多Bug的，比如迭代器失效，最后经过优化修改实现了insert，这里我们以最初的版本为例，分析并解决迭代器失效问题。如下： void insert(iterator pos, const T& x) { //检测参数合法性 assert(pos >= _start); assert(pos *(end + 1) = *end; end--; } //插入指定的数据 *pos = x; _finish++; }insert的迭代器失效分为两大类： 扩容导致野指针迭代器指向位置意义改变 1.1.扩容导致野指针我们给出两组测试用例如下：
我们发现push_back尾插4个后调用insert会出现随机值，而push_back尾插5个后调用insert就没有问题。 这里我们就不墨迹了，问题就是扩容导致pos迭代器失效，原因在于pos没有更新，导致非法访问野指针。
上述当尾插4个数字后，再头插一个数字，发生扩容，根据reserve扩容机制，_ start和_ finish都会更新，但是这个插入的位置pos没有更新，此时pos依旧执行旧空间，再者reserve后会释放旧空间，此时的pos就是野指针，导致*pos = x就是对非法访问野指针。因为pos迭代器没有更新，所以后续挪动数据并没有实现，而插入数据是对释放的空间进行操作，同样没有意义。这也就是说不论你在哪个位置插入，都没有效果。 解决办法：可以通过创建变量n来计算扩容前pos迭代器（指针）位置和_ start迭代器（指针）位置的相对距离，最后在扩容后，让_start再加上先前算好的相对距离n就是更新后的pos指针的位置了。 修正如下： void insert(iterator pos, const T& x) { //检测参数合法性 assert(pos >= _start); assert(pos *(end + 1) = *end; end--; } //插入指定的数据 *pos = x; _finish++; }此时的迭代器失效已经解决了一部分，当然还存在一个迭代器失效问题，见下文： 1.2.迭代器指向位置意义改变比如现在我要在所有的偶数前面插入2，可是测试结果确是如下：
这里发生了断言错误，这段代码发生了两个错误： 和上面的错误一样，首先it是指向原来的空间，当insert插入新元素时会发生扩容，原来的旧数据被拷贝到了新空间上，并且释放旧空间，这也就意味着旧空间已经被操作系统回收，而it一直是指向旧空间的，随后遍历it时就非法访问野指针，也就失效了。形参的改变不会影响实参，即使你内部pos的指向改变了，但是并不会影响我外部的it。所以我们仍然无法通过it去访问元素。为了解决上面的错误，有人可能会说提前reserve开辟足够大的空间即可避免发生野指针的现象，但是又出现了一个新的问题，看图：
此时insert以后虽然没有扩容，it也没有成为野指针，但是it指向位置意义变了，每插入一个数据，it就指向插入数据的下一个数据，导致我们这个程序重复插入20。 解决办法：给insert函数加上返回值即可解决，返回指向新插入元素的位置。 iterator insert(iterator pos, const T& x) { //检测参数合法性 assert(pos >= _start); assert(pos *(end + 1) = *end; end--; } //插入指定的数据 *pos = x; _finish++; return pos; }我们调用函数模块也得改动，让it自己接收insert后的返回值： //在所有的偶数前面插入2 void test_vector3() { vector v; v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector::iterator it = find(v.begin(), v.end(), 1); while (it != v.end()) { if (*it % 2 == 0) { it = v.insert(it, 20); } it++; } for (auto e : v) { cout *(begin - 1) = *begin; } _finish--; } erase的失效都是意义变了，或者不在有效访问数据的有效范围内一般不会使用缩容的方案，那么erase的失效，一般也不存在野指针的失效 2.1.迭代器失效指向位置意义改变现在要对如下代码进行测试： void test_vector2() { cpp::vector v; //v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout cout if (*it % 2 == 0) { v.erase(it); } it++; } for (auto e : v) { cout *(begin - 1) = *begin; } _finish--; return pos; }我们调用函数模块也得改动，让it自己接收erase后的返回值： void test4() { //删除所有的偶数 std::vector v; //v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); } else { it++; } } for (auto e : v) { cout _start[i] = v[i]; } 注意：_start[i] = _v[i] 本质是调用string类的赋值运算符重载函数进行深拷贝。代码中看似是使用普通的“=”将容器当中的数据一个个拷贝过来，实际上是调用了所存元素的赋值运算符重载函数，而string类的赋值运算符重载函数就是深拷贝，所以拷贝结果是这样的：
代码修改如下： // 拷贝构造 v1(v) // 传统写法 vector(const vector& v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { _start = new T[v.capacity()]; // 开辟一块和v大小相同的空间 for (size_t i = 0; i /* class Solution { public: // 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j] vector generate(int numRows) { vector vv; vv.resize(numRows);// 先开辟杨辉三角的空间 for (size_t i = 0; i < vv.size(); ++i) { vv[i].resize(i + 1, 0); vv[i][0] = vv[i][vv[i].size() - 1] = 1;// 每一行的第一个和最后一个都是1 } for (size_t i = 0; i < vv.size(); ++i) { for (size_t j = 0; j < vv[i].size(); ++j) { if (vv[i][j] == 0) { vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1]; } } } return vv; } }; void test_vector9() { vector vvRet = Solution().generate(5); for (size_t i = 0; i < vvRet.size(); ++i) { for (size_t j = 0; j < vvRet[i].size(); ++j) { cout cout // 1.开辟新空间 T* tmp = new T[n]; if (_start) { //2.拷贝元素 memcpy(tmp, _start, sizeof(T) * size()); //3. 释放旧空间 delete[] _start; } _start = tmp; } // 这里_start的地址变了，而_finish还是原来的位置 //_finish = _start + size(); error _finish = _start + oldSize; _endofstorage = _start + n; } 分析如下：这里出错的原因在于扩容，错在扩容时调用的memcpy是浅拷贝，导致先前存储的数据被memcpy后再delete就全删掉变成随机值了。vector调用析构函数析构掉原来的对象，每个对象又调用自身的析构函数，把指向的空间释放掉，然后就会出现随机值。 画图演示上述测试用例的原因：
总结： vector中，当T设计深浅拷贝的类型时，如：string/vector等等，我们扩容使用memcpy拷贝数据是存在浅拷贝问题。memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。解决方案： reserve扩容时不使用memcpy，改成for循环来解决： //reserve扩容 void reserve(size_t n) { int oldSize = size(); if (capacity() //2.拷贝元素 // 这里直接用memcpy会有问题，发生浅拷贝 //memcpy(tmp, _start, sizeof(T) * size()); for (size_t i = 0; i |
【本文地址】