C++7：STL-模拟实现vector

目录

vector的成员变量

构造函数

reserve

size()

capacity()

push_back

 一些小BUG

赋值操作符重载

析构函数

 【】操作符重载

resize

pop_back

Insert

 迭代器失效

erase

二维数组问题

总结一下

---

vector，翻译软件会告诉你它的意思是向量，但其实它就是个顺序表容器，与我们刚开始实现的顺序表大差不差，但是模板的应用让它变得更加万能，接下来我们就尝试去了解学习源码是如何实现vector的。

vector的使用：

int main()
{vector<int> v;v = { 1,2,3,4,5 };for (auto& e : v){cout << e;}
}	

由于模板的使用，vector不仅能存放内置类型，也可以存放自定义类型，比如说用vector套vector

 当然vector还有很多的应用型接口，在这里不记述，有需要的话请移步至这个网站：https://cplusplus.com/reference/

看上去vector的使用相当方便，也加入了我们的老熟人模板参数，那么我们就来模拟实现一下。

vector的成员变量

 借助顺序表的前车之鉴，我们推断vector的成员变量的实现应该是如下这样的

namespace myvector
{template<class T>class vector{public:private:T* _v;size_t _size;size_t _capacity;};
}

但是事与愿违，跑去查询STL的源码给了我们当头棒喝

 坏了，怎么是3个迭代器？我们看到，迭代器的定义是两个typedef的套娃，它的本质依旧是T*，Start我们可以理解，顺序表结构的头指针，但是为什么size和capacity变成了finish和end of storage?

在《SLT源码剖析》中我们得到了答案

 那么其实它们的本质没什么太大的分别，这样也有助于范式使用。但我这边还是比较喜欢size和capacity就不更改了。

构造函数

我们先实现一个最基本的无参版本

//无参构造函数
vector():_start(nullptr), _size(nullptr), _capacity(nullptr)
{}

 然后是传参版本

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

reserve

 为了能实现一个有基本功能的vector，我们先解决一下扩容的问题，然后就可以愉快的写push_back了。

由于扩容的前提是不要缩容，那么我们就需要得到当前vector的size，但是不同于string可以直接得到当前的size，我们需要额外写一个函数来获取，不过也不算难事，毕竟也是比较常用的函数。

两个同类型的指针相减，得到的就是它们之间的数据类型个数。

size()

size_t size()
{return _size - _start;
}

capacity()

size_t capacity()
{return _capacity - _start;
}

那么就可以拿来实现reserve了，重置空间的逻辑跟string差不太多，首先我们检查是否发生了缩容，然后借助传入的需要开辟的空间个数来new出来一个新空间，接着把旧空间的数据用memcpy拷贝过去，然后新空间的size和capacity还需要重置一下，因为它们的本体是指针，指向的空间已经被销毁了，我们就以当前的新头指针+=上原先的数据个数让其重归正轨。

如下的代码有小BUG，我们后面讲

