藍 爆笑教程 《C++要笑着学》 火速订阅
写在前面
STL 的源代码整体考虑的东西比较多，还要考虑和其他地方的结合，因此整体的设计是比较复杂的。基于这一系列原因，我们会以简单的形式去实现其核心框架接口，方便去学习 vector。
还是那句话，我们去模拟实现它们，不是为了造更好的轮子，而是为了去学习它，理解它的本质！自己造一次，心里会更清楚，更利于加深对它们的理解。
Ⅰ. 实现基本框架
0x00 结构的定义
我们参考《STL源码剖析》，用 STL3.0 版本去实现一个阉割版的 vector。
成员变量的定义：
#include#include using namespace std; namespace chaos { template class vector { 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：插入数据
检查增容和增容都已经分析完了，最后就只剩一个插入了，插入是最简单的：
分析结束，开始写代码：
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 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 的迭代器是一个原生指针：
templateclass 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 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::iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
it++;
}
cout << endl;
}
运行结果如下：
我们知道，老老实实地实现迭代器，范围for也就能用了，我们来试试：
void test_vector1() {
vector 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::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 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::iterator it = v.begin();
while (it != v.end()) {
*it *= 2;
it++;
}
for (auto e : v) cout << e << " ";
}
运行结果如下：
测试一下 const 迭代器：
void test_vector3() {
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
// const 迭代器
vector::const_iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
it++;
}
cout << endl;
}
运行结果如下：
❌ 如果对 const 迭代器进行 "写" 操作：
error C3892: “it”: 不能给常量赋值
…… 测试成功，果然不行，不行就对了。
0x03 实现迭代器区间
我们在构造时需要注意，使用迭代器区间必须是左闭右开 —— .
（一个类模板的成员函数，又可以是一个函数模板）
迭代器区间：
template// 类模板的成员函数又可以是一个函数模板 vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _eos(nullptr) { while (first != last) { // 遵循左闭右开 // 逐个插入 push_back(*first); first++; } }
现在我们就可以用迭代器区间去初始化 vector 了。
❓ 为什么这里要叫 InputIterator？不用它行不行？
想要知道这个问题，我们先讲解一下迭代器的分类。
0x04 浅谈迭代器的分类
就功能上来说：C>B>A" src="https://latex.codecogs.com/gif.latex?D%3EC%3EB%3EA" /> （一代更比一代强）
它们本质上是一个继承关系：下面是子类，上面是父类。
子类都是一个父类，因为它满足父类的所有特征。
也就是说，虽然在语法上它是个模板，允许你传任意类型的迭代器，
但是在更深层次上存在着更进一步的限制 ——
① 它要求你传随机迭代器，你就不能用双向迭代器。因为只有随机迭代器才能满足随机迭代器的所有操作。换言之，你不能用功能比它指定的迭代器少的迭代器。（可以理解为权限的放大）
② 它要求你用双向迭代器，你就不能用单向迭代器，因为单项迭代器不能满足所有双向迭代器的操作。但是你可以用比它功能多的迭代器，比如随机迭代器，因为随机迭代器也能满足双向迭代器的操作。因为随机迭代器是双向迭代器的子类，它满足父类（双向迭代器）的所有功能。（可以理解为权限的缩小）
限制你用 "儿子" ，你就不能用 "爸爸"
但是，限制你用 "爸爸"，你可以用 "儿子"
我们弄明白了这些，我们再回到刚才提的问题 ——
❓ 为什么这里要叫 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
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：
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 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：
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：
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
void pop_back() {
assert(_finish > _start);
_finish--;
}
测试一下：
void test_vector6() {
vector 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 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;
}
运行结果如下：
Ⅳ. 浅谈迭代器失效问题
0x00 引入：通过 insert / erase 了解迭代器失效问题
我们通过实现 vector 的 insert 和 erase，去顺带讲解迭代器失效的问题。
❓ 什么是迭代器失效？
" 迭代器失效是一种现象，由特定操作引发，这些特定操作对容器进行操作，使得迭代器不指向容器内的任何元素，或者使得迭代器指向的容器元素发生了改变。"
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，
或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T* 。
因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，
而使用一块已经被释放的空间，造成的后果是程序崩溃，
即，如果继续使用已经失效的迭代器，程序可能会出现崩溃。
0x01 实现 insert
插入可分为四个步骤：① 检查 pos 是否越界 ② 检查是否需要扩容 ③ 移动数据 ④ 插入数据
insert
void insert(iterator pos, const T& x) {
assert(pos >= _start);
assert(pos <= _finish);
// 检查是否需要增容
if (_finish == _eos) {
// 扩容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
// 移动数据
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
end--;
}
// 插入数据
*pos = x;
_finish++;
}
测试：在2的位置前插入一个20
void test_vector7() {
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
vector::iterator pos = find(v1.begin(), v1.end(), 2);
if (pos != v1.end()) {
v1.insert(pos, 20);
}
for (auto e : v1) cout << e << " "; cout << endl;
}
运行结果如下：
我们的 insert 似乎没什么问题？我们再 push_back 一个数据看看，让它出现扩容的情况：
void test_vector7() {
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector::iterator pos = find(v1.begin(), v1.end(), 2);
if (pos != v1.end()) {
v1.insert(pos, 20);
}
for (auto e : v1) cout << e << " "; cout << endl;
}
运行结果如下：
迭代器失效问题。扩容导致的 pos 失效，我们的 insert 没有去处理这个问题。
如果发生扩容，我们的 pos 是不是应该去更新一下？
insert：
void insert(iterator pos, const T& x) {
assert(pos >= _start);
assert(pos <= _finish);
// 检查是否需要增容
if (_finish == _eos) {
// 扩容会导致迭代器失效，扩容需要更新一下 pos
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
// 移动数据
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
end--;
}
// 插入数据
*pos = x;
_finish++;
}
运行结果如下：
但是外面的 pos（实参） 还是失效的，这里是传值，pos（形参） 是 pos（实参） 的临时拷贝。
如果 insert 中发生了扩容，那么会导致 pos（实参）指向空间被释放。
pos（实参） 本身就是一个野指针，这种问题我们称之为 —— 迭代器失效
❓ 如何解决这里的迭代器失效问题？传引用？
传引用当然时不好的，有的 vector 还会缩容呢，传引用不能彻底解决所有问题。
我们来看看大佬是如何解决这一问题的：
然而它们是通过返回值去拿的，返回新插入的迭代器。
如果迭代器失效了，你想拿另一个迭代器去代替，就可以通过返回值去拿一下。
⚡ insert：
iterator insert(iterator pos, const T& x) {
assert(pos >= _start);
assert(pos <= _finish);
// 检查是否需要增容
if (_finish == _eos) {
// 扩容会导致迭代器失效，扩容需要更新一下 pos
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
// 移动数据
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
end--;
}
// 插入数据
*pos = x;
_finish++;
return pos;
}
0x02 实现 erase
erase
void erase(iterator pos) {
assert(pos >= _start);
assert(pos <= _finish);
iterator begin = pos + 1;
while (begin < _finish) {
*(begin - 1)* begin;
begin++;
}
_finish--;
}
测试：删除2
void test_vector8() {
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector::iterator pos = find(v1.begin(), v1.end(), 2);
if (pos != v1.end()) {
v1.erase(pos);
}
for (auto e : v1) cout << e << " "; cout << endl;
}
运行结果如下：
思考：erase 有没有迭代器失效的问题？
当然了，erase 也会有失效的情况！
比如我们要求删除 v1 所有的偶数：
void test_vector8() {
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
// 要求删除v1所有的偶数
vector::iterator pos = find(v1.begin(), v1.end(), 2);
while (pos != v1.end()) {
if (*pos % 2 == 0) {
v1.erase(pos);
}
pos++;
}
for (auto e : v1) cout << e << " "; cout << endl;
}
❓ 删除会导致 pos 失效吗？
我们用三种场景去测试：
1 2 3 4 5 1 2 4 5 1 2 3 4
测试结果如下，如果数据是：
① 1 2 3 4 5 正常（其实是个巧合）
② 1 2 3 4 崩溃
③ 1 2 4 5 结果不对（没删除完）
erase(pos) 以后，pos 指向的意义已经变了，直接 pos++ 可能会导致一些意料之外的结果。
对于情况 ③：比如连续的偶数，导致后一个偶数没有判断，导致没有删掉。
再其次，erase 的删除有些 vector 版本的实现，不排除它会缩容。
如果是这样，erase(pos) 以后，pos 也可能会是野指针，跟 insert 类似。
（SGI 和 PJ 版本 vector 都不会缩容）
对于情况 ②：如果最后一个数据是偶数，会导致 erase 以后，pos 意义变了。
再 ++ 一下，导致 pos 和 end 错过结束判断，出现越界问题。
而情况 ①： 之所以没有翻车，是因为被删除的偶数后面恰巧跟的是奇数，运气好逃过了一劫。
导致上述三种问题的本质：erase(pos) 以后，pos 的意义变了，再去 pos++ 是不对的。
为了解决这个问题，erase 是这么说明的：
最近 erase 的元素的后方位置。
⚡ 改进 erase：
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos <= _finish);
iterator begin = pos + 1;
while (begin < _finish) {
*(begin - 1) = *begin;
begin++;
}
_finish--;
return pos;
}
void test_vector9() {
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
// 要求删除v1所有的偶数
vector::iterator pos = find(v1.begin(), v1.end(), 2);
while (pos != v1.end()) {
if (*pos % 2 == 0) {
pos = v1.erase(pos); // erase以后pos失效，会返回下一个位置的迭代器
}
else {
pos++;
}
}
for (auto e : v1) cout << e << " "; cout << endl;
}
运行结果如下：
0x03 可能导致迭代器失效的操作
对于 vector 可能会导致其迭代器失效的操作有：
① 会引起其底层空间改变的操作，都有可能存在迭代器失效。
比如：resize、reverse、insert、assign、push_back 等。
② 指定位置元素的删除操作：erase
#includeusing namespace std; #include int main() { int a[] = { 1, 2, 3, 4 }; vector v(a, a + sizeof(a) / sizeof(int)); // 使用find查找3所在位置的iterator vector ::iterator pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据，导致pos迭代器失效。 v.erase(pos); cout << *pos << endl; // 此处会导致非法访问 return 0; }
erase 删除 pos 位置元素后，pos 位置之后的元素就会往前搬移，
没有导致底层空间的改变，理论上讲迭代器不应该会失效。
但是 pos 刚好是最后一个元素，删完之后 pos 刚好在 end 的位置，
而 end 位置是没有元素的，那么 pos 就失效了。
因此删除 vector 中任意位置元素时，VS 就认为该位置迭代器失效了。
还有就是我们刚才讲解的奇偶数，删除 pos 位置的数据，导致 pos 迭代器失效。
当然，vector 迭代器的失效主要发生在 insert 和 erase。vector 的其他接口基本不碰迭代器，自然也就不涉及这些问题。
迭代器失效解决方法：在使用前，对迭代器重新赋值即可。
❓ string 的 insert 和 erase 迭代器是否会失效？string 有没有迭代器失效？
当然会，只要使用迭代器的容器，都可能会涉及迭代器失效。
只是 string 一般很少涉及迭代器失效，因为它 insert 和 erase 时主要用下标。
Ⅴ. vector 深拷贝
0x00 拷贝构造
可以使用传统写法，也可以使用现代写法。
传统写法：全都自己干，
vector(const vector& v) { //_start = new T[v.capacity()]; //_finish = _start + v.size(); //_eos = _start + v.capacity(); reserve(v.capacity()); // 我们可以直接调用写好的reserve去开空间 // memcpy(_start, v._start, v.size() * sizeof(T)); // 会翻车 for (const auto& e : v) { push_back(e); } }
老老实实开空间，老老实实拷数据。
因为我们已经实现好了 reserve，所以我们这里可以直接调用 reserve 去开空间。
注意这里不能使用 memcpy，这个我们前面已经强调过了。
现代写法：找工具人帮忙干活：
刚来，谁是工具人？ —— 让迭代器区间当工具人：
vector(const vector& v) : _start(nullptr) , _finish(nullptr) , _eos(nullptr) { vector tmp(v.begin(), v.end()); swap(_start, tmp._start); swap(_finish, tmp._finish); swap(_eos, tmp._eos); }
测试一下：
void test_vector4() {
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector v2(v1);
for (auto e : v2) cout << e << " "; cout << endl;
}
运行结果如下：
tmp 完成交换工作后，出了作用域要调用析构函数，
如果我们不对 _start、_finish 和 _eos 进行初始化，那么 tmp 将会是随机值。
所以我们用初始化列表给它们先初始化成 nullptr，这样交换后 tmp 就都是 nullptr 了。
根据经验，我们下面肯定还会用到 swap 的，我们不如把它封装成一个 Swap 函数。
Swap：
void Swap(vector& tmp) { swap(_start, tmp._start); swap(_finish, tmp._finish); swap(_eos, tmp._eos); }
⚡ 更新拷贝构造：
vector(const vector& v) : _start(nullptr) , _finish(nullptr) , _eos(nullptr) { vector tmp(v.begin(), v.end()); Swap(tmp); }
当然，不加模板参数的写法也是可以的：
vector(const vector& v)
: _start(nullptr)
, _finish(nullptr)
, _eos(nullptr)
{
vector tmp(v.begin(), v.end());
Swap(tmp);
}
（这样语法上是支持的，但是还是推荐用加模板参数的写法，因为写类型会比较清楚）
0x01 赋值构造 operator=
传统写法就是把 v2 赋值给 v1，自己把 v1 释放了，再去深拷贝出 v2 一样大的空间……
太麻烦了，直接用现代写法，只要有了拷贝构造，赋值都可以用现代写法。
并且，这里还可以利用 "传参调用拷贝构造" 这一特性，做到真正的 "压榨" 工具人。
所以我们去掉 const 和引用传参，为的是让形参去充当临时变量 tmp ——
现代写法：v1 = v3
vector& operator=(vector v) { Swap(v); // 让形参v充当tmp工具人 return *this; }
这里也一样，不写模板参数也是可以的：
vector& operator=(vector v) {
Swap(v); // 让形参v充当tmp工具人
return *this;
}
想要 v1 跟 v3 有一样大的空间一样大的值，我们让传参的时候就顺便把这件事给办了。
现在 v 手上就有 v3 了，然后再用 Swap 函数夺取 v 的劳动成果，最后返回 *this 就大功告成了。
这里 v1 不仅把 v 从 v3 得到的东西，还让 v 帮忙把垃圾丢了（释放空间） ——
（画技烂轻喷）
"传参调用拷贝构造" 压榨工具人的方式，是我们第二次讲了。
第一次是在 string 模拟实现的时候讲的，当时我们称之为 —— 更简洁的写法：
正所谓一回生二回熟，相信到这里你应该理解，我们为什么可以这么做了。
❓ 现在请思考：既然有这种好事，为什么不在拷贝构造的时候用？
如果你答错了，建议复习一下：
【C++要笑着学】类的默认成员函数详解 | 构造函数 | 析构函数 | 构造拷贝函数
测试一下：
void test_vector5() {
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
cout << "赋值前：";
for (auto e : v1) cout << e << " "; cout << endl;
vector v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
cout << "赋值后：";
v1 = v3;
for (auto e : v1) cout << e << " "; cout << endl;
}
运行结果如下：
（不崩溃了）
参考资料
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
. C++reference[EB/OL]. []. http://www.cplusplus.com/reference/.
百度百科[EB/OL]. []. https://baike.baidu.com/.
比特科技. C++[EB/OL]. 2021[2021.8.31]. .
[ 笔者 ] 王亦优
[ 更新 ] 2022.5.11
❌ [ 勘误 ]
[ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
本人也很想知道这些错误，恳望读者批评指正！
