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

---

1. 前言

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

vector深度剖析(上)

在此之前,我将在文章末尾把vector
自我实现的完整代码分享给大家

---

2. 什么是迭代器失效?

vector的每一次扩容都不是在
原地扩容,而是新开辟一块儿空间后
将原先的数据拷贝到新空间

vector<int> 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

迭代器失效的本质原因是:
扩容后start和finish的地址发生变化
指向原先位置的迭代器统统失效!

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

---

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

除了前面讲到的insert导致迭代器失效外
erase函数也会导致迭代器失效

vector<int> 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;

这段代码在删除顺序表中所有的偶数
但是你会发现它并没有删除完
这是为啥呢?

---

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

1. 对于insert来说

在pos位置使用一次insert后
不要再次直接访问pos迭代器
一定要更新了pos之后再去访问!

insert会返回一个迭代器,此迭代器的
返回的是新插入元素的迭代器

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

1. 对于erase来说

删除后不用再++迭代器
只用在没删除的时候再++

vector<int> 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. 对于reverse的深度剖析

众所周知,reverse只改变capacity大小
而不会改变size的大小

vector<int> vv;
vv.reverse(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];
}

---

6. vector深浅拷贝问题

首先来看看以下代码:

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

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

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

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

会发现,虽然x的地址和vv的地址不同
但是vv中的迭代器和x中的迭代器
的地址是相同的也就是指向同一份空间

---

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

由于这种深浅拷贝问题是因为memcpy
导致的,所以这里不能使用memcpy
只需要老实的使用一个for循环就能解决:

Vector(const Vector<T>& 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
时出现问题可以很快的排查出来!

gitee代码仓库

---