• 【 C++ 】vector迭代器失效与深浅拷贝问题

    目录

    1、vector迭代器失效问题

            1.1、insert迭代器失效

                     扩容导致野指针

                     意义变了

                     官方库winsows下VS和Linux下对insert迭代器失效的处理

            1.2、erase迭代器失效

                     官方库windows下VS和Linux下对erase迭代器失效的处理

            1.3、迭代器失效总结

    2、深浅拷贝问题

    1、vector迭代器失效问题

    insert迭代器失效

    上文我们写了insert的模拟实现，这里先我们给出不完善版本，以insert的雏形开始往后深层次递进演化，如下：

    1. void insert(iterator pos, const T& x)
    2. {
    3. 	//检测参数合法性
    4. 	assert(pos >= _start && pos <= _finish);
    5. 	//检测是否需要扩容
    6. 	if (_finish == _endofstoage)
    7. 	{
    8. 		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
    9. 		reserve(newcapcacity);
    10. 	}
    11. 	//挪动数据
    12. 	iterator end = _finish - 1;
    13. 	while (end >= pos)
    14. 	{
    15. 		*(end + 1) = *(end);
    16. 		end--;
    17. 	}
    18. 	//把值插进去
    19. 	*pos = x;
    20. 	_finish++;
    21. }

    insert的迭代器失效分为两大类：

    1. 扩容导致野指针
    2. 意义变了

    扩容导致野指针

    我们给出两组测试用例如下：

    怎么push_back尾插4个后调用insert会出现随机值？而push_back尾插5个后调用insert就没问题？

    此问题就是迭代器失效，原因在于pos没有更新。导致非法访问野指针。

    上述当尾插4个数字后，再头插一个数字，发生扩容，根据reserve扩容机制，_start和_finish都会更新，维度这个插入的位置pos没有更新，此时pos依旧执行旧空间，再者reserve后会释放旧空间，此时的pos就是野指针，这也就导致后续执行*pos = x就是对非法访问野指针，所以最终结果就是随机值。

    • 解决办法：

     可以通过设定变量n来计算扩容前pos指针位置和_start指针位置的相对距离，最后在扩容后，让_start再加上先前算好的相对距离n就是更新后的pos指针的位置了。

    • 修正如下：
    1. void insert(iterator pos, const T& x)
    2. {
    3. 	//检测参数合法性
    4. 	assert(pos >= _start && pos <= _finish);
    5. 	/*扩容以后pos就失效了，需要更新一下*/
    6. 	if (_finish == _endofstoage)
    7. 	{
    8. 		size_t n = pos - _start;//计算pos和start的相对距离
    9. 		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
    10. 		reserve(newcapcacity);
    11. 		pos = _start + n;//防止迭代器失效，要让pos始终指向与_start间距n的位置
    12. 	}
    13. 	//挪动数据
    14. 	iterator end = _finish - 1;
    15. 	while (end >= pos)
    16. 	{
    17. 		*(end + 1) = *(end);
    18. 		end--;
    19. 	}
    20. 	//把值插进去
    21. 	*pos = x;
    22. 	_finish++;
    23. }

     

    此时的迭代器失效已经解决了一部分，当然还存在一个迭代器失效问题，见下文： 

    意义变了

    比如现在我要在所有的偶数前面插入2，可是测试结果确是如下：

    这里发生了断言错误，这段代码发生了两个错误：

    1. 和上面的错误一样，首先it是指向原空间的，当insert插入到要扩容时，原来的旧数据被拷到了新空间上，这也就意味着旧空间全是野指针，而it一直是指向旧空间的，随后遍历it时就非法访问野指针，也就失效了。形参的改变不会影响实参，即使你内部pos的指向改变了，但是并不会影响我外部的it。
    2. 为了解决上面的错误，有人会觉着提前reserve开辟足够大的空间即可避免发生野指针的现象，但是又出现了一个新的问题，看图：

    此时insert以后虽然没有扩容，it也没有成为野指针，但是it指向位置意义变了，导致我们这个程序重复插入20。

    • 解决办法：

    给insert函数加上返回值即可解决，返回指向新插入元素的位置。

    1. iterator insert(iterator pos, const T& x)
    2. {
    3. 	//检测参数合法性
    4. 	assert(pos >= _start && pos <= _finish);
    5. 	//检测是否需要扩容
    6. 	/*扩容以后pos就失效了，需要更新一下*/
    7. 	if (_finish == _endofstoage)
    8. 	{
    9. 		size_t n = pos - _start;//计算pos和start的相对距离
    10. 		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
    11. 		reserve(newcapcacity);
    12. 		pos = _start + n;//防止迭代器失效，要让pos始终指向与_start间距n的位置
    13. 	}
    14. 	//挪动数据
    15. 	iterator end = _finish - 1;
    16. 	while (end >= pos)
    17. 	{
    18. 		*(end + 1) = *(end);
    19. 		end--;
    20. 	}
    21. 	//把值插进去
    22. 	*pos = x;
    23. 	_finish++;
    24. 	return pos;
    25. }

    我们实际调用那块也得改动，让it自己接收insert后的返回值：

    1. void test_vector10()
    2. {
    3. 	//在所有的偶数前面插入2
    4. 	cpp::vector<int> v;
    5. 	//v.reserve(10);
    6. 	v.push_back(1);
    7. 	v.push_back(2);
    8. 	v.push_back(3);
    9. 	v.push_back(4);
    10. 	v.push_back(5);
    11. 	v.push_back(6);
    12. 	cpp::vector<int>::iterator it = v.begin();
    13. 	while (it != v.end())
    14. 	{
    15. 		if (*it % 2 == 0)
    16. 		{
    17. 			it = v.insert(it, 20);
    18. 			it++;
    19. 		}
    20. 		it++;
    21. 	}
    22. 	for (auto e : v)
    23. 	{
    24. 		cout << e << " ";
    25. 	}
    26. }

    官方库windows下VS和Linux下对insert迭代器失效的处理

    • VS：

    针对于扩容发生野指针类的迭代器失效，VS官方库是直接断言报错。把相同的代码放到Linux的g++下面试试看呢？

    • Linux：

    很明显Linux这里可以直接访问，甚至是可以修改。可见不同环境下对待迭代器失效的处理方式是不一样的，windows下更加严格，Linux下比较佛系。

    erase迭代器失效

    先给出上篇博文erase模拟实现的代码：

    1. iterator erase(iterator pos)
    2. {
    3. 	//检查合法性
    4. 	assert(pos >= _start && pos < _finish);
    5. 	//从pos + 1的位置开始往前覆盖，即可完成删除pos位置的值
    6. 	iterator it = pos + 1;
    7. 	while (it < _finish)
    8. 	{
    9. 		*(it - 1) = *it;		
    10.         it++;
    11. 	}
    12. 	_finish--;
    13. 	return pos;
    14. }
    • erase的失效都是意义变了，或者不在有效访问数据的有效范围内
    • 一般不会使用缩容的方案，那么erase的失效，一般也不存在野指针的失效

    现在要对如下代码进行测试：

    1. void test2()
    2. {
    3. 	cpp::vector<int> v;
    4. 	//v.reserve(10);
    5. 	v.push_back(1);
    6. 	v.push_back(2);
    7. 	v.push_back(3);
    8. 	v.push_back(4);
    9. 	cout << v.size() << ":" << v.capacity() << endl;
    10. 	auto pos = find(v.begin(), v.end(), 2);
    11. 	if (pos != v.end())
    12. 	{
    13. 		v.erase(pos);
    14. 	}
    15. 	cout << *pos << endl;
    16. 	*pos = 10;
    17. 	cout << *pos << endl << endl;
    18. 	cout << v.size() << ":" << v.capacity() << endl;
    19. 	for (auto e : v)
    20. 	{
    21. 		cout << e << " ";
    22. 	}
    23. }

    这里首先在尾插4个数据后，比较了下size和capacity的大小，此时是相等的，接下来删除值为2的数，此时*pos就是删除数字的下一个数据，没有问题，并且s=有效数据size也少了一个，后续修改*pos也没有问题。

    • 可是当我要删除值为4的数据呢，再执行上述测试用例会是什么结果呢？

    这里我总共就有4个数字，按理说把最后一个数字删去后，有效数字-1，理应不存在说还会访问最后一个值的现象，但是此结果确实是删掉4后又访问了4，离谱的是还修改了4为10，这就是erase典型的迭代器失效。但是这里也不足为奇，因为你空间还没有缩容，删掉的4还存在，导致最终还能够被访问。

    官方库windows下VS和Linux下对erase迭代器失效的处理

    • VS下：

    VS环境下检擦非常严格， 直接强制检擦断言错误。

    • Linux下：

    很明显看出Linux下对于迭代器失效的检擦就宽泛很多，不会报错。

    • 结论如下：
    1. erase(pos)以后pos失效了，pos的意义变了，但是在不同平台下面对于访问pos的反应是不一样的，我们用的时候要以失效的角度去看待此问题。
    2. 对于insert和erase造成迭代器失效问题，linux的g++平台检查很佛系，基本靠操作系统本身野指针越界检擦机制。windows下VS系列检擦更严格一些，使用一些强制检擦机制，意义变了可能会检擦出来。
    3. 虽然g++对于迭代器失效检查时是非常佛系的，但是套在实际场景中，迭代器意义变了，也会出现各种问题。

    下面再给出一组测试用例：

    1. void test4()
    2. {
    3. 	//删除所有的偶数
    4. 	std::vector<int> v;
    5. 	//v.reserve(10);
    6. 	v.push_back(1);
    7. 	v.push_back(2);
    8. 	v.push_back(3);
    9. 	v.push_back(4);
    10. 	v.push_back(5);
    11. 	auto it = v.begin();
    12. 	while (it != v.end())
    13. 	{
    14. 		if (*it % 2 == 0)
    15. 		{
    16. 			v.erase(it);
    17. 		}
    18. 		it++;
    19. 	}
    20. 	for (auto e : v)
    21. 	{
    22. 		cout << e << " ";
    23. 	}
    24. }

    在VS下用官方库去测试会直接崩，而Linux下的结果如下：

    • 画图演示错误过程：

    •  解决方案如下：
    1. void test4()
    2. {
    3. 	//删除所有的偶数
    4. 	std::vector<int> v;
    5. 	//v.reserve(10);
    6. 	v.push_back(1);
    7. 	v.push_back(2);
    8. 	v.push_back(2);
    9. 	v.push_back(2);
    10. 	v.push_back(2);
    11. 	v.push_back(3);
    12. 	v.push_back(4);
    13. 	v.push_back(5);
    14. 	auto it = v.begin();
    15. 	while (it != v.end())
    16. 	{
    17. 		if (*it % 2 == 0)
    18. 		{
    19. 			it = v.erase(it);
    20. 		}
    21. 		else
    22. 		{
    23. 			it++;
    24. 		}
    25. 	}
    26. 	for (auto e : v)
    27. 	{
    28. 		cout << e << " ";
    29. 	}
    30. }

    迭代器失效总结

    vector迭代器失效有2种

    • 1、扩容，缩容，导致野指针式失效
    • 2、迭代器指向的位置意义变了

    系统越界机制检查，不一定能检查到

    编译实现机制检查，相对靠谱

    2、深浅拷贝问题

    接下来用先前模拟实现的vector来测试杨辉三角以此来解释我们的深浅拷贝问题：

    1. namespace cpp
    2. {
    3. 	class Solution {
    4. 	public:
    5. 		// 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]
    6. 		vectorint>> generate(int numRows) {
    7. 			vectorint>> vv;
    8. 			// 先开辟杨辉三角的空间
    9. 			vv.resize(numRows);
    10. 			for (size_t i = 1; i <= numRows; ++i)
    11. 			{
    12. 				vv[i - 1].resize(i, 0);
    13. 				// 每一行的第一个和最后一个都是1
    14. 				vv[i - 1][0] = 1;
    15. 				vv[i - 1][i - 1] = 1;
    16. 			}
    17. 			for (size_t i = 0; i < vv.size(); ++i)
    18. 			{
    19. 				for (size_t j = 0; j < vv[i].size(); ++j)
    20. 				{
    21. 					if (vv[i][j] == 0)
    22. 					{
    23. 						vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
    24. 					}
    25. 				}
    26. 			}
    27. 			return vv;
    28. 		}
    29. 	};
    30.  
    31. 	void test7()
    32. 	{
    33. 		vectorint>> vv = Solution().generate(5);
    34. 		for (size_t i = 0; i < vv.size(); ++i)
    35. 		{
    36. 			for (size_t j = 0; j < vv[i].size(); ++j)
    37. 			{
    38. 				cout << vv[i][j] << " ";
    39. 			}
    40. 			cout << endl;
    41. 		}
    42. 	}
    43. }

    理想结果如下：

    测试结果如下：

    再把扩容的代码给出：

    1. //reserve扩容
    2. void reserve(size_t n)
    3. {
    4. 	size_t sz = size();//提前算出size()的大小，方便后续更新_finish
    5. 	if (n > capacity())
    6. 	{
    7. 		T* tmp = new T[n];
    8. 		if (_start)//判断旧空间是否有数据
    9. 		{
    10. 			memcpy(tmp, _start, sizeof(T) * size());
    11. 			delete[] _start;//释放旧空间
    12. 		}
    13. 		_start = tmp;//指向新空间
    14. 	}
    15. 	//更新_finish和_endofstoage
    16. 	_finish = _start + sz;
    17. 	_endofstoage = _start + n;
    18. }
    • 分析如下：

    这里出错的原因在于扩容，错在扩容时调用的memcpy是浅拷贝，导致先前存储的数据被memcpy后再delete就全删掉变成随机值了。

    仔细观察我调用的这行代码：

    vectorint>> vv = Solution().generate(5);

    这行代码的意义是有一个vector容器，其内部成员也是一个vector容器，就好比一个二维数组，有n行，每一行都是一个一维数组。画图演示上述测试用例的原因：

    总结：

    1. vector中，当T设计深浅拷贝的类型时，如：string/vector等等，我们扩容使用memcpy拷贝数据是存在浅拷贝问题。
    2. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
    3. 如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

    解决方案：

    reserve扩容时不使用memcpy，改成for循环来解决：

    1. //reserve扩容
    2. void reserve(size_t n)
    3. {
    4. 	size_t sz = size();//提前算出size()的大小，方便后续更新_finish
    5. 	if (n > capacity())
    6. 	{
    7. 		T* tmp = new T[n];
    8. 		if (_start)//判断旧空间是否有数据
    9. 		{
    10. 			//不能用memcpy，因为memcpy是浅拷贝
    11. 			for (size_t i = 0; i < size(); i++)
    12. 			{
    13. 				tmp[i] = _start[i];
    14. 			}
    15. 			delete[] _start;//释放旧空间
    16. 		}
    17. 		_start = tmp;//指向新空间
    18. 	}
    19. 	//更新_finish和_endofstoage
    20. 	_finish = _start + sz;
    21. 	_endofstoage = _start + n;
    22. }
    • 更正结果如下：

  • 相关阅读:
    Android Studio 使用gradle自动打包报错:
    蓝牙智能音箱采用哪些音频功放芯片
    ES6——类以及模块化管理
    家政服务小程序，提高企业在市场中的竞争力
    ppt 作图 如何生成eps格式
    SimpleQA：OpenAI 开源评估大模型事实性的基准测试
    【数据结构】堆的应用+TOP-K问题+二叉树遍历
    【LeetCode】最大矩形（单调栈）
    并发基础总结
    gitlab采用sourcetree进行push的时候不行解决方法
  • 原文地址：https://blog.csdn.net/bit_zyx/article/details/125753269