【C++进阶(三)】STL大法–vector迭代器失效&深浅拷贝问题剖析

💓博主CSDN主页:杭电码农-NEO💓

 

⏩专栏分类:C++从入门到精通⏪

 

🚚代码仓库:NEO的学习日记🚚

 

🌹关注我🫵带你学习C++

  🔝🔝

vector-下

• 1. 前言
• 2. 什么是迭代器失效?
• 3. 迭代器失效的经典案例
• 4. 迭代器失效的解决方案
• 5. 对于reserve的深度剖析
• 6. vector深浅拷贝问题
• 7. vector深浅拷贝的解决方法
• 8. 总结以及拓展

1. 前言

在阅读本篇文章前,一定要先看前集:

vector深度剖析(上)

本章重点:

本章会重点讲解vector迭代器失效问题

以及vector中的深浅拷贝问题

并且简单完善一下vector的自我实现

在此之前,我将在文章末尾把vector

自我实现的完整代码分享给大家

2. 什么是迭代器失效?

首先我们要清楚一点:

vector的每一次扩容都不是在

原地扩容,而是新开辟一块儿空间后

将原先的数据拷贝到新空间

请看下面的代码:

vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(),v.end(),3);
v.insert(pos,30);
v.insert(pos,40);

这段代码在3前面插入一个30和40

但是这段代码会出错!

为什么呢?请看下图:

注:从四个数据插入为五个会扩容

• 扩容前

  迭代器pos在start和finish之间

• 扩容后

  start和finish的地址改变,pos失效

  pos不再指向现在的位置3

迭代器失效的本质原因是:

指向原先位置的迭代器统统失效!

若没发生扩容,则一切安好!

3. 迭代器失效的经典案例

除了前面讲到的insert导致迭代器失效外

erase函数也会导致迭代器失效

请看下面的案例:

vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(6);

for (auto e : v)
{
	cout << e << " ";
}
cout << endl;
auto it = v.begin();
while (it != v.end())
{
	if (*it % 2 == 0)
	{
		it = v.erase(it);
	}
	++it;
}

for (auto e : v)
{
	cout << e << " ";
}
cout << endl;

这段代码在删除顺序表中所有的偶数

但是你会发现它并没有删除完

这是为啥呢?请看下图的分析

erase删除后,后面的数据会覆盖过来

此时不让迭代器++它也指向下一个位置

注:在VS编译器中.只要使用了erase函数

编译器自动认为此位置迭代器失效

所以在VS上进行多次erase操作时

一定要不断更新迭代器的位置!

4. 迭代器失效的解决方案

1. 对于insert来说

在pos位置使用一次insert后

不要再次直接访问pos迭代器

一定要更新了pos之后再去访问!

库中的vector提供了返回值来解决此问题:

insert会返回一个迭代器,此迭代器的

返回的是新插入元素的迭代器

请看下图理解:

所以以后我们可以这样写代码:

vector v;
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);
vector::iterator it = v.begin();
while(it!=v.end())
{
	it = insert(it,100);
	it+=2;
}
for (auto e : v)
{
	cout << e << " ";
}
cout << endl;

在每一个元素前插入一个100

2. 对于erase来说

删除后不用再++迭代器

只用在没删除的时候再++

vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
v.push_back(6);
auto it = v.begin();
while (it != v.end())
{
	if (*it % 2 == 0)
	{
		it = v.erase(it);
	}
	else
	{
		++it;
	}
}
for (auto e : v)
{
	cout << e << " ";
}
cout << endl;

5. 对于reserve的深度剖析

众所周知,reserve只改变capacity大小

而不会改变size的大小

所以这样写代码是有问题的:

vector vv;
vv.reserve(10);//开辟10份空间
for(int i=0;i<10;i++)
{
	vv[i]=i;
}

因为size此时是0,也就是有效长度为0

虽然你开辟了10份空间,但是运算符

操作[ ]的内部实现会检查下标:

T& operator[](size_t pos)
{
	assert(pos < size());
	return _start[pos];
}

所以使用reserve后直接用[ ]

访问会报错,这也是很多人会出错的地方!

6. vector深浅拷贝问题

首先来看看以下代码:

vector<vector> vv(3,vector(5));

这是一个二维数组,初始化为三行五列

vector<vector> vv(3,vector(5));
vector<vector> x(vv);

这是在拷贝构造类对象x

自我实现的拷贝构造使用的是memcpy:

Vector(const Vector& v)
{
	assert(v._start && v._finish && v._endofsto);
	_start = new T[v.capacity()];//给size或capacity都可以
	memcpy(_start, v._start, sizeof(T) * v.size());
}

然而memcpy是逐个字节拷贝

当数组是一维时,用memcpy没有问题

但是当数组是二维数组时,会出错!

我们在VS上调试窗口的监视查看地址信息:

会发现,虽然x的地址和vv的地址不同

但是vv中的迭代器和x中的迭代器

的地址是相同的也就是指向同一份空间

可以用下图来理解这个过程:

7. vector深浅拷贝的解决方法

由于这种深浅拷贝问题是因为memcpy

导致的,所以这里不能使用memcpy

只需要老实的使用一个for循环就能解决:

修改后的代码:

Vector(const Vector& v)
{
	assert(v._start && v._finish && v._endofsto);
	_start = new T[v.capacity()];//给size或capacity都可以
	//memcpy(_start, v._start, sizeof(T) * v.size()); //使用memcpy时,数组是二维数组会发生问题
	for (size_t i = 0; i < size(); i++)
	{
		_start[i] = v._start[i];
		_finish = _start + v.size();
	}
	_endofsto = _start + v.capacity();
}

直接使用等号=是外部和内部都是

原来的一份拷贝,这样就能解决问题了

8. 总结以及拓展

vector的自我实现的目的不是

为了实现一个比库中更好的vector

而是为了带大家熟悉vector的使用

并且了解了内部实现后,以后用vector

时出现问题可以很快的排查出来!

拓展:vector自我实现全部代码链接:

gitee代码仓库

🔎
下期预告:链表接口熟悉以及模拟实现 🔍