【C++】vector的模拟实现

个人主页

文章目录

⭐一、基本框架

vector是一种类模板，它可以存储不同类型的元素，其底层是一段连续的线性内存空间。

template<classT>classvector{public://普通迭代器typedef T* iterator;//const常量迭代器typedefconst T* const_iterator;private:
    iterator _start =nullptr;
    iterator _finish =nullptr;
    iterator _end_of_storage =nullptr;

🚆二、默认成员函数

1.构造

构造函数我们又可以分为两种，一种是无参构造，另一种则为带参构造。
无参构造：什么参数都没有传，其内部并没有开辟空间。

//构造vector(){};

我们也可以用C++11前置生成默认构造

vector()=default;

带参构造：构造并初始化n个val

vector(size_t n,const T& val =T()){reserve(n);for(size_t i =0; i < n; i++){push_back(val);}}

2.拷贝构造

先开辟要拷贝对象的空间大小，然后使用范围for进行遍历，不断尾插即可。

//拷贝构造vector(const vector<T>& v){reserve(v.size());for(auto& e : v){push_back(e);}}

3.赋值重载

我们可以使用和string一样的思路，直接复用库里面标准的swap函数。

voidswap(vector<T>& v){
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);}

vector<T>&operator=(vector<T> v){swap(v);return*this;}

4.析构

完成对空间和资源的释放操作。

//析构~vector(){if(_start){delete[] _start;
        _start = _finish = _end_of_storage =nullptr;}}

🎄三、迭代器

vector的begin是返回容器的_start的位置，end则返回容器的_finish的位置。

iterator begin(){return _start;}

iterator end(){return _finish;}

既然有了普通迭代器，我们就会考虑到有const对象的调用，因此就会有const迭代器。

//const迭代器
const_iterator begin()const{return _start;}

const_iterator end()const{return _finish;}

⏱️四、容量及大小相关函数

1.size和capacity

size函数是用来返回数据vector对象中的有效数据个数，capacity函数则返回vector对象的容量空间的大小。

    size_t size()const{return _finish - _start;}

    size_t capacity()const{return _end_of_storage - _start;}

2.resize和reserve

resize函数是用来调整vector对象中的内容以及大小的。

voidresize(size_t n,T val =T()){//当n<size时，会截断n后面的数据if(n <size()){
        _finish = _start + n;}else{reserve(n);while(_finish < _start + n){*_finish = val;++_finish;}}}

reserve函数是完成对对象空间进行扩容操作的，当插入的数据大于对象的空间时，则会进行扩容操作，如果插入的数据小于对象空间时，则不会进行任何操作。

voidreserve(size_t n){if(n >capacity()){
        size_t old_size =size();
        T* tmp =new T[n];//memcpy(tmp, _start, size() * sizeof(T));for(size_t i =0; i < old_size; i++){
            tmp[i]= _start[i];}delete[] _start;
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_storage = tmp + n;}}

这里需要注意的是：在代码最后三行我们可以看出，此时的_start是指向新空间的起始位置，_finish如果想调用size()时，而此时的size()不是之前的size()了。 因为size()的返回值是_finish - _start，而由于_start改变了，而_finish的值并没有发生改变，因此会产生报错。所以我们需要用一个变量来存储旧空间的size()，就可以解决这一问题了。

🎡五、有关增加的函数

1.insert

首先要判断插入的位置是否越界，其次还需判断空间是否需要扩容，接着挪动数据，最后再进行插入操作。

iterator insert(iterator pos,const T& x){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;}
    iterator end = _finish -1;while(end >= pos){//挪动数据*(end +1)=*end;--end;}*pos = x;++_finish;return pos;}

2.push_back

这一函数是用来尾插数据的。和insert函数也相似，都是需要判断一下是否需要扩容，再将数据进行插入，然后更新一下_finish即可。

voidpush_back(const T& x){//空间满了就扩容if(_finish == _end_of_storage){reserve(capacity()==0?4:capacity()*2);}*_finish = x;++_finish;}

🚀六、有关删除的函数

1.pop_back

我们可以断言一下数据内不为空，然后进行尾删操作。

voidpop_back(){assert(!empty());--_finish;}

2.erase

首先判断一下需要删除的位置pos是否合法，然后从pos+1的位置开始往前覆盖pos的位置即可完成删除。

voiderase(iterator pos){assert(pos >= _start);assert(pos < _finish);
    iterator it = pos +1;while(it !=end()){*(it -1)=*it;++it;}--_finish;}

3.clear

用来清空数据，只需把起始位置的指针_start赋值给_finish即可。

voidclear(){
    _finish == _start;}

🏠七、operator[]运算符重载

普通对象调用版本：检查一下i的位置是否合法，然后用下标+[ ]的方式进行访问即可。

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

const对象调用版本：也是需要检查一下位置是否合法，然后采用下标+[ ]的方式访问。

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

💎八、判空empty

boolempty(){return _start == _finish;}