💭 写在前面
STL 的源代码整体考虑的东西比较多，还要考虑和其他地方的结合，因此整体的设计是比较复杂的。基于这一系列原因，我们会以简单的形式去实现其核心框架接口，方便去学习 vector。
还是那句话，我们去模拟实现它们，不是为了造更好的轮子，而是为了去学习它，理解它的本质！自己造一次，心里会更清楚，更利于加深对它们的理解。
Ⅰ. 实现基本框架
0x00 结构的定义
我们参考《STL源码剖析》，用 STL3.0 版本去实现一个阉割版的 vector。
💬 成员变量的定义：
#include <iostream> #include <assert.h> using namespace std; namespace chaos { template<class T> class vector { public: typedef T* iterator; private: iterator _start; // 开始位置 iterator _finish; // 结束位置 iterator _eos; // end of storage }; }
❓ 我们发现 —— 怎么成员函数和我们之前模拟实现 string 的写法不一样了？
不要慌，我们参考的是 STL3.0 的写法，它给的就是 start 、finish 和 end_of_storage。
（这里我们把 end_of_storge 简写成 eos ）
虽然表面上看起来不一样，但是实际上表达的效果是大同小异的，看图：
我们用指针记录 _start 、_finish 和 _eos 的位置，只需要 "指针减指针" 就可以得到大小或容量。
这非常的自由！我们想求 size，只需要 _finish - _start 即可，
同样的，求 capacity 我们可以 _eos - _start 。甚至可以求可用空间，_eos - _finish 就行。
真的是太自由了！我们之前实现 string 时记录 _capacity 和 _size 的形式，是不是瞬间不香了？
这种写法真的是非常的高雅，没错就是这么的🐂🍺！
再说回代码的实现，为了和库中的 vector 进行区分，我们这里依然用命名空间包含起来。
我们这里造一个 vector 的类模板去适应各种类型，我们用 typedef 将 T* 重命名为 iterator。
0x01 构造函数的实现
这里要完成的是初始化工作，我们利用初始化列表将它们值成空指针即可。
💬 vector：
vector() : _start(nullptr) , _finish(nullptr) , _eos(nullptr) {}
0x02 析构函数的实现
析构函数也没什么说的，要做的就是释放空间，并将定义的指针置空。
💬 ~vector：
/* 析构函数 */ ~vector() { if (_start) { delete[] _start; _start = _finish = _eos = nullptr; } }
0x03 实现 size() 和 capacity()
通过刚才的讲解，我们已经知道 _start 、_finish 与 _eos 的用法了，
通过指针减指针，我们就可以轻松实现 size() 和 capacity() 了，实现方式如下：
💬 size：
size_t size() const { return _finish - _start; // 返回数据个数 }
💬 capacity：
size_t capacity() const { return _eos - _start; // 返回容量 }
0x04 实现 push_back 尾插
我们这里先实现一个简单的 push_back，以便于我们能先把 vector 跑起来。
因为是阉割版，我们的 push_back 也自然没有空间配置器，我们就用 new 去替代它。
首先思考，尾插需要做哪些事？
Step1：检查是否需要增容
需要增容，就先增容后再插入数据；不需要增容，就直接插入数据。
我们先去思考，如何判断是否需要增容 ——
我们之前的判断方式是 size == capacity 的时候需要增容（数据结构专栏、string 的模拟实现）
问题是，这次我们没有定义 _size 和 _capacity，取而代之的是 _start 、 _finish 和 _eos 的形式。
当 _finish 触及到 _eos （end of storage） 时，不就说明容量不够了吗？如下所示：
Step2：如果需要增容
我们再来思考一下增容部分的实现，我们在 vector 常用接口介绍章节里说过：
" vector 使用动态分配数组来存储它的元素。当新元素插入时，为了增加存储空间，这个数组就需要被重新分配大小。具体做法是分配一个新的数组，然后将全部元素转移到这个新的数组。"
因此，我们的增容操作可以大致可分为4个步骤：
① 开一块带有新容量的空间存到 tmp 中。
② 再把原空间的数据拷贝到新空间。
③ 并释放原有的旧空间（我们先 "故意" 使用 memset，至于 memset 的问题我们最后探讨）
④ 最后将 _start、_finish 和 _eos 指向新的空间。
📌 注意事项：
值得注意的是，最后一步如果先将 _start 指向 tmp 后，再计算 _finish 时，
此时不能现场算 size() ，现场算会出问题，因为 _start 已经被更新成 tmp 了，
如果不想改变顺序，还是想按 _start、_finish 和 _eos 的顺序赋值，
我们可以提前把 size() 算好，存到一个变量中。
此外，真 vector 这里扩容是要调空间配置器的，开空间和初始化是分开的。
我们这里的实现也没有空间配置器，所以这里就直接一把梭了。
对于空间配置器的知识我们放到后面再说，我们目前的重点不是空间配置器，重点是 vector。
至于新容量给多少，我们还是按照自己的习惯，首次给4默认扩2倍的方式去增容。
Step3：插入数据
检查增容和增容都已经分析完了，最后就只剩一个插入了，插入是最简单的：
💬 分析结束，开始写代码：
/* 尾插：push_back */ void push_back(const T& x) { // 检查是否需要增容 if (_finish == _eos) { size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2; size_t sz = size(); // 提前把size算好 T* tmp = new T[new_capacity]; // 开一块带有新容量new_capacity的空间存到tmp中 if (_start) { memcpy(tmp, _start, sizeof(T) * size()); // 再把原空间的数据拷贝到新空间，并释放原有的旧空间。 delete[] _start; // 并释放原有的旧空间 } _start = tmp; // 指向新空间 _finish = tmp + sz; // 现场算size() 会有问题，因为start已经被更新成tmp了 _eos = _start + new_capacity; } // 插入数据 *_finish = x; _finish++; }
为了方便测试尾插的效果，我们先来实现一下 operator[] ，利用 "下标+方括号" 的方式遍历。
0x05 实现 operator[]
T：由于我们不知道返回值类型，所以给 T。
T&：引用返回减少拷贝。
const：这里 cosnt 修饰 T 和 this，是为了限制写。
const T& operator[](size_t idx) const { assert(idx < size()); return _start[idx]; }
接收下标，断言判断一下下标是否合法，合直接返回。
💬 测试 push_back：
void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; }
🚩 运行结果如下：
Ⅱ. 迭代器的实现
0x00 实现迭代器的 begin 和 end
vector 的迭代器是一个原生指针：
template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator;
我先实现一下 begin() 和 end() ，直接分别返回 _start 和 _finish 即可：
💬 begin
iterator begin() { return _start; }
💬 end
iterator end() { return _finish; }
0x01 实现 const 迭代器的 begin 和 end
const 类型的迭代器，即可读不可写。在实现的时候用 const 修饰即可：
💬 begin
const_iterator begin() const { return _start; }
💬 end
const_iterator end() const { return _finish; }
0x02 测试实现效果
💬 测试迭代器的效果：
void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); 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也就能用了，我们来试试：
void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); // 下标 + [] 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 for (auto e : v) { cout << e << " "; } cout << endl; }
🚩 运行结果如下：
至此，我们已经还原好了上一章介绍的 vector 的三种遍历方式。
💬 测试迭代器的 "写" ：
void test_vector2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) cout << e << " "; cout << endl; // 迭代器 vector<int>::iterator it = v.begin(); while (it != v.end()) { *it *= 2; it++; } for (auto e : v) cout << e << " "; }
🚩 运行结果如下：
💬 测试一下 const 迭代器：
void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // const 迭代器 vector<int>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; }
🚩 运行结果如下：
❌ 如果对 const 迭代器进行 "写" 操作：
error C3892: “it”: 不能给常量赋值
…… 测试成功，果然不行，不行就对了。
0x03 实现迭代器区间
我们在构造时需要注意，使用迭代器区间必须是左闭右开 ——
（一个类模板的成员函数，又可以是一个函数模板）
💬 迭代器区间：
/* 迭代器区间 */ template <class InputIterator> // 类模板的成员函数又可以是一个函数模板 vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _eos(nullptr) { while (first != last) { // 遵循左闭右开 // 逐个插入 push_back(*first); first++; } }
现在我们就可以用迭代器区间去初始化 vector 了。
❓ 为什么这里要叫 InputIterator？不用它行不行？
想要知道这个问题，我们先讲解一下迭代器的分类。
0x04 浅谈迭代器的分类
| 迭代器 | 对应类型 |
A 👴 输入 / 输出迭代器：input_iterator / output_iterator * 特点：单步向前迭代，不可写 / 单步向前迭代，可写 |
无对应类型 |
B 🧓 单向迭代器：forward_iterator * 特点：满足以上所有功能，并且能 ++ （不能 - -没有 rbegin / rend） |
<forward_list> （C++11） <unordered_map> （C++11） <unordered_set> （C++11） |
就功能上来说： （一代更比一代强）
它们本质上是一个继承关系：下面是子类，上面是父类。
子类都是一个父类，因为它满足父类的所有特征。
也就是说，虽然在语法上它是个模板，允许你传任意类型的迭代器，
但是在更深层次上存在着更进一步的限制 ——
① 它要求你传随机迭代器，你就不能用双向迭代器。因为只有随机迭代器才能满足随机迭代器的所有操作。换言之，你不能用功能比它指定的迭代器少的迭代器。（可以理解为权限的放大）
② 它要求你用双向迭代器，你就不能用单向迭代器，因为单项迭代器不能满足所有双向迭代器的操作。但是你可以用比它功能多的迭代器，比如随机迭代器，因为随机迭代器也能满足双向迭代器的操作。因为随机迭代器是双向迭代器的子类，它满足父类（双向迭代器）的所有功能。（可以理解为权限的缩小）
限制你用 "儿子" ，你就不能用 "爸爸"
但是，限制你用 "爸爸"，你可以用 "儿子"
我们弄明白了这些，我们再回到刚才提的问题 ——
❓ 为什么这里要叫 InputIterator？不用它行不行？
首先，InputIterator 是输入迭代器，这么写是为了满足命名规范。
可以不用，我们可以传单向迭代器、双向迭代器，也可以传随机迭代器。
因为这些迭代器都满足输入迭代器的所有功能。
Ⅲ. vector 的扩容
0x00 引入：先把 reserve 写咯
我们要实现 vector 的 insert，肯定需要用到增容，我们这里当然不会傻傻地重写一遍。
我们可以把刚才写 push_back 实现的增容部分拎出来，实现一个 CheckCapacity 函数。
但是我们这里可以直接实现出 reserve，到时候实现 resize 也可以复用得上，岂不美哉？
所以，我们先实现 reserve，顺便把 resize 再实现一下，再去实现 insert 。
0x01 实现 reserve
直接复制粘贴刚才实现的 push_back 中 "检查否需要增容" 的部分，然后稍作修改即可。
首先还是检查是否真的需要扩容，如果传入的 new_capacity 确实比现有 capacity 要大，
并且 _finish == _eos 时，我们就进行扩容，这相当于是一个检测，
防止根本就不需要扩容，还给它扩容的情况。还是分为四个步骤：
① 开新空间：new 空间的地方，我们直接给上传入的 new_capacity 即可，要求开多少就开多少。
② 拷贝数据：暂时先用 memset（如果你知道 memcpy 的问题，先别急，我们最后再专门探讨）
③ 释放旧空间：释放 _start，new[] 对应 delete[] 去释放。
④ 指向新空间：把 size() 提前算好，然后让 _start、_finish 和 _eos 指向新空间。
💬 reserve
/* reserve */ void reserve(size_t new_capacity) { if (new_capacity > capacity()) { // 检查是否真的需要扩容 if (_finish == _eos) { size_t sz = size(); // 提前把size算好 T* tmp = new T[new_capacity]; if (_start) { memcpy(tmp, _start, sizeof(T) * size()); // 再把原空间的数据拷贝到新空间，并释放原有的旧空间。 delete[] _start; // 并释放原有的旧空间 } _start = tmp; // 指向新空间 _finish = tmp + sz; // 现场算size() 会有问题，因为start已经被更新成tmp了 _eos = _start + new_capacity; } } }
0x02 让 push_back 复用 reserve
实现完 reserve 之后，我们可以把刚才的 push_back 简化一下：
有了 reserve，我们的 push_back 直接去调它就可以了，还是按首次给4，默认扩2倍的形式走。
三目运算符得到的结果传入 reserve，结果变成 reserve 中的 new_capacity 参数，
然后 reserve 执行 new 的时候，会按照传入的 new_capactiy 的大小去开空间。
最后再插入数据即可。所以，本质上其实是一样的。
⚡ push_back：
/* 尾插：push_back */ void push_back(const T& x) { // 检查是否需要增容 if (_finish == _eos) { // 扩容 reserve(capacity() == 0 ? 4 : capacity() * 2); } // 插入数据 *_finish = x; _finish++; }
0x03 使用 memcpy 拷贝问题
我们一开始实现的 push_back 就用了 memcpy 进行拷贝的，
然后我们刚才实现了 reserve，因而又让 push_back 复用了 reserve，
reserve 搬元素的时候也是 memcpy 去进行拷贝的，其实这里存在一个非常严重的问题！
💬 我们现在给出一个测试用例：
void test_vector10() { vector<string> v; // 在vector里放string v.push_back("233333333333333333"); v.push_back("233333333333333333"); v.push_back("233333333333333333"); v.push_back("233333333333333333"); v.push_back("233333333333333333"); v.push_back("233333333333333333"); v.push_back("233333333333333333"); for (auto& e : v) { cout << e << " "; } cout << endl; }
🚩 运行结果如下：
为什么会这样？原因在于我们在扩容和深拷贝时，用了一个 memcpy！
push_back 调用 reserve 扩容时就会出问题，根本原因是 memcpy 是浅拷贝。
问题分析：
memcpy 是内存的二进制格式拷贝，
将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
如果拷贝的是自定义类型的元素，memcpy 既高效又不会出错，
但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，
就会出错，因为memcpy的拷贝实际是浅拷贝。
结论：
如果对象中涉及到资源管理时，千万不能使用 memcpy 进行对象之间的拷贝，
因为 memcpy 是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃！
解决方案：
不要使用 memcpy，我们手动去拷！
⚡ 我们修改一下 reserve：
/* reserve */ void reserve(size_t new_capacity) { if (new_capacity > capacity()) { // 检查是否真的需要扩容 if (_finish == _eos) { size_t sz = size(); // 提前把size算好 T* tmp = new T[new_capacity]; if (_start) { // memcpy(tmp, _start, sizeof(T) * size()); 有问题！ //自己把原空间的数据拷贝到新空间 for (size_t i = 0; i < sz; i++) { // 如果T是int，一个一个拷贝没问题 // 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。 tmp[i] = _start[i]; } delete[] _start; // 并释放原有的旧空间 } _start = tmp; // 指向新空间 _finish = tmp + sz; // 现场算size() 会有问题，因为start已经被更新成tmp了 _eos = _start + new_capacity; } } }
如果 T 是 int，一个一个拷贝没问题，
如果 T 是 string 等自定义问题，一个一个拷贝调用的是 T 的深拷贝，也不会出问题。
我们拿刚才的测试用例测试一下，看看效果如何：
0x03 实现 resize
💬 resize：
/* resize */ void resize(size_t new_capacity, const T& val = T()) { // 如果容量足够 if (new_capacity < size()) { _finish = _start + new_capacity; // 直接修改 _finish } else { // 容量不够 if (new_capacity > capacity()) { // 检查是否需要扩容 reserve(new_capacity); } while (_finish != _start + new_capacity) { // 初始化 *_finish = val; // 按val初始化，默认缺省为 T() _finish++; } } }
vector 的 resize 如果不给第二个参数，默认给的是其对应类型的缺省值作为 "填充值"。
由于这里我们不知道具体类型是什么，这里缺省值我们使用匿名对象 T() ，
此外因为匿名对象的生命周期仅在当前一行，这里必须要用 const 引用匿名对象，
可以理解为延长其生命周期。
0x04 实现 pop_back
pop_back 很简单，只需要 _finish-- 就可以了。
但是需要考虑删完的情况，我们这里采用暴力的处理方式 —— 断言。
💬 push_back
/* 尾删：pop_back */ void pop_back() { assert(_finish > _start); _finish--; }
测试一下：
void test_vector6() { vector<int> v1; v1.push_back(1); v1.push_back(2); for (auto e : v1) cout << e << " "; cout << endl; v1.pop_back(); for (auto e : v1) cout << e << " "; cout << endl; }
🚩 运行结果如下：
测试一下断言效果：
void test_vector6() { vector<int> v1; v1.push_back(1); v1.push_back(2); for (auto e : v1) cout << e << " "; cout << endl; v1.pop_back(); v1.pop_back(); v1.pop_back(); for (auto e : v1) cout << e << " "; cout << endl; }
🚩 运行结果如下：
