开发者

C++中vector迭代器失效与深浅拷贝问题详析

目录
  • 一、vector迭代器失效问题
    • 1. insert迭代器失效
      • 1.1.扩容导致野指针
      • 1.2.迭代器指向位置意义改变
      • 1.3.Windows下VS中标准库和linux下g++中标准库对insert迭代器失效的处理
    • 2. erase迭代器失效
      • 2.1.迭代器失效指向位置意义改变
      • 2.2.windows下VS中标准库和Linux下g++中标准库对erase迭代器失效的处理
    • 3.迭代器失效总结
    • 二、深浅拷贝问题
      • 1.拷贝构造浅拷贝问题
        • 2.扩容浅拷贝问题
        • 总结:

          一、vector迭代器失效问题

          1. insert迭代器失效

          上文我们写了insert的模拟实现,最开始的版本是有许多Bug的,比如迭代器失效,最后经过优化修改实现了insert,这里我们以最初的版本为例,分析并解决迭代器失效问题。如下:

          void insert(iterator pos, const T& x)
          {
          	//检测参数合法性
          	assert(pos >= _start);
              assert(pos <= _finish);
          	//检测是否需要扩容
          	if (_finish == _endofstorage)
          	{
          		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
          		reserve(newcapcacity);
          	}
          	//挪动数据
          	iterator end = _finish - 1;
          	while (end >= pos)
          	{
          		*(end + 1) = *end;
          		end--;
          	}
          	//插入指定的数据
          	*pos = x;
          	_finish++;
          }
          

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

          1.1.扩容导致野指针

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

          C++中vector迭代器失效与深浅拷贝问题详析

          我们发现push_back尾插4个后调用insert会出现随机值,而push_back尾插5个后调用insert就没有问题。

          这里我们就不墨迹了,问题就是扩容导致pos迭代器失效,原因在于pos没有更新,导致非法访问野指针。

          C++中vector迭代器失效与深浅拷贝问题详析

          上述当尾插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 <= _finish);
          	//检测是否需要扩容,扩容以后pos就失效了,需要更新一下
          	if (_finish == _endofstorage)
          	{
                  size_t n = pos - _start;//计算pos和start的相对距离
          		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
          		reserve(newcapcacity);
                  // 扩容会导致pos迭代器失效,需要更新处理一下
                  pos = _start + n;//防止迭代器失效,要让pos始终指向与_start间距n的位置
          	}
          	//挪动数据
          	iterator end = _finish - 1;
          	while (end >= pos)
          	{
          		*(end + 1) = *end;
          		end--;
          	}
          	//插入指定的数据
          	*pos = x;
          	_finish++;
          }
          

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

          1.2.迭代器指向位置意义改变

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

          C++中vector迭代器失效与深浅拷贝问题详析

          这里发生了断言错误,这段代码发生了两个错误:

          1. 和上面的错误一样,首先it是指向原来的空间,当insert插入新元素时会发生扩容,原来的旧数据被拷贝到了新空间上,并且释放旧空间,这也就意味着旧空间已经被操作系统回收,而it一直是指向旧空间的,随后遍历it时就非法访问野指针,也就失效了。形参的改变不会影响实参,即使你内部pos的指向改变了,但是并不会影响我外部的it。所以我们仍然无法通过it去访问元素。
          2. 为了解决上面的错误,有人可能会说提前reserve开辟足够大的空间即可避免发生野指针的现象,但是又出现了一个开发者_JS教程新的问题,看图:

          C++中vector迭代器失效与深浅拷贝问题详析

          C++中vector迭代器失效与深浅拷贝问题详析

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

          解决办法:

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

          iterator insert(iterator pos, const T& x)
          {
          	//检测参数合法性
          	assert(pos >= _start);
              assert(pos <= _finish);
          	//检测是否需要扩容,扩容以后pos就失效了,需要更新一下
          	if (_finish == _endofstorage)
          	{
                  size_t n = pos - _start;//计算pos和start的相对距离
          		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
          		reserve(newcapcacity);
                  // 扩容会导致pos迭代器失效,需要更新处理一下
                  pos = _start + n;//防止迭代器失效,要让pos始终指向与_start间距n的位置
          	}
          	//挪动数据
          	iterator end = _finish - 1;
          	while (end >= pos)
          	{
          		*(end + 1) = *end;
          		end--;
          	}
          	//插入指定的数据
          	*pos = x;
          	_finish++;
          
              return pos;
          }
          

          我们调用函数模块也得改动,让it自己接收insert后的返回值:

          //在所有的偶数前面插入2
          void test_vector3()
          {
          	vector<int> v;
          	v.reserve(10);
          	v.push_back(1);
          	v.push_back(2);
          	v.push_back(3);
          	v.push_back(4);
          
          	vector<int>::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 << e << " ";
          	}
          	cout << endl;
          }
          

          扩展:

          有的同学可能说,能否用引用,那样就不用返回迭代器了,引用需要传一个左值变量,但是如果我传insert(bgein(),0)中的begin()是表达式的返回值,是一个临时变量,具有常性。不能这样使用。还有一些原因涉及到更深层次的问题。

          1.3.windows下VS中标准库和Linux下g++中标准库对insert迭代器失效的处理

          VS:

          C++中vector迭代器失效与深浅拷贝问题详析

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

          Linux:

          C++中vector迭代器失效与深浅拷贝问题详析

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

          2. erase迭代器失效

          和insert函数一样,erase同样会存在迭代器失效问题,这里先给出erase模拟实现的代码,存在一些问题:

          // 返回删除数据的下一个数据
          // 方便解决:一边遍历一边删除的迭代器失效问题
          void erase(iterator pos)
          {
          	assert(pos >= _start);
          	assert(pos < _finish);
          	//从pos + 1的位置开始往前覆盖,即可完成删除pos位置的值
          	iterator begin = pos + 1;
          	while (begin < _finish)
          	{
          		*(begin - 1) = *begin;
          	}
          	_finish--;
              }
          
          • erase的失效都是意义变了,或者不在有效访问数据的有效范围内
          • 一般不会使用缩容的方案,那么erase的失效,一般也不存在野指针的失效

          2.1.迭代器失效指向位置意义改变

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

          void test_vector2()
          {
          	cpp::vector<int> v;
          	//v.reserve(10);
          	v.push_back(1);
          	v.push_back(2);
          	v.push_back(3);
          	v.push_back(4);
          	cout << v.size() << ":" << v.capacity() << endl;
          	vector<int>::iterator it = find(v.begin(), v.end(), 2);
          	if (it != v.end())
          	{
          		v.erase(it);
              	}
          	cout << *it << endl; // 读
          	(*pos)++; // 写
          	cout << *it << endl << endl;
          	cout << v.size() << ":" << v.capacity() << endl;
          	for (auto e : v)
          	{
          		cout << e << " ";
          	}
          }
          

          运行结果:

          C++中vector迭代器失效与深浅拷贝问题详析

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

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

          C++中vector迭代器失效与深浅拷贝问题详析

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

          总结:

          可见代码确实是实现了删除,但是程序访问出现问题,原因就是erase后pos失效了,pos的意义变了,(但是在不同平台下对于访问pos的反编程客栈应是不一样的,因此我们使用的时候要特别小心,统一以失效的角度去看待)。但如果不访问pos指向的内容就不会出问题。比如我们没有访问v.end()python

          2.2.windows下VS中标准库和Linux下g++中标准库对erase迭代器失效的处理

          这里我们以如上程序进行对比vs和g++标准库对erase迭代器失效的处理:

          VS下:

          C++中vector迭代器失效与深浅拷贝问题详析

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

          Linux下:

          C++中vector迭代器失效与深浅拷贝问题详析

          很明显看出Linux下对于迭代器失效的检查就松懈很多,不会报错。

          结论如下:

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

          总结:

          大家可能发现我们实现的vector如果不使用std::命名空间封装的话,结果和Linux下的结果一样。这是因为VS使用的STL标准库是PJ版本,它检查更为复杂,实现更为复杂;而我们使用的STL标准库是SGI版,是Linu编程x的g++编译器使用的版本,也是侯捷老师的《STL源码剖析》的版本。它检查较为松懈,因为这里的迭代器就是原生指针,没有进行封装检查等。

          下面分别给出三组测试用例:

          • 1 2 3 4
          • 1 2 3 4 5
          • 1 2 2 3 4 5
          void test_vector4()
          {
          	//删除所有的偶数
          	std::vector<int> 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)
          		{
          			v.erase(it);
          		}
          		it++;
          	}
          	for (auto e : v)
          	{
          		cout << e << " ";
          	}
          }
          

          在VS下用官方库去测试会三组数据都崩溃:

          C++中vector迭代器失效与深浅拷贝问题详析

          而Linux下的结果如下:

          C++中vector迭代器失效与深浅拷贝问题详析

          画图演示错误过程:

          C++中vector迭代器失效与深浅拷贝问题详析

          原因分析:

          毫无疑问上诉代码会崩溃,因为erase后迭代器it所指向的位置失效,(虽然感觉是可以继续使用的,但在vs下就是不可以使用,在Linux下就可以对这个位置进行访问),所以下面我们用返回值来更新迭代器。

          解决方案如下:

          给erase加上返回值即可避免问题,返回删除元素的下一个位置。

          修正如下:

          // 返回删除数据的下一个数据
          // 方便解决:一边遍历一边删除的迭代器失效问题
          void erase(iterator pos)
          {
          	assert(pos >= _start);
          	assert(pos < _finish);
          	//从pos + 1的位置开始往前覆盖,即可完成删除pos位置的值
          	iterator begin = pos + 1;
          	while (begin < _finish)
          	{
          		*(begin - 1) = *begin;
          	}
          	_finish--;
              return pos;
          }
          

          我们调用函数模块也得改动,让it自己接收erase后的返回值:

          void test4()
          {
          	//删除所有的偶数
          	std::vector<int> 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 << e << " ";
          	}
          }
          

          分析:

          erase删除pos位置元素后,pos位置之后的元素会往前移动,没有导致底层空间的改变,理论上讲迭代器不会失效,但是如果pos位置刚好是最后一个元素,删完之后pos刚好是end的位置,而end的位置是没有有效元素的,那么pos就失效了。因此删除vector中任意位置元素时,vs均认为该位置上迭代器失效了!也就是说vector删除一定会导致迭代器失效。

          3.迭代器失效总结

          vector迭代器失效有2种

          1、扩容,导致野指针失效

          2、迭代器指向的位置意义变了

          系统越界机制检查,不一定能检查到;编译实现机制检查,相对靠谱。

          总结:

          1. 对于insert和erase造成迭代器失效问题,linux g++平台检查很松懈,基本依靠操作系统自身野指针越界检查机制,windows下vs系列检查更严格,使用一些强制检查机制,意义变了也可能会检查出来。
          2. 虽然g++对于erase迭代器失效检查时非常鸡肋的,但是套在实际场景中,迭代器意义变了,也会出现各种问题,所以我们要有正确处理迭代器失效的方式,比如用函数返回值来更新迭代器。
          3. windows下vs系列对意义失效的检查很双标,由insert函数引起的意义失效检查不出来,而且可以访问pos位置,但是由erase函数引起的意义失效却检查很严格,丝毫不准访问pos位置。但是Linux平台下都检查不出来,都可以访问pos位置。

          二、深浅拷贝问题

          1.拷贝构造浅拷贝http://www.devze.com问题

          我们的拷贝构造是存在一定问题的,存在浅拷贝问题,会导致程序崩溃。

          // 拷贝构造 v1(v)
          // 传统写法
          vector(const vector<T>& v)
          	:_start(nullptr)
          	,_finish(nullptr)
          	,_endofstorage(nullptr)
          {
          	_start = new T[v.capacity()]; // 开辟一块和v大小相同的空间
          	memcpy(_start, v._start, sizeof(T) * v.size()); //error
          	_finish = _start + v.size();
          	_endofstorage = _start + v.capacity();
          }
          

          注意:

          将容器当中的数据一个个拷贝过来时不能使用memcpy函数,当vector存储的数据是内置类型或无需进行深拷贝的自定义类型时,使用memcpy函数是没什么问题的,但当vector存储的数据是需要进行深拷贝的自定义类型时,使用memcpy函数就会出现问题。例如,当vector存储的数据是string类的时候。

          并且vector当中存储的每一个string都指向自己所存储的字符串。

          C++中vector迭代器失效与深浅拷贝问题详析

          如果此时我们使用的是memcpy函数进行拷贝构造的话,那么拷贝构造出来的vector中每个string的成员变量的值,将与被拷贝的vector中每个string的成员变量的值相同,即两个vector当中的每个对应的string成员都指向同一个字符串空间。

          C++中vector迭代器失效与深浅拷贝问题详析

          这显然不是我们得到的结果,那么所给代码是如何解决这个问题的呢?

          解决办法:使用for循环把容器v中的数据一个一个拷贝过来。

          for (size_t i = 0; i < v.size(); i++)
          {
          	_start[i] = v[i];
          }
          

          注意:_start[i] = _v[i] 本质是调用string类的赋值运算符重载函数进行深拷贝。

          代码中看似是使用普通的“=”将容器当中的数据一个个拷贝过来,实际上是调用了所存元素的赋值运算符重载函数,而string类的赋值运算符重载函数就是深拷贝,所以拷贝结果是这样的:

          C++中vector迭代器失效与深浅拷贝问题详析

          代码修改如下:

          // 拷贝构造 v1(v)
          // 传统写法
          vector(const vector<T>& v)
          	:_start(nullptr)
          	,_finish(nullptr)
          	,_endofstorage(nullptr)
          {
          	_start = new T[v.capacity()]; // 开辟一块和v大小相同的空间
          	for (size_t i = 0; i < v.size(); i++)
          	{
          		_start[i] = v[i];
          	}
          	//memcpy(_start, v._start, sizeof(T) * v.size()); //error
          	_finish = _start + v.size();
          	_endofstorage = _start + v.capacity();
          }
          

          总结一下: 如果vector当中存储的元素类型是内置类型(int)或浅拷贝的自定义类型(Date),使用memcpy函数进行进行拷贝构造是没问题的,但如果vector当中存储的元素类型是深拷贝的自定义类型(string),则使用memcpy函数将不能达到我们想要的效果。

          2.扩容浅拷贝问题

          接下来用先前模拟实现的vector来测试杨辉三角以此来解释我们的深浅拷贝问题,由于杨辉三角不太好理解,还是换个简单点的:

          namespace vector_realize
          {
          	/* class Solution {
          	public:
                  // 核心思想:找出杨辉三角的规律,发现每一行头尾都是1,中间第[j]个数等于上一行[j-1]+[j]
          		vector<vector<int>> generate(int numRows) {
          			vector<vector<int>> 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<vector<int>> vvRet = Solution().generate(5);
          
          		for (size_t i = 0; i < vvRet.size(); ++i)
          		{
          			for (size_t j = 0; j < vvRet[i].size(); ++j)
          			{
          				cout << vvRet[i][j] << " ";
          			}
          			cout << endl;
          		}
          		cout << endl;
              }*/
              
              vector<vector<int>> vv;
          	vector<int> v(5, 1);
          	vv.push_back(v);
          	vv.push_back(v);
          	vv.push_back(v);
          	vv.push_back(v);
          	vv.push_back(v);
          
          	for (size_t i = 0; i < vv.size(); i++)
          	{
          		for (size_t j = 0; j < vv[i].size(); j++)
          		{
          			cout << vv[i][j] << " ";
          		}
          		cout << endl;
          	}
          	cout << endl;
          }
          

          运行结果:

          C++中vector迭代器失效与深浅拷贝问题详析

          这里如果我只插入4个元素就不会发生报错,所以关键就在插入第五个元素改变了什么?改变容量,因为我们扩容的代码有问题。

          把扩容的代码给出:

          //reserve扩容
          void reserve(size_t n)
          {
          	int oldSize = size();
          	if (capacity() < n)
          	{
          		// 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调用析构函数析构掉原来的对象,每个对象又调用自身的析构函数,把指向的空间释放掉,然后就会出现随机值。

          画图演示上述测试用例的原因:

          C++中vector迭代器失效与深浅拷贝问题详析

          总结:

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

          解决方案:

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

          //reserve扩容
          void reserve(size_t n)
          {
          	int oldSize = size();
          	if (capacity() < n)
          	{
          		// 1.开辟新空间
          		T* tmp = new T[n];
          		if (_start)
          		{
          			//2.拷贝元素
          			// 这里直接用memcpy会有问题,发生浅拷贝
          			//memcpy(tmp, _start, sizeof(T) * size());
          			for (size_t i = 0; i <www.devze.com oldSize; i++)
          			{
          				tmp[i] = _start[i]; // 本质调用赋值运算符重载进行深拷贝
          			}
          			//3. 释放旧空间
          			delete[] _start;
          		}
          		_start = tmp;
          	}
          	// 这里_start的地址变了,而_finish还是原来的位置
          	//_finish = _start + size(); error 
          	_finish = _start + oldSize;
          	_endofstorage = _start + n;
          }
          

          分析:这里使用for循环,看似是使用普通的“=”将容器当中的数据一个个拷贝过来,实际上是调用了所存元素的赋值运算符重载函数,而vector的赋值运算符重载函数就是深拷贝,所以拷贝过程是这样的:

          C++中vector迭代器失效与深浅拷贝问题详析

          使用这种方式就能完美避免上述问题,我们运行试一下:

          C++中vector迭代器失效与深浅拷贝问题详析

          总结:

          我们析构旧空间的时候,析构的是对象数组,每个数组调用自身的析构函数,会析构数组的空间。我们用memcpy浅拷贝时,拷贝的临时对象和原来的对象指向同一块空间,所以旧空间被销毁后,我们扩容的新空间中的前4个对象变成野指针,访问的数据都是随机值。我们用for循环调用vector的赋值运算符重载可以将旧空间的数据拷贝到新空间,这样析构旧空间就不会影响新空间。

          0

          上一篇:

          下一篇:

          精彩评论

          暂无评论...
          验证码 换一张
          取 消

          最新开发

          开发排行榜