文章目录

1.vector的设计2.功能的模拟实现2.1 push_back、reserve、size、capacity、operator[ ]与析构2.2 iterator2.3 pop_back、insert、erase(迭代器失效)2.4 resize、swap、operator= 与构造 3.代码

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拷贝了数据。

memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中如果拷贝的是自定义类型的元素，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(迭代器失效)

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

//尾删void pop_back(){ assert(_start);--_finish;} 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;}

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

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= 与构造

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);} 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;}}} 构造

拷贝构造

首先，我们先实现其最简单的版本，拷贝构造。由于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);}}

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 ;//指向存储容量的尾的下一个};}