C++初阶：STL详解（五）——vector的模拟实现

✨✨小新课堂开课了，欢迎欢迎~✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：C++：由浅入深篇

小新的主页：编程版小新-CSDN博客

前言：

我们前面已经了解了vecto的特性和常见接口的使用，今天就来了解一下vector的底层。vector和string又非常的相似，所有今天要介绍的底层大家也会处理的得心应手，在实现的时候又会用到我们前面说的迭代器失效的问题，也可以简单回忆一下。

C++初阶：STL详解（三）——vector的介绍和使用-CSDN博客

C++初阶：STL详解（四）——vector迭代器失效问题-CSDN博客

vector各函数接口总览

namespace fu
{//模拟实现vectortemplate<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认成员函数vector();                                           //无参的构造函数1vector(size_t n, const T& val = T());                     //构造函数2template<class InputIterator>vector(InputIterator first, InputIterator last);    //构造函数3vector(const vector<T>& v);                         //拷贝构造函数vector<T>& operator=(const vector<T> v);           //赋值运算符重载函数~vector();                                          //析构函数//迭代器相关函数iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//容量和大小相关函数size_t size()const;size_t capacity()const;void reserve(size_t n);void resize(size_t n, const T& val = T());bool empty()const;//修改容器内容相关函数void push_back(const T& x);void pop_back();iterator  insert(iterator pos, const T& x);iterator erase(iterator pos);void swap(vector<T>& v);//访问容器相关函数T& operator[](size_t i);const T& operator[](size_t i)const;private:iterator _start;        //指向容器的头iterator _finish;       //指向有效数据的尾iterator _endofstorage; //指向容器的尾};
}

注意：为了与标准库里的vector产生命名冲突，在模拟实现时要放到我们自己的命名空间中去。

成员变量简介

默认成员函数 

构造函数1

我们第一个介绍的是一个无参的构造函数，只需对成员变量进行简单的初始化即可，这里我们都初始化为空指针。

// 无参的构造函数
vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{
}

 构造函数2

第二种构造方式，我们可以用一个迭代器区间区去构造。至于这里为什么会使用函数模版，是因为我们也不知道要接送的迭代器类型是什么，可能是string类型，可能就是某个vector迭代器区间。之后我们在将该迭代器区间的数据一个个尾插即可。

template<class InputIterator> //模板函数
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{//将迭代器区间在[first,last)的数据一个个尾插到容器当中while (first != last){push_back(*first);first++;}
}

构造函数3

第三种构造方式，我们可以用n个val进行初始化。我们可先利用reserve这个接口提前开好空间，避免多次扩容使得效率低下，之后在用push_back这个接口尾插即可。

	//用n个val进行构造vector(size_t n, const T& val=T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)              {reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

好了看到这里，我们已经认识了这三种构造方式，但是这里还有一些小瑕疵。

fu::vector<int> v1(5, 8);

你猜这个v1会调用哪种构造函数，是构造函数2，是构造函数3。编译器会优先选择与构造函数2匹配，但是构造函数2内对first进行了解引用，但是整形(int）不能解引用，就会报错。

解决方式就是我们需要几个与构造函数2类似的重载函数。

vector(int n, const T& val=T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); for (size_t i = 0; i < n; i++) {push_back(val);}
}
vector(long n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); for (int i = 0; i < n; i++) {push_back(val);}
}

拷贝构造

和string类似，vector的拷贝拷贝也涉及深拷贝问题，这里我们也提供两种方式。

传统写法：

先开辟一块与该容器大小相同的空间，然后将该容器当中的数据一个个拷贝过来即可，最后更新_finish和_endofstorage的值即可。

//拷贝构造函数
//传统写法
vector(const vector<T>& v)
{//开辟一个足够大小的空间_start = new T[v.size()];//将数据插入到容器中for (size_t i = 0; i < v.size(); i++){_start[i] = v[i];}//更新信息_finish = _start + v.size();//当前容器有效数据的个数_endofstorage = _start + v.capacity();//当前容器的容量大小
}

现代写法： 

现代写法和传统写法的思路是一样的，只是现代写法用了范围for（自动迭代，自动取数据，自动判断结束）。

