👉前言👈
我们接下来要模拟实现的 vector，主要参照源码来写。但也不是完全照抄源码，主要是实现 vector 核心的函数接口，知道 vector 的底层实现逻辑。
👉如何看源码👈
源码并不是每一行都要看懂，而是抓住源码的核心。那对于一个类，我们需要关注的是这个类的成员变量和核心的成员函数。而 vector 的成员函数我们不用太关心，因为 STL 要实现哪些函数接口是有规定的。
以下为 vector 源码的成员变量。
注：源码中的 vector 的成员变量都是迭代器，而 vector 的迭代器是指针。而我们之前写的 string 和顺序表都是T* a; size_t _size; size_t _capacity，那为什么源码要这么定义成员变量呢？见下图：
其实这两种定义成员变量的方式本质上是一致的，只是换了种玩法而已。
👉vector 的模拟实现👈
vector 的主要框架
namespace Joy { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; iterator _finish; iterator _endofstorage; }; }
为了避免跟库里的 vector 冲突了，我们用命名空间将我们自己实现的 vector 封装起来。
无参的拷贝构造
vector() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {}
注：_start 指向第一个位置，_finish 指向最后一个元素的下一个位置，_endofstorage 指向最大容量的下一个位置。
正向迭代器
iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
size 和 capacity
bool empty() const { return _start == _finish; } size_t size() const { return _finish - _start; } size_t capacity() const { return _endofstorage - _start; }
指针相减为两个指针之间的元素个数，所以_finish - _start为 size，_endofstorage - _start为 capacity。当_start == _finish时，size 为0。
reserve 和 resize
void reserve(size_t n) { if (n > capacity()) { size_t oldSize = size(); T* tmp = new T[n]; // _start为nullptr时，不需要拷贝数据 if (_start) { memcpy(tmp, _start, sizeof(T) * oldSize); delete[] _start; } _start = tmp; _finish = tmp + oldSize; _endofstorage = tmp + n; } } void resize(size_t n, T x = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish < _start + n) { *_finish = x; ++_finish; } } else { _finish = _start + n; } }
reserve 函数接口说明
注：使用 memcpy 函数来拷贝数据会带来一些问题，我们在后面的内容会讲解。
如果没有oldSize来记录原来 size 的大小，就需要考虑成员变量的更新顺序了。见下方代码：
// 错误的更新方式:先更新_start _start = tmp; _finish = tmp + size(); _endofstorage = tmp + n; // 正确的更新方式:先更新_finish _finish = tmp + size(); _start = tmp; _endofstorage = tmp + n;
如果先更新_start的话，那么就无法通过size()来得到原来的size了，从而出现 BUG。所以我们可以用oldSize来记录size的大小，那么这样就没有更新成员变量的先后顺序问题了。当_start为nullstr时，，说明 vector 对象中没有数据，不需要拷贝数据；反之则通过 memcpy 函数来拷贝数据。最后更新相关成员变量的大小。
resize 函数接口说明
只有当n > capacity()时，才会去调整capacity的大小（采取不缩容的原则）。如果n > size()的话，就利用 while 循环插入x，这个过程_finish也刚好更新了。如果n <= size()的话，就只需要修改_finish为_start + n。
push_back 和 pop_back
void push_back(const T& x) { if (_finish == _endofstorage) { int newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); } *_finish = x; ++_finish; } void pop_back() { assert(!empty()); --_finish; }
push_back 函数接口说明
首先需要判断是否需要扩容，当_finish == _endofstorage时，容量已满，需要扩容。扩容之后，就插入数据，更新_finish。
pop_back 函数接口说明
先断言 vector 类对象是否为空，如果为空，就直接报错；如果不为空，就删除数据。
[ ] 运算符重载
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 vectorTest1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (size_t i = 0; i < v.size(); ++i) { cout << v[i] << " "; } cout << endl; vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : v) { cout << e << " "; } cout << endl; v.pop_back(); v.pop_back(); v.pop_back(); for (auto e : v) { cout << e << " "; } cout << endl; } void vectorTest2() { vector<int> v; v.resize(10, -1); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(5); for (auto e : v) { cout << e << " "; } cout << endl; }
insert 和 erase
// 迭代器失效：野指针问题 iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos < _finish); if (_finish == _endofstorage) { // 保存pos和_start的相对位置，避免迭代器失效问题 size_t len = pos - _start; size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); // 扩容会导致pos迭代器失效，需要更新处理一下 pos = _start + len; } // 挪动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } // STL规定erase返回删除位置下一个位置迭代器 iterator erase(iterator pos) { assert(!empty()); assert(pos >= _start); assert(pos < _finish); iterator begin = pos + 1; while (begin < _finish) { *(begin - 1) = *begin; ++begin; } --_finish; return pos; }
insert 函数接口说明
注：insert 的返回值为新插入元素的位置。
首先要判断pos位置是否合法，然后插入数据。插入数据时，需要判断容量是否已满，是否需要扩容。如果需要扩容的话，则需要将pos和_start的相对距离保存为len。如果保存它们的相对距离的话，扩容将会造成迭代器失效，从而导致野指针问题。那为什么扩容就会带来迭代器失效的问题呢？因为扩容有可能是异地扩容的，异地扩容的话，那么pos就不会在_start和_finish之间。
所以，保存了pos和_start的相对距离，就可以在扩容后更新pos的值了，从而避免迭代器失效造成野指针问题。解决这个问题后，就移动数据，插入数据，更新_finish就行了。
现在，我们就写好了 insert 函数接口。那我想问大家一个问题，在我们插入数组后，find 函数返回的迭代器是否还可以再用，也就是说是否还可以对 it 进行读写操作。不能，因为也有可能带来野指针问题。那为什么会这样呢？因为插入数据时会发生异地扩容，然后迭代器 it 就会失效。有小伙伴就会说了，我们刚才不是已经解决了这个问题了吗。其实，我们只是解决了 insert 函数内部的迭代器失效问题，并未解决外部的迭代器失效问题，也就是说 it 不在_start和_finish之间了。
通过上图就可以清楚地看到，it 已经不在_start和_finish之间。这时候，对 it 进行读写操作就是纯纯的野指针问题。
erase 函数接口说明
进行相关的断言，挪动数据，更新_finish。
那我再想问大家一个问题，这里的迭代器 it 会不会失效呢？我们先来看一下 VS 对这一问题的判定。
可以看到，程序没有报错直接就崩掉了。所以 VS 认为这样是不行的。那么我们再去 Linux 下跑一下这段代码。
可以发现，这段代码是可以在 Linux 下跑过的。那我们再来试一下写能不能跑过。可以发现，写也没什么问题。
注：不同的编译器跑的结果一般不一样。
那迭代器 it 究竟是失效还是不生效呢？其实，我个人认为是失效的。
如果删除最后一个位置的元素，那么 it 就是v.end()。其实如果我们将要删除的元素改成5,后，代码在 Linux 下也能跑过。为什么呢？因为我们现在模拟实现的 vector 就是 Linux 下的 vector 源码。删除数据就只是指针减减一下，而 it 此时指向的位置不再是有效数据的位置，但是操作系统无法做到对每个位置的越界访问都进行检查，所以上面的代码可以跑过。
那我们再来验证一下，我们自己实现的 vector 是不是也可以在 VS 下跑过。
是不是可以跑过啊！！！那为什么用 VS 下的 vector 就不能跑过呢？原因就是 VS 的 vector 原码的迭代器并不是原生指针，而是函数调用（以后会讲解）。所以，我们应该认为 it 会失效，不要对其进行读写操作。
