前言
vector容器
vector是可以动态变化大小的数组容器。所以它的很多操做和数组类似，虽然如此，但它毕竟也是一个类，所以在是线上与数组还是有不小的区别。
本文章主要从底层去模拟实现vector的常见接口的实现，vector有多个接口，每个接口的功能都对应着不同的效果，常见功能有增删改查和扩容等。
vector的优点
vector可以动态去管理数据，它的本质上就是一个动态数组。
vector既然是一个数组他就能随机访问，支持排序。
访问数据元素比较高效。
vector缺点
vector在中间插入和删除已经头部插入的时候效率极低，这就需要后续用到的list填补这一缺点。
vector的定义
vector定义变量格式：vector<类型> 变量名。
比如：vector<int> v1,vector<char> v2,vector<string> v3,vector<float> v4等等。
由以上特性，所以我们底层模拟实现vector的时候就需要用模板的思想去实现。
由于vector支持迭代器的操作方法，所以我们需要把成员变量都设为迭代器类型。
vector类定义
template<typename T>
class vector
{
public:
typedef T* iterator; //T*
private:
iterator _start;首个元素位置
iterator _finish;//末尾元素的下一个位置
iterator _endofstorage;//容量大小的下一个位置
};vector构造函数
主要目的是给vector进行初始化。
vector()
:_start(nullptr), //初始化列表
_finish(nullptr),
_endofstorage(nullptr)
{
}vector拷贝构造
vector(const vector<T>& v)
{
_start = new T[capacity()];
_finish = _start;
_endofstorage = _start + v.capacity();
for (size_t i = 0; i < v.size(); i++)
{
*_finish = v[i];
_finish++;
}
}简便拷贝构造写法
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr) //初始化
{
reserve(v.capacity());//开辟空间
for (const auto& e : v)
{
push_back(e);//尾插
}
}swap重载函数
目的是实现三个变量的交换实现深拷贝
void swap(vector<T> & v)
{
::swap(_start, v._start); //::解决函数同名，调用的是全局的swap而非此处的swap
::swap(_finish, v._finish);
::swap(_endofstorage, v._endofstorage);
}vector的获取长度和容量的函数
size()以及capacity()
由于vector定义的成员变量都为iterator类型，所以我们需要通过他们的差值获取size和capacity。
size()
int size()const //加const是因为便于const定义的vector对象调用这个函数
{
return _finish - _start;
}capacity()
int capacity()const
{
return _endofstorage - _start;
}迭代器
迭代器由普通迭代器，常量迭代器，和反向迭代器（未实现）
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
iterator begin() const //常量迭代器
{
return _start;
}
iterator end() const
{
return _finish;
}operator[]的实现
T& operator[](size_t i)//可写
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const //只能读且const定义的变量调用
{
assert(i < size());
return _start[i];
}operator=的实现
vector<int>& operator=(vector<T>& v) //传参数应用，避免再次拷贝构造，返回应用是因为避免返回时候
{ //临时拷贝一个变量，设置返回值是因为要支持连等。
swap(v); //直接交换三个变量地址
return *this;
}reserve()
reserve是实现扩容，但不会初始化。
void reserve(size_t ca)
{
if (ca > capacity())
{
int sz = size();
iterator temp = new T[ca];
memcpy(temp, _start, sizeof(T) * sz);
delete[] _start;
_start = temp;
_finish = temp + sz;
_endofstorage = temp+ca;
}
}reserve的实现要注意：
在vector<>在内置类型下用memcpy没有问题，但如果在自定义类型下将会有重大隐患，比如我们定义一个vector<string>的时候。
比如上面这段代码的时候运行结果就会出现乱码
他就会出现代码，当我们继续push_back的时候程序就会直接挂掉。
这是什么原因呢，这就有关于memcpy的浅拷贝有关了，由于string的拷贝必须用深拷贝进行，否则就会导致新开辟string的对象指针的地址指向的与需要拷贝的源指针所指向的地址相同，然后将源地址delete之和，最后程序结束又会去调用新开辟string对象的析构函数，导致了一块地址被析构了两次，就导致程序崩溃。
所以，由于定义的是vector<string>的自定义类型，所以它也会存在深浅拷贝的问题，memcpy本质上就是浅拷贝，所以我们在这里的代码就需要修改为深拷贝。
void reserve(size_t ca)
{
if (ca > capacity())
{
int sz = size();
iterator temp = new T[ca];
/*memcpy(temp, _start, sizeof(T) * sz);*/
for (int i = 0; i < sz; i++) //赋值
{
temp[i] = _start[i];
}
delete[] _start;
_start = temp;
_finish = temp + sz;
_endofstorage = temp+ca;
}
}resize()
调整空间大小，可用于开辟空间，开辟之后自动初始化。
void resize(size_t n, const T& val= T()) //T（）表示缺省值类似于int（）
{
if (n >= capacity())
{
if(n>capacity()) reserve(n);
for (_finish; _finish < _endofstorage; _finish++)
{
*_finish = val;
}
}
else if (n < capacity())
{
_finish = _start + n;
}
}push_back()
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = (capacity() == 0 ? 2 : capacity() * 2);
reserve(newcapacity);
}
*_finish = x;
_finish++;
}pop_back()
尾删，只需要长度减少就行。
void pop_back()
{
assert(_finish > _start);
--_finish;
}insert()
中间插入，支持尾插，头插。
void insert(iterator pos, const T& value)
{
assert(pos <= _finish);
size_t n = pos - _start;
if (_finish == _endofstorage)
{
size_t newcapacity = (capacity() == 0 ? 2 : 2 * capacity());
reserve(newcapacity);
pos = n + _start; //坑，存在pos失效，由于扩容原因
}
iterator it = end();
while (it >= pos)
{
*it = *(it - 1);
it--;
}
*pos = value;
_finish++;
}insert需要注意的点就是pos失效，在进行扩容之后，pos 是指向之前的数组的中间位置，而新开辟的空间不存在pos这时候就会导致pos失效，这时我们需要重新调整pos的位置。
erase()
iterator& erase(iterator pos)
{
assert(pos >= _start);
iterator it = pos;
while (it < _finish)
{
*it = *(it + 1);
it++;
}
_finish--;
return pos;
}迭代器失效
- 迭代器失效指的是迭代器失去了原本的作用，或者在某条需要使用迭代器的代码中迭代器出现了混乱情况，这些情况统称为迭代器失效。
- 在vector的内部最容易出现迭代器失效的地方分别是 insert 和 erase
情景一：insert扩容插入时
这就是由于扩容后，it还记录着原来位置的空间的位置，而扩容之后插入位置的地址变了，所以导致无法插入数据，迭代器失效。
情景二：erase删除的时候。
比如删除数组中的偶数
因为erase删除是覆盖原来，所以当偶数连续出现就会出现删不干净的情况。
所以准确代码应该修改为
析构函数
~vector()
{
delete[]_start;
_start = _finish = _endofstorage = nullptr;
}