一、vector 的介绍
- vector 是表示可变大小数组的序列容器。
- 就像数组一样，vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自
动处理。 - 本质讲，vector 使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小。为了增加存储空间，其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
- vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。
- 因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
二、vector 的模拟实现
vector 学习时一定要学会查看文档：vector文档介绍，vector 在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面我们直接开始模拟实现，在模拟实现中我们实现的是常见的接口，并且会在实现中讲解它们的使用以及注意事项。
首先我们将 vector 放到我们自己的命名空间 namespace Young 中；其次我们需要知道，在 vs2019 中，vector 的实现是用三个迭代器实现的，这三个迭代器分别指向的是：数据块的开始、有效数据的尾、存储容量的尾，它跟 string 的实现方式差不多，就是换了一种表达形式，本质上还是一样的，声明如下：
namespace Young { // 使用模板，泛型编程 template <class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: // 给缺省值 iterator _start = nullptr; // 指向数据块的开始 iterator _finish = nullptr; // 指向有效数据的尾 iterator _endofstorage = nullptr; // 指向存储容量的尾 }; }
1. 容量相关的接口
（1）size
我们要获取到有效数据的长度，只需要用两个迭代器相减，用指向有效数据尾部的减去指向数据块开头的即可，实现如下：
// 获取有效数据长度 size_t size() const { return _finish - _start; }
（2）capacity
获取容量的接口与上面的相似，如下：
// 获取容量 size_t capacity() const { return _endofstorage - _start; }
（3）reserve
reserve 我们在 string 中也实现过，vector 的 reserve 与 string 的相似，当 n（需要调整的空间大小） 大于 capacity() 才进行扩容，否则不会缩容；并且它只改变 capacity 不改变 size；其实现如下：
// 申请空间 void reserve(size_t n) { if (n > capacity()) { T* tmp = new T[n]; size_t sz = size(); if (_start) { // 不能使用 memcpy 拷贝数据 --- 浅拷贝问题 // memcpy(tmp, _start, sizeof(T) * sz); for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n; } }
注意，我们在进行拷贝数据的时候，不能使用 memcpy 进行拷贝，因为这会导致深层度的浅拷贝问题，例如实例化以下的对象：
我们在进行尾插的时候，由于 v 对象没有空间，所以需要开空间，我们默认是开4个空间，当我们需要插入第5个数据的时候，需要再次扩容，此时问题就体现出来了，如下图：
因为 _start 维护的数据块中，里面是 string 自定义类型，所以它里面的 _str 指针应该指向一段字符串，在我们需要扩容的时候，memcpy 会按照逐字节的方式进行拷贝，拷贝到 _tmp 中，其中 _tmp 中的 string 的 _str 也是指向原来的空间中，当我们 delete[] _start; 的时候，_start 的空间被释放掉了，而 _tmp 中还有指针指向那段被释放的空间，所以这是造成了野指针问题，所以不能用 memcpy 进行拷贝数据。
所以我们应该采用赋值的方式进行拷贝，如下，如果是像上面的自定义类型 string，它会调用它自己的赋值重载，是深拷贝，所以不会造成上面的问题；
for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; }
还需要注意的是，我们在拷贝数据前，需要记录原来的长度，在拷贝完数据后，将 _tmp 重新赋给 _start 后，需要更新 _finish 和 _endofstorage，就需要用到原来的长度和容量相加了。
（4）resize
// 调整空间为 n，并初始化空间 void resize(size_t n,const T& value = T()) { // 如果 n 小于原来的长度，调整 _finish 的位置 if (n <= size()) { _finish = _start + n; } // 否则，重新开空间，并在数据的尾部插入需要初始化的值 else { reserve(n); while (_finish < _start + n) { *_finish = value; _finish++; } } }
（5）empty
// 判断是否空 bool empty() { return _start == _finish; }
2. [] 重载
在 vector 中我们也可以实现下标的随机访问，所以我们可以重载 [] ，支持随机访问，实现如下：
非 const 对象：
// [] 重载 T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; }
const 对象：
const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; }
3. 迭代器
非 const 对象：
// 迭代器 iterator begin() { return _start; } iterator end() { return _finish; }
const 对象：
const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
4. 修改数据相关的接口
（1）push_back
尾插需要注意先要判断空间是否满了，满了就要扩容，如果一开始为空，我们默认开 4 个空间，实现如下：
// 尾插 void push_back(const T& x) { if (size() == capacity()) //if (_finish == _endofstorage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; _finish++; }
（2）pop_back
尾删只需要将 _finish 减减即可；实现如下：
// 尾删 void pop_back() { assert(size() > 0); _finish--; }
（3）insert
在 pos 位置插入数据，实现如下：
// 在 pos 位置插入数据 void insert(iterator pos, const T& value) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _endofstorage) { // 记录 pos 的长度，防止开空间后迭代器失效 size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); // 开好空间后 _start 重新加上 len ，使 pos 回到原来相对 _start 的位置 pos = _start + len; } // 挪动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } // 插入数据 *pos = value; _finish++; }
在实现 insert 的时候需要注意迭代器失效的问题，在上面实现的代码中，如果不记录 pos 的长度，然后空间不够需要扩容的时候， pos 还留在原来的空间中，而原来的空间已经被释放了，所以会导致野指针问题；所以我们为了避免这种问题，在扩容之前需要记录 pos 的长度，开好空间后更新 pos 的位置，让它回到新的空间相对原来空间的位置中。这是第一种迭代器失效的问题。
insert 的使用如下图：
（4）erase
删除在 pos 位置的数据，实现如下：
// 删除 pos 位置的数据 iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); // 挪动数据 iterator end = pos + 1; while (end < _finish) { *(end - 1) = *end; end++; } // 有效数据减一 _finish--; return pos; }
erase 的使用和实现会面临迭代器失效的第二种情况，例如我们就以以上的数据为例，假设我们需要删除数据中的偶数，例如下图：
结果没有把偶数完全删除，这是为什么呢？这是因为删除了第一个 2 后，it 指向原来的第二个 2，再 ++ 后，就错过了第二个 2；后面的 6 也同理，例如下图：
找到偶数：
删除第一个 2 后：
it ++ 后：
这种迭代器失效的情况还可能面临程序崩溃的问题，如果上面的数据中最后只有一个 6 ，it 就会因为与 v1.end() 错过一个位置导致程序崩溃，例如下图：
找到 6 后：
删除后：
it ++ 后：
如上图，这种情况 it 永远都不会等于 v1.end() 所以程序会死循环。
解决方案是什么呢？解决方案就是我们在实现 erase 的时候，需要返回被删除后当前 pos 的位置，例如上面的实现中；而在使用的时候，我们在 erase 之后用 it 接收这个位置，并且不再访问这个位置，例如下图：
这段代码中，我们 erase 后，没有访问当前位置，而是在没有 erase 的时候去访问 it；
if (*it % 2 == 0) { it = v1.erase(it); } else { it++; }
结论：insert 和 erase 以后迭代器都失效了，不能再访问。
（5）swap
我们利用标准库的 swap 函数实现我们 vector 中的 swap 函数，实现如下：
// 交换 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }
（6）clear
清空数据，只需要将 _finish 变成 _start 即可，实现如下：
// 清空数据 void clear() { _finish = _start; }
5. 构造函数
因为我们在声明处给了缺省值，所以无参的构造函数写成以下形式即可，因为缺省值最终也会走初始化列表：
// 构造函数 vector() {}
我们再重载其它形式的构造函数，例如 vector<int> v(10,0) ，开 10 个空间并将它们初始化为 0，实现如下：
// vector<int> v(10,0); vector(int n, const T& value = T()) { reserve(n); for (int i = 0; i < n; i++) { push_back(value); } }
我们在缺省值中给了一个匿名对象，因为我们不知道 T 的类型是什么，所以我们在缺省值中需要给一个匿名对象；如果是内置类型，它会初始化为 nullptr 或 0，我们以前了解到的是编译器不会对内置类型进行处理，但是匿名对象会对它进行处理；注意在类型前要加 const 因为匿名对象具有常性。如果是自定义类型，它会去调自己的构造函数给缺省值。
使用如下图：
我们还需要重载一个构造的形式，用迭代器区间进行构造，实现如下：
// vector<string> v(str.begin(),str.end()); template <class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); first++; } }
我们在类模板内再使用了函数模板，这个函数模板的生命周期只在这个构造函数内；使用如下：
6. 拷贝构造函数
拷贝构造函数只需要申请和形参对象一样大的空间，然后插入数据即可，实现如下：
// 拷贝构造函数 -- v2(v1); vector(const vector<T>& v) { reserve(v.capacity()); for (auto& e : v) { push_back(e); } }
7. 赋值运算符重载
赋值运算符重载我们利用传参拷贝 tmp，然后将 *this 的数据和 tmp 进行交换即可，最后返回 *this，tmp 出了作用域会自动调用析构函数；实现如下：
// 赋值运算符重载 -- v2 = v1; vector<T>& operator=(vector<T> tmp) { swap(tmp); return *this; }
8. 析构函数
析构函数只需要释放 _start 的空间即可，因为 _start, _finish, _endofstorage 实际上都是同一块空间，只是它们所在的位置不一样，实现如下：
// 析构函数 ~vector() { delete[] _start; _start = _finish = _endofstorage = nullptr; }
