前文

vector是stl库中非常重要的一个容器，熟练使用vector可以有效提高我们的代码效率以及逼格，而模拟实现vector能使我们深入了解vector一些重要机制以及使用方法。
本文将带领铁子们完成vector一些重要接口的实现
老规矩，源码结尾自取。

一,vector的成员变量

首先我们可以先观察在stl30的源码中，vector的成员变量与之前的string大有不同。
由上图可以看到三个成员变量全都是指针。
那么这些指针都代表什么意思，指向哪里呢？
start指向空间开始的位置，finish指向空间中最后一个有效数据的下一个位置，end_of_storage指向的是空间最大容量的下一个位置。

而我们的模拟实现vectord的成员变量自然也要向源码看齐。
当然我们后续的功能肯定是不能照搬源码的，源码只是一个参考，而我们模拟实现的目的也是更加深入的了解vector，只要实现的功能和源码的功能相同或者类似就好。

成员变量如下：

        typedef V* iterator;typedef const V* const_iterator;iterator _start;//指向空间最开始的地址iterator _finsh;//指向空间有效数据的下一个地址iterator _end_of_storage;//指向空间最大容量的下一个地址

二，构造函数/析构函数

2.1 构造函数

如图，构造函数共有四种，我们要实现的是前三种。

2.1.1 无参构造函数

对于无参构造函数，我们只要将成员变量进行初始化即可。

        //1.无参vector():_start(nullptr),_finsh(nullptr),_end_of_storage(nullptr){}

2.1.2 有参构造函数

有参构造函数，我们需要先开辟n个大小的空间，再将数据一个一个尾插进去即可。
ps：扩容和尾插函数后续马上就会讲到，铁子们也可以先看扩容和尾插函数，再回头看这个。

        //2.有参数vector(size_t n, const V& val = V()):_start(nullptr), _finsh(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}//int函数重载，原因马上讲到 vector(int n, const V& val = V()):_start(nullptr), _finsh(nullptr), _end_of_storage(nullptr){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}

2.1.3 范围构造函数

范围构造函数，故名思义就是构造一个范围为[first,last)的vector，然后vector中的每个数据都和范围中的数据一一对应。
实现逻辑：先开辟和范围一样大小的空间， 再将数据一一尾插即可。

代码如下：

        //3,范围构造template vector(InputIterator first, InputIterator last):_start(nullptr), _finsh(nullptr), _end_of_storage(nullptr){size_t n = last - first;reserve(n);while (first != last){push_back(*first);first++;}}

2.1.4 函数构造适配的问题

相信老铁们已经看到有参构造函数的代码中有一个int类型的重载，那么这是为什么呢？
我们可以先将int重载代码屏蔽，然后实验一下

如上图所示，我们传的明明是有参构造的参数，为什么会出错呢？
这是因为编译器会自动匹配最合适的函数。
有参构造函数的参数类型为(size_t,const int)
而范围构造函数由于模板的问题，其参数类型会变成(int,int)
因此系统会自动认为范围构造函数更加匹配
但是我们范围构造函数要的是地址参数，而int会导致无法解引用从而报错。
解决办法：1.可以强转参数类型，如vector s2(3u,1);将第一个参数强制转为无符号
2.就是对有参构造函数进行int类型的函数重载
这里我们选择的是函数重载。

重载后就不会出现上述问题

2.2 析构函数

vector的析构函数逻辑比较简单，释放空间资源然后置空就可以。

    void test4(){vector s2(3,1);for (auto ch : s2){cout << ch << " ";}cout << endl;}

三，拷贝构造函数(重点)

拷贝构造函数的逻辑很简单，先开辟一个同样大小的空间，再把数据一个一个挪进去。
但是挪数据一定不要用memcpy，因为mencpy属于是浅拷贝，而要拷贝的数据又有可能出现vector的情况，浅拷贝析构肯定会报错的。
因为这里有一个非常重要的问题：就是深浅拷贝的问题，由于这个问题比较复杂，后面会专门写一篇文章详解这个问题。

代码如下：

        //拷贝构造vector(const vector& v){_start = new V[v.capacity()];//memcpy(_start, v._start, sizeof(V) * v.size());for (int i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finsh = _start + v.size();_end_of_storage = _start = v.capacity;}

四，迭代器(iterator)和空间增长接口(capacity)的实现

4.1 begin()/end()

begin和end是两个非常简单但是很实用的接口。
begin是返回第一个数据的位置，end是返回最后一个有效数据的下一位。

代码如下:

        //返回beginiterator begin(){return _start;}//返回end,迭代器访问左闭右开，所以直接返回_finshiterator end(){return _finsh;}//begin/end的const版本,防止出现权限扩大的问题const_iterator begin() const{return _start;}const_iterator end() const{return _finsh;}

4.2 size()/capacity()/empty()

