C++模拟实现—

C++模拟实现——vector

一、成员变量

成员变量由三个模板指针构成：

_start : 指向开头位置

_finish : 指向数据结束的地方

_end_of_storage : 指向空间结束的位置

二、基本指标

实现vector的基本思路和顺序表相同，因此会频繁的需要用到数据大小、容量大小这些指标，因此优先提高这两个接口，方便后续复用。

		//常用指标size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage - _start;}bool empty()const //判空{return _start == _finish;}

三、迭代器

vector的迭代器，由于物理空间上连续，因此可以直接使用原生指针去实现。

		typedef T* iterator;typedef const T* con_iterator;//迭代器iterator begin(){return _start;}iterator end(){return _finish;}con_iterator begin()const{return _start;}con_iterator end()const{return _finish;}

四、构造与析构

1.构造函数

（一）、默认构造函数

只需要完成初始化的任务即可，将三个指针初始化为空指针即可

		vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

（二）构造函数——一次性构造多个值

这里提供一个能一次性初始化多个值的构造函数，参数一是数据的数量，参数二是数据本身

vector(size_t n,const T& val = T())//这里使用匿名对象去给缺省值，const&能延长匿名对象的生命周期:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){if(n > capacity()){reserve(n);}for(size_t i =0;i<n;i++){push_back(val);}}//函数重载，避免vector<int>(5,10)的情况，被默认到两个迭代器的位置vector(int n,const T& val = T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){if(n > capacity()){reserve(n);}for(int i =0;i<n;i++){push_back(val);}}

这里要构成函数重载的原因是为了避免特殊情况下，匹配错误的问题，例如int类型的构造时，若没有第二个函数重载，会被默认匹配到两个迭代器构造中

（三）构造函数——用迭代器区间去构造

这里提供的是用任意类型的迭代器区间去完成构造初始化，因此用使用函数模板

        template<class input_iterator>vector(input_iterator first,input_iterator last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){while(first != last){push_back(*first);first++;}}

（四）拷贝构造

拷贝构造可以复用迭代器区间构造得到一个临时拷贝的tmp，然后交换即可

        vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//reserve(v.capacity());//iterator it = begin();//con_iterator vit = v.begin();//while(vit != v.end())//{//	*it++ = *vit++;//}//_finish =_start + v.size();vector<T> tmp(v.begin(),v.end());swap(tmp);}

2.析构函数

		~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}

五、运算符重载

1.operator[ ]

		T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}

2.operator=

		void swap(vector<T>& tmp){std::swap(_start,tmp._start);std::swap(_finish,tmp._finish);std::swap(_end_of_storage,tmp._end_of_storage);}vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}

重点：关于深浅拷贝的问题

在reserve的实现中，为什么用memcpy是浅拷贝，而使用while逐一赋值就不是浅拷贝了呢？

例如在vector<vector<int>>类型去调用reserve时，while中*it指代的其实是vector<int>类型，为什么赋值操作可以使得浅拷贝变成深拷贝呢？这个与赋值重载的实现有关

赋值实现如上，深拷贝的完成实际上是在传参时，系统对赋值操作右值进行了深拷贝，并赋值给tmp，空间也是在此时开辟的，然后在使用交换函数，对这一块临时拷贝的空间，转移到赋值操作左值上，在函数结束后对tmp进行销毁，实际上是对原本赋值左操作数的空间进行销毁，并且在此过程中成功完成了深拷贝

六、空间管理

1.reserve

        void reserve(size_t n){if(n > capacity()){size_t sz = size();iterator tmp = new T[n];if(_start)//如果扩容前有数据，则需要拷贝数据{//不能使用浅拷贝//memcpy(tmp,_start,sizeof(T)*size());for(size_t i = 0;i<size();i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}

2.resize

		void resize(size_t n,const T& val = T()){if(n < size()){_finish = _start + n;}else{if(n > capacity())reserve(n);while(_finish!=_start+n){*_finish = val;_finish++;}}}

七、增删操作

1.insert

优先实现insert，其他的增加操作即可对其进行复用

		iterator insert(iterator pos,const T& val){assert(pos>=_start);assert(pos<=_finish);if(_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity()*2);pos = _start + len;//更新pos，避免迭代器失效}iterator end = _finish-1;while(end >=pos){*(end+1) = *end;end--;}*pos = val;_finish++;return pos;}

2.erase

		iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator start = pos+1;while(start != _finish){*(start-1) = *start;start++;}_finish--;return pos;}