STL之vector刨析

vector的使用(常用接口)Member functionsConstruct vector(构造)voidtest01(){//构造1;无参构造vectorintv1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//构造2:10个1vectorintv2(10,1);//构造3:迭代器区间vectorintv3(v1.begin(),v1.end());}//拷贝构造4:vectorintv4(v1);//initializer_list(C11语法)vectorintv5{1,2,3,4,5};Iterators(迭代器)beginendCapacitysizereserve(扩容)预定空间但不改变 sizevectorintv(10,1);// size10, capacity10v.reserve(20);// 申请至少能容纳20个元素的空间coutv.size()endl;// 输出 10size 不变coutv.capacity()endl;// 输出 20reserve(n) 只会增大 capacity不会添加元素所以 size 不变。如果你提前知道要存多少数据用 reserve 一次性开好空间可以避免多次扩容带来的拷贝开销提升性能。reserve 不会缩容v.reserve(5);// 试图缩小容量coutv.capacity()endl;// 依然是 20不会变小resizeresize改变 size可能引发扩容vectorintv(10,1);v.resize(30,2);// 增加到30个元素新增的元素用 2 填充coutv.size()endl;// 30coutv.capacity()endl;// 30可能触发了扩容v.resize(5);// 减少到5个元素多出的被删除coutv.size()endl;// 5coutv.capacity()endl;// 容量不变不会缩容capacityvoidtest02(){vectorintv1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//遍历1:[]for(size_t i0;iv1.size();i){coutv1[i] ;}coutendl;//范围forfor(autoe:v1){coute ;}coutendl;//迭代器vectorint::iterator itv1.begin();while(it!v1.end()){cout*it ;it;}coutendl;}voidtest03(){vectorintv1(10,1);size_t oldv1.capacity();coutoldendl;for(size_t i0;i100;i){v1.push_back(i);if(v1.capacity()!old){coutv1.capacity()endl;oldv1.capacity();}}//1.5倍扩容//reservev1.reserve(100);//不会缩容//resize(3种情况):与string类似}Element accessoperator越界检查:断言报错at越界检查:抛异常front作用:取第一个数据back作用: 取最后一个数据data作用返回指向 vector 底层连续数组首元素的普通指针 T*Modifierspush_backpop_backinserterasevoidtest04(){vectorintv1(10,1);//push_backv1.push_back(100);//insert//迭代器v1.insert(v1.begin(),1000);//效率低下v1.insert(v1.begin()3,1000);//在下标为3的位置插入//在指定值前插入//find(使用算法库里面的)autoitstd::find(v1.begin(),v1.end(),100);if(it!v1.end()){v1.insert(it,33);}for(autoe:v1){coute ;}coutendl;//erase//头删v1.erase(v1.begin());//删除指定值intx;cinx;auto_itstd::find(v1.begin(),v1.end(),x);if(_it!v1.end()){v1.erase(_it);}for(autoe:v1){coute ;}coutendl;}特殊语法vector vector 作用:动态开辟二维数组//动态开辟二维数组intnumRows;vectorvectorintvv;vv.resize(numRows,vectorint());for(size_t i0;inumRows;i){vv[i].resize(i1,1);}vector的模拟实现(模板:声明和定义不能分离到两个文件)vector.h#define_CRT_SECURE_NO_WARNINGS#pragmaonce#includeiostream#includeassert.husingnamespacestd;//模板:声明和定义不能分离到两个文件namespacemySTL{templateclassTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;//构造函数vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//拷贝构造vector(constvectorTv){reserve(v.capacity());for(autoe:v){push_back(e);}}//initializer_listvector(initializer_listTil){reserve(il.size());for(autoe:il){push_back(e);}}//迭代器区间构造/*vector(iterator first, iterator last) { while (first ! last) { push_back(*(first)); first; } }*///函数模板//任意类型容器迭代器初始化templateclassInputIteratorvector(InputIterator first,InputIterator last){while(first!last){push_back(*(first));first;}}//n个val构造/*vector(size_t n, T valT()) { resize(n,val); } *///匹配不上//swapvoidswap(vectorTv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);}//vectorToperator(vectorTv){swap(v);return*this;}//扩容voidreserve(size_t n){if(ncapacity()){size_t old_sizesize();//保存旧空间大小,_finish计算要用T*tmpnewT[n];//拷贝旧空间数据到新空间if(_start){//memcpy(tmp, _start, size() * sizeof(T));//无法完成深层次的深拷贝for(size_t i0;iold_size;i){tmp[i]_start[i];//对于string这种类型,赋值调用operator完成深拷贝//对于int,赋值完成浅拷贝}delete[]_start;}_starttmp;_finish_startold_size;_end_of_storage_startn;}}//sizesize_tsize()const{return_finish-_start;}//capacutysize_tcapacity()const{return_end_of_storage-_start;}//[]Toperator[](size_t pos){assert(possize());return_start[pos];}constToperator[](size_t pos)const{assert(possize());return_start[pos];}//迭代器iteratorbegin(){return_start;}const_iteratorbegin()const{return_start;}iteratorend(){return_finish;}const_iteratorend()const{return_finish;}//判空boolempty()const{return_start_finish;}//push_backvoidpush_back(constTx){if(_finish_end_of_storage){reserve(capacity()0?4:2*capacity());}*_finishx;_finish;}//存在浅拷贝问题//memcpy不能深层次深拷贝(string)这种类型//pop_backvoidpop_back(){assert(!empty());--_finish;}//insertvoidinsert(iterator pos,constTx){assert(pos_start);assert(pos_finish);//下面扩容后,可能会发生迭代器失效if(_finish_end_of_storage){size_t newcapacitycapacity()0?4:capacity()*2;reserve(newcapacity);//解决方法就是使用reserve提前扩容size_t lenpos-_start;pos_startlen;}iterator end_finish-1;while(endpos){*(end1)*(end);--end;}*posx;_finish;}//clearvoidclear(){_finish_start;}//eraseiteratorerase(iterator pos){assert(pos_start);assert(pos_finish);//挪动数据iterator startpos;while(start1!_finish){*(start)*(start1);start;}_finish--;returnpos;}//resizevoidresize(size_t n,T valT()){if(nsize()){reserve(n);while(_finish!_startn){*(_finish)val;_finish;}}else{_finish_startn;}}//~vector~vector(){if(_start){delete[]_start;_start_finish_end_of_storagenullptr;}}private:iterator _startnullptr;iterator _finishnullptr;iterator _end_of_storagenullptr;};}test.cpp#define_CRT_SECURE_NO_WARNINGS#includevector.htemplateclassContinervoidPrint(constContinerv){for(autoe:v){coute ;}coutendl;}namespacemySTL{voidtest01(){vectorintv;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.pop_back();v.insert(v.end(),88);//在指定值前插入intx;cinx;autoitfind(v.begin(),v.end(),x);if(it!v.end()){v.insert(it,x*10);//it失效?这里it能否继续使用?不能//扩容会导致it失效,但是C标准没有规定vector扩容规则//*it1000;(不要继续使用)}Print(v);v.erase(v.begin());Print(v);//在指定值前删除inty;ciny;auto_itfind(v.begin(),v.end(),y);if(_it!v.end()){v.erase(_it);//it失效?这里it能否继续使用?不能//失效//erase 操作导致元素向前移动pos之后所有元素位置发生变化旧迭代器指向的语义不再合法。标准直接禁止继续使用防止产生难以察觉的 BUG。//库里面有返回值,返回删除位置的下一个位置(更新)}Print(v);v.resize(10);Print(v);vectorintv2{1,2,3,4,5,6,7,8,9,0};Print(v2);vectorintv3(v2.begin()1,v2.end());Print(v3);//vectorint v4(10, 1);//Print(v4);vectorintv5v3;Print(v5);}voidtest02(){vectorstringv1;v1.push_back(hello word);Print(v1);}}intmain(){//mySTL::test01();mySTL::test02();}