【C++】vector的模拟实现

1.vector的设计

STL中的vector是一个动态数组容器，它可以存储任意类型的元素，模板的使用使其可以自动匹配类型。

namespace vct
{//类模板template<class T>class vector{//vector的迭代器是一个原生指针typedef T* iterator;public:private:iterator _start = nullptr;//指向数据块的开始位置iterator _finish = nullptr;//指向数据块的 结束位置的 下一个iterator _end_of_storage = nullptr;//指向存储容量的尾的下一个};
}

2.功能的模拟实现

2.1 push_back、reserve、size、capacity、operator[ ]与析构

要实现尾插功能，首先要检查容量，是否需要扩容；由于我们的vector不像string那样有size与capacity成员变量，所以为了获得其大小，我们需要先写两个函数。

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

若容量不足，在正式插入数据前，需要进行扩容操作

		void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];//申请新空间if (_start)//为空就不需要拷贝数据{memcpy(tmp, _start, sizeof(T) * size());//拷贝数据delete[] _start;//释放旧空间}_start = tmp;//重新指向_finish = _start + size();_end_of_storage = _start + n;}}

尾插操作

		void push_back(const T& x){//检查容量，扩容if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}//尾插*_finish = x;++_finish;}

当我们运行代码发现它崩溃了。什么原因呢？

此时finish依然是一个空指针，那说明扩容时出现了问题，finish改的不对。

我们不能使用旧的finish去减新的start得到size，所以在销毁旧空间之前，我们需要将size记录下来。

		void reserve(size_t n){if (n > capacity()){size_t oldsize = size();//记录旧的sizeT* tmp = new T[n];//申请新空间if (_start)//为空就不需要拷贝数据{memcpy(tmp, _start, sizeof(T) * size());//拷贝数据delete[] _start;//释放旧空间}_start = tmp;//重新指向_finish = _start + oldsize;_end_of_storage = _start + n;}}

为了方便打印数据，我们需要重载一下[ ]

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

那么上方的代码就没有问题了么？有时候为了验证我们的代码是否存在问题，我们可以写一下析构函数，看看是否存在越界的问题。

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

当我们将模板参数修改为string时，上方代码就出现了问题。

为什么跑到析构这里就崩溃了呢？----它对同一块空间析构了两次！
问题分析：
在reserve函数中，我们使用了memcpy拷贝了数据。

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

所以，此处应该完成深拷贝。

		void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];//申请新空间if (_start)//为空就不需要拷贝数据{//memcpy(tmp, _start, sizeof(T) * size());//拷贝数据for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];//使用了string的operator=}delete[] _start;//释放旧空间}_start = tmp;//重新指向_finish = _start + oldsize;_end_of_storage = _start + n;}}

结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

2.2 iterator

迭代器的实现较为简单，返回一个指针即可

		//vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iteratorl;iterator begin(){return _start;}iterator end(){return _finish;}const_iteratorl cbegin() const{return _start;}const_iteratorl cend() const{return _finish;}

2.3 pop_back、insert、erase(迭代器失效)

1. 尾删很简单，直接移动finish即可。

		//尾删void pop_back(){assert(_start);--_finish;}

2. pos位置前插入
   

我们发现，标准库中的insert函数它要插入的位置不像以前那样直接是下标了，现在是一个迭代器了。
它的实现也很简单，挪动数据，插入即可。

		//pos位置之前插入void insert(iterator pos, const T& x){assert(pos < _end_of_storage);if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = x;++_finish;}

我们好像翻车了，什么原因呢？—迭代器失效

我们发现，当我要插入数据时，它刚好要扩容，那么它就会在开一段新的空间，成员都会指向新的空间。但是此时的pos还是指向旧的空间，pos就成了野指针。

所以那么怎么让pos位置在新空间的正确位置呢？

此时就不会出现随机值的场景了。

那么会不会有这样一种场景，我还需要再次访问pos位置的数据呢？此时pos在函数内部确实改了，但是在外部它依然还是野指针。

那该如何解决该问题呢？我们可以看到库中实现的该函数是有一个迭代器返回值的。它就是通过该返回值修改外部pos的。

		//pos位置之前插入iterator insert(iterator pos, const T& x){assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;//记录再就空间的位置size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);//reserve中会更新_start的位置pos = _start + len;//切换到新空间pos位置}iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;}

总之，建议失效以后的迭代器不要使用，除非赋值更新一下这个迭代器。

2. erase删除数据

erase很简单，后面的数据往前挪，覆盖前面的数据即可。

		void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator i = pos;while (i < end()){*i = *(i + 1);++i;}--_finish;}

那erase是否有迭代器失效的问题呢？

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了，此时就是越界访问了。 因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

因此，为了解决迭代器失效的问题，它的处理方式跟insert一样，将pos位置返回。

2.4 resize、swap、operator= 与构造

1. swap

swap比较简单，我们可以借助标准库下的swap交换两个vector变量。

		//v1.swap(v2)void swap(vector<T>& t){std::swap(_start, t._start);std::swap(_finish, t._finish);std::swap(_end_of_storage, t._end_of_storage);}

2. resize

• 如果 n 小于当前容器大小，则内容将减少到其前 n 个元素，删除（并销毁）超出的元素。
• 如果 n 大于当前容器大小，则通过在末尾插入所需数量的元素来扩展内容，以达到 n 的大小。如果指定了 val，则新元素将初始化为 val 的副本，否则，它们将进行值初始化。
• 如果 n 也大于当前容器容量，则会自动重新分配分配的存储空间

		void resize(size_t n,const T& val= T()){if (n < size()){_finish = _start + n;}else{reserve(n);//扩大了空间，拷贝了数据while (_finish != start + n){*finish = val;++_finish;}}}

3. 构造

• 拷贝构造

首先，我们先实现其最简单的版本，拷贝构造。由于vector就是顺序表，所以我们需要先开一块大小一样大的空间

		//v2(v1)vector(const vector<T>& t){_start = new T[t.capacity()];//开空间for (size_t i = 0; i < t.size(); i++)//拷贝数据{_start[i] = t._start[i];}_finish = _start + t.size();_end_of_storage = _start + t.capacity();}

由于上面的代码有点麻烦，所以我们还可以这样写：

		vector(const vector<T>& t){reserve(t.capacity());//预留空间，无需扩容for (auto e : t){push_back(e);//直接尾插}}

• 迭代器区间的初始化

这里使用了函数模板，目的是可以使用任意类型的迭代器初始化。

		//类模板中的成员函数，函数模板template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

使用其它类型的迭代器初始化也是可以的：

• n个val的构造

这里，库中的实现是给了val缺省值的，这个缺省值是什么意思呢？
如果我们是一个int的vector那可以给0，string类型的vector可以给个空串，如果是其它复杂的类型那我们怎么知道给什么呢？

所以这里使用了匿名对象，让该对象去调用它的默认构造作为缺省值。

		//在这里，为了解决（int,int）与迭代区间的冲突问题//可以写一个重载vector (int n, const T& val = T())vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

4. operator=

传统写法与拷贝构造的写法是一样的：

		vector<int>& operator=(vector<int>& t){_start = new T[t.capacity()];for (size_t i = 0; i < t.size(); i++){_start[i] = t._start[i];}_finish = _start + t.size();_end_of_storage = _start + t.capacity();return *this;}

这里我们也可以直接使用传值传参，参数就是要交换目标的拷贝，然后再与参数交换一下即可。

		vector<int>& operator=(vector<int> t){this->swap(t);return *this;}

3.代码

#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
#include<assert.h>
#include<string.h>
using namespace std;namespace vct
{//类模板template<class T>class vector{public://构造与析构vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//已经写了构造，但是仍然强制使用编译器默认的方式//vector() = default;//v2(v1)vector(const vector<T>& t){_start = new T[t.capacity()];for (size_t i = 0; i < t.size(); i++){_start[i] = t._start[i];}_finish = _start + t.size();_end_of_storage = _start + t.capacity();}//vector(const vector<T>& t)//{//	reserve(t.capacity());//预留空间，无需扩容//	for (auto e : t)//	{//		push_back(e);//直接尾插//	}//}//类模板中的成员函数，函数模板template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}//迭代器相关//vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin()const{return _start;}iterator end()const{return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}//   capacityvoid reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];//申请新空间if (_start)//为空就不需要拷贝数据{//memcpy(tmp, _start, sizeof(T) * size());//拷贝数据for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];//使用了string的operator=}delete[] _start;//释放旧空间}_start = tmp;//重新指向_finish = _start + oldsize;_end_of_storage = _start + n;}}void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}size_t capacity() const{return _end_of_storage - _start;}size_t size()const{return _finish - _start;}//   operatorT& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}/*vector<int>& operator=(vector<int> t){this->swap(t);return *this;}*/vector<int>& operator=(vector<int>& t){_start = new T[t.capacity()];for (size_t i = 0; i < t.size(); i++){_start[i] = t._start[i];}_finish = _start + t.size();_end_of_storage = _start + t.capacity();return *this;}//   modifyvoid push_back(const T& x){//检查容量，扩容if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}//尾插*_finish = x;++_finish;}//尾删void pop_back(){assert(_start);--_finish;}//pos位置之前插入iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;//记录再就空间的位置size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);//reserve中会更新_start的位置pos = _start + len;//切换到新空间pos位置}iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator i = pos;while (i < end()){*i = *(i + 1);++i;}--_finish;return pos;}//v1.swap(v2)void swap(vector<T>& t){std::swap(_start, t._start);std::swap(_finish, t._finish);std::swap(_end_of_storage, t._end_of_storage);}private:iterator _start ;//指向数据块的开始位置iterator _finish ;//指向数据块的 结束位置的 下一个iterator _end_of_storage ;//指向存储容量的尾的下一个};
}