各位读者老爷好，俺打算在这篇博客浅浅介绍一下vector的模拟实现，以更好的理解vector，若有兴趣，欢迎垂阅！
由于vector是一个类模板，那么俺模拟实现也搞一个类模板。。。由于模版不建议声明和定义分离到两个文件.h 和.cpp会出现链接错误，当然可以通过一系列麻烦操作实现分离到两个文件下而不出现链接错误，但是巨麻烦！！所以，俺模拟实现的vector的声明和定义全部放在一个vector.h文件下。
由于模拟实现的vector于命名空间std的vector类模板名相同，为了方便本博客的讲述，以下若是所述vector均默认指模拟实现的vector，若是指命名空间std的vector，则会标红，如vector。
1.模拟实现vector
俺将模拟实现的vector全部放到了vector.h文件当中：
PS：我不是想要模拟实现一个尽善尽美的vector，我也做不到，所哟俺模拟实现的vector只是模拟实现了部分常用接口。
既然vector底层是可以存储任何类型数据的顺序表，所以我对vector的成员变量设计如下，共有3个成员变量：
模拟实现的vector完整代码如下：
#include<iostream>
#include<vector>
#include<string>
#include<assert.h>
#include<stdbool.h>
using namespace std;
namespace HD
{template<typename T>class vector{public:typedef T* iterator;typedef const T* const_iterator;typedef T value_type;typedef size_t size_type;//*******************************************************************vector<T>(size_type n,const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}/*vector<T>(int n, const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}*///*******************************************************************//*******************************************************************// C++11新增关键字default用法：可以强制生成默认构造。//vector<T>() = default;vector<T>(){}//*******************************************************************//*******************************************************************vector<T>(const vector<T>& x){/*for (auto& ch : x){push_back(ch);}*/iterator tmp = new value_type[x.capacity()];for (int i=0;i<x.size();i++){tmp[i] = x[i];}_start = tmp;_finish = tmp + x.size();_endofstorage = tmp + x.capacity();}//*******************************************************************//*******************************************************************template<typename InputIterator>vector<T>(InputIterator first, InputIterator last){InputIterator it = first;while (it != last){push_back(*it);it++;}}//*******************************************************************//*******************************************************************void push_back(const value_type& val){if (capacity() == size()){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = val;_finish++;}//*******************************************************************//*******************************************************************void pop_back(){if (!empty()){--_finish;}}//*******************************************************************//*******************************************************************bool empty()const{return _start == _finish;}//*******************************************************************//*******************************************************************void reserve(size_type n){if (n > size()){iterator tmp = new value_type[n];size_type oldsize = size();for (int i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + oldsize;_endofstorage = tmp + n;}}//*******************************************************************//*******************************************************************size_type size()const{return _finish - _start;}//*******************************************************************//*******************************************************************size_type capacity()const{return _endofstorage - _start;}//*******************************************************************//*******************************************************************void clear(){_finish = _start;}//*******************************************************************//*******************************************************************value_type& operator[](size_type n){assert(n < size());return _start[n];}//*******************************************************************//*******************************************************************const value_type& operator[](size_type n)const{assert(n < size());return _start[n];}//*******************************************************************//*******************************************************************vector<T>& operator=(const vector<T>& x){if (&x == this){return*this;}clear();for (auto& ch : x){push_back(ch);}return *this;}//*******************************************************************//*******************************************************************iterator begin(){return _start;}//*******************************************************************//*******************************************************************const_iterator begin()const{return _start;}//*******************************************************************//*******************************************************************iterator end(){return _finish;}//*******************************************************************//*******************************************************************const_iterator end()const{return _finish;}//*******************************************************************//*******************************************************************void swap(vector<T>& x){std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofstorage, x._endofstorage);}//*******************************************************************//*******************************************************************~vector<T>(){delete[]_start;_start = _finish = _endofstorage = nullptr;}//*******************************************************************//*******************************************************************iterator insert(iterator position, const value_type& val);iterator erase(iterator position);void resize(size_type n,value_type val=value_type());//*******************************************************************private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&template<typename T> //vector<T>::iterator没有实例化的适合 不清楚iterator是类型还是静态的成员变量需要加typenametypename vector<T>::iterator vector<T>::insert(vector<T>::iterator position, const vector<T>::value_type& val){assert(begin() <= position);assert(position <= end());if (size() == capacity()){size_type pos = position - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);position = _start + pos;//更新position}iterator tmp = end() - 1;while (position <= tmp){*(tmp + 1) = *tmp;tmp--;}*position = val;++_finish;return position;}//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&template<typename T>typename vector<T>::iterator vector<T>::erase(vector<T>::iterator position){assert(begin() <= position && position < end());assert(!empty());iterator tmp = position + 1;while (tmp < end()){*(tmp - 1) = *tmp;tmp++;}--_finish;return position;}//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&template<typename T>void vector<T>::resize(vector<T>::size_type n, vector<T>::value_type val){if (n < size()){_finish = _start + n;}else{reserve(n);for (iterator it = _finish; it < _start + n; it++){*it = val;++_finish;}}}//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
}为了于命名空间std里的vector区分开来，俺将模拟实现的vector用命名空间HD封装起来。
对于模拟实现的vector，这个类模板的成员函数大部分均在类模板内声明和定义；而对于成员函数insert、erase、resize则采取声明和定义分离，在类模板内声明，在类模板外定义，但声明和定义均在同一个vector.h中。
2.附带两个函数模板
为了方便模拟实现的vector<T>对象的输出，我实现了1个函数模板用于模拟实现的vector<T>对象的输出：
这个函数模板同样实现在vector.h中，并用命名空间HD封装：
namespace HD
{template<typename T>void print_vector(const vector<T>& v){//规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator是类型还是静态成员变量,// 需要加typename说明const_iterator是类型//typename vector<T>::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << ' ';it++;}cout << endl;/*for (auto& ch : v){cout << ch << ' ';}cout << endl;*/}
}其中要注意的是：
- 并非所有的vector<T>对象通过这个函数模板实例化得到的函数都能用于vector<T>对象的输出，
*it的类型（也就是T）的数据要能支持直接的流插入才行。
例如，若T是vector<int>，那么HD::vector<vector<T>>对象通过这个函数模板实例化而来的函数，当这个函数调用时，必定报错：
在test.cpp中：
#include"vector.h" int main() {HD::vector<vector<int>> v(5);print_vector(v);return 0; }
再例如，若T是string，那么那么HD::vector<string>对象通过这个函数模板实例化而来的函数调用起来是没有问题的，因为string类型的数据支持直接的流插入：
在test.cpp中：
#include"vector.h" int main() {HD::vector<string> v(5,"aaaa");print_vector(v);return 0; }
- 看到it的类型是vector<T>::const_iterator，那么在这个类型之前的typename是干啥的？
通过类名::这种方式去类里面取东西，可以取到静态成员变量和类型。但是若这个类是一个抽象的没有实例化的类（也就是类模板）里面取东西，编译器无法区分取到的是静态成员变量还是类型。就像这里vector<T>是一个没有实例化的类，去这里取到const_iterator，编译器无法区分这到底是静态成员变量还是类型。
解决办法有2种：
1.加typename，声明取到的是类型而不是静态成员变量。
typename vector<T>::const_iterator it = v.begin();2.用auto，让编译器自己推到it的类型。
auto it = v.begin();
为了方便”任何“容器对象的输出，我实现了1个函数模板用于”任何“容器对象的输出：
这个函数模板同样实现在vector.h中，并用命名空间HD封装：
namespace HD
{template<typename container>void print_container(const container& v){//规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator是类型还是静态成员变量，//需要加typename说明const_iterator是类型typename container::const_iterator it = v.begin();//auto it = v.begin();while (it != v.end()){cout << *it << ' ';it++;}cout << endl;/*for (auto& ch : v){cout << ch << ' ';}cout << endl;*/}
}这里也有2点要注意，但是跟上一个函数模板一样，俺就不细说了。
如果有兴趣可以对比上一个函数模板，为什么这两个函数模板适用的对象不同，为什么上一个函数模板只能用于vector<T>对象，而本函数模板适用于”任何“容器对象？
3.模拟实现部分接口的细节
我模拟实现vector中有很多个接口，我就介绍其中一些接口的模拟实现。
3.1.insert
我模拟实现insert采取声明和定义分离，其中，定义如下：
template<typename T> //vector<T>::iterator没有实例化的适合 不清楚iterator是类型还是静态的成员变量需要加typenametypename vector<T>::iterator vector<T>::insert(vector<T>::iterator position, const vector<T>::value_type& val){assert(begin() <= position);assert(position <= end());if (size() == capacity()){size_type pos = position - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);position = _start + pos;//更新position}iterator tmp = end() - 1;while (position <= tmp){*(tmp + 1) = *tmp;tmp--;}*position = val;++_finish;return position;}模拟实现insert的思想还是很简单的，大致上无非查容量是否充足，若不充足就扩容，然后挪动数据，最后插入数据。其中需要注意的细节是更新position。
如果更新position这个细节不处理的话，会导致迭代器失效的问题。假设没有更新position，且看：
若是vector<T>对象容量是4，且存储的数据也有4个，那么当insert尾插入第5个数据的时候会扩容（reserve），那么：
如果不更新position，那么position还是指向旧空间，这是正确的吗？这就导致2个问题：
1.还指向被delete掉了的旧空间，这不是就类似野指针了吗？野迭代器吗？
2.position这个迭代器没有指向扩容后的正确空间上，会导致接下来的挪动数据（while循环）逻辑混乱
这里position是一个迭代器，那么若是不更新position，就导致position会出现问题，不就失效了吗？这里也引申出迭代器失效的概念，迭代器失效有很多形态，这里只是体现其中1种：类似野指针。
我们也可以验证一下：
若没有更新position，也就是将更新position那句语句注释掉后，我在test.cpp测试：
#include"vector.h"
int main()
{HD::vector<int> v(4, 10);v.insert(v.begin()+2, 5);print_vector(v);return 0;
}
若将更新position那句语句取消注释：
#include"vector.h"
int main()
{HD::vector<int> v(4, 10);v.insert(v.begin()+2, 5);print_vector(v);return 0;
}
3.2.reserve
看到模拟实现的reserve，其声明和定义不分离：
void reserve(size_type n){if (n > size()){iterator tmp = new value_type[n];size_type oldsize = size();for (int i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + oldsize;_endofstorage = tmp + n;}}这里需要注意的细节是：
1.动态开辟了新空间后，要将数据从旧空间拷贝到新空间上。其中，这个拷贝动作不能用memcpy函数等拷贝，因为那是浅拷贝。我们不确定vector容器里面到底存放了什么类型的数据，若存放了int这种内置类型的数据，用memcpy拷贝当然没问题，但是若是存放了string等类型的数据，还能浅拷贝吗？
解决办法：就是深拷贝数据。其中一种写法如上。
2._finish指向新空间时，一定要指向正确位置。若是写成_finish=tmp+size();就会出问题，因为_start先更新过了，那么size()里面的_start已经更新为了tmp，那么_finish=tmp+size()实际上就变为了_finish=tmp+_finish-tmp，导致_finish原来的_finish，还是指向旧空间上的原本位置，没有指向新空间的正确位置。
解决办法：更新_start、_finish前，可以用一个变量oldsize记录size()……如上代码，自己看哈！
3.3.constructor
模拟实现了4个构造：
//*******************************************************************vector<T>(size_type n,const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}vector<T>(int n, const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}//*******************************************************************//*******************************************************************// C++11新增关键字default用法：可以强制生成默认构造。//vector<T>() = default;vector<T>(){}//*******************************************************************//*******************************************************************vector<T>(const vector<T>& x){/*for (auto& ch : x){push_back(ch);}*/iterator tmp = new value_type[x.capacity()];for (int i=0;i<x.size();i++){tmp[i] = x[i];}_start = tmp;_finish = tmp + x.size();_endofstorage = tmp + x.capacity();}//*******************************************************************//*******************************************************************template<typename InputIterator>vector<T>(InputIterator first, InputIterator last){InputIterator it = first;while (it != last){push_back(*it);it++;}}其中explicit vector (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type())模拟实现如下第1个成员函数：
vector<T>(size_type n,const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}vector<T>(int n, const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}看到这两个构造函数高度相似，仅仅一个参数类型不同，那么为什么还要实现如上第2个 成员函数呢？
原因在于如下情形，若没有实现如上第2个成员函数（我先将其注释掉），在test.cpp中：
#include"vector.h"
int main()
{HD::vector<int> v(4, 10);print_vector(v);return 0;
}运行：
导致运行错误的原因在于，它去匹配了如下模拟实现的构造函数模板：
template<typename InputIterator>vector<T>(InputIterator first, InputIterator last){InputIterator it = first;while (it != last){push_back(*it);it++;}}为什么匹配了如上构造函数模板呢？因为主函数内的调用HD::vector<int> v(4,10);可以匹配如上构造函数模板的实例化，也可以匹配如下构造函数：
vector<T>(size_type n,const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}那么编译器就选择匹配构造函数模板的实例化，因为构造函数模板的实例化的2个参数类型均是int；而匹配另一个构造函数的话，参数类型1个是size_type，1个是int，也可以匹配，但是相比于构造函数模板的实例化来说就没那么匹配了，当匹配了构造函数模板的实例化时，实例化而来的函数函数体内需要解引用操作，拿一个int类型的数据去解引用不报错才怪。
如这种情形，在test.cpp中：
#include"vector.h"
int main()
{HD::vector<int> v(4, 10);print_vector(v);return 0;
}不希望匹配到函数模板的实例化的话，可以附带实现如下构造函数：
vector<T>(int n, const value_type& val = value_type()){for (int i = 0; i < n; i++){push_back(val);}}附带实现了如上构造函数的话。编译器看到有现成的构造函数且去构造函数模板实例化一个构造函数的匹配度不会更高，就不会选择去构造函数模板实例化一个构造函数来匹配了。
4.小知识
介绍一下insert接口和erase接口调用可能引起的迭代器失效的问题：
4.1.insert
首先，再次附上模拟实现的insert的定义：
template<typename T> //vector<T>::iterator没有实例化的适合 不清楚iterator是类型还是静态的成员变量需要加typenametypename vector<T>::iterator vector<T>::insert(vector<T>::iterator position, const vector<T>::value_type& val){assert(begin() <= position);assert(position <= end());if (size() == capacity()){size_type pos = position - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);position = _start + pos;//更新position}iterator tmp = end() - 1;while (position <= tmp){*(tmp + 1) = *tmp;tmp--;}*position = val;++_finish;return position;}-
情形1：
在test.cpp中：
#include"vector.h"
int main()
{HD::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = find(v.begin(), v.end(), 2);if (it != v.end()){v.insert(it, 100);cout << *it << endl;}return 0;
}PS：find 是C++算法库中的一个函数模板，用于查找一段迭代器区间的某个值，若找不到返回find实例化函数第二个参数。
运行结果：
导致出现这样子问题的原因还是因为insert中的扩容（reserve）导致迭代器it失效了：
当迭代器去访问一段不属于自己的空间，就会出问题！迭代器失效了：跟一个野指针似的。
解决办法：
insert后迭代器就失效了，想要访问就要更新后再访问，如：
#include"vector.h"
int main()
{HD::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = find(v.begin(), v.end(), 2);if (it != v.end()){it = v.insert(it, 100);//insert并更新itcout << *it << endl;//更新后访问it}return 0;
}
这就是insert接口为什么要返回1个指向新插入元素的迭代器了，方便我们更新迭代器！
对于这种情形，我还想过一些不靠谱的解决办法，但是想想还是不靠谱的：
不靠谱解决办法：我们在模拟实现insert时，不是在insert函数体内更新过position吗？能不能通过position的更新来实现it的更新呢？insert模拟实现成这样子：
声明：
iterator insert(iterator& position, const value_type& val);定义：
template<typename T> //vector<T>::iterator没有实例化的适合 不清楚iterator是类型还是静态的成员变量需要加typenametypename vector<T>::iterator vector<T>::insert(vector<T>:: iterator& position, const vector<T>::value_type& val){assert(begin() <= position);assert(position <= end());if (size() == capacity()){size_type pos = position - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);position = _start + pos;//更新position}iterator tmp = end() - 1;while (position <= tmp){*(tmp + 1) = *tmp;tmp--;}*position = val;++_finish;return position;}position是it的引用，这样子如果扩容的话，position的更新也会导致it更新。我可太聪明了！
可是：
#include"vector.h" int main() {HD::vector<int> v;v.push_back(1);v.push_back(2);v.insert(v.begin(), 0);return 0; }
为什么报错呢？
v.begin()传值返回一个迭代器，由于传值返回，所以这个迭代器是一个临时变量，临时变量具有常性。一个具有常性的临时变量作为实参传递给position，position作为其引用，能是普通引用吗？想要搞引用就必须是常引用。
那好，再改，改为常引用：
声明：
iterator insert(const iterator& position, const value_type& val);定义：
template<typename T> //vector<T>::iterator没有实例化的适合 不清楚iterator是类型还是静态的成员变量需要加typenametypename vector<T>::iterator vector<T>::insert( const vector<T>::iterator& position, const vector<T>::value_type& val){assert(begin() <= position);assert(position <= end());if (size() == capacity()){size_type pos = position - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);position = _start + pos;//更新position}iterator tmp = end() - 1;while (position <= tmp){*(tmp + 1) = *tmp;tmp--;}*position = val;++_finish;return position;}可是如果改成常引用的话，position不是不能更新了吗？这不倒反天罡了？
所以不靠谱。
- 情形2：
在test.cpp中：
#include"vector.h"
int main()
{HD::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);auto it = find(v.begin(), v.end(), 3);if (it != v.end()){v.insert(it, 520);(*it) *= 10;}print_vector(v);return 0;
}
看一下这种情况：这种情况insert不涉及扩容问题了，但是我原本想着在3前面插入520，然后将3乘以10来着，到头来让520乘以10了，问题在于：
insert过后迭代器it的位置意义已经变了，我们认为这也是一种迭代器失效。
解决办法：
insert后若是想要访问迭代器，记得更新后再访问：
#include"vector.h"
int main()
{HD::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);auto it = find(v.begin(), v.end(), 3);if (it != v.end()){v.insert(it, 520);it++;//更新迭代器it(*it) *= 10;//更新it再访问}print_vector(v);return 0;
}
像迭代器失效的第2种情况，迭代器的位置意义已经变了，也能正常运行啊，那为什么也认为是迭代器失效的表现呢？
当底层发生扩容的insert，迭代器就像一个野指针似的，迭代器失效无疑了。但是你不知道insert的时候，底层到底扩不扩容。所以我们也将迭代器位置的意义发生改变也认为迭代器失效了，想要访问的话一律需要更新才行。
在VS2022当中对insert进行了强制的检查，若是insert后没有更新迭代器就去访问，就算是没有发生扩容那种情况，也会报错：
我先摸清楚VS2022平台下对于vector容器的扩容是怎么个扩法：
#include<vector> using namespace std; int main() {vector<int> v;size_t vcapacity = v.capacity();int i = 20;while (i--){v.insert(v.end(), 5);if (vcapacity != v.capacity()){cout << "扩容了：" << v.capacity() << endl;}}return 0; }
其中可以看到，当底层容量为9到13不会进行扩容。所以：
#include<vector> using namespace std; int main() {vector<int> v;int i = 10;while (i--){v.insert(v.end(), i);}auto it = find(v.begin(), v.end(), 5);if (it != v.end()){v.insert(it, 66);//不扩容cout << *it << endl;//不更新访问}return 0; }
若是更新迭代器再访问：
#include<vector> using namespace std; int main() {vector<int> v;int i = 10;while (i--){v.insert(v.end(), i);}auto it = find(v.begin(), v.end(), 5);if (it != v.end()){it = v.insert(it, 66);//更新it，不扩容cout << *it << endl;//更新再访问}return 0; }
4.2.erase
这个接口不会发生扩容导致的迭代器像野指针的失效问题，但是会发生迭代器位置意义变了而导致迭代器失效问题，很好理解的，不解释了。
解决办法：erase后若要访问迭代器，请更新。
VS2022下同样进行了强制检查，若erase后访问了没有更新的迭代器，你敢访问它就敢报错：
#include<vector> using namespace std; int main() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);int x ;cin >> x;auto it = find(v.begin(), v.end(), 2);if (it != v.end()){v.erase(it);//erase且不更新itcout << *it << endl;//不更新it就访问}return 0; }
如果更新了it就没问题：
#include<vector> using namespace std; int main() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);int x ;cin >> x;auto it = find(v.begin(), v.end(), 2);if (it != v.end()){it = v.erase(it);//erase且更新itcout << *it << endl;//更新it访问}return 0; }
如有错误，恳请斧正，感谢阅读！