?博主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<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;这段代码在删除顺序表中所有的偶数
但是你会发现它并没有删除完
这是为啥呢?请看下图的分析
erase删除后,后面的数据会覆盖过来
此时不让迭代器++它也指向下一个位置
注:在VS编译器中.只要使用了erase函数编译器自动认为此位置迭代器失效所以在VS上进行多次erase操作时一定要不断更新迭代器的位置!
4. 迭代器失效的解决方案
对于insert来说 在pos位置使用一次insert后
不要再次直接访问pos迭代器
一定要更新了pos之后再去访问!
库中的vector提供了返回值来解决此问题:
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;在每一个元素前插入一个100
对于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. 对于reserve的深度剖析
众所周知,reserve只改变capacity大小
而不会改变size的大小
所以这样写代码是有问题的:
vector<int> 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<int>> vv(3,vector<int>(5));这是一个二维数组,初始化为三行五列
vector<vector<int>> vv(3,vector<int>(5));vector<vector<int>> x(vv);这是在拷贝构造类对象x
自我实现的拷贝构造使用的是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());}然而memcpy是逐个字节拷贝
当数组是一维时,用memcpy没有问题
但是当数组是二维数组时,会出错!
我们在VS上调试窗口的监视查看地址信息:
会发现,虽然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
时出现问题可以很快的排查出来!
拓展:vector自我实现全部代码链接:
gitee代码仓库
? 下期预告:链表接口熟悉以及模拟实现 ?