vector1、vector的介绍vector是数组大小可变化的序列容器就像数组一样vector使用连续的存储空间来存储元素可以采用下标对vector的元素进行访问他的大小是可以动态改变的vector可能会分配一些额外的存储空间以适应可能的生长因此实际容量可能大于严格容纳其元素所需的容量与数组相比vector消耗更多内存以换取高效管理和动态增长的能力与其他动态序列容器(deques, lists and forward_lists)相比向量访问其元素非常高效对于涉及在非末尾位置插入或移除元素的操作它们的性能不如其他操作且迭代器和引用的一致性不如list和forward_lists。2、vector的使用2.1 vector的定义(constructor) 构造函数声明接口说明vector() 重点无参构造vector (size_type n, const value_type val value_type())构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造size_type表示无符号整形value是第一个模板参数使用迭代器区间的构造函数是函数模板vectorintfirst;vectorintsecond(4,100);vectorintthird(second.begin(),second.end());vectorintfourth(third);intmyints[]{16,2,77,29};vectorintfifth(myints,myintssizeof(myints)/sizeof(int));coutThe contents of fifth are:;for(vectorint::iterator itfifth.begin();it!fifth.end();it)cout *it;cout\n;2.2 vector iteratoriterator 的使用接口说明begin end重点获取第一个数据位置的 iterator/const_iterator获取最后一个数据的下一个位置的 iterator/const_iteratorrbegin rend获取最后一个数据位置的 reverse_iterator获取第一个数据前一个位置的 reverse_iterator迭代器遍历voidPrint(vectorintv){vectorint::iterator itv.begin();while(it!v.end()){cout*itendl;it;}coutendl;}2.3 vector空间增长问题容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize重点改变 vector 的 sizereserve重点改变 vector 的 capacitycapacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。voidTestVectorExpand(){size_tsz;vectorintv;szv.capacity();coutmaking v grow:\n;for(inti0;i100;i){v.push_back(i);if(sz!v.capacity()){szv.capacity();coutcapacity changed: sz\n;}}}在VS下的输出结果making foo grow:capacity changed: 1capacity changed: 2capacity changed: 3capacity changed: 4capacity changed: 6capacity changed: 9capacity changed: 13capacity changed: 19capacity changed: 28capacity changed: 42capacity changed: 63capacity changed: 94capacity changed: 141在Linux下的结果making v grow:capacity changed: 1capacity changed: 2capacity changed: 4capacity changed: 8capacity changed: 16capacity changed: 32capacity changed: 64capacity changed: 128由于VS在扩容时按大约1.5倍扩容所以如果知道vector中存储元素的大概个数可以提前将空间设置足够避免边插入边扩容导致效率低下voidTestVectorExpandOP(){vectorintv;size_tszv.capacity();v.reserve(100);// 提前将容量设置好可以避免一遍插入一遍扩容coutmaking bar grow:\n;for(inti0;i100;i){v.push_back(i);if(sz!v.capacity()){szv.capacity();coutcapacity changed: sz\n;}}}2.4 vector增删查改vector 增删查改接口说明push_back重点尾插pop_back重点尾删find查找。注意这个是算法模块实现不是 vector 的成员接口insert在 position 之前插入 valerase删除 position 位置的数据swap交换两个 vector 的数据空间operator[]重点像数组一样访问注意reserve只改变vector的capacity不改变sizeeg:intmain(){vectorintv;// 一开始size0capacity0cout初始sizev.size() capacityv.capacity()endl;// 调用 reserve(100) —— 只改容量v.reserve(100);// 重点size 还是 0capacity 变成 100coutreserve(100)后sizev.size() capacityv.capacity()endl;return0;}正确做法是把reserve改成resizeresize会改变size的大小如果使用reserve插入数据时需要使用push_back2.5 vector和string的区别vector插入时结尾没有\0string插入后结尾有\0string可以实现一个字符串vector一次只能插入一个字符串3、vector的模拟实现3.1 成员变量public:typedefT*iterator;typedefconstT*const_iterator;private:iterator _start;iterator _finish;iterator _endofstorage;3.2 成员函数3.2.1 构造函数和析构函数vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}vector(size_tn,constTvalT()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){resize(n,val);}vector(intn,constTvalT()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){resize(n,val);}vector(initializer_listTil):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(il.size());for(autoe:il){push_back(e);}}templateclass InputIteratorvector(InputIterator first,InputIterator last){while(first!last){push_back(*first);first;}}//强制编译器生成默认构造vector()default;//析构函数~vector(){if(_start){delete[]_start;_start_finish_endofstoragenullptr;}}迭代器区间初始化采用的是函数模板可能会有不同类型的迭代器必须要提供vector(int n, const T val T())如果没有这个构造函数vector v(10, 20)就会选择最匹配的vector(size_t n, const T val T())构造函数但10被认为是int型和size_t匹配不上因此会和迭代器区间初始化函数进行匹配不符合逻辑所以要对int型单独提供一个构造函数vector(initializer_list il)构造函数作用是可以用vector v {1,2,3,4};这种花括号方式初始化对象il就是接受这串数据的变量名最后用尾插把元素x添加到vector的末尾vector() default;是强制编译器生成默认构造3.2.2 拷贝构造vector(initializer_listTil):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(il.size());for(autoe:il){push_back(e);}}vector(constvectorTv):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(v.capacity());for(autoe:v){push_back(e);}}vector(const vectorT v)作用是用一个已有的vector对象v来创建一个新的vector对象这里涉及深拷贝浅拷贝是只复制指针地址不复制实际数据修改时会互相影响深拷贝不仅复制指针还复制指针指向的全部数据给新对象开辟一块独立的内存空间修改时互不影响3.2.3 operatorvoidswap(vectorTv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}// v1 v7vectorToperator(vectorTv){swap(v);return*this;}3.2.4 sizesize_tsize()const{return_finish-_start;}3.2.5 capacitysize_tcapacity()const{return_endofstorage-_start;}3.2.6 迭代器iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}加const后迭代器只读不会意外修改const对象3.2.7 reservevoidreserve(size_tn){if(ncapacity()){size_told_sizesize();T*tmpnew T[n];// 拷贝旧空间数据到新空间if(_start){memcpy(tmp,_start,sizeof(T)*old_size);delete[]_start;}_starttmp;_finish_startold_size;_endofstorage_startn;}}注意关于old_size因为拷贝旧空间后被释放所以需要重新设置_start的位置同时需要更新_finish和_endofstorage更新_start后_start指向新空间的开头而_finish指向旧空间的结尾此时调用size()计算出的结果有问题所以需要先将旧空间的size()保存一份关于拷贝数据的方式memcpy是逐字节的拷贝数据是浅拷贝当执行delete[] _start;销毁空间时会影响到新空间所以用for循环实现深拷贝修改后voidreserve(size_tn){if(ncapacity()){size_told_sizesize();T*tmpnew T[n];// 拷贝旧空间数据到新空间 迭代器失效if(_start){//memcpy(tmp, _start, sizeof(T) * old_size);for(size_ti0;iold_size;i){tmp[i]_start[i];}delete[]_start;}_starttmp;// 更新_start更新新内存的起始位置_finish_startold_size;_endofstorage_startn;}}修改后执行tmp[i] _start[i];会调用赋值运算符重载进行深拷贝3.2.8 resizevoidresize(size_tn,T valT()){if(nsize()){reserve(n);while(_finish!_startn){*_finishval;_finish;}}else{_finish_startn;}}3.2.9 operator[]Toperator[](size_ti){assert(isize());return_start[i];}constToperator[](size_ti)const//只读{assert(isize());return_start[i];}3.2.10 insert迭代器失效问题iteratorinsert(iterator pos,constTx){assert(pos_start);assert(pos_finish);//检查容量if(_finish_endofstorage){size_tlenpos-_start;reserve(capacity()0?4:capacity()*2);// 更新pospos_startlen;}iterator end_finish-1;while(endpos){*(end1)*end;--end;}*posx;_finish;returnpos;}再进行insert操作时会引发迭代器失效需要将pos重新移动位置在pos位置插入一个数据时pos是一个迭代器首先检查容量进行扩容在reserve后_start、_finish、_endofstorage都指向了新空间旧空间被释放而pos指向的还是原来空间的某个位置此时pos成为野指针造成非法访问为了解决这个问题可以先保存pos的相对位置扩容后再更新pos3.2.11 erase迭代器失效问题iteratorerase(iterator pos){assert(pos_start);assert(pos_finish);// 挪动数据iterator itpos1;while(it!_finish){*(it-1)*it;it;}--_finish;returnpos;}erase删除pos位置的元素后导致缩容pos位置之后的元素会往前移动使pos指向已释放的空间使迭代器失效因此采用返回值的方式返回pos位置下一个位置的元素3.2.12 push_backvoidpush_back(constTx){if(_finish_endofstorage){reserve(capacity()0?4:capacity()*2);}*_finishx;_finish;}先检查扩容再插入元素最后移动指针3.2.13 pop_backvoidpop_back(){//assert(_finish _start);assert(!empty());--_finish;}3.2.14 clearvoidclear(){_finish_start;}3.2.15 emptyboolempty()const{return_start_finish;}如果文章中有错误或不足欢迎大家指正交流。
【C++】vector类
vector1、vector的介绍vector是数组大小可变化的序列容器就像数组一样vector使用连续的存储空间来存储元素可以采用下标对vector的元素进行访问他的大小是可以动态改变的vector可能会分配一些额外的存储空间以适应可能的生长因此实际容量可能大于严格容纳其元素所需的容量与数组相比vector消耗更多内存以换取高效管理和动态增长的能力与其他动态序列容器(deques, lists and forward_lists)相比向量访问其元素非常高效对于涉及在非末尾位置插入或移除元素的操作它们的性能不如其他操作且迭代器和引用的一致性不如list和forward_lists。2、vector的使用2.1 vector的定义(constructor) 构造函数声明接口说明vector() 重点无参构造vector (size_type n, const value_type val value_type())构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造size_type表示无符号整形value是第一个模板参数使用迭代器区间的构造函数是函数模板vectorintfirst;vectorintsecond(4,100);vectorintthird(second.begin(),second.end());vectorintfourth(third);intmyints[]{16,2,77,29};vectorintfifth(myints,myintssizeof(myints)/sizeof(int));coutThe contents of fifth are:;for(vectorint::iterator itfifth.begin();it!fifth.end();it)cout *it;cout\n;2.2 vector iteratoriterator 的使用接口说明begin end重点获取第一个数据位置的 iterator/const_iterator获取最后一个数据的下一个位置的 iterator/const_iteratorrbegin rend获取最后一个数据位置的 reverse_iterator获取第一个数据前一个位置的 reverse_iterator迭代器遍历voidPrint(vectorintv){vectorint::iterator itv.begin();while(it!v.end()){cout*itendl;it;}coutendl;}2.3 vector空间增长问题容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize重点改变 vector 的 sizereserve重点改变 vector 的 capacitycapacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。voidTestVectorExpand(){size_tsz;vectorintv;szv.capacity();coutmaking v grow:\n;for(inti0;i100;i){v.push_back(i);if(sz!v.capacity()){szv.capacity();coutcapacity changed: sz\n;}}}在VS下的输出结果making foo grow:capacity changed: 1capacity changed: 2capacity changed: 3capacity changed: 4capacity changed: 6capacity changed: 9capacity changed: 13capacity changed: 19capacity changed: 28capacity changed: 42capacity changed: 63capacity changed: 94capacity changed: 141在Linux下的结果making v grow:capacity changed: 1capacity changed: 2capacity changed: 4capacity changed: 8capacity changed: 16capacity changed: 32capacity changed: 64capacity changed: 128由于VS在扩容时按大约1.5倍扩容所以如果知道vector中存储元素的大概个数可以提前将空间设置足够避免边插入边扩容导致效率低下voidTestVectorExpandOP(){vectorintv;size_tszv.capacity();v.reserve(100);// 提前将容量设置好可以避免一遍插入一遍扩容coutmaking bar grow:\n;for(inti0;i100;i){v.push_back(i);if(sz!v.capacity()){szv.capacity();coutcapacity changed: sz\n;}}}2.4 vector增删查改vector 增删查改接口说明push_back重点尾插pop_back重点尾删find查找。注意这个是算法模块实现不是 vector 的成员接口insert在 position 之前插入 valerase删除 position 位置的数据swap交换两个 vector 的数据空间operator[]重点像数组一样访问注意reserve只改变vector的capacity不改变sizeeg:intmain(){vectorintv;// 一开始size0capacity0cout初始sizev.size() capacityv.capacity()endl;// 调用 reserve(100) —— 只改容量v.reserve(100);// 重点size 还是 0capacity 变成 100coutreserve(100)后sizev.size() capacityv.capacity()endl;return0;}正确做法是把reserve改成resizeresize会改变size的大小如果使用reserve插入数据时需要使用push_back2.5 vector和string的区别vector插入时结尾没有\0string插入后结尾有\0string可以实现一个字符串vector一次只能插入一个字符串3、vector的模拟实现3.1 成员变量public:typedefT*iterator;typedefconstT*const_iterator;private:iterator _start;iterator _finish;iterator _endofstorage;3.2 成员函数3.2.1 构造函数和析构函数vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}vector(size_tn,constTvalT()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){resize(n,val);}vector(intn,constTvalT()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){resize(n,val);}vector(initializer_listTil):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(il.size());for(autoe:il){push_back(e);}}templateclass InputIteratorvector(InputIterator first,InputIterator last){while(first!last){push_back(*first);first;}}//强制编译器生成默认构造vector()default;//析构函数~vector(){if(_start){delete[]_start;_start_finish_endofstoragenullptr;}}迭代器区间初始化采用的是函数模板可能会有不同类型的迭代器必须要提供vector(int n, const T val T())如果没有这个构造函数vector v(10, 20)就会选择最匹配的vector(size_t n, const T val T())构造函数但10被认为是int型和size_t匹配不上因此会和迭代器区间初始化函数进行匹配不符合逻辑所以要对int型单独提供一个构造函数vector(initializer_list il)构造函数作用是可以用vector v {1,2,3,4};这种花括号方式初始化对象il就是接受这串数据的变量名最后用尾插把元素x添加到vector的末尾vector() default;是强制编译器生成默认构造3.2.2 拷贝构造vector(initializer_listTil):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(il.size());for(autoe:il){push_back(e);}}vector(constvectorTv):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(v.capacity());for(autoe:v){push_back(e);}}vector(const vectorT v)作用是用一个已有的vector对象v来创建一个新的vector对象这里涉及深拷贝浅拷贝是只复制指针地址不复制实际数据修改时会互相影响深拷贝不仅复制指针还复制指针指向的全部数据给新对象开辟一块独立的内存空间修改时互不影响3.2.3 operatorvoidswap(vectorTv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}// v1 v7vectorToperator(vectorTv){swap(v);return*this;}3.2.4 sizesize_tsize()const{return_finish-_start;}3.2.5 capacitysize_tcapacity()const{return_endofstorage-_start;}3.2.6 迭代器iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}加const后迭代器只读不会意外修改const对象3.2.7 reservevoidreserve(size_tn){if(ncapacity()){size_told_sizesize();T*tmpnew T[n];// 拷贝旧空间数据到新空间if(_start){memcpy(tmp,_start,sizeof(T)*old_size);delete[]_start;}_starttmp;_finish_startold_size;_endofstorage_startn;}}注意关于old_size因为拷贝旧空间后被释放所以需要重新设置_start的位置同时需要更新_finish和_endofstorage更新_start后_start指向新空间的开头而_finish指向旧空间的结尾此时调用size()计算出的结果有问题所以需要先将旧空间的size()保存一份关于拷贝数据的方式memcpy是逐字节的拷贝数据是浅拷贝当执行delete[] _start;销毁空间时会影响到新空间所以用for循环实现深拷贝修改后voidreserve(size_tn){if(ncapacity()){size_told_sizesize();T*tmpnew T[n];// 拷贝旧空间数据到新空间 迭代器失效if(_start){//memcpy(tmp, _start, sizeof(T) * old_size);for(size_ti0;iold_size;i){tmp[i]_start[i];}delete[]_start;}_starttmp;// 更新_start更新新内存的起始位置_finish_startold_size;_endofstorage_startn;}}修改后执行tmp[i] _start[i];会调用赋值运算符重载进行深拷贝3.2.8 resizevoidresize(size_tn,T valT()){if(nsize()){reserve(n);while(_finish!_startn){*_finishval;_finish;}}else{_finish_startn;}}3.2.9 operator[]Toperator[](size_ti){assert(isize());return_start[i];}constToperator[](size_ti)const//只读{assert(isize());return_start[i];}3.2.10 insert迭代器失效问题iteratorinsert(iterator pos,constTx){assert(pos_start);assert(pos_finish);//检查容量if(_finish_endofstorage){size_tlenpos-_start;reserve(capacity()0?4:capacity()*2);// 更新pospos_startlen;}iterator end_finish-1;while(endpos){*(end1)*end;--end;}*posx;_finish;returnpos;}再进行insert操作时会引发迭代器失效需要将pos重新移动位置在pos位置插入一个数据时pos是一个迭代器首先检查容量进行扩容在reserve后_start、_finish、_endofstorage都指向了新空间旧空间被释放而pos指向的还是原来空间的某个位置此时pos成为野指针造成非法访问为了解决这个问题可以先保存pos的相对位置扩容后再更新pos3.2.11 erase迭代器失效问题iteratorerase(iterator pos){assert(pos_start);assert(pos_finish);// 挪动数据iterator itpos1;while(it!_finish){*(it-1)*it;it;}--_finish;returnpos;}erase删除pos位置的元素后导致缩容pos位置之后的元素会往前移动使pos指向已释放的空间使迭代器失效因此采用返回值的方式返回pos位置下一个位置的元素3.2.12 push_backvoidpush_back(constTx){if(_finish_endofstorage){reserve(capacity()0?4:capacity()*2);}*_finishx;_finish;}先检查扩容再插入元素最后移动指针3.2.13 pop_backvoidpop_back(){//assert(_finish _start);assert(!empty());--_finish;}3.2.14 clearvoidclear(){_finish_start;}3.2.15 emptyboolempty()const{return_start_finish;}如果文章中有错误或不足欢迎大家指正交流。
