STL vector底层揭秘：从构造到迭代器失效

STL:一篇带你搞懂vectorvector底层实现1.constructor与destructor2.迭代3.capacity4.modifier4.1 push_back4.4 pop_back4.3 insert4.4 erase5.access [ ]vector底层实现1.constructor与destructorvector的构造包括默认构造普通的构造函数、拷贝构造以及使用迭代区间进行构造。下面我们逐一分析这几种构造方式。vector(){_start_finishnullptr;_end_of_storagenullptr;}vector(intn,constTvalT()){for(inti0;in;i){push_back(val);}}templateclassInputiteratorvector(Inputiterator first,Inputiterator last){Inputiterator beginfirst;while(begin!last){push_back(*begin);begin;}}vector(constvectorTv){for(autoe:v){push_back(e);}}voidswap(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;}~vector(){delete[]_start;_start_finish_end_of_storagenullptr;}这里要着重说一下T,它对于内置类型自动初始化为0对于自定义类型会调用自己的默认构造。赋值操作采用现代写法交换地址同时重载函数的参数并没有使用引用这样可以在调用完重载函数自动实现对资源的释放。2.迭代vector的底层本身就是数组所以它迭代器的底层就是指针我们可以使用三个迭代器start,finish,end_of_storage来控制这个数组顺序表。templateclassTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;/////////////////////////////////////////////////迭代器iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}private:iterator _startnullptr;iterator _finishnullptr;iterator _end_of_storagenullptr;}3.capacitysize_tsize()const{return_finish-_start;}size_tcapacity()const{return_end_of_storage-_start;}voidreserve(size_t n){if(ncapacity()){size_t old_sizesize();T*tmpnewT[n];//这里如果是自定义类型就是错误的因为这里仅仅是浅拷贝/*memcpy(tmp, _start, sizeof(T) * size()); delete[] _start;*///这里要进行拷贝构造if(_start){for(size_t i0;in;i){tmp[i]_start[i];}delete_start;}_starttmp;_finish_startold_size;_end_of_storage_startn;}voidresize(size_t n,constTvalT()){if(ncapacity()){reserve(n);}for(size_t isize();in;i){_start[i]val;}_finish_startn;}vector的扩容问题:vs(STL为pj版本)以1.5倍进行扩容g(STL为SGI版本)以2倍扩容。memcpy问题memcpy是对内存中的内容进行一字节一字节拷贝如果是内置类型没有任何问题如果是自定义类型这就是浅拷贝释放空间时也会导致拷贝的元素释放进而报错。4.modifier4.1 push_backvoidpush_back(constTval){if(size()capacity()){reserve(capacity()0?4:2*capacity());}*_finishval;_finish;}4.4 pop_backvoidpop_back(){assert(_start!_finish);_finish--;}4.3 insertiteratorinsert(iterator pos,constTval){assert(pos_start);assert(pos_finish);if(size()capacity()){size_t npos-_start;reserve(capacity()0?4:2*capacity());pos_startn;//防止迭代器失效}iterator end_finish-1;while(endpos){*(end1)*(end);end--;}*posval;_finish;returnpos;}4.4 eraseiteratorerase(iterator pos){assert(pos_start);assert(pos_finish);iterator beginpos1;while(begin_finish){*(begin-1)*(begin);begin;}_finish--;returnpos;}迭代器失效1.对于insert来说如果容量满了的话那么就需要扩容原来的pos就会被释放掉进而导致访问时就是随机数。2.对于erase来说pos原本指向的值已经被后一个值覆盖因此返回的pos是指向下一个值的如果删除的是末尾的值话pos指向的值就已经越界不能进行解引用或自增操作因为已经越界。3.对于底层有内存的改变pos位置都有可能出现迭代器失效问题。解决方法更新迭代器。5.access [ ]Toperator[](size_t pos){assert(possize());return_start[pos];}constToperator[](size_t pos)const{assert(possize());return_start[pos];}---------------------------------------------------------------------完结啦