目录前言一、vector 的成员变量1.1 vector 是什么1.2 _start、_finish、_endofstorage 三个指针成员1.3 与 string 的成员设计对比二、vector 的默认成员函数2.1 默认构造函数2.2 迭代器区间构造2.3 构造函数重载n 个 val2.3.1 vector v(10, 1) 的重载陷阱2.4 拷贝构造函数2.5 析构函数三、赋值运算符重载四、容量与元素访问4.1 size、capacity 和 operator[]4.2 reserve 和 resize4.2.1 reserve 更新 _finish 的坑4.2.2 迭代器失效 —— 扩容引发的野指针4.3 迭代器 begin/end五、深浅拷贝问题5.1 vector 的崩溃分析5.2 正确做法赋值重载逐个拷贝5.3 动态二维数组 vector六、修改操作6.1 push_back 和 pop_back6.2 insert6.2.1 迭代器失效—— insert 偏向野指针6.3 erase6.3.1 迭代器失效—— erase 偏向意义改变6.3.2 vs 与 g 的检测差异结语前言上一篇博客【C编程】STL容器一--- string简单模拟实现常用接口实现 | 深浅拷贝讲解-CSDN博客上一篇我们完成了 string 类的模拟实现从三个成员变量出发把构造、深浅拷贝、赋值、容量管理、增删查改这一整套核心接口都自己动手撸了一遍。那今天这篇文章我们就正式进入 STL 的重头戏——vector 的模拟实现。vector 可以说是我们平时写 C 用得最多、也最能代表 STL 设计思想的一个容器。我们常说学习 STL 有三个境界——能用、明理、能扩展。上一篇讲 string 接口用法的时候我们其实一直停留在“能用”和“明理”之间而到了模拟实现这一步就是实打实地往“明理”和“能扩展”去迈进。vector 的学习我们同样按照这个思路来先搞清楚它是什么再把它的底层掰开揉碎讲明白。不过要提前给大家打个预防针这一篇会比上一篇 string 难上不少难度主要来自三个地方——第一vector 是一个模板类它要适配任意类型 T而不像 string 只管 char很多问题会因为“T 到底是什么类型”而变得复杂第二vector 有一个新手很头疼的问题——迭代器失效我们会讲到具体接口时结合场景展开第三vector 的扩容拷贝里藏着一个 memcpy 的经典深坑我们专开了一节来讲。至于那些和 string 基本一样的部分比如命名空间隔离、赋值运算符的现代写法、operator[] 的越界检查我们就简单带过把火力集中在真正有差别的地方。同样地为了不和标准库的 vector 冲突我们依然把自己造的 vector 放进 Marks 命名空间里。一、vector 的成员变量1.1 vector 是什么在动手写代码之前我们先要搞清楚一个问题vector 到底是什么东西说白了它就是一个可变大小的数组。我们把它拆开来看就是三层意思它底层是一块连续的存储空间所以可以像数组一样用下标 v[i] 随机访问访问效率和数组一样高它的大小是动态可变的而且这个“变大”不需要我们操心容器会自动处理代价是当空间不够装新元素时vector 要经历“重新配置一块更大的空间 - 把旧元素全部搬过去 - 释放原来的空间”这一整套流程这是一个相对昂贵的操作。也正因为扩容昂贵vector 不会每插入一个元素就扩一次容而是“提前多备一些”每次都分配一些额外的空间以适应可能的增长并且这个增长是按倍数进行的。这样把扩容的代价平摊下来就能保证末尾插入元素接近常数时间的体验。我们用一句话总结vector 就是一个会自动扩容的数组。随机访问快、尾插快但扩容那一瞬间是“搬家”级别的开销——记住这个特点它决定了后面所有的实现细节。1.2 _start、_finish、_endofstorage 三个指针成员既然 vector 底层是一块连续的动态数组那我们要管理这块数组本质上就是要回答三个问题数据从哪开始有效数据到哪结束整个空间到哪为止对应地vector 用三个指针来回答这三个问题namespace Marks { templateclass T class vector { public: // vector 的迭代器就是原生指针 typedef T* iterator; typedef const T* const_iterator; private: iterator _start nullptr; // 指向数组的起始位置 iterator _finish nullptr; // 指向最后一个有效元素的下一个位置 iterator _endofstorage nullptr; // 指向整个已分配空间的末尾 }; }根据上面的这张图三个指针的分工就一目了然了_start指向这块连续内存的首地址所有数据都从这里开始放_finish指向最后一个有效元素的下一个位置_start 到 _finish之间就是“真正存了数据”的区域_endofstorage指向整个已分配空间的末尾_finish 到 _endofstorage之间是“已经开好但还没有用上”的备用空间。它们之间天然满足_start _finish _endofstorage的关系。有了这个关系两个最常用的接口就变得极其简单size_t size() const { return _finish - _start; } // 有效元素个数 size_t capacity() const { return _endofstorage - _start; } // 已分配的容量看到没size 和 capacity 这两个天天用的接口底层就是两个指针相减。这也是 vector 的精妙之处——它把“有效数据长度”和“总容量”都藏在了指针的差值里不需要再单独维护两个整数变量。1.3 与 string 的成员设计对比成员变量有了那我们现在再思考一个问题上一篇 string 我们用的是 _str、_size、_capacity——“一个指针 两个整数”的结构为什么 vector 不照着抄反而要搞出三个指针呢这里就是我们这篇要讲的第一个关键差别点了。我们把两者的成员摆在一起看// string一个指针 两个整数 char* _str; // 数据载体 size_t _size; // 有效字符个数 size_t _capacity; // 总容量 // vector三个指针 T* _start; // 数据起始 T* _finish; // 有效数据末尾 T* _endofstorage; // 空间末尾两者在功能上其实是等价的都能回答“数据在哪、有效数据多长、总空间多大”这三个问题。那 vector 为什么要选择三指针原因有两点第一vector 的迭代器就是原生指针。上一篇我们说过 string 的迭代器本质也是 char* 但到了 vector 这里这个特性被发挥了极致——begin() 直接返回 _startend() 直接返回 _finish一行代码都不用多写iterator begin() { return _start; } // 第一个元素的地址 iterator end() { return _finish; } // 最后一个元素的下一个地址如果沿用 string 那套 _str _size 的设计end() 就得写成 return _str _size虽然也能跑但不如直接维护一个 _finish 指针来得直观。第二指针相减天然就是“元素个数”。在C里两个同类型指针相减得到的是它们之间相隔的元素个数而不是字节数。所以 _finish - _start 直接就是 size()连 sizeof(T) 都不用除代码会非常清爽。1小结一下vector 和 string 都是在管“堆上的动态数组”思想一脉相承但 vector 因为是模板类、迭代器又是原生指针所以改用“三指针”来记账——这是它和 string 的第一个关键差别。记住 _start / _finish / _endofstorage 这套结构后面讲扩容、迭代器失效全都围绕它展开。二、vector 的默认成员函数在上一篇 string 里我们详细聊过“6个默认成员函数”这回事——构造、析构、拷贝构造、赋值重载、取地址重载、const 取地址重载。到了 vector 这里我们重点处理其中和资源管理直接相关的几个构造函数含各种重载、拷贝构造函数、析构函数赋值运算符重载因为有个“偷梁换柱”的写法值得单独讲我们放到下一节至于取地址重载和 const 取地址重载编译器默认生成的那份已经够用了这里直接略过不提。2.1 默认构造函数成员变量有了第一个问题就是一个 vector 对象刚创建出来的时候它的三个指针应该是什么状态答案很简单——都指向空。我们在声明成员的时候就直接用默认成员初始化器给它们赋上 nullptrprivate: iterator _start nullptr; // 声明时就初始化为空 iterator _finish nullptr; iterator _endofstorage nullptr;这样一来默认构造函数体里其实什么都不用写vector() {}这里大家不妨回想一下上一篇 string 的默认构造——string 那边我们可是要 new char[1] 专门开一个放 \0 的空间的。为什么 vector 就不用呢因为 string 要兼容 C 风格的字符串必须保证任何时候 _str 都指向一个合法的、以 \0 结尾的空间而 vector 是个纯数组空就是空三个指针都是 nullptr 就是最合理、最安全的“空”状态不需要也不应该去额外 new 一块空内存。这个“空指针”的初始化还有一层意义后面析构函数里我们判断 if(_start) 才去 delete[]就是建立在这个“要么是合法空间、要么说 nullptr”的约定之上的。所以成员初始化成 nullptr 这件事一定要做。2.2 迭代器区间构造光会造一个空的 vector 还不够。实际开发里最常见的需求其实是——从一段已有的数据初始化出一个 vector。比如我手里有一个数组或者有另一个容器的某一段区间我想把它直接变成一个新的 vector。这个时候就要用到 vector 的迭代器区间构造了// [first, last) 左闭右开区间 templateclass InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); // push_back 尾插 first; } }它的作用就是给我一个 [first, last) 的区间我逐个把区间里的元素拷进来。注意这里的 InputIterator 是一个模板参数而不是写死的某种具体类型。为什么要用模板因为“迭代器”的身份五花八门它可能是另一个 vector 的迭代器可能是 string 的迭代器甚至可能就是一个原生指针数组名。这些类型各不相同我们没法用一个固定类型写死所以干脆用模板泛化让编译器根据实参自动推导。我们看几个实际的用法就明白了。假设已经有了一个 vectorint v1 和一个 string str 那么可以这样vectorint v3(v1.begin(), v1.end()); // 用另一个 vector 的迭代器区间构造 vectorchar v4(str.begin(), str.end()); // 用 string 的迭代器区间构造 int a[] { 16, 2, 77, 29 }; vectorint v5(a, a 4); // 用原生指针数组首尾当迭代器v3 用的是 vector 的迭代器v4 用的是 string 的迭代器 v5 用的干脆就是两个原生指针 a 和 a 4——它们都能被 InputIterator 这个模板参数接住这就是模板的强大之处。顺便和 string 对比一句上一篇模拟 string 的时候我们并没有写这个迭代器区间构造是因为 string 的场景几乎都是直接传 C 字符串用不上这种“从别的容器拷贝区间”的需求。但 vector 作为最通用的容器经常要从数组、list、甚至另一个 vector 里初始化所以这个模板构造就成了标配也是它和 string 的一个重要差别。2.3 构造函数重载n 个 val从区间造会了还有一种更直白的场景我想一口气造出 n 个一模一样的元素比如 10 个 1、或者 10个空字符串。这个构造也很直接根据前面的经验直接复用我们后面讲的 resize 就行了// 构造 n 个 val vector(size_t n, const T val T()) { resize(n, val); }这里有两个点值得留意参数用const T val—— 传引用避免 T 是自定义类型时发生不必要的拷贝。默认参数val T()—— 这里的 T() 是一个匿名对象当 T 是 int 这种内置类型时 int() 就是 0 当 T 是 string 时 string() 就是空串。这个匿名对象的细节我们放到第四节讲 resize 的时候再展开这里先记住“默认参数给一个 T()”就够了。2.3.1 vector v(10, 1) 的重载陷阱上面我们写的是 vectorsize_t n, const T val 这个版本本以为 vectorint v(10, 1)会顺理成章地走进去、造出 10 个 1。但真实情况是——它会直接编译报错vectorint v(10, 1); // 本意10 个 1这是为什么呢关键在于C的重载决议规则。当我们调用 v(10, 1)时编译器手里有两个候选vector(size_t n, const T val); // 候选一需要 int → size_t 的隐式转换 // 候选二2.2 里的模板构造InputIterator 直接推导成 int两个参数都精确匹配候选一虽然名字听着像“构造 n 个val”但它要求第一个参数 size_t无符号整数而我们传的 10 是int有符号要走一步隐式类型转换候选二是函数模板InputIterator 直接被推导成 int 两个参数 10 和 1 都是int精确匹配精确匹配一步转换都不用。那编译器会选谁在重载决议里“精确匹配”永远优先于“需要隐式转换的匹配”。于是 vectorint v(10, 1)就稀里糊涂地被推给了迭代器区间构造——两个 int 被当成了“一对迭代器”进去之后对 *first 解引用也就是对一个 int 解引用直接编译报错。那怎么解决很简单再补一个 int 版本的重载专门“抢回”这种两个 int 的调用// 额外补一个 int 版本专门接住 vectorint v(10, 1) 这种调用 vector(int n, const T val T()) { resize(n, val); }有了这个 int 版本vectorint v(10, 1)就能精确匹配到它两个参数都是 int不会再被模板抢走问题就解决了。这也是为什么你在一些成熟的 vector 实现里会同时看到 size_t 和 int 两个几乎一模一样的构造函数——就是为了堵住这个重载的坑。2.4 拷贝构造函数vector(const vectorT v) { _start new T[v.capacity()]; // 注意这里不能用 memcpy 一把梭拷贝原因留到第五节专门讲 for (size_t i 0; i v.size(); i) { _start[i] v._start[i]; } _finish _start v.size(); _endofstorage _start v.capacity(); }逻辑分三步先在堆上开一块容量和 v 一样大的新空间 - 把 v 里的有效元素逐个拷进来 - 更新三个指针。这里有个非常关键的细节也是 vector 和 string 拷贝最大的不同拷贝元素用的是 for 循环逐个赋值而不是 memcpy。上一篇 string 的拷贝构造我们可是直接用 memcpy 一把唆的——因为 string 的元素是 charmemcpy 按字节原样拷贝完全没问题。但 vector 的元素类型是模板参数 T 它可能是 int也可能是 string 这种自己管理资源的类型memcpy 一梭子下去就变成浅拷贝会直接崩溃。这个问题比较重要我专门用第五节一整节来讲这里先记住即可。不过拷贝构造其实还有第二种写法——先 reserve(v.capacity()) 预留好空间再push_back 逐个插进去。两种写法效果一样一个先开空间再直接赋值一个边扩容边插看个人习惯。这里我们用第一种先开空间的思路跟后面 reserve 的逻辑也更统一。2.5 析构函数就是负责把堆上的空间还回去~vector() { if (_start) { delete[] _start; _start _finish _endofstorage nullptr; } }这里和 string 的析构基本一个套路就两点需要留意用 delete[] 要对应前面的 new[]。删之前先 if(_start) 判断一下——因为默认构造出来的空 vector它的 _start 是 nullptr养成“先判空再删”的习惯总没坏处而且删完把三个指针统一置空也能防止后续误用。到这里vector 就能安全地创建、拷贝、销毁了。但注意我们还没写赋值运算符——没有它 v1 v2 这种操作会走编译器默认生成的浅拷贝又会出现当时在模拟 string 时出现的“double free”的问题下一节我们就来解决这个问题。三、赋值运算符重载拷贝构造处理的是“用一个 vector 去初始化另一个 vector”的场景但更常见的其实是这种情况——两个 vector 都已经存在了我要把 把一个赋给另一个vectorint v1(10, 1); vectorint v2(5, 2); v1 v2; // 赋完值v1 应该变成 5 个 2那这个 该谁来干活如果我们的类里不写 operator 编译器会默认生成一个——而默认生成的是浅拷贝直接把 v2 的三个指针值原样拷给 v1。后果会和上一篇 string 一模一样v1 原来指向的那块堆空间没人管了 - 内存泄漏。赋完之后 v1 和 v2 的 _start 指向同一块空间 - 两个对象析构时对同一块内存 delete[] 两次 -程序崩溃。所以我们必须自己写一个 operator 。这里我们直接沿用上一篇 string 里重点讲过的“现代写法”——传值 swap偷梁换柱// 先写一个 swap 成员函数交换两个 vector 的三个指针 void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } // 现代写法按值传参编译器自动调拷贝构造再 swap 偷梁换柱 vectorT operator(vectorT v) { swap(v); // v临时副本拿到旧资源离开作用域时析构自动释放 return *this; }我们再来拆解一下这其中的过程当执行 v1 v2 时第一步按值传参。operator 的参数是 vectorT v按值不是引用所以把 v2 传进去的时候编译器会先调用我们 2.4 写的拷贝构造用 v2 造出一个临时副本 v。这个副本是深拷贝有自己独立的一块空间数据跟 v2 一样。第二步swap。把 v1 的三个指针和副本 v 的三个指针互换。换完之后v1 拿到了副本那块装着正确数据的新空间而副本 v 拿到的是 v1 原来那块旧空间。第三步副本析构。函数返回副本 v 离开作用域自动调用析构函数把它手里那块 v1 的旧空间释放掉。这个写法的好处上一篇已经详细分析过这里简单回顾不用写自赋值判断传值自动生成副本即使 v1 v1 也安全、不用手动 delete旧资源跟着副本走自动析构、异常安全拷贝在传参时完成如果拷贝崩了根本进不到 swap原对象完好无损。到这里默认成员函数这一块就齐了能创建、能拷贝、能赋值、能销毁。但光能“存在”还不够接下来我们要让 vector 能“用”起来——知道它多大、能访问某个元素、能在空间不够时自动扩容。四、容量与元素访问4.1 size、capacity 和 operator[]size 和 capacity 第一节已经见过就是两个指针相减size_t size() const { return _finish - _start; } // 有效元素个数 size_t capacity() const { return _endofstorage - _start; } // 总容量operator[] 按下标访问两个版本可读写 / 只读T operator[](size_t pos) { assert(pos size()); // 标准库为性能不做检查模拟实现加个 assert 方便排错 return _start[pos]; } const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; }返回引用是为了能直接改比如 v[0] 10。跟 string 是一样的。4.2 reserve 和 resize这两个是经常会弄混的。一句话reserve 只改容量resize 改元素个数。先看 reserve它只把底层空间变大不碰元素void reserve(size_t n) { if (n capacity()) { size_t sz size(); // 先把旧元素个数记下来 T* tmp new T[n]; // 开一块更大的新空间 if (_start) { for (size_t i 0; i sz; i) // 逐个搬过去为什么不用 memcpy第五节讲 { tmp[i] _start[i]; } delete[] _start; // 释放旧空间 } _start tmp; _finish _start sz; _endofstorage _start n; } }空间不够才扩开新空间、搬旧数据、放旧空间、更新三个指针就这四步。4.2.1 reserve 更新 _finish 的坑第一行size_t sz size();藏着一个坑。可能有人会想最后不是要_finish _start size()吗直接写不就行了干嘛提前存个 sz因为执行到最后一行时_start 已经改成指向新空间了这时候 size() 算的是 _finish - _start而 _finish 还存在旧空间_start 已经是新空间一减就是乱七八糟的数。拿它去更新 _finishvector 直接废掉。所以必须趁 _start 还没动先把 size() 存进 sz最后用 _start sz 恢复 _finish。4.2.2 迭代器失效 —— 扩容引发的野指针reserve 还有个副作用扩容时旧空间被 delete[] 释放了。谁要是之前拿过迭代器指向旧空间的指针现在就是野指针再访问就是未定义行为。vectorint v; v.push_back(1); auto it v.begin(); // 指向旧空间 v.reserve(100); // 扩容旧空间释放 // *it —— 已失效未定义行为这就是迭代器失效的第一种来源扩容产生野指针。VS 下这种访问直接崩g 检查得松可能还能读到但结果是错的。insert/erase 引发的失效第六节会系统讲这里先记住一句任何可能扩容的操作都可能让之前的迭代器失效。再看 resize它连空间带元素一起管void resize(size_t n, const T val T()) { if (n size()) { _finish _start n; // 缩小砍掉尾巴 } else { reserve(n); // 先保证空间够 while (_finish ! _start n) // 多出来的位置逐个填 val { *_finish val; _finish; } } }n 比当前元素少就把 _finish 缩回去n 比当前元素多先 reserve再把多出来的位置填上 val。这里重点讲解一下默认参数 val T() 。T() 是个匿名对象会调 T 的默认构造T 是 int int() 就是 0T 是 stringstring() 就是空串。内置类型本来没有构造函数但为了让模板能统一写 T()C给内置类型也补上了默认构造int() 合法且值为 0。所以 resize 的默认构造才能直接写成 T()。4.3 迭代器 begin/endvector 的迭代器就是原生指针begin/end 直接返回两个指针四个版本可读写 只读iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }五、深浅拷贝问题前面 2.4 拷贝构造、4.2 reserve 里我们一直留着一句话没说透拷贝元素为什么不用 memcpy非要 for 循环一个个赋值接下来我们就开始讨论这个问题5.1 vector 的崩溃分析先看一段会崩的代码。假设我们偷懒reserve 里用 memcpy 拷贝// 错误示范reserve 里用 memcpy void reserve(size_t n) { if (n capacity()) { size_t sz size(); T* tmp new T[n]; if (_start) { std::memcpy(tmp, _start, sizeof(T) * sz); // 错就错在这一行 delete[] _start; } _start tmp; _finish _start sz; _endofstorage _start n; } }再用 vector 测一下vectorstring v; v.push_back(1111111111111111); v.push_back(2222222222222222); v.push_back(3333333333333333); v.push_back(4444444444444444); v.push_back(5555555555555555); // 第 5 个元素触发扩容memcpy 浅拷贝后崩溃为什么崩问题全出在 memcpy 上。memcpy 是把一段内存按字节原样搬到另一段它才不管里面装的是什么。而 vector 的空间里装的是一个个 string 对象——每个 string对象内部还有自己的 _str 指针指向堆上真正的字符串。所以 memcpy 一搬把 string 对象的 _str 指针值原样复制过去了。搬完之后新空间的 string 对象和旧空间的 string 对象_str 指向同一块字符串内存。这就是浅拷贝。接着 delete[] _start 释放旧空间。delete[] 会依次调用旧空间里每个 string 的析构析构又把自己 _str 指向的字符串释放掉。这一下新空间里那些 string 的 _str 就成了野指针——指向一块已经被释放的内存。再访问一个被释放的内存就会崩溃。一句话总结vector 本身是深拷贝但 memcpy 把元素string 对象给浅拷贝了结果就是野指针 崩溃。5.2 正确做法赋值重载逐个拷贝正确写法就是我们一直在用的 for 循环for (size_t i 0; i sz; i) { tmp[i] _start[i]; }区别在哪tmp[i] _start[i] 这一行调用的是 string 的赋值运算符重载走的是 string 自己的深拷贝每个 string 对象会重新开一块堆空间把字符串内容拷贝过去。所以搬完之后新空间的每个 string 都有独立的一份字符串谁也不影响谁。对比一下就清楚了memcpy按字节硬拷指针值 - 元素浅拷贝 - 两个 string 共享一块字符串 - 释放旧空间后新空间变野指针 - 程序崩溃。循环赋值调元素的 operator - 元素深拷贝 - 每个 string 独立 - 安全。结论元素是自定义类型尤其带资源管理的时拷贝一律用赋值/拷贝构造绝不用memcpy。5.3 动态二维数组 vectorvector最后看一个挺直观的例子能帮我们把“vector 空间里存的是 T 的对象数组”这句话彻底想明白——vector 的元素本身也可以是 vector。比如杨辉三角这种二维结构填充前vectorvectorint vv(n); // 外层 n 行每行是一个 vectorint for (size_t i 0; i n; i) vv[i].resize(i 1, 1); // 每行先 resize 成 i1 个元素都填 1填充后for (size_t i 2; i n; i) // 前两行已经是 1从第 2 行起填中间值 for (size_t j 1; j i; j) // 中间元素 左上方 右上方 vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];vv 是外层 vector它的元素类型 T 是 vectorint。所以外层空间里一个挨一个存的是 n 个 vector 对象每个对象都有自己的一套三指针。刚构造完时vv(n) 调的是 2.2 的 n 个 val 构造这些内层对象的三指针都还是空指针vv[i].resize(i1, 1) 才给每一行各自开数据空间。这个例子反过来也印证了 5.1正因为 vector 空间里存的是“对象”拷贝 vectorvector 时更不能 memcpy——否则内层 vector 的三指针被浅拷贝几个 vector 共享同一段数据又会变成野指针。六、修改操作6.1 push_back 和 pop_back逻辑很简单我们这里直接复用后续要讲解的 insert 和 erasevoid push_back(const T x) { insert(end(), x); // 在末尾插入 } void pop_back() { erase(end() - 1); // 删掉最后一个元素 }push_back 的参数是 const T x用引用是为了避免 T 是 string 这种类型时传参还要多一次拷贝。这俩本质就是“在 end() 处插入”和“删 end() 前一个”。6.2 insertinsert 在任意位置 pos 插入元素是 vector 里最“重”的操作之一iterator insert(iterator pos, const T x) { assert(pos _start pos _finish); if (_finish _endofstorage) // 满了先扩容 { size_t len pos - _start; // 先记下 pos 相对 _start 的偏移 size_t newcapacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapacity); // 扩容会释放旧空间pos 失效 pos _start len; // 用偏移量恢复 pos } iterator end _finish - 1; while (end pos) // 把 pos 及其后的元素整体后移一位 { *(end 1) *end; --end; } *pos x; // 空出来的位置放 x _finish; return pos; }流程分两块先看满没满满了就扩容再把 pos 及其后面的元素整体往后挪一位空出 pos 放 x。挪数据这里和 string 的 insert 有个区别值得说一下。上一篇 string 的 insert 里挪数据要小心 size_t 下溢——pos 是 0 时循环变量减到 -1 会变成无符号最大值死循环。vector 没有这个麻烦因为 pos 是迭代器原生指针end pos 这个条件天然保证不会减到 _start 前面去。这就是“insert 对比 string挪动数据更简单因为 pos 不会小于 0”。6.2.1 迭代器失效—— insert 偏向野指针上面 insert 里有一段挺突兀的代码扩容前先 size_t len pos - _start 记偏移扩容后再 pos _start len 恢复。这是在干嘛呢因为 reserve 扩容会把旧空间 delete[] 释放掉pos 指向的还是旧空间就成了野指针。所以 insert 内部先记下 pos 离 _start 有多远偏移量扩容后用新 _start 加上偏移量把 pos 找回来。但注意insert 只能“救”它自己的 pos 形参。你要是从外面传一个迭代器进来insert 之后还用原来的那个就踩雷了vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 现在 size capacity 4满了 vectorint::iterator p v.begin() 3; // 指向 4 v.insert(p, 300); // 满了插入必扩容p 失效所以结论insert 之后原来拿到的迭代器就当作失效别再用了。insert 返回的那个才是有效的新迭代器。6.3 eraseiterator erase(iterator pos) { assert(pos _start pos _finish); iterator it pos 1; while (it ! _finish) // 把 [pos1, _finish) 整体前移一位 { *(it - 1) *it; it; } --_finish; return pos; }逻辑是把 pos 后面的元素整体往前挪一位把 pos 盖掉然后 _finish 减一。返回 pos也就是删除位置现在的那个元素原来 pos 1 的那个。6.3.1 迭代器失效—— erase 偏向意义改变erase 也涉及迭代器失效但性质和 insert 不一样erase 不扩容、不释放空间所以迭代器不会变野指针。问题在于元素前移之后pos 这个位置”指向的东西“变了。所以 erase 的失效是”这个迭代器的意义变了“不是”变野指针了“。这也是 erase 要返回一个迭代器的原因——用 it erase(it) 接住删除位置的新迭代器继续遍历才不会出错。看个实际场景删除 vector 里所有偶数错误和正确写法对比// 错误erase 后 it 已失效it 是未定义行为 auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) v.erase(it); it; } // 正确用 erase 的返回值接住新迭代器 auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) it v.erase(it); // 删完it 指向下一个有效元素 else it; }6.3.2 vs 与 g 的检测差异最后说一下同样是访问失效的迭代器不同编译器反应不一样。VS 的 STL 检查很严格失效迭代器一访问直接断言崩溃。Linux 下的 g 检查得松很多失效的迭代器照样能读能写但读出来的是垃圾、写进去是往野内存里写反而更危险——程序不崩结果悄悄错了这种 bug 最难查。所以别指望编译器帮你兜底规矩就一条insert、erase以及一切可能扩容的操作之后之前拿到的迭代器一律当作失效别再用。需要继续用就用接口返回的那个新的。顺带说一句 list它和 vector 不一样list 的迭代器不是原生指针是包了一层的自定义类型所以它的 insert/erase 不会让迭代器失效。这个等后面讲到 list 再展开。到这里vector 的核心接口就全部实现了。结语至此一个相对完整的 vector 模拟实现就完成了。我们从三个指针成员出发一路实现了构造函数含各种重载和迭代器区间构造、拷贝构造、赋值、容量管理、增删改以及贯穿始终的两个核心难点——迭代器失效和 memcpy 浅拷贝。当然真实的标准库 vector 远比这复杂比如它用空间配置器allocator来管理内存、扩容策略各平台不同VS 约 1.5 倍、g 2 倍、insert 内部用 uninitialized_copy 处理未构造内存等等。我们这里追求的是把核心思想吃透而不是复刻工程细节剩下的优化留给大家有兴趣再深入。下一篇我们会讲 list。list 和 vector 最大的不同在于它的迭代器不是原生指针而是包了一层的自定义类型——这也正好接上了本篇结尾留下的迭代器失效这个话题因为 list 的 insert/erase 不会让迭代器失效。写文不易希望各位给个三连~言已至此感谢各位读者花费时间阅读本人浅学才疏如有文笔拙劣之处还望见谅~