void reserve(const size_t n)
{if (n > capacity()){T* tmp = new T[n];//如果旧空间就是需要被开辟的，也就是_start是个空指针，不需要拷贝直接赋值就行//重置空间的话就往下走。if (_start != nullptr){memcpy(tmp, _start, _size);delete[] _start;}_start = tmp;_size = _start + size();_capacity = _start + n;}
}

push_back

 有了空间开辟的函数，push_back就没什么难度了。

		void push_back(const T& val){if (_size == _capacity){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_size = val;++_size;}

 一些小BUG

 到这里时，一个基本的vector就可以使用了，但是还是有一个小问题，假如我们直接运行如上代码，就会报如下的错误。

怎么回事？为什么_size 还是空？调试时已经走过了前面的过程，那么问题就应该出现在扩容的时候，_size 赋值的方法出现了问题。

我们回到reseve函数，发现我们想利用size（）函数来获得当前的数据个数时，忽略了此时的_size本身还是指向旧空间的，而_start早已更新，两个指针相减根本得不出正确答案

那么我们还是需要保存一下旧空间的个数

void reserve(const size_t n){if (n > capacity()){T* tmp = new T[n];size_t oldsize = size();if (_start != nullptr){memcpy(tmp, _start, sizeof(T)*size());delete[] _start;}_start = tmp;_size = _start + oldsize;_capacity = _start + n;}
}

再插入5个数据试试看

 没有问题。

赋值操作符重载

 为了应对赋值的问题，编译器默认生成的赋值操作符重载函数是浅拷贝会导致析构两次而崩溃的问题，所以我们还是需要实现一下

赋值的情况发生在同类型的情况下，所以返回值和参数都应该是vector

然后借用我们之前string的现代写法，也就是把一份拷贝与当前的this进行交换，我们再实现一个简单的swap函数

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

 那么为了不影响到赋值操作符左边的值，我们不传引用，直接传值，产生一个拷贝构造然后交换。

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

析构函数

		//析构函数~vector(){delete[] _start;_start = _size = _capacity = nullptr;}

 【】操作符重载

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

resize

 resize函数同string的逻辑没什么太多的区别，唯一需要注意的是关于填充缺省值的问题。

当n>_capacity的时候，需要扩容，当n>size的时候需要向多出来的空间填充缺省值，当n<size的时候需要重置当前size的位置到n

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

在这里val为了适应自定义类型，采用了匿名构造的方式来为val赋值，对于内置类型也是生效的

T val = T()

pop_back

		void pop_back(){assert(_size  > _start);--_size;}

Insert

 我们先看看描述

 传入一个迭代器，然后在迭代器位置插入数据。那么我们简单实现一个迭代器

//迭代器
iterator begin() 
{return _start;
}iterator end()
{return _size - 1;
}

由于auto的使用原理是自动推导，所以当我们实现了某个容器的迭代器的时候，就可以正常的使用范围for了，auto可以在范围for中成功的推导出来容器的迭代器从而实现遍历。

接下来是insert的主体逻辑

		void insert(iterator n, const T& val){assert(n >= _start);//若满扩容if (_size == _capacity){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}if (n < _size){iterator end = _size;while (end > n){*end = *(end - 1);--end;}*n = val;++_size;}}

 坏了，怎么崩溃了？发生什么事了？我们调试看看

通过调试，我们发现n的值完全不在当前_start 到 _size 的位置之间，这个while循环也走了非常多遍，而且这个问题是在扩容时才发生的，那么我们就得出了一个最初的结论，n所指向的位置在扩容后无法正确生效，也就是迭代器失效问题。

 迭代器失效

迭代器失效原因如图所示，为了更好的理解，传入的迭代器n更名为pos

 那么为了能成功的修正pos的新位置，跟我们处理pushback的方法一样，我们保存之前的数据长度，然后在新的空间更新pos

		void insert(iterator n, const T& val){assert(n >= _start);//扩容会引发迭代器失效的问题，需要更新迭代器if (_size == _capacity){size_t length = n - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);n = _start + length;}if (n <  _size){iterator end = _size;while (end > n){*(end) = *(end - 1);end--;}*n = val;//整体大小+1，更新_size_size++;}}

那么通过上面的分析，我们知晓了迭代器失效的具体原因，而迭代器失效指向的真正失效其实是inset之后的迭代器不能再使用了。因为我们是传值调用，inset外部的迭代器依然没有更新，假如我们想要继续使用很有可能发生越界访问的问题。

erase

void erase(iterator n)
{assert(n >= _start);assert(n < _size);if (n == _size - 1){pop_back();return;}iterator cur = n + 1;while (cur < _size){*(cur - 1) = *cur;++cur;}--_size;
}

二维数组问题

 vector容器本身服务的对象是各种各样的类型，所以当我们希望在vector内部存放其他容器类型的时候，它也应该是支持的，我们就拿我们自己实现的vector来尝试实现一个二维数组。

 没啥问题，但是一旦发生扩容会直接崩溃

 通过调试我们发现问题发生在析构的时候

 但追根溯源，析构能发生错误的时候肯定是空间的开辟发生了问题，那么罪魁祸首应该就是我们的reserve了

 那么为什么创建二维数组的时候才报错？还是需要画图来缕一缕。

 

那么为了避免这种情况，我们应该抛弃malloc换成更加深层次的拷贝，也就是新开辟一个空间之后把原本的值原封不动的拷贝一份新的，也就是内容相同但是地址不同的新拷贝再放入扩容之后的空间。

		void reserve(const size_t n){if (n > capacity()){T* tmp = new T[n];size_t oldsize = size();if (_start){for (size_t i = 0; i < oldsize; ++i){tmp[i] = _start[i];}//释放旧空间防止内存泄漏delete[]_start;}_start =  tmp;_size  =  tmp + oldsize;_capacity = _start + n;}}

总结一下

 根据以上的模拟实现，我们基本上了解了vector的基本结构以及接口的使用，其本质不同于顺序表，为了服务于自定义类型以及泛型变成，成员变量是迭代器，而迭代器的本身则是类模板参数，实现并不算困难但是细节还是需要额外处理。

 到此，模拟vector的概述就结束了，感谢阅读！希望对你有点帮助！