size():获取vector的有效数据个数。两个地址相减可以的得到两个数组元素的距离
capacity():获取vector的最大空间.
empty():判断是否有数据。

代码如下：

//返回容量size_t capacity() const{return _end_of_storage - _start;}//返回有效数据个数size_t size() const{return _finsh - _start;}//判断vector是否为空bool empty() const{return _start == _finsh;}

4.3 []重载

[]的实现很简单,先保证n是合法的，然后直接返回即可。
这个接口在string的时候比较常用，但vector往后大多使用迭代器访问数据。

代码如下：

//[]重载V& operator[](size_t n) {assert(n < size());return _start[n];}const V& operator[](const size_t n) const{assert(n < size());return _start[n];}

4.4 reserve()扩容

实现逻辑:先检查是否需要扩容，然后用一个新的指针开空间，没问题的话，把原来空间拷贝到新空间，原空间释放，然后在给成员变量赋值。

代码如下：

        void reserve(const size_t n){if (n > capacity()){size_t sz = size();//保存size大小，防止后面_start先改变，//导致size()计算出错从而导致_finsh出错V* tmp= new V[n];if (_start){//memcpy(tmp, _start, sizeof(V)*sz);for (int i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start; }_start = tmp;//_finsh=tmp+size()=_start+_finsh-_start=_finsh//如上如果不提前存储size()的值，新_finsh的值会和之前一样_finsh = tmp + sz;_end_of_storage = tmp + n;}}

注意上面有两个需要注意的点
1.size()要提前保存起来，因为后面我们要确定_finsh的值需要原来的size()，而size的求法是_finsh-_start,如果不提前保存就会因为_start的改变无法求出准确求出size()的值,从而导致新_finsh的值出问题.

2.在往新空间进行拷贝数据时，涉及一个深浅拷贝的问题，后续会讲，这里要注意不能使用memcpy

4.5 resize()

resize():改变vector的size。
有三种情况：1.当ncapacity(),要先扩容至n的大小，然后重复2.

代码如下：

//resizevoid resize(const size_t n, const V& val = V())//这里用V()作为缺省参数有两个原因//1.V有可能是自定义类型，如string等//2.因为模板的实现，所以内置类型也有构造函数{if (n < size()){_finsh = _start + n;}else{if (n > capacity()){reserve(n);}while (_finsh != _start + n){(*_finsh) = val;_finsh++;}}}

老铁看到上面代码肯定有一个很疑惑的点，为什么val=V()，而不是0或者其他。
这是因为，vector中存的类型有可能是自定义类型，如string等，所以需要调用其构造函数。
那可能有的同学又疑惑了，那内置类型呢？有构造函数吗？
答案肯定是有的，因为模板的特性，内置类型的构造函数也是有的，如下

那么问题到这里就结束了吗？不是的。
众所周知，V()作为匿名函数，其生命周期只有一行，那么是怎么延长到整个函数作用域的呢？
这里我们规定V()生命周期只有一行是因为没名字没人用，但是const V& val会延长V()的生命周期至引用对象val的生命周期。
ps：必须带有const引用，因为V()作为常量有不可变性，如果不用const修饰，属于权限放大，会报错。

五，增删查改(Modifiers)

5.1 push_back(尾插)/pop_back(尾删)

尾插，先检查是否需要扩容，这里的capacity()有可能是0，所以如果进行的是二倍扩容，需要考虑capacity()为0的情况，扩容后在尾部插入数据就行。

尾删，尾部直接删即可.

代码如下:

        //尾插void push_back(const V& val){if (size() + 1 > capacity()){reserve(capacity() == 0 ? 4 : capacity()*2);//容量为0，要先开辟初始空间}*_finsh = val;_finsh++;}//尾删void pop_back(){assert(!empty());//判空_finsh--;}

5.2 insert(插入)/erase(删除)(重点)

insert和erase是vector相当重要的一部分，因为这里会涉及到迭代器失效的问题，这个问题后续我们会和深浅拷贝放到一起讲

insert:我们实现的是第一种，在pos的位置插入数据val
实现逻辑:1.首先需要判断pos是否合法。
2.判断是否需要扩容，这里需要注意的一点是扩容后会重新开辟空间，而pos指向的还是原来空间，所以需要更新

3.从pos开始往后的每个数据往后挪一个单位，这里不像string注意的点比较多，这里只要实现就可以
4.挪完赋值即可

erase:我们要实现的是第一种，删除pos位置的数据
实现逻辑:判断pos是否合法，然后pos往后的数据往前挪一个单位即可

代码如下:

//eraseiterator erase(iterator pos){assert(pos <= _finsh && pos >= _start);iterator end = pos;while (end < _finsh - 1){*end = *(end + 1);end++;}_finsh--;return pos;}

五，源码

#pragma once
#include 
#include 
using namespace std;namespace mjw
{template class vector{public://定义迭代器typedef V* iterator;typedef const V* const_iterator;//构造函数//1.无参vector():_start(nullptr),_finsh(nullptr),_end_of_storage(nullptr){}//2.有参数vector(size_t n, const V& val = V()):_start(nullptr), _finsh(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const V& val = V()):_start(nullptr), _finsh(nullptr), _end_of_storage(nullptr){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}//3,范围构造template vector(InputIterator first, InputIterator last):_start(nullptr), _finsh(nullptr), _end_of_storage(nullptr){size_t n = last - first;reserve(n);while (first != last){push_back(*first);first++;}}//拷贝构造vector(const vector& v){_start = new V[v.capacity()];//memcpy(_start, v._start, sizeof(V) * v.size());for (int i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finsh = _start + v.size();_end_of_storage = _start = v.capacity;}//析构函数~vector(){delete[] _start;_start = _finsh = _end_of_storage = nullptr;}//返回beginiterator begin(){return _start;}//返回end,迭代器访问左闭右开，所以直接返回_finshiterator end(){return _finsh;}//begin/end的const版本,防止出现权限扩大的问题const_iterator begin() const{return _start;}const_iterator end() const{return _finsh;}//返回容量size_t capacity() const{return _end_of_storage - _start;}//返回有效数据个数size_t size() const{return _finsh - _start;}//判断vector是否为空bool empty() const{return _start == _finsh;}//[]重载V& operator[](size_t n) {assert(n < size());return _start[n];}const V& operator[](const size_t n) const{assert(n < size());return _start[n];}//扩容函数void reserve(const size_t n){if (n > capacity()){size_t sz = size();//保存size大小，防止后面_start先改变，//导致size()计算出错从而导致_finsh出错V* tmp= new V[n];if (_start){//memcpy(tmp, _start, sizeof(V)*sz);for (int i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start; }_start = tmp;_finsh = tmp + sz;_end_of_storage = tmp + n;}}//resizevoid resize(const size_t n, const V& val = V())//这里用V()作为缺省参数有两个原因//1.V有可能是自定义类型，如string等//2.因为模板的实现，所以内置类型也有构造函数{if (n < size()){_finsh = _start + n;}else{if (n > capacity()){reserve(n);}while (_finsh != _start + n){(*_finsh) = val;_finsh++;}}}//尾插void push_back(const V& val){if (size() + 1 > capacity()){reserve(capacity() == 0 ? 4 : capacity()*2);//容量为0，要先开辟初始空间}*_finsh = val;_finsh++;}//尾删void pop_back(){assert(!empty());//判空_finsh--;}//insertiterator insert(iterator pos, const V& val){assert(pos <= _finsh&&pos>=_start);//判断扩容if (size() + 1 > capacity()){//由于扩容会重新开辟空间,原有的pos会失效//所以需要保存pos的相对位置，方便在新空间定位size_t p = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//容量为0，要先开辟初始空间//新空间pospos = _start + p;}//从pos开始往后的每个数据往后挪一个单位iterator end = _finsh - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finsh++;return pos;}//eraseiterator erase(iterator pos){assert(pos <= _finsh && pos >= _start);iterator end = pos;while (end < _finsh - 1){*end = *(end + 1);end++;}_finsh--;return pos;}private:iterator _start;//指向空间最开始的地址iterator _finsh;//指向空间有效数据的下一个地址iterator _end_of_storage;//指向空间最大容量的下一个地址};//下面是测试函数void test1(){vector s1;s1.resize(5, 0);for (auto ch : s1){cout << ch << " ";}cout << endl;}void test2(){vector s1;s1.push_back(1);s1.push_back(2);s1.push_back(3);s1.push_back(4);s1.push_back(5);for (auto ch : s1){cout << ch << " ";}cout << endl;s1.pop_back();s1.pop_back();s1.pop_back();s1.pop_back();s1.pop_back();s1.pop_back();for (auto ch : s1){cout << ch << " ";}cout << endl;}void test3(){vector s1;s1.insert(s1.begin(), 1);s1.insert(s1.begin(), 2);s1.insert(s1.begin(), 3);s1.insert(s1.begin(), 4);s1.insert(s1.begin(), 5);for (auto ch : s1){cout << ch << " ";}cout << endl;s1.erase(s1.begin());s1.erase(s1.begin());s1.erase(s1.begin());s1.erase(s1.begin());for (auto ch : s1){cout << ch << " ";}cout << endl;}void test4(){vector s2(3,1);for (auto ch : s2){cout << ch << " ";}cout << endl;}void test5(){int a = int();double b = double();cout << a << endl;cout << b << endl;}};

总结

vector的重要功能算是已经完成模拟实现，相信铁子们对vector也有了更深入的理解，
同时这里面还有两个问题，我们没有解决：1.深浅拷贝的问题 2.迭代器失效的问题
后续近两天就会出一篇文章详解这两个问题，铁子们敬请期待。