创作不易，感谢三连 ！！
一，前言
在学习string类的时候，我们可能会发现遍历的话下标访问特别香，比迭代器用的舒服，但是下标其实只能是支持连续的空间，他的使用是非常具有局限性的，随着STL学习的深入我们会发现其实迭代器才是大佬！！Vector虽然也支持下标访问，但是很多成员函数都是用的迭代器，所以我们要模拟实现的话迭代器十分重要，vs使用的是PJ版的STL版本，比较难懂，所以我们模拟实现统一用SGI版本去实现，所以在模拟实现之前，我们要去看看他的源码到底有哪些成员变量
SGI下的vector有三个成员变量，通过观察其他源码可以大致推断 _start是指向起始位置，_finish是指向有效数据的下一个位置（迭代器都遵循左闭右开），end_of_storage是指向有效容量的最后一个位置。
通过这个我们可以观察到SGI版本下的迭代器其实就是一个原生指针，value_type*类型相当于是模板T对应的指针类型，有了这些大致了解，我们就可以去模拟实现啦！！
二，vector的模拟实现
大致框架需要有模板（类外定义）/迭代器以及迭代器的获取（public定义，要有可读可写的也要有可读不可写的）/成员变量（private定义） 并且为了不和库的vector冲突，我们需要自己搞一个命名空间
namespace cyx { //模板 template<class T> //迭代器(可读可写) class vector { public： typedef T* iterator; iterator begin() { return _start; } iterator end() { return _finish; } //迭代器(可读不可写) typedef const T* const_iterator; const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } private： //成员变量 iterator _start; iterator _finish; iterator _end_of_storage; } }
然后我们开始实现！！
2.1 相关成员函数
2.1.1 无参构造函数
//无参构造函数 vector() :_start(nullptr) ,_finish(nullptr) ,_end_of_storage(nullptr) {}
2.1.2 迭代器区间构造
//传别人的迭代器进行构造 template<class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { //这里传的是别人的迭代器，不知道会传多少数据，不能提前扩容，只能让pushback的时候去判断 while (first != last) { push_back(*first); ++first; } }
push_back是尾插数据，具体实现后面会写。
思考：为什么迭代器也要搞个类模板呢？
答：本质上是为了让这个函数更加灵活，可以传不同类型的迭代器来帮助我们初始化！！
比如这个地方我们传string类的迭代器
传vector类的迭代器
2.1.3 有参构造函数（对n个存储的类型去调用他们的构造）
//有参构造函数（对n个存储的类型去调用他们的构造） vector(size_t n,const T&val=T() ) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(n);//因为我们知道会进多少数据，所以可以提前开空间 for (int i = 0; i < n; ++i) push_back(val); }
reserve是扩容到n，具体实现后面会写。
思考：
1.缺省值T( )是什么意思
答：这个地方的缺省值不能给0！！因为vector可能会存储内置类型，也可能会存储自定义类型，比如vector<string>,所以如果我们没给值，缺省值就要给他的默认无参构造函数，这个默认构造函数可以使用匿名对象。
2.const T&val=T（） T（）不是用一次就析构吗，为什么可以用引用
答：T（）是一个用一次就析构的匿名对象，其实本质上是因为他没有名字，用T引用val可以充当他的名字，此时用val就相当于用这个匿名对象，所以匿名对象的生命周期被延长到和val一样，但是由于匿名对象是一个临时变量，所以具有常性，所以必须用const修饰的val才可以当他的别名，否则会出现权限放大！！
3.非法的间接寻址是为什么？
如下图我传（10，5），会出非法间接寻址
但是我传（10u，5）就可以正常使用了，为什么会这样？？
答：
根据上图写出一个重载的有参构造
//重载一个防止间接寻址 vector(int n, const T val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(n);//因为我们知道会进多少数据，所以可以提前开空间 for (int i = 0; i < n; ++i) push_back(val); }
2.1.4 assign
assign跟赋值很相似，都是将新内容分配给容器，替换其当前内容，并相应地修改其大小。然后assign有两个版本，第一个版本是迭代器区间替换（我们可以控制范围），第二个版本是直接替换成n个相同元素，而赋值的话就是简单的直接替换，可以说是assign的一个特殊情况，所以我们先实现assign再用=来复用。
（1）迭代器区间替换
//assign的迭代器区间替换 template <class InputIterator> void assign(InputIterator first, InputIterator last) { size_t sz = last - first; T* temp = new T[sz]; for (int i = 0; i < sz; ++i) temp[i] =*(first+i); delete[]_start; _start = temp; _finish = _end_of_storage = _start + sz; }
（2）直接替换
//assign的直接替换 void assign(size_t n, const T& val) { T* temp = new T[n]; for (int i = 0; i < n; ++i) temp[i] = val; delete[]_start; _start = temp; _finish = _end_of_storage = _start + n; }
但是这样的话，就会跟之前的有参构造一样，会由于n是size_t类型，如果两个都是传的int就会出现间接寻址的问题
所以我们必须要写一个重载版本
void assign(int n, const T& val) { T* temp = new T[n]; for (int i = 0; i < n; ++i) temp[i] = val; delete[]_start; _start = temp; _finish = _end_of_storage = _start + n; }
2.1.5 拷贝构造+memcpy拷贝问题+赋值重载
但是真的有这么顺利吗？？
思考：
为什么存string类就会崩了？？ 这就涉及到memcpy的拷贝问题
我们以上述问题来画图解释一下
总结：
1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是
浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
所以在这个地方我们的拷贝构造不能用memcpy
//拷贝构造（传统） vector(const vector<T>& v) :_start(nullptr) ,_finish(nullptr) ,_end_of_storage(nullptr) { _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T)*v.size()); 不能用memcpy 是浅拷贝 for (int i = 0; i < v.size(); ++i) _start[i] = v._start[i];//实现重载运算符 _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); }
但是真的没有问题了吗？？看看这个
但道理来说得打印出9个1 结果呢？？
原因是什么呢，我们先看看resize函数
传统赋值重载可以复用assign
//重载赋值=（传统） vector<T>& operator=(const vector<T>& v) { assign(v.begin(), v.end()); return *this; }
2.1.6 拷贝构造和赋值重载的现代写法
现代的写法就是用的资本家的思想，窃取劳动成果
先写个swap函数
//交换 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }
拷贝构造的现代写法思路：创建一个临时对象利用被拷贝对象的迭代器区间构造，然后再swap一下就可以了！
vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { vector<T> temp(v.begin(), v.end());//让临时对象借助迭代器区间构造出来 swap(temp);//窃取革命成果 }
赋值重载的现代写法的思路：反正我自己的空间也不要了，被赋值对象传值过来（这样被赋值对象不会被修改），然后直接和临时对象swap就可以了！！
vector<T>& operator=(vector<T> v) { swap(v);//反正我原来的空间也要销毁，我跟你传值过来的v直接交换，而且不会改变你 return *this; }
2.1.7 析构函数
~vector() { /*if (_start)*///delete 会自动检查空指针 没必要 delete[] _start; _start = _finish = _end_of_storage = nullptr; }
注意：delete空指针是没关系的，delete会自己判断 delete出问题一般都是野指针
2.1.8 构造函数相关的全部代码
我们发现大部分都设计要到初始化为nullptr，c11后是支持直接在成员变量那边给缺省值的，所以们可以美化一下
全部代码
//无参构造函数 vector() {} //有参构造函数（对n个存储的类型去调用他们的构造） vector(size_t n, const T& val = T()) { reserve(n);//因为我们知道会进多少数据，所以可以提前开空间 for (int i = 0; i < n; ++i) push_back(val); } //重载一个防止间接寻址 vector(int n, const T val = T()) { reserve(n);//因为我们知道会进多少数据，所以可以提前开空间 for (int i = 0; i < n; ++i) push_back(val); } //传别人的迭代器区间进行构造 template<class InputIterator> vector(InputIterator first, InputIterator last) { //这里传的是别人的迭代器，不知道会传多少数据，不能提前扩容，只能让pushback的时候去判断 while (first != last) { push_back(*first); ++first; } } //拷贝构造（传统写法） vector(const vector<T>& v) { _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T)*v.size()); 不能用memcpy 是浅拷贝 for (size_t i = 0; i < v.size(); ++i) _start[i] = v._start[i];//实现重载运算符 _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); } //拷贝构造（现代写法） //vector(const vector<T>& v) //{ // vector<T> temp(v.begin(), v.end());//让临时对象借助迭代器区间构造出来 // swap(temp);//窃取革命成果 //} //交换 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } 重载赋值=（传统） vector<T>& operator=(const vector<T>& v) { T* temp = new T[v.capacity()]; for (int i = 0; i < v.size(); ++i) temp[i] = v[i]; delete[]_start; _start = temp; _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); return *this; } //赋值重载现代写法 //vector<T>& operator=(vector<T> v) //{ // swap(v);//反正我原来的空间也要销毁，我跟你传值过来的v直接交换，而且不会改变你 // return *this; //} //析构函数 ~vector() { /*if (_start)*///delete 会自动检查空指针 没必要检查 delete[] _start; _start = _finish = _end_of_storage = nullptr; }
2.2 常见接口
2.2.1 获取size和capacity
//获取size size_t size() const { return _finish - _start; } //获取capacoty size_t capacity() const { return _end_of_storage - _start; }
2.2.2 判空
//判空 bool empty() const { return _start == _finish; }
2.2.3 重载[ ]
1.可读可写[ ]
//重载[](可读可写) T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; }
2.可读不可写[]
//重载[](可读不可写) const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; }
3.三种访问方法
下标
//下标遍历 for (int i = 0; i < v1.size(); ++i) cout << v1[i] << " "; cout << endl;
迭代器
//迭代器遍历 vector<int>::const_iterator it = v1.begin(); while (it != v1.end()) { cout << *it << " "; ++it; } cout << endl;
范围for
//范围for遍历 for (auto e : v1) cout << e << " "; cout << endl; v1.resize(100); cout << v1.size() << endl; for (auto e : v1) cout << e << " "; cout << endl;
2.2.4 提前扩容
void reserve(size_t n) { size_t sz = size();//防止丢失 if (n > capacity()) { T* temp = new T[n]; if (_start)//如果为空，就不需要拷贝也不需要释放 { for (size_t i = 0; i < sz; ++i) temp[i] = _start[i]; delete[] _start; } _start = temp; _finish = _start + sz; _end_of_storage = _start + n; } }
考虑到之前的memcpy拷贝问题，这里不能用memcpy了！！
还要注意的是要提前记录size（），否则原空间销毁了就找不到了。
2.2.5 提前扩容+初始化
有三种情况，第一种是给的n比原来的size小，第二种是n比size大但是比capacity小，第三种是n比capacity大，这个时候需要扩容
//提前扩容+初始化 void resize(size_t n, T val = T()) { //给小 if (n < size()) _finish = _start + n; //给大 else { //容量不够就扩 if (n > capacity()) reserve(n); while (_finish != _start + n) { *_finish = val; ++_finish; } } }
2.2.6 尾插和尾删
void push_back(const T& val) { if (_finish == _end_of_storage) reserve(capacity() == 0 ? 4 : 2 * capacity()); *_finish = val; ++_finish; } //尾删 void pop_back() { //防止没有元素可删 assert(!empty()); --_finish; }
尾插要注意扩容之前要判断一下，因为如果是0的话怎么扩都是0
我们会发现这次的指定位置插入删除不像string那样用size_t pos 而是iterator pos
2.2.7 指定位置插入
这样写有什么问题吗？？
看似好像没有什么问题，但是如果把pushback（5）去掉
为什么会这样呢？
原因就是扩容后空间变了，但是pos还是指向原来的空间！！
所以我们解决方案就是pos在扩容的时候要更新一下
iterator insert(iterator pos, const T& val) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _end_of_storage) { size_t len = pos - _start;//记录相对距离，方便更新pos reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = val; ++_finish; return pos; }
2.2.8 指定位置删除
返回值是pos的下一个位置
iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator start = pos + 1; while (start != _finish) { *(start - 1) = *start; ++start; } --_finish; return pos; }
2.3 迭代器失效问题
会引起其底层空间改变的操作，都有可能使得迭代器失效。
比如：resize、reserve、insert、erase、 push_back等。
2.3.1.insert的失效
就是因为扩容导致pos失效，我们需要去及时更新pos
但是我们传的pos是值传递，所以我们更新的后pos更新，我们在后面解引用pos就会出现经典的解引用野指针问题。
那我们怎么传回pos呢？？就得用返回值！！这也是为什么insert的返回值用iterator的原因，我们想继续用的话就得去接收一下返回值，就可以了
虽然有了返回值，我们可以去接收更新后的pos，但是一旦我们使用了任意一个可能扩容的函数，都会到时pos的失效，从而有可能回引发野指针问题，这个问题是不太好避免的，所以我们认为迭代器只能用一次，因为结果不可预测！
2.3.2 erase的失效
erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 就失效了。因此删除 vector 中任意位置上元素时，vs 就认为该位置迭代器失效了。
vs和g++对比
结果是未定义的！！不同编译器场景可能不同，严格来说vs更严谨
思考：
假设没有强制检查（比如我们自己写的vector），想删除删除 vector 中所有偶数
但是如果只有4个
为什么会这样呢，我们画图分析
从这边我们也能看到为什么erase返回值也要用iterator的原因，我们想继续用的话就得去接收一下返回值
2.3.3 扩容导致的失效
可能本来还能用，但是中间扩容过，所以也不能用了
用pos前用一样reserve，也会失效
总而言之：尽量不要复用pos迭代器，因为任何一个可能扩容的操作都会导致失效
2.4 比较不常用的接口
2.4.1 清理元素
void clear() const { _finish = _start; }
2.4.2 缩容
void shrink_to_fit() { size_t sz = size();//记录 T* temp = new T[sz]; for (size_t i = 0; i < sz; ++i) temp[i] = _start[i]; delete _start; _start = temp; _finish = _start + sz; _end_of_storage = _start + sz; }
2.5 反向迭代器
这里博主直接上代码，等list模拟实现的时候再放在一起分析
1、利用正向迭代器去封装反向迭代器
//反向迭代器的封装 template<class iterator, class Ref> struct ReverseIterator { typedef ReverseIterator<iterator, Ref> Self;//Ref单纯是为了控制解引用的时候是否可以被写 //利用反向迭代器的类来封装正向迭代器，同时在类里面设置反向迭代器的行为 ReverseIterator(iterator it) :_cur(it) {} Ref operator*() { iterator temp = _cur; --temp; return *temp; } Self& operator++() { --_cur; return *this; } Self operator++(int) { iterator temp = _cur; --_cur; return temp; } Self& operator--() { ++_cur; return *this; } Self operator--(int) { iterator temp = _cur; ++_cur; return temp; } Self operator+(int n) { iterator temp = _cur; temp-=n; return temp; } Self operator-(int n) { iterator temp = _cur; temp+= n; return temp; } bool operator!=(const Self& s) { return _cur != s._cur; } bool operator==(const Self& s) { return _cur == s._cur; } //成员变量 iterator _cur; };
2、rebegin和rend
//反向迭代器(可读可写) reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } //反向迭代器（可读不可写） const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
三，vector实现的全部代码
namespace cyx { //反向迭代器的封装 template<class iterator, class Ref> struct ReverseIterator { typedef ReverseIterator<iterator, Ref> Self;//Ref单纯是为了控制解引用的时候是否可以被写 //利用反向迭代器的类来封装正向迭代器，同时在类里面设置反向迭代器的行为 ReverseIterator(iterator it) :_cur(it) {} Ref operator*() { iterator temp = _cur; --temp; return *temp; } Self& operator++() { --_cur; return *this; } Self operator++(int) { iterator temp = _cur; --_cur; return temp; } Self& operator--() { ++_cur; return *this; } Self operator--(int) { iterator temp = _cur; ++_cur; return temp; } Self operator+(int n) { iterator temp = _cur; temp-=n; return temp; } Self operator-(int n) { iterator temp = _cur; temp+= n; return temp; } bool operator!=(const Self& s) { return _cur != s._cur; } bool operator==(const Self& s) { return _cur == s._cur; } //成员变量 iterator _cur; }; template<class T> class vector { public: //正向迭代器 typedef T* iterator; typedef const T* const_iterator; //反向迭代器 typedef ReverseIterator<iterator, T&> reverse_iterator; typedef ReverseIterator<iterator, const T&> const_reverse_iterator; //正向迭代器(可读可写) iterator begin() { return _start; } iterator end() { return _finish; } //正向迭代器（可读不可写） iterator begin() const { return _start; } iterator end() const { return _finish; } //反向迭代器(可读可写) reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } //反向迭代器（可读不可写） const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } //无参构造函数 vector() {} //有参构造函数（对n个存储的类型去调用他们的构造） vector(size_t n, const T& val = T()) { reserve(n);//因为我们知道会进多少数据，所以可以提前开空间 for (int i = 0; i < n; ++i) push_back(val); } //重载一个防止间接寻址 vector(int n, const T val = T()) { reserve(n);//因为我们知道会进多少数据，所以可以提前开空间 for (int i = 0; i < n; ++i) push_back(val); } //传别人的迭代器进行构造 template<class InputIterator> vector(InputIterator first, InputIterator last) { //这里传的是别人的迭代器，不知道会传多少数据，不能提前扩容，只能让pushback的时候去判断 while (first != last) { push_back(*first); ++first; } } //拷贝构造（传统写法） vector(const vector<T>& v) { _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T)*v.size()); 不能用memcpy 是浅拷贝 for (size_t i = 0; i < v.size(); ++i) _start[i] = v._start[i];//实现重载运算符 完成深拷贝 _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); } //拷贝构造（现代写法） //vector(const vector<T>& v) //{ // vector<T> temp(v.begin(), v.end());//让临时对象借助迭代器区间构造出来 // swap(temp);//窃取革命成果 //} //交换 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } //重载赋值=（传统） vector<T>& operator=(const vector<T>& v) { assign(v.begin(), v.end()); return *this; } //赋值重载现代写法 //vector<T>& operator=(vector<T> v) //{ // swap(v);//反正我原来的空间也要销毁，我跟你传值过来的v直接交换，而且不会改变你 // return *this; //} //assign的迭代器区间替换 template <class InputIterator> void assign(InputIterator first, InputIterator last) { size_t sz = last - first; T* temp = new T[sz]; for (int i = 0; i < sz; ++i) temp[i] =*(first+i); delete[]_start; _start = temp; _finish = _end_of_storage = _start + sz; } //assign的直接替换 void assign(size_t n, const T& val) { T* temp = new T[n]; for (int i = 0; i < n; ++i) temp[i] = val; delete[]_start; _start = temp; _finish = _end_of_storage = _start + n; } assign的直接替换 重载//防止间接寻址 void assign(int n, const T& val) { T* temp = new T[n]; for (int i = 0; i < n; ++i) temp[i] = val; delete[]_start; _start = temp; _finish = _end_of_storage = _start + n; } // //析构函数 ~vector() { /*if (_start)*///delete 会自动检查空指针 delete[] _start; _start = _finish = _end_of_storage = nullptr; } //获取size size_t size() const { return _finish - _start; } //获取capacoty size_t capacity() const { return _end_of_storage - _start; } //判空 bool empty() const { return _start == _finish; } //重载[](可读可写) T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } //重载[](可读不可写) const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } //提前扩容+初始化 void resize(size_t n, T val = T()) { //给小 if (n < size()) _finish = _start + n; //给大 else { //容量不够就扩 if (n > capacity()) reserve(n); while (_finish != _start + n) { *_finish = val; ++_finish; } } } //提前扩容 void reserve(size_t n) { size_t sz = size();//防止丢失 if (n > capacity()) { T* temp = new T[n]; if (_start)//如果为空，就不需要拷贝也不需要释放 { for (size_t i = 0; i < sz; ++i) temp[i] = _start[i]; delete[] _start; } _start = temp; _finish = _start + sz; _end_of_storage = _start + n; } } //尾插 void push_back(const T& val) { if (_finish == _end_of_storage) reserve(capacity() == 0 ? 4 : 2 * capacity()); *_finish = val; ++_finish; } //尾删 void pop_back() { //防止没有元素可删 assert(!empty()); --_finish; } //指定位置插入 iterator insert(iterator pos, const T& val) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = val; ++_finish; return pos; } //指定位置删除 iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator start = pos + 1; while (start != _finish) { *(start - 1) = *start; ++start; } --_finish; return pos; } //清理元素 void clear() const { _finish = _start; } //缩容 void shrink_to_fit() { size_t sz = size();//记录 T* temp = new T[sz]; for (size_t i = 0; i < sz; ++i) temp[i] = _start[i]; delete _start; _start = temp; _finish = _start + sz; _end_of_storage = _start + sz; } private: iterator _start= nullptr; iterator _finish= nullptr; iterator _end_of_storage= nullptr; };
有什么不懂得可以问博主哦！后面有时间再来细化接口
