C++——vector的模拟实现
引言：
本篇主要针对以下两点做出简要分析（个人角度）：
1、部分模拟实现vector类的的代码；
2、在模拟实现vector类过程中遇到的问题；
总体框架：
因为是模拟实现vector，因此要在命名空间中实现，避免与重命名与库函数冲突，因此整体的大框架如下：
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace jc
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//成员函数
private:
iterator _start = nullptr; //初始化列表的缺省参数
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
}
}注：
1、因为vector容器的数据不单单是字符，因此需要类模板来实现
2、此处的iterator类似为指针，但需要知道的是iterator不单单是指针，还有其他(尚未学习)
一、vector中各类函数的返回值
1：size() / capacity()
在模拟实现string类时，string类的成员函数分别为：字符数组指针—_str、当前字符串个数—_size、和字符串容量—_capacity。因此通过capacity()以及size()求字符串个数和字符串容量时，其返回类型为无符号的整型变量(size_t)。返回值为： _size、_capacity。
而在模拟实现vector类时，vector类的成员函数分别为：类似指针的起始数据地址—_start、类似指针的有效数据结束时的地址—_finish、和所开辟的空间最后一个地址—_end_of_storage。
虽然对于vector类中capacity()和size()函数返回类型也为无符号的整型(size_t)，但是不是像string类那样简单的将成员变量的值返回即可，而是通过地址减的方式来实现。代码如下
//size() size_t size() const { return _finish - _start; } //capacity() size_t capacity() const { return _end_of_storage - _start; }注：通过上述需要知道的是：在模拟实现vector的过程中，大多是通过指针减的方式，来确定变量间的关系，最终实现vector类的
2：reserve() / push_back() / insert() / erase()
这四个成员函数本应该都是无返回类型(void)的函数，但是后两个在某些情况下需要改为返回类型为iterator类型
reserve():
void reserve(size_t n);
void reserve(size_t n) { if (n > capacity()) { size_t oldsize = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * oldsize); //delete[] _start; for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + oldsize; _end_of_storage = _start + n; } }在模拟实现reserve()的过程中，存在两个注意点：
1、_finish为nullptr
2、当vector容器中存储的是其他类类型的数据(涉及更加深层次的拷贝时)
注意点1：
前面提到 _finish是vector容器中最后一个数据的地址，那么按理来说，_start+size()即为当前vector容器的最后一个数据的地址，为什么为得到nullptr呢？如下图
再仔细想象size()函数，他的返回值为 _finish-_start，这下就明白为什么_finish会是nullptr了，因为前后两个_start相互抵消了。
为此我们需要记录原来数据的大小并保存到oldsize中，当扩容完时，再通过_start+oldsize确定_finish的大小。如下图
注意点2：
这个有点难以叙述，通过图像来解决，假设现在在vector容器中的数据类型为string即：vector<string> v1；
通过memcpy()，我们确实能够得到一个地址完全不同于 v1 的空间 tmp，并且指向string。
但问题是：不管是v1还是tmp中，各个string中的_str都指向的是同一块空间，因此在调用delete [] _start 时，会对string的内容进行析构，tmp中无法存储有效数据，且最后对_tmp进行析构时，会对同一块空间析构两次，因此会报错。
注：知识点复习：出作用域时，系统会对临时对象和局部对象自动调用析构
因此为了避免这种错误的发生，需要使用以下写法：
for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start;
push_back():
void push_back( const T& x);
void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(_end_of_storage == 0 ? 4 : 2 * (_end_of_storage-_start)); } *_finish = x; _finish++; }这一块没什么可说的，与顺序表实现的思路完全一致
insert():
void/iterator insert(iterator pos, T x);
void insert(iterator pos, T x) { assert(pos >= _start && pos < _finish); if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator i = _finish; while (i > pos) { *i = *(i - 1); i--; } *pos = x; _finish++; }在模拟实现insert()时，同样需要注意两个地方
1、pos失效问题
2、迭代器失效问题
注意点1：
原pos指针是指向空间A的某一位置处，方才通过分析reserve()函数时，可知：我们析构了原来的空间A，转而开辟了一块新的空间B，因此原来指向空间A的指针pos就变成了野指针，我们需要对pos进行更新，记录原来pos指针较_start的相对位置len，在开辟的新的空间B后，_start也得到了更新，将_start+len便可得到新的pos指针。
注意点2：
这个问题是由系统造成的，系统为了解决这个问题，将返回值从 void 转变为 iterator，并且将pos返回，代码如下：
iterator insert(iterator pos, T x) { assert(pos >= _start && pos < _finish); if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator i = _finish; while (i > pos) { *i = *(i - 1); i--; } *pos = x; _finish++; return pos; }并且在测试文件中，通过接收返回值来更新当前指针的一个位置
erase():
iterator erase(iterator pos);
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator i = pos; while (i != _finish) { *i = *(i + 1); ++i; } _finish--; return pos; }erase()同样存在迭代器失效的问题，与insert()函数的解决方式一致
二、vector中其他成员函数的实现
1：现代版本的深拷贝
// v3(v2) vector(const vector<T>& v) { reserve(v.capacity()); for (auto ch : v) //范围for { push_back(ch); } }不要忘了拷贝构造的写法：类名(const 类型& 变量名)
2：其他拷贝构造
// 类模板的成员函数，也可以是一个函数模板 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<int> v4(10, 1); // 拷贝构造10个1
系统认定模板函数相较于非模板函数更加匹配，系统会调用模板函数，而整型是不能解引用的因此会报错。那么如何解决这个问题呢？
代码如下：
vector(int n, const T& val = T()) { reserve(n); for (int i = 0; i < n; i++) { push_back(val); } }写一个更加匹配的函数，来避免上述问题
注：知识点复习：系统在调用函数时，会有一个最佳匹配的问题，即系统会默认调用更加匹配的函数来运行
3：现代版的运算符重载
void swap(vector<T>& tmp) { std::swap(_start,tmp._start); std::swap(_finish,tmp._finish); std::swap(_end_of_storage, tmp._end_of_storage); } //现代版的运算符重载 v3 = v1 vector<T>& operator=(vector<T>& v) { swap(v); return *this; }交换后v1中的数据全部丢失
4：operator[]实现
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}