//现代写法
vector(const vector<T>& v)
{//开辟一个足够大小的空间reserve(v.capacity());//将数据插入到容器中for (auto ch : v){push_back(ch);}//更新信息_finish = _start + v.size();//当前容器有效数据的个数_endofstorage = _start + v.capacity();//当前容器的容量大小}

赋值运算符重载

vector的赋值运算符重载也涉及深拷贝问题，这里还是提供两种方式。

传统写法：

首先先判断是否自己给自己赋值，自我赋值没必要，开辟一个足够的空间，将容器中的数据一个个拷贝过来，释放旧空间，指向新空间，最后更新成员变量的信息即可。

//赋值运算符重载函数
//传统写法
vector<T>& operator=(const vector<T>& v)
{//自己给自己赋值不需要改变if (this != v){//开辟一个足够大小的空间T tmp = new T[v.capacity()];//将原来的数据拷贝给容器for (size_t i = 0; i < v.size(); i++){_start[i] = v[i];}//释放旧空间delete[] _start;//指向新空间_start = tmp;_finish = _start + v.size();//当前容器有效元素的个数_endofstorage = _start + v.capacity();//当前容器容量的大小return *this;//可重复赋值}
}

现代写法： 

赋值运算符重载的现代写法十分精巧，首先在右值传参时并没有使用引用传参，传值传参调用vector的拷贝构造函数，然后将这个拷贝构造出来的容器v与左值进行交换，此时就相当于完成了赋值操作，而容器v会在该函数调用结束时自动析构。

//现代写法
vector<T>& operator=(const vector<T> v)
{//交换swap(v);return *this;//可重复赋值
}

析构函数

首先要判断容器是否为空，避免对空指针进行解引用，不过不为空，就先释放原来空间，再将成员变量置空即可。

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

迭代器相关的函数

begin和end

//迭代器相关函数iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}

vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。

容量和大小相关函数

size和capacity

指针相减即可。

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

reserve和resize

resize函数改变容器中的有效元素个数，reserse函数改变容器的容量。

reserve规则：
 1、当所给值大于当前容器的capacity时，将capacity扩大到该值。
 2、当所给值小于当前容器的capacity时，什么也不做，不会缩容。

void reserve(size_t n)
{//检查是否需要扩容if (n > capacity()){//记录当前容器的大小size_t sz = size();//开辟一个足够大小的空间T* tmp = new T[n];//将先前数据拷贝给新容器for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}//释放旧空间delete[] _start;//指向新空间_start = tmp;_finish = _start + sz;//当前容器有效元素个数_endofstorage = _start + n;//当前容器的容量大小}
}

 resize规则：
 1、当所给值大于容当前容器的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则int型默认为0，char型默认是'\0'。

   2、当所给值小于容器当前的size时，将size缩小到该值。

void resize(size_t n, const T& val = T())
{//当n小于sizeif (n < size()){_finish = _start + n;}else//大于size{//检查是否需要扩容if (n > capacity()){//提前开够足够的空间reserve(n);//填充数据while (_finish != _start+n){*_finish = val;_finish++;}}}
}

empty

当_start 和_finish指向的位置相同的时候代表容器为空。

 bool empty()const{return _start == _finish;}

修改容器内容相关函数

push_back

在进行插入的前的第一步都是先判断空间是否够用，有需要就扩容，之后我们就将数据插入到_finish的位置，在++_finish即可。

	// 尾插数据void push_back(const T & x){if (_finish == _endofstorage) //判断是否需要增容{size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍reserve(newcapacity); //增容}*_finish = x; //尾插数据_finish++; //_finish指针后移}

pop_back

在容器不为空的情况下。直接将_finish指向的位置往前挪动即可。

void pop_back()
{assert(!empty());_finish--;
}

insert

在插入操作前，不变的第一步还是检查是否需要扩容。在实现扩容操作的时候，可能一不小心就会犯让迭代器失效的问题，这里我们记录扩容前pos与_start的相对位置就是方便在扩容后能找到pos位置，这里也就避开了我们之前举例的迭代器失效问题的一个常见场景。该场景的迭代器失效就是由扩容引起的。之后我们就只需要挪动数据，再在pos位置插入即可，记得要++_finish哦，因为这里又多一个数据。insert返回插入元素的位置。

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);//检查是否需要扩容if (_finish == _endofstorage){size_t len = pos - _start;//记录相对位置，避免迭代器失效问题reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;//找到扩容后pos的位置}//将pos及其后面的元素往后移，移出位置，给要插入的元素iterator end = _finish;while (end>=pos+1){*end = *(end - 1);end--;}*pos = x;//插入_finish++;//往后移return pos;
}

erase 

在删除数据前要判断容器是否为空，空的容器还怎么删除呢。这里所说的删除其实就是挪动覆盖，记得要--_finish哦，因为这里少了一个数据。erase返回被删除位置的下一个位置的迭代器。

iterator erase(iterator pos)
{assert(!empty());iterator it = pos + 1;//挪动覆盖数据while (it != _finish){*(it - 1) = *it;it++;}_finish--;//少了一个数据，往前移return pos;//返回被删除位置的下一个位置的迭代器}

swap

我们直接使用库里面的交换函数即可。

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

访问容器相关函数

operator[]

vector也支持下标+[]对容器进行访问，我们这里实现了可读可写和只读的接口。检查下标的合法性后，返回对应的数据即可。

//访问容器相关函数
T& operator[](size_t i)
{assert(i < size()); //检测下标的合法性return _start[i]; //返回对应数据
}const T& operator[](size_t i)const
{assert(i < size()); //检测下标的合法性return _start[i]; //返回对应数据
}

总结：

vector的模拟实现到这里也结束了，和string非常的相似，所以也很好理解，我们在学习了string和vector之后，就要进入到list的学习，也是有很多想通性，list的特性决定了它的模拟实现和vector有所不同，之后我们一起来看吧。

感谢各位大佬的观看，创作不易，还请各位大佬支持~