发布时间:2025-06-24 09:13:53 作者:北方职教升学中心 阅读量:940
pop_back
- 迭代器失效
- memcpy的浅拷贝问题
发布时间:2025-06-24 09:13:53 作者:北方职教升学中心 阅读量:940
pop_back
上篇博客我们已经详细介绍了vector 以及它的各种函数还有使用方法
了解这一流程我们已经过去啦,下面就是自己模拟实现一下我们的vector
在模拟实现vector过程中,还是有很多细节要处理的
‘话不多说 fellow me
首先就是自定义一个vector类,我们把它放在自定义的空间命名域,然后给定相应的成员以及函数,像默认成员函数,还有自定义变量
构造函数,拷贝构造,析构函数,在实现这些函数前,我们先来实现一些前置函数,能让这些默认成员复用
下面是vector最初始的样子,只有自定义成员变量
namespacexxx{template<classT>classvector{public:typedefT*iterator;// 因为vector 会支持迭代器访问,所以我们这里定义 T* private:iterator _start =nullptr;// _start , _finish 相当于vector的开头和末尾的指针iterator _finish =nullptr;iterator _end_of_storage =nullptr;// 这个带表边界 vector的容量边界};}
vector支持迭代器访问,我们先来简单实现一下迭代器
// 指向数据不能修改,本身可以修改typedefconstT*const_iterator;// 普通迭代器和const迭代器 iterator begin(){return_start;}iterator end(){return_finish;}const_iterator begin()const{return_start;}const_iterator end()const{return_finish;}
在模拟实现vector过程中,使用了 size_t 和 int 版本的 构造函数,避免了负数隐式转换的风险,确保类型安全
在实现赋值重载时,通过复用库函数的swap,通过 swap 交换资源,避免手动管理内存
在迭代器失效方面,深究文档,慢慢找出解决的办法,迭代器失效还是能处理的
最后就是memcpy是浅拷贝,要注意memcpy的使用场景,注意内存的多次析构问题和泄漏
模拟实现下来,还是发现了很多问题的,慢慢解决出现的问题,慢慢提升自己的debug能力,加油
今天就到这里啦,不要走开,小编持续更新中~~~~
对于vector可能会导致其迭代器失效的操作有:
intmain(){xxx::vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for(constauto&e :v1){cout <<e <<" ";}cout <<endl;// 迭代器失效 //删除所有的偶数/*auto it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { v1.erase(it); } ++it; }*///删除所有的偶数/*auto it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { v1.erase(it); } else { ++it; } }*/// 前面两种删除方式都会使迭代器失效 it已经不是指向该指向的位置// 迭代器完全体 autoit =v1.begin();while(it !=v1.end()){if(*it %2==0){it =v1.erase(it);// 删除之后重新赋值迭代器 解决问题}else{++it;}}for(constauto&e :v1){cout <<e <<" ";}cout <<endl;return0;}
迭代器失效的问题到这里就结束了,还有一个小问题
下面我们运行一下这样的程序
intmain(){xxx::vector<string>v1;v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");for(constauto&e :v1){cout <<e <<" ";}cout <<endl;return0;}
显示的是这样的情况,百思不得其解,一开始以为是push_back的问题,但是慢慢调试下来,push_back是没有问题的
后面发现问题出在memcpy这个函数,我们在扩容的时候,使用了memcpy
voidreserve(size_t n){if(n >capacity()){size_t oldSize =size();// 记住之前的sizeT*tmp =newT[n];memcpy(tmp,_start,sizeof(T)*oldSize);// 拷贝时,拷贝之前的 size大小的内容delete[]_start;// 释放空间_start =tmp;_finish =_start +oldSize;_end_of_storage =_start +n;// 赋值给扩容后的vector}}
后面才知道memcpy是浅拷贝 释放空间时会多次析构,那程序不就崩溃了吗??
重新实现了一下扩容函数
voidreserve(size_t n){if(n >capacity()){size_t oldSize =size();T*tmp =newT[n];//memcpy(tmp, _start, sizeof(T) * oldSize); memcpy是浅拷贝 释放空间时会多次析构 for(size_t i =0;i <oldSize;i++)// 这里直接赋值,会调用拷贝函数,那就是深拷贝了{tmp[i]=_start[i];}delete[]_start;_start =tmp;_finish =_start +oldSize;_end_of_storage =_start +n;}}
完美解决
如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。**** */while(it !=v.end()){cout<<*it <<" ";++it;}cout<<endl;return0;}// 程序运行会崩掉
#include<iostream>usingnamespacestd;#include<vector>intmain(){inta[]={1,2,3,4};vector<int>v(a,a +sizeof(a)/sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos =find(v.begin(),v.end(),3);// 删除pos位置的数据,导致pos迭代器失效。因此迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。v.erase(pos);cout <<*pos <<endl;// 此处会导致非法访问return0;}
erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是没有元素的,那么pos就失效了。pop_back 再来实现一下 reserve(扩容)函数 还有 resize(控制size) push_back 以及 pop_back 上面这些函数实现之后,我们的默认成员函数实现起来就方便了 多种构造函数,拷贝构造,析构函数,感觉都是在复用已经实现的一些函数 有了前面的函数做铺垫,我们可以来实现运算符重载了,vector有点像数组一样,数组支持随机访问 最后就剩下插入和删除函数啦,其中也是有一些细节的 到这里vector的函数基本实现的差不多了 在实现插入函数时,会有扩容的操作,会导致pos发生变化,虽然已经解决,但是在程序中的迭代器会失效 迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装,比如:vector的迭代器就是原生态指针T* 。push_back等。reserve、size_t size()const//返回大小{return_finish -_start;}size_t capacity()const// 返回容量 {return_end_of_storage -_start;}voidreserve(size_t n){if(n >capacity()){size_t oldSize =size();// 记住之前的sizeT*tmp =newT[n];memcpy(tmp,_start,sizeof(T)*oldSize);// 拷贝时,拷贝之前的 size大小的内容delete[]_start;// 释放空间_start =tmp;_finish =_start +oldSize;_end_of_storage =_start +n;// 赋值给扩容后的vector}}voidresize(size_t n,constT&val =T()){if(n <size())// 如果n 小于当前的size{_finish =_start +n;// 直接定义尾指针}else{reserve(n);// 直接扩容到 nwhile(_finish !=_start +n)// ——finish指针后移{*_finish =val;++_finish;}}}voidpush_back(constT&x)// 插入函数{if(_finish ==_end_of_storage)// 判断当前大小 是否需要扩容{reserve(capacity()==0?4:capacity()*2);}*_finish =x;++_finish;}voidpop_back()// 删除函数{assert(_finish >_start);--_finish;// 直接--_finish}
vector——默认成员函数
vector(){}vector(size_t n,constT&val =T())// 这里我们实现了两个函数 {// 一个是size_t 的 n 一个是intresize(n,val);// 可以有效的匹配不同调用场景}// 防止负数隐式转换vector(intn,constT&val =T()){resize(n,val);}vector(constvector<T>&v)// 拷贝构造函数 {reserve(v.size());for(auto&e :v){push_back(e);}}~vector()// 析构函数{delete[]_start;_start =_finish =_end_of_storage =nullptr;}
实现起来还是简单的vector——运算符重载
那我们的vector也应该支持 [ ] 的随机访问,我这里主要实现了 [ ]运算符重载还有赋值运算符重载
其中赋值运算符可是大有门道,复用函数在这里得到了很好的展现T&operator[](size_t i){assert(i <size());return_start[i];}constT&operator[](size_t i)const{assert(i <size());return_start[i];}// v1 = v3; vector<T>&operator=(constvector<T>&v)// 正常写法{if(this!=&v)// 判断是不是和本身一样{delete[]_start;// 释放this指针的_start_start =_finish =_end_of_storage =nullptr;// 再重新赋值reserve(v.size());// 扩容for(auto&e :v)//插入参数{push_back(e);}}return*this;}// 比起正常写法,不用那么麻烦,我们直接复用库函数的swapvoidswap(vector<T>&v)// 这个函数还可以用到两个对象 swap {std::swap(_start,v._start);// 直接把两个对象的变量交换 std::swap(_finish,v._finish);// 通过 swap 交换资源,避免手动管理内存std::swap(_end_of_storage,v._end_of_storage);}// v1 = v3;vector<T>&operator=(vector<T>v)// 现代写法 直接复用库函数的swap{// 这里不传引用 传临时参数 v3是不用修改的//this->swap(v);swap(v);return*this;}
vector——插入和删除函数
// 迭代器失效 voidinsert(iterator pos,constT&x){assert(pos >=_start);assert(pos <=_finish);// 满了就扩容,导致pos失效,失效后不能使用,更新后才能使用if(_finish ==_end_of_storage){size_t len =pos -_start;// 这里保留原来的长度, 在扩容之后,相当于保存了pos的位置reserve(capacity()==0?4:capacity()*2);// 不然pos位置会丢失pos =_start +len;}iterator it =_finish -1;while(it >=pos)// vector内容后移{*(it +1)=*it;--it;}*pos =x;++_finish;}iterator erase(iterator pos)// 删除函数{assert(pos >=_start);assert(pos <_finish);iterator it =pos +1;while(it <_finish)// vector内容前移 直接覆盖pos的位置{*(it -1)=*it;++it;}--_finish;returnpos;}
但是还是有一些问题的vector——实现过程的问题
引入第一个问题——迭代器失效迭代器失效
文章目录
#include<iostream>usingnamespacestd;#include<vector>intmain(){vector<int>v{1,2,3,4,5,6};autoit =v.begin();// 将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间,可能会引起扩容,而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值,可能会引起底层容量改变v.assign(100,8);/* 出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉 而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时 实际操作的是一块已经被释放的空间,而引起代码运行时崩溃。
如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝
因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。