目录一 vector的介绍及使用1、vector的介绍2、vector的使用二 vector在OJ中的使用三 vector深度剖析及模拟实现一、vector的介绍及使用1、vector的介绍std::vector是动态顺序数组底层是一块连续堆内存会自动扩容下标随机访问O(1)2、vector的使用1.2.1 vector的构造可以不传参构造可以构造并初始化n个valval类型是第一个模板参数可拷贝构造可使用迭代器进行初始化构造//无参构造vectorintv1;vectorstringv2;//构造并初始化n个valvectorintv3(10,1);//拷贝构造vectorintv4(v3);//用迭代器初始化构造vectorintv5(v3.begin(),v3.end());1.2.2 vector iterator的使用这里vector的迭代器与string的迭代器大致相同而且由于范围for底层有迭代器实现所以范围for也适用于vector//initializer_list也可以用来初始化vector,initializer_list有迭代器//{...}先传给initializer_list再用范围for将里面的值赋值到v中vectorintv{1,2,3,4,5,6,7,8,9,10};constvectorintconst_v{1,2,3};for(vectorint::iterator it1v.begin();it1!v.end();it1){cout*it1 ;}coutendl;for(vectorint::const_iterator it2const_v.begin();it2!const_v.end();it2){cout*it2 ;}coutendl;//倒着遍历for(vectorint::const_reverse_iterator it3const_v.crbegin();it3!const_v.crend();it3){cout*it3 ;}1.2.3 vector空间增长问题size_type size() const;获取数据个数size_type capacity() const;获取容量大小bool empty() const;判断是否为空void resize (size_type n, value_type val value_type());改变vector的sizevoid reserve (size_type n);改变vector的capacity1.2.4 vector增删查改void push_back (const value_type val);尾插void pop_back();尾删template class InputIterator, class TInputIterator find (InputIterator first, InputIterator last, const T val);查找在算法模块不是vector的成员函数iterator insert (iterator position, const value_type val);在position位置前插入valiterator erase (iterator position);删除position位置数据void swap (vector x);交换两个vector的数据空间reference operator[] (size_type n);像数组一样访问vectorvectorintv;intold_capacityv.capacity();coutold_capacityendl;for(inti1;i100;i){v.push_back(i);if(v.capacity()!old_capacity){old_capacityv.capacity();coutold_capacityendl;}}v.insert(find(v.begin(),v.end(),10),{1,2});for(autoe:v){coute ;}coutendl;intnum;cinnum;v.erase(find(v.begin(),v.end(),num));for(autoe:v){coute ;}二、vector在OJ中的使用2.1 只出现一次的数字只出现一次的数字intsingleNumber(vectorintnums){//0与任何数异或的结果都是任何数intn0;for(autoe:nums){n^e;}returnn;}2.2 杨辉三角OJ杨辉三角OJvectorvectorintgenerate(intnumRows){vectorvectorintvv;vv.resize(numRows,vectorint());for(inti0;inumRows;i){vv[i].resize(i1,1);}//从第三行第二列开始初始化for(inti2;ivv.size();i){for(intj1;jvv[i].size()-1;j)vv[i][j]vv[i-1][j]vv[i-1][j-1];}returnvv;}2.3 删除排序数组中的重复项删除排序数组中的重复项intremoveDuplicates(vectorintnums){if(nums.size()1)return1;intdst0,src1;while(srcnums.size()){if(nums[src]nums[dst])nums[dst]nums[src];src;}returndst1;}2.4 只出现一次的数II只出现一次的数IIintsingleNumber(vectorintnums){mapint,intmp;for(constautoe:nums){mp[e];}intans;for(autot:mp){if(t.second1){anst.first;break;}}returnans;}2.5 只出现一次的数字III只出现一次的数字IIIvectorintsingleNumber(vectorintnums){vectorintans;mapint,intmp;for(autoe:nums){mp[e];}intcnt0;for(autot:mp){if(t.second1){ans.push_back(t.first);cnt;}if(cnt2)break;}returnans;}2.6 数组中出现次数超过一半的数字数组中出现次数超过一半的数字intMoreThanHalfNum_Solution(vectorintnumbers){// write code heresort(numbers.begin(),numbers.end());returnnumbers[numbers.size()/2];}2.7 电话号码字母组合电话号码字母组合classSolution{public:vectorstringans;string ret;vectorvectorcharvv{{a,b,c},{d,e,f},{g,h,i},{j,k,l},{m,n,o},{p,q,r,s},{t,u,v},{w,x,y,z}};voiddfs(stringdigits,intpos){if(posdigits.size()){ans.push_back(ret);return;}intndigits[pos]-2;for(intj0;jvv[n].size();j){ret.push_back(vv[n][j]);dfs(digits,pos1);ret.pop_back();}}vectorstringletterCombinations(string digits){dfs(digits,0);returnans;}};三 vector深度剖析及模拟实现迭代器失效问题迭代器的主要作用就是让算法能够不关心底层数据结构其底层实际是一个指针。因此迭代器失效实际是迭代器底层对应指针指向的空间被销毁了使用一块已经被销毁的空间会使程序崩溃。1.会使迭代器失效的操作有会引起其底层空间改变的操作都有可能使迭代器失效比如resize、reserve、insert、assign、push_back等2.erase操作在vs环境下会对失效的迭代器进行严格检查所以在erase操作后应更新迭代器。而在Linux下g对迭代器失效检测并不非常严格但为保证代码的可移植性最好要更新迭代器3.与vector类似string在进行插入扩容操作后迭代器也会失效扩容时将原数据拷贝进新空间时的操作不能使用memcpy因为当vector中存储的是自定义类型时如string类型memcpy只会进行浅拷贝将存储数据的_str地址拷贝过来而释放原空间资源时_str已被销毁因此要调用深拷贝的拷贝构造将原数据拷贝进新空间。vector.h:#pragmaonce#includeiostream#includecassert#includeutility#includestring#includetype_traitsusingnamespacestd;namespacemyspace{templateclassTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorcbegin(){return_start;}const_iteratorcend(){return_finish;}vector()default;vector(vectorTv){reserve(v.capacity());for(autoe:v){*_finishe;_finish;}}vector(initializer_listTil){reserve(il.size());for(autoe:il){push_back(e);}}templateclassInputIterator,classtypenameenable_if!is_integralInputIterator::value::typevector(InputIterator first,InputIterator last){iterator itfirst;while(it!last){push_back(*it);it;}}vector(size_t n,constTvalT()){reserve(n);while(_finish!_startn){*_finishval;_finish;}}~vector(){delete[]_start;_finish_endofstorage_startnullptr;}vectorToperator(vectorTtmp){swap(tmp);return*this;}size_tsize(){return_finish-_start;}size_tcapacity(){return_endofstorage-_start;}voidreserve(size_t n){if(ncapacity()){size_t old_sizesize();T*tmpnewT[n];for(size_t i0;iold_size;i){tmp[i]_start[i];}delete[]_start;_starttmp;_finish_startold_size;_endofstorage_startn;}}voidresize(size_t n,constTxT()){if(nsize()){reserve(n);while(size()n){*_finishx;_finish;}}else{_finish_startn;}}constToperator[](size_t pos)const{assert(possize());return_start[pos];}Toperator[](size_t pos){assert(possize());return_start[pos];}boolempty(){return_finish_start;}voidpush_back(constTx){if(_finish_endofstorage){reserve(capacity()0?4:capacity()*2);}*_finishx;_finish;}voidpop_back(){assert(size()0);--_finish;}iteratorinsert(iterator pos,constTval){assert(pos_start);assert(pos_finish);if(_finish_endofstorage){intsubpos-_start;reserve(capacity()0?4:capacity()*2);pos_startsub;}iterator end_finish;while(end!pos){*end*(end-1);end--;}*posval;_finish;returnpos;}iteratorerase(iterator pos){assert(pos_start);assert(pos_finish);iterator endpos;while(end!_finish-1){*end*(end1);end;}--_finish;returnpos;}voidclear(){_finish_start;}voidswap(vectorv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}private:T*_startnullptr;T*_finishnullptr;T*_endofstoragenullptr;};}test.cpp:#includevector.hnamespacemyspace{templateclassContainervoidPrint(Containerv){for(autoe:v){coute ;}coutendl;}voidtest01(){vectorintv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.pop_back();vectorintv2{1,2,3,4,5,6};v2.insert(v2.begin()3,100);Print(v);Print(v2);//删除v2中的偶数for(vectorint::iterator itv2.begin();it!v2.end();){if((*it)%20){//防止it迭代器失效要更新迭代器itv2.erase(it);}elseit;}Print(v2);vectorintv3(v2.begin(),v2.end()-1);Print(v3);vectorintv4(5,5);Print(v4);v4v3;Print(v4);coutv4.size()endl;v4.resize(10);coutv4.size()endl;}voidtest02(){vectorstringv;v.push_back(11111);v.push_back(11111);v.push_back(11111);v.push_back(11111);v.push_back(11111);Print(v);}}intmain(){myspace::test02();return0;}
目录一 vector的介绍及使用1、vector的介绍2、vector的使用二 vector在OJ中的使用三 vector深度剖析及模拟实现一、vector的介绍及使用1、vector的介绍std::vector是动态顺序数组底层是一块连续堆内存会自动扩容下标随机访问O(1)2、vector的使用1.2.1 vector的构造可以不传参构造可以构造并初始化n个valval类型是第一个模板参数可拷贝构造可使用迭代器进行初始化构造//无参构造vectorintv1;vectorstringv2;//构造并初始化n个valvectorintv3(10,1);//拷贝构造vectorintv4(v3);//用迭代器初始化构造vectorintv5(v3.begin(),v3.end());1.2.2 vector iterator的使用这里vector的迭代器与string的迭代器大致相同而且由于范围for底层有迭代器实现所以范围for也适用于vector//initializer_list也可以用来初始化vector,initializer_list有迭代器//{...}先传给initializer_list再用范围for将里面的值赋值到v中vectorintv{1,2,3,4,5,6,7,8,9,10};constvectorintconst_v{1,2,3};for(vectorint::iterator it1v.begin();it1!v.end();it1){cout*it1 ;}coutendl;for(vectorint::const_iterator it2const_v.begin();it2!const_v.end();it2){cout*it2 ;}coutendl;//倒着遍历for(vectorint::const_reverse_iterator it3const_v.crbegin();it3!const_v.crend();it3){cout*it3 ;}1.2.3 vector空间增长问题size_type size() const;获取数据个数size_type capacity() const;获取容量大小bool empty() const;判断是否为空void resize (size_type n, value_type val value_type());改变vector的sizevoid reserve (size_type n);改变vector的capacity1.2.4 vector增删查改void push_back (const value_type val);尾插void pop_back();尾删template class InputIterator, class TInputIterator find (InputIterator first, InputIterator last, const T val);查找在算法模块不是vector的成员函数iterator insert (iterator position, const value_type val);在position位置前插入valiterator erase (iterator position);删除position位置数据void swap (vector x);交换两个vector的数据空间reference operator[] (size_type n);像数组一样访问vectorvectorintv;intold_capacityv.capacity();coutold_capacityendl;for(inti1;i100;i){v.push_back(i);if(v.capacity()!old_capacity){old_capacityv.capacity();coutold_capacityendl;}}v.insert(find(v.begin(),v.end(),10),{1,2});for(autoe:v){coute ;}coutendl;intnum;cinnum;v.erase(find(v.begin(),v.end(),num));for(autoe:v){coute ;}二、vector在OJ中的使用2.1 只出现一次的数字只出现一次的数字intsingleNumber(vectorintnums){//0与任何数异或的结果都是任何数intn0;for(autoe:nums){n^e;}returnn;}2.2 杨辉三角OJ杨辉三角OJvectorvectorintgenerate(intnumRows){vectorvectorintvv;vv.resize(numRows,vectorint());for(inti0;inumRows;i){vv[i].resize(i1,1);}//从第三行第二列开始初始化for(inti2;ivv.size();i){for(intj1;jvv[i].size()-1;j)vv[i][j]vv[i-1][j]vv[i-1][j-1];}returnvv;}2.3 删除排序数组中的重复项删除排序数组中的重复项intremoveDuplicates(vectorintnums){if(nums.size()1)return1;intdst0,src1;while(srcnums.size()){if(nums[src]nums[dst])nums[dst]nums[src];src;}returndst1;}2.4 只出现一次的数II只出现一次的数IIintsingleNumber(vectorintnums){mapint,intmp;for(constautoe:nums){mp[e];}intans;for(autot:mp){if(t.second1){anst.first;break;}}returnans;}2.5 只出现一次的数字III只出现一次的数字IIIvectorintsingleNumber(vectorintnums){vectorintans;mapint,intmp;for(autoe:nums){mp[e];}intcnt0;for(autot:mp){if(t.second1){ans.push_back(t.first);cnt;}if(cnt2)break;}returnans;}2.6 数组中出现次数超过一半的数字数组中出现次数超过一半的数字intMoreThanHalfNum_Solution(vectorintnumbers){// write code heresort(numbers.begin(),numbers.end());returnnumbers[numbers.size()/2];}2.7 电话号码字母组合电话号码字母组合classSolution{public:vectorstringans;string ret;vectorvectorcharvv{{a,b,c},{d,e,f},{g,h,i},{j,k,l},{m,n,o},{p,q,r,s},{t,u,v},{w,x,y,z}};voiddfs(stringdigits,intpos){if(posdigits.size()){ans.push_back(ret);return;}intndigits[pos]-2;for(intj0;jvv[n].size();j){ret.push_back(vv[n][j]);dfs(digits,pos1);ret.pop_back();}}vectorstringletterCombinations(string digits){dfs(digits,0);returnans;}};三 vector深度剖析及模拟实现迭代器失效问题迭代器的主要作用就是让算法能够不关心底层数据结构其底层实际是一个指针。因此迭代器失效实际是迭代器底层对应指针指向的空间被销毁了使用一块已经被销毁的空间会使程序崩溃。1.会使迭代器失效的操作有会引起其底层空间改变的操作都有可能使迭代器失效比如resize、reserve、insert、assign、push_back等2.erase操作在vs环境下会对失效的迭代器进行严格检查所以在erase操作后应更新迭代器。而在Linux下g对迭代器失效检测并不非常严格但为保证代码的可移植性最好要更新迭代器3.与vector类似string在进行插入扩容操作后迭代器也会失效扩容时将原数据拷贝进新空间时的操作不能使用memcpy因为当vector中存储的是自定义类型时如string类型memcpy只会进行浅拷贝将存储数据的_str地址拷贝过来而释放原空间资源时_str已被销毁因此要调用深拷贝的拷贝构造将原数据拷贝进新空间。vector.h:#pragmaonce#includeiostream#includecassert#includeutility#includestring#includetype_traitsusingnamespacestd;namespacemyspace{templateclassTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorcbegin(){return_start;}const_iteratorcend(){return_finish;}vector()default;vector(vectorTv){reserve(v.capacity());for(autoe:v){*_finishe;_finish;}}vector(initializer_listTil){reserve(il.size());for(autoe:il){push_back(e);}}templateclassInputIterator,classtypenameenable_if!is_integralInputIterator::value::typevector(InputIterator first,InputIterator last){iterator itfirst;while(it!last){push_back(*it);it;}}vector(size_t n,constTvalT()){reserve(n);while(_finish!_startn){*_finishval;_finish;}}~vector(){delete[]_start;_finish_endofstorage_startnullptr;}vectorToperator(vectorTtmp){swap(tmp);return*this;}size_tsize(){return_finish-_start;}size_tcapacity(){return_endofstorage-_start;}voidreserve(size_t n){if(ncapacity()){size_t old_sizesize();T*tmpnewT[n];for(size_t i0;iold_size;i){tmp[i]_start[i];}delete[]_start;_starttmp;_finish_startold_size;_endofstorage_startn;}}voidresize(size_t n,constTxT()){if(nsize()){reserve(n);while(size()n){*_finishx;_finish;}}else{_finish_startn;}}constToperator[](size_t pos)const{assert(possize());return_start[pos];}Toperator[](size_t pos){assert(possize());return_start[pos];}boolempty(){return_finish_start;}voidpush_back(constTx){if(_finish_endofstorage){reserve(capacity()0?4:capacity()*2);}*_finishx;_finish;}voidpop_back(){assert(size()0);--_finish;}iteratorinsert(iterator pos,constTval){assert(pos_start);assert(pos_finish);if(_finish_endofstorage){intsubpos-_start;reserve(capacity()0?4:capacity()*2);pos_startsub;}iterator end_finish;while(end!pos){*end*(end-1);end--;}*posval;_finish;returnpos;}iteratorerase(iterator pos){assert(pos_start);assert(pos_finish);iterator endpos;while(end!_finish-1){*end*(end1);end;}--_finish;returnpos;}voidclear(){_finish_start;}voidswap(vectorv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}private:T*_startnullptr;T*_finishnullptr;T*_endofstoragenullptr;};}test.cpp:#includevector.hnamespacemyspace{templateclassContainervoidPrint(Containerv){for(autoe:v){coute ;}coutendl;}voidtest01(){vectorintv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.pop_back();vectorintv2{1,2,3,4,5,6};v2.insert(v2.begin()3,100);Print(v);Print(v2);//删除v2中的偶数for(vectorint::iterator itv2.begin();it!v2.end();){if((*it)%20){//防止it迭代器失效要更新迭代器itv2.erase(it);}elseit;}Print(v2);vectorintv3(v2.begin(),v2.end()-1);Print(v3);vectorintv4(5,5);Print(v4);v4v3;Print(v4);coutv4.size()endl;v4.resize(10);coutv4.size()endl;}voidtest02(){vectorstringv;v.push_back(11111);v.push_back(11111);v.push_back(11111);v.push_back(11111);v.push_back(11111);Print(v);}}intmain(){myspace::test02();return0;}
