前段时间在一个项目里排查一处诡异的内存越界翻来覆去定位到最后问题出在对std::vector底层内存布局的错误假设上。当时我就在想如果自己真正动手写过一遍 vector很多坑根本不会踩。后来我花了两天时间从零手写了一个可用的 vector虽然只是一个教学性质的实现但这个过程把之前很多知其然不知其所以然的细节彻底打通了。这篇文章就是那两天的完整复盘。这篇文章适合三类人正在学 C 但总觉得 STL 是黑盒的初学者准备面试被问到底层实现但心里没底的求职者以及用 vector 写过业务但从来没想过它内部怎么工作的老开发。我会从设计思路讲起逐步到内存管理、迭代器、异常安全、性能对比最后给出完整的可运行代码和测试方法。你会发现手写一个 vector 最难的不是实现功能而是把所有边界情况和异常路径都处理对。1. 动手之前先弄清楚 vector 到底在管什么1.1 拆掉黑盒vector 的三个指针和一个分配器先说结论std::vector本质上就是一个动态数组它和普通数组的最大区别是自己管理内存的分配和释放。这个管理动作浓缩下来就是三个指针start指向分配到的内存块起始位置也就是begin()返回的位置。finish指向当前最后一个有效元素的下一个位置size()就是finish - start。end_of_storage指向整个内存块的末尾capacity()就是end_of_storage - start。内存布局用一句话概括就是分配器一次性买下一块地vector 只负责在这块地上盖房子构造元素和拆房子析构元素。房子盖到地皮的边界时就找分配器再买一块更大的地把所有东西搬过去。理解了这三个指针就理解了 vector 的所有核心操作。push_back要看finish有没有碰到end_of_storagepop_back要把finish往回退一步并且析构那个元素reserve要检查new_cap和capacity()的大小关系shrink_to_fit则要把内存缩到和元素数量刚好匹配。所以手写 vector 的第一课就是不要让 vector 自己记住 size 和 capacity而是通过指针运算来算。这不仅省内存更重要的是所有 STL 算法都依赖迭代器相减这类指针运算保持这个语义是一切的根基。1.2 构造和析构为什么要分离普通对象是分配内存 构造对象一步到位的比如new T。但 vector 不一样它必须把这两件事拆开。原因很直接如果 vector 要扩容旧内存里的元素需要搬到新内存如果直接delete[]旧内存再new[]新内存元素会被整体重新构造性能极差。vector 的优化空间恰恰来自先分配裸内存再在裸内存上用 placement new 构造元素。// 分配裸内存 T* raw allocator.allocate(new_cap); // 在裸内存上构造元素 for (size_t i 0; i old_size; i) { new (raw i) T(std::move_if_noexcept(old_start[i])); }释放时的顺序正好相反先逐个手动调用析构函数再把整块裸内存还给分配器。for (size_t i 0; i size; i) { start[i].~T(); } allocator.deallocate(start, capacity());这套先分配、后构造的模型是所有容器实现的基础。理解了这一点你就能解释为什么 vector 对元素类型有要求为什么某些类型放进 vector 会编译失败以及为什么移动构造函数不声明noexcept时 vector 扩容会退化为拷贝——这些我们后面细说。2. 逐行实现从裸指针到完整容器2.1 类骨架模板参数、成员变量和类型别名我实现的时候没有直接裸写T*而是用了std::allocatorT来封装内存分配。这样做好处很多一是符合标准库的结构后面要扩展成自定义分配器很自然二是allocator_traits帮我们处理了很多细节省得自己写destroy和construct的转发。template typename T class MiniVector { public: using value_type T; using size_type size_t; using difference_type ptrdiff_t; using reference T; using const_reference const T; using pointer T*; using const_pointer const T*; private: pointer start_; // 指向内存起始 pointer finish_; // 指向有效元素末尾 pointer end_of_storage_; // 指向容量末尾 std::allocatorT alloc_; // 分配器 // 三个关键计算 size_type size() const { return finish_ - start_; } size_type capacity() const { return end_of_storage_ - start_; } };你可以看到成员变量就这么简单。整个 vector 的全部状态就是三根指针加一个分配器对象。这也暗示了 vector 为什么拷贝、移动都比较直接——它只需要搬运这三根指针而真正内存里的元素才是大头。类型别名这块别看它只是using声明它关系到后面迭代器能不能正常工作。比如iterator直接定义为T*在 C 里这是合法的——原生指针天然满足随机访问迭代器的所有要求。2.2 构造函数从默认到范围构造构造函数的主要工作是确保对象创建后三个指针处于一致状态。默认构造最简单三个指针全空。参数构造需要分配内存并填充元素。范围构造传入一对迭代器稍复杂一点我直接用insert来实现避免重复代码——把end()位置传入insert就能复用后面的插入逻辑。MiniVector() : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) {} explicit MiniVector(size_type n) : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) { resize(n); } template typename InputIt MiniVector(InputIt first, InputIt last) : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) { insert(begin(), first, last); }有个坑必须提醒范围构造的模板参数InputIt要避免和重载的MiniVector(size_type n, const T val)冲突。比如调用MiniVectorint v(5, 10)时编译器可能把这个签名解释成两个迭代器也可能解释成数量初值。标准库的解法是引入enable_if判断InputIt是不是真正的迭代器。我自己的实现里做了一个简化用std::is_integral排除整型参数。template typename InputIt MiniVector(InputIt first, InputIt last, typename std::enable_if!std::is_integralInputIt::value::type* nullptr) { insert(begin(), first, last); }这样MiniVectorint v(5, 10)就会走数量初值的重载MiniVectorint v(v2.begin(), v2.end())走范围构造。2.3 push_back 与扩容动态数组的心脏push_back是 vector 最核心的操作它的行为决定了 vector 的性能特征。极简版本是这样的void push_back(const T value) { if (finish_ end_of_storage_) { reserve(grow_capacity()); } alloc_.construct(finish_, value); finish_; }如果容量够直接在finish_位置构造元素然后指针前移。如果容量不够进行扩容。grow_capacity的策略我后面专门分析这里先给出一个最常见的版本size_type grow_capacity() const { size_type old_cap capacity(); return old_cap 0 ? 1 : old_cap * 2; }这个old_cap 0 ? 1 : old_cap * 2有个边界细节第一次插入时容量是 0如果直接0 * 2就永远是 0所以必须特判成 1。reserve的实现要处理几个边界如果new_cap capacity()直接返回如果new_cap 0则释放所有内存。真正的扩容流程分五步分配新内存、搬运旧元素、析构旧元素、释放旧内存、更新三根指针。void reserve(size_type new_cap) { if (new_cap capacity()) return; if (new_cap 0) { clear(); deallocate(); return; } pointer new_start alloc_.allocate(new_cap); size_type old_size size(); for (size_type i 0; i old_size; i) { new (new_start i) T(std::move_if_noexcept(start_[i])); } for (size_type i 0; i old_size; i) { start_[i].~T(); } if (start_) alloc_.deallocate(start_, capacity()); start_ new_start; finish_ new_start old_size; end_of_storage_ new_start new_cap; }std::move_if_noexcept是这里的关键它的意思是如果元素的移动构造函数不抛异常就移动否则就拷贝。这样能保证扩容时如果元素构造抛出异常旧元素仍然完好无损vector 仍处于有效状态。这就是异常安全里的强保证。2.4 insert、erase 与其他关键操作insert是所有操作里最麻烦的因为要在容器中间插入元素所有后续元素都要后移。我分了三种情况来处理容量够插入位置在末尾附近——先移动元素再插入。容量不够——重新分配整块内存把插入点之前的元素、新元素、插入点之后的元素依次放进去。插入位置是end()——直接转发给push_back。iterator insert(const_iterator pos, const T value) { size_type index pos - begin(); if (finish_ end_of_storage_) { // 扩容路径 size_type new_cap grow_capacity(); pointer new_start alloc_.allocate(new_cap); // 拷贝前半段 for (size_type i 0; i index; i) { new (new_start i) T(start_[i]); } // 构造插入值 new (new_start index) T(value); // 拷贝后半段 for (size_type i index; i size(); i) { new (new_start i 1) T(start_[i]); } // 清理旧内存 for (size_type i 0; i size(); i) { start_[i].~T(); } alloc_.deallocate(start_, capacity()); start_ new_start; finish_ new_start size() 1; end_of_storage_ new_start new_cap; return iterator(start_ index); } // 容量够的路径 // 先把最后一个元素构造到末尾 alloc_.construct(finish_, start_[size() - 1]); finish_; // 从后往前移动元素 for (size_type i size() - 1; i index; --i) { start_[i] std::move(start_[i - 1]); } start_[index] value; // 这里应该是赋值而不是构造 return iterator(start_ index); }注意容量够的路径最后一个元素的处理尤其容易出错因为finish_指向的位置是未构造的裸内存必须先construct再移动而中间区域的元素都已经是构造好的对象用operator赋值即可。两者混着用是我调试时踩得最多的坑。erase相对简单把后面元素往前搬析构最后一个元素iterator erase(const_iterator pos) { size_type index pos - begin(); for (size_type i index; i size() - 1; i) { start_[i] std::move(start_[i 1]); } start_[size() - 1].~T(); --finish_; return iterator(start_ index); }pop_back更简单析构末尾元素然后--finish_。clear则是循环析构所有元素然后把finish_重置为start_但不释放内存。resize要处理三种情况比size()大且容量够直接在末尾构造比size()大且容量不够先reserve再构造比size()小析构多余元素。3. 扩容策略2 倍增长背后的权衡3.1 为什么不是用到多少就扩到多少新手最容易想到的策略是每次push_back只多分配一个元素的内存。这样省空间但代价是灾难级的——每插入一个元素都要把所有旧元素搬一次。插入 n 个元素的总搬移次数是 123...n O(n²)这在数据量大时根本跑不动。vector 的做法是倍增分配每次扩容时容量翻倍或者乘 1.5这样插入 n 个元素的搬移总次数是 1248...n ≈ 2n均摊下来每个元素只搬移 O(1) 次。这就是所谓的均摊常数复杂度。3.2 2 倍还是 1.5 倍这是一个空间与时间的问题到这儿你可能会问既然翻倍这么好能不能翻 10 倍搬移次数更少但内存浪费巨大。实际上不同编译器的选择很有意思某主流编译器的标准库用 1.5 倍而非 2 倍另一个主流编译器用 2 倍。为什么关键在于内存分配器的行为。如果每次扩容翻倍vector 占用的内存不断翻倍分配器可能一直不回收旧内存。而如果按 1.5 倍增长内存块的增长较平缓分配器有机会复用之前释放的内存块内存碎片更少。代价是搬移次数略多一点约 2.5 倍于 1 倍增长。我自己实现时用 2 倍因为代码最简单面试也够用了。但如果你要做一个生产级的容器建议改成类似 1.5 倍的策略size_type grow_capacity() const { size_type old_cap capacity(); if (old_cap 0) return 1; if (old_cap 8) return old_cap * 2; // 小容量快速翻倍 return old_cap old_cap / 2; // 大容量 1.5 倍增长 }小对象快速翻倍可以避免频繁扩容大对象缓和增长可以控制浪费。这也是很多工程实践里的折中方案。3.3 均摊分析的直觉我经常用一个类比来帮助理解均摊复杂度假设你开了一家奶茶店每接待 1 个客人才开始准备下一天的材料。如果材料准备量也是 1 份那每天开业前都要去采购一次。但如果每次准备的量翻倍前期多花的一点精力会摊薄到后面无数次营业里。vector 的扩容就是同样的道理——一次性多分配一倍的空间是为了让后续多次push_back都不再需要扩容。计算一下就知道假设最终有 n 个元素扩容序列是 1、2、4、8、...、2^k总搬移次数约等于 2n。n 次插入中绝大多数都只是 O(1) 的尾后构造只有扩容那几次才做 O(n) 的大搬移。平摊下来每次插入的均摊复杂度确实是 O(1)。4. 迭代器失效规则那些必须遵守的游戏规则4.1 什么是迭代器失效迭代器失效指的是迭代器指向的内存位置已经不属于这个容器了。vector 的迭代器是原生指针所以失效的本质是指针的值没变但它指向的内存已经被释放或者语义已经不再属于这个容器。如果你继续解引用这样的迭代器轻则读到野数据重则直接段错误。引起迭代器失效的操作主要分两类一是导致扩容的操作push_back、insert、resize、reserve扩容后所有迭代器都失效原因是start_换了一块新内存二是不引起扩容但改变了元素位置的操作erase从被擦除位置到end()的迭代器全部失效。4.2 自己实现时最容易踩的失效场景我在实现初期犯过一个经典错误在insert的容量够路径里用了start_[index]来赋值但index是在push_back内部计算出来的。如果此时后面的元素移动操作已经改变了start_指针比如容量不够触发了reserveindex就不再有效。正确做法是在做任何可能改变指针的操作之前先把位置差算好保存下来size_type index pos - begin(); // 此时再执行 reserve/扩容index 依然是正确的还有一个很隐蔽的坑insert返回的迭代器如果在插入后马上调用push_back引发扩容这个返回的迭代器也会失效。很多业务代码里喜欢保存insert的返回值反复使用这在 vector 上是极度危险的。4.3 实践中如何规避失效风险工程上规避迭代器失效最有效的办法是不要保存长期存活的迭代器用下标代替。下标的值在扩容后依然指向相同逻辑位置的元素而迭代器会指向旧内存。比如你要在一个容器里同时保存多个位置用size_t index而不是iterator// 危险扩容后 v.begin()pos 可能失效 auto it v.begin() pos; v.push_back(x); do_something(it); // 未定义行为 // 安全下标天然免疫扩容 size_t idx pos; v.push_back(x); do_something(v[idx]); // 没问题这个习惯在你使用 vector 的所有代码里都适用尤其是那些边遍历边插入的循环。5. 异常安全让容器在任何情况下都不坏掉5.1 三个级别的异常安全异常安全是个绕不开的话题我在自己实现的测试阶段被它狠狠教训过一次。标准里一般分三级基本保证抛出异常后容器处于有效但未指定状态可析构、可继续使用。强保证抛出异常后容器和调用前完全相同。不抛保证函数承诺不抛出异常。vector 的push_back和insert在扩容时如果元素的拷贝/移动构造函数抛异常旧元素必须保持完好。这就是强保证。实现它的关键在于先在新内存里完成所有构造所有构造成功后再一次性销毁旧内存。5.2 我的实现里如何保证强保证看reserve的完整流程先allocate新内存然后逐个在新内存上构造元素。如果第 k 个元素构造失败抛异常新内存里的前 k-1 个元素需要析构新内存要释放但旧内存的元素一个都不能动。pointer new_start alloc_.allocate(new_cap); size_type old_size size(); size_type i 0; try { for (; i old_size; i) { new (new_start i) T(std::move_if_noexcept(start_[i])); } } catch (...) { // 析构已构造的新元素释放新内存然后重新抛出 for (size_type j 0; j i; j) { new_start[j].~T(); } alloc_.deallocate(new_start, new_cap); throw; } // 走到这里说明所有构造都成功了才处理旧内存 for (size_type i 0; i old_size; i) { start_[i].~T(); } alloc_.deallocate(start_, old_capacity()); start_ new_start; finish_ new_start old_size; end_of_storage_ new_start new_cap;注意catch块里不能直接调用alloc_.deallocate就完事必须先析构已经构造好的元素。否则就是内存泄漏。5.3 为什么移动构造必须声明 noexcept这里有一个非常反直觉的细节如果你的类型有移动构造函数但没声明noexceptvector 扩容时会退化用拷贝构造函数搬移元素。原因是强保证要求如果搬移过程中抛出异常旧元素必须完好。但如果用移动构造搬移了元素旧位置上的元素已经被移走状态未明确指定此时再抛异常旧数组就回不到原来的状态了。只有拷贝构造抛出异常时旧元素保持原样才能保证强保证。所以std::move_if_noexcept的逻辑就是移动构造标记了noexcept就用移动否则用拷贝。这也解释了为什么现代 C 里只要我们想让一个类型高效放进 vector就必须给移动构造函数加上noexceptclass MyType { public: MyType(MyType other) noexcept { /* ... */ } MyType operator(MyType other) noexcept { /* ... */ } };这个细节是面试高频题也是实际项目里性能玄学的来源之一。一个没有noexcept移动构造的类型放进 vector每次扩容都是全量拷贝性能直接掉一个量级。6. 和真正的 std::vector 对比差距清单与实测数据6.1 功能层面的差距我的 MiniVector 基本实现了 vector 的核心接口但离标准库还很远。差距主要体现在以下方面功能点std::vectorMiniVector自定义分配器支持通过模板参数传入不支持固定用 std::allocatoremplace_back支持直接构造避免临时量未实现右值 push_back有 重载移动插入仅有 const Tinsert 的移动版本有 和 emplace未实现shrink_to_fit有释放多余容量未实现data()返回裸指针未实现可以直接返回 start_noexcept 标记大量优化标记不完整元素为 bool 的优化特化为位压缩未实现功能层面的差距大都不难补真正难的是性能层面的差距。6.2 性能实测插入 100 万个元素的用时对比我用一段简单的测试代码对比了 MiniVector 和std::vector#include chrono #include iostream #include vector template typename Vec void bench_insert(size_t n) { Vec v; v.reserve(1000); // 给小容量避免 reserve(n) 抹平差距 auto t1 std::chrono::high_resolution_clock::now(); for (size_t i 0; i n; i) { v.push_back(i); } auto t2 std::chrono::high_resolution_clock::now(); std::cout elapsed: std::chrono::duration_caststd::chrono::microseconds(t2 - t1).count() us\n; } int main() { bench_insertstd::vectorint(1000000); bench_insertMiniVectorint(1000000); return 0; }在一个中等配置的开发机上std::vector插入 100 万个int大约 5-8 毫秒MiniVector 大约 6-9 毫秒差距在 10%-20% 左右。如果编译时开启-O2差距会更小因为大部分开销在于内存分配和搬移这部分两者逻辑几乎一样。差距主要在两点一是标准库的reserve和push_back内联更好、分支预测更友好二是标准库对is_trivially_copyable等类型做了特化直接用memcpy/memmove搬移元素避免了逐元素构造/析构。我自己实现的代码所有类型都走循环 placement new对int这类平凡类型没有特化自然慢一点。6.3 生产环境我建议你直接忘掉手写版本如果你打算在项目里替换std::vector我的建议是除非你有极其特殊的场景比如固定分配器、嵌入式环境否则不要换。标准库的 vector 经过了无数亿次调用和几十年的打磨边界情况处理、指令级优化、异常安全都远好于任何人短期手写的版本。手写 vector 的价值不在替代在于理解。当你理解了它的内部机制你再写业务代码时就能自然避开很多性能陷阱和 UB未定义行为。比如你会知道为什么尽量reserve为什么提前知道上限就别反复push_back为什么迭代器不能保存太久。7. 测试自己的 vector从暴力乱用到 sanitizer7.1 基础功能测试写完实现第一关是功能正确性。我会用一个简单的测试程序覆盖每个公开接口void test_basic() { MiniVectorint v; assert(v.empty()); assert(v.size() 0); for (int i 0; i 100; i) { v.push_back(i); } assert(v.size() 100); assert(v.capacity() 100); for (int i 0; i 100; i) { assert(v[i] i); } v.insert(v.begin() 50, 999); assert(v[50] 999); assert(v.size() 101); v.erase(v.begin() 50); assert(v[50] 50); assert(v.size() 100); MiniVectorint v2(v); assert(v2 v); MiniVectorint v3(std::move(v)); assert(v3.size() 100); }这只是能跑通离可信还差很远。因为 vector 的 bug 往往藏在内存越界、double free、未析构对象这类不会立刻崩溃的问题里。7.2 用 ASan 和 UBSan 抓内存错误真实测试必须开 sanitizer 编译。我用下面的编译选项跑同样的测试瞬间就能暴露内存错误g -stdc17 -g -fsanitizeaddress,undefined -fno-omit-frame-pointer test.cpp -o test ./test如果代码里有越界访问ASan 会输出详细的报错指出是哪个地址、哪一行触发的。UBSan 则专门抓未定义行为比如有符号整数溢出、空指针解引用、对齐错误。我开发过程中用 ASan 抓出来的第一个 bug就是insert容量够路径里把start_[size()]当成已构造对象直接调用operator其实那还是裸内存。ASan 立刻报警。7.3 压力测试随机操作序列固定流程测试只能证明特定路径没问题随机化测试能覆盖更多组合路径。我写了一个简单的随机操作生成器随机执行 push_back、pop_back、insert、erase、reserve每一步后都校验容器的基本不变量if (v.size() 0) { assert(v.front() v[0]); assert(v.back() v[v.size() - 1]); assert(v.front() v.data_pointer()); assert(v.back() v.data_pointer() v.size() - 1); } assert(v.empty() (v.size() 0)); assert(v.capacity() v.size());配合 ASan 跑上几百万次随机操作很多隐蔽问题都会浮出水面。这也是我在实际项目里验证容器实现的固定套路功能测试打底sanitizer 拉满随机序列压测。8. 完整可运行的 MiniVector 实现下面是核心实现的完整代码。我刻意保持了简洁注释随手写方便你对照文章理解。这个版本去掉了enable_if的范围构造重载换成std::is_integral的简化方案适合学习和扩展。#include memory #include algorithm #include utility #include stdexcept template typename T class MiniVector { public: using value_type T; using size_type size_t; using difference_type ptrdiff_t; using reference T; using const_reference const T; using pointer T*; using const_pointer const T*; using iterator T*; using const_iterator const T*; private: pointer start_; pointer finish_; pointer end_of_storage_; std::allocatorT alloc_; public: MiniVector() noexcept : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) {} explicit MiniVector(size_type n) : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) { resize(n); } MiniVector(size_type n, const T value) : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) { assign(n, value); } ~MiniVector() { clear(); if (start_) alloc_.deallocate(start_, capacity()); } MiniVector(const MiniVector other) { start_ finish_ end_of_storage_ nullptr; reserve(other.size()); for (const auto elem : other) { push_back(elem); } } MiniVector(MiniVector other) noexcept : start_(other.start_), finish_(other.finish_), end_of_storage_(other.end_of_storage_) { other.start_ other.finish_ other.end_of_storage_ nullptr; } MiniVector operator(const MiniVector other) { if (this ! other) { MiniVector tmp(other); swap(tmp); } return *this; } MiniVector operator(MiniVector other) noexcept { if (this ! other) { clear(); alloc_.deallocate(start_, capacity()); start_ other.start_; finish_ other.finish_; end_of_storage_ other.end_of_storage_; other.start_ other.finish_ other.end_of_storage_ nullptr; } return *this; } void swap(MiniVector other) noexcept { using std::swap; swap(start_, other.start_); swap(finish_, other.finish_); swap(end_of_storage_, other.end_of_storage_); // 注意allocator 通常视为不交换C17 后默认分配器的 swap 是 noexcept } iterator begin() noexcept { return start_; } iterator end() noexcept { return finish_; } const_iterator begin() const noexcept { return start_; } const_iterator end() const noexcept { return finish_; } const_iterator cbegin() const noexcept { return start_; } const_iterator cend() const noexcept { return finish_; } size_type size() const noexcept { return finish_ - start_; } size_type capacity() const noexcept { return end_of_storage_ - start_; } bool empty() const noexcept { return start_ finish_; } reference operator[](size_type i) noexcept { return start_[i]; } const_reference operator[](size_type i) const noexcept { return start_[i]; } reference at(size_type i) { if (i size()) throw std::out_of_range(MiniVector::at); return start_[i]; } reference front() noexcept { return *start_; } reference back() noexcept { return *(finish_ - 1); } pointer data() noexcept { return start_; } void push_back(const T value) { if (finish_ end_of_storage_) { reserve(grow_capacity()); } alloc_.construct(finish_, value); finish_; } void push_back(T value) { if (finish_ end_of_storage_) { reserve(grow_capacity()); } alloc_.construct(finish_, std::move(value)); finish_; } void pop_back() { if (size() 0) return; --finish_; alloc_.destroy(finish_); } iterator insert(const_iterator pos, const T value) { size_type index pos - begin(); if (finish_ end_of_storage_) { size_type old_size size(); size_type new_cap grow_capacity(); pointer new_start alloc_.allocate(new_cap); for (size_type i 0; i index; i) { new (new_start i) T(start_[i]); } new (new_start index) T(value); for (size_type i index; i old_size; i) { new (new_start i 1) T(start_[i]); } for (size_type i 0; i old_size; i) { start_[i].~T(); } alloc_.deallocate(start_, capacity()); start_ new_start; finish_ new_start old_size 1; end_of_storage_ new_start new_cap; return iterator(start_ index); } // 容量够最后一个元素构造到新位置中间元素整体后移 alloc_.construct(finish_, std::move_if_noexcept(*(finish_ - 1))); finish_; for (size_type i size() - 1; i index; --i) { start_[i] std::move_if_noexcept(start_[i - 1]); } start_[index] value; return iterator(start_ index); } iterator erase(const_iterator pos) { size_type index pos - begin(); for (size_type i index; i size() - 1; i) { start_[i] std::move_if_noexcept(start_[i 1]); } --finish_; alloc_.destroy(finish_); return iterator(start_ index); } void clear() noexcept { for (size_type i 0; i size(); i) { alloc_.destroy(start_ i); } finish_ start_; } void reserve(size_type new_cap) { if (new_cap capacity()) return; if (new_cap 0) { clear(); alloc_.deallocate(start_, capacity()); start_ finish_ end_of_storage_ nullptr; return; } pointer new_start alloc_.allocate(new_cap); size_type old_size size(); for (size_type i 0; i old_size; i) { new (new_start i) T(std::move_if_noexcept(start_[i])); } for (size_type i 0; i old_size; i) { alloc_.destroy(start_ i); } alloc_.deallocate(start_, capacity()); start_ new_start; finish_ new_start old_size; end_of_storage_ new_start new_cap; } void resize(size_type new_size) { if (new_size size()) { reserve(new_size); for (size_type i size(); i new_size; i) { alloc_.construct(finish_); finish_; } } else if (new_size size()) { for (size_type i new_size; i size(); i) { alloc_.destroy(start_ i); } finish_ start_ new_size; } } void assign(size_type n, const T value) { clear(); if (capacity() n) reserve(n); for (size_type i 0; i n; i) { alloc_.construct(start_ i, value); } finish_ start_ n; } private: size_type grow_capacity() const { size_type old_cap capacity(); if (old_cap 0) return 1; return old_cap 8 ? old_cap * 2 : old_cap old_cap / 2; } }; template typename T bool operator(const MiniVectorT a, const MiniVectorT b) { if (a.size() ! b.size()) return false; for (size_t i 0; i a.size(); i) { if (a[i] ! b[i]) return false; } return true; }这个版本有一个最小实现上的取舍insert在扩容路径里用的是拷贝构造而非std::move_if_noexcept异常安全性稍弱一档。如果你要拿它当生产代码建议把那一行改成和reserve一样的std::move_if_noexcept逻辑再套一层 try-catch。不过这会让代码长度翻倍所以我在这里做了个简化理解思路比拿到终极版更重要。还有一个小地方值得注意swap里我没有交换alloc_。C17 之前的规则要求两个容器的分配器必须相等才允许交换而默认构造的std::allocator都是相等的所以这里不交换alloc_没问题。但如果你以后扩展支持自定义分配器交换逻辑要重新设计。9. 手写 vector 之后我对 STL 的理解发生了哪些变化整个过程做下来最大的收获不是我会写 vector 了而是很多以前靠死记硬背的规则现在变成了本来就是如此。比如为什么insert或者push_back会失效所有迭代器——因为内存一换所有指针都成了野指针这在物理层面是必然的。又比如为什么 vector 不适合频繁在头部插入——因为每个元素都要整体后移复杂度是 O(n)。再比如为什么 nomove 的类型放进 vector 扩容会很慢——因为强异常安全要求只能用拷贝拷贝的成本远高于移动。这些规则如果只是背下来面试过了就忘。但如果你亲手实现过一遍规则在你的认知里就不再是规则而是数据结构的本质属性。以后你在代码里看到v.insert(v.begin(), x)脑子里自然会浮现出那个元素集体后移的画面就会条件反射地意识到这段代码性能有问题。如果你也想做这个练习我建议你按这个顺序来先只实现默认构造、push_back、size、capacity、operator[]跑通最基本的测试再逐步加reserve、insert、erase、迭代器、拷贝/移动语义、异常安全性。每加一个功能就用 ASan 跑一遍随机测试别急着一次性写完。这个循序渐进的过程比直接抄一个完整实现有用得多。最后说一个调试技巧如果你的 vector 实现出现了内存问题先别急着看逻辑把start_、finish_、end_of_storage_三根指针的值打出来很多问题一眼就能看出来——比如size()变成负数说明finish_跑到start_前面了比如capacity()巨大无比说明某个指针被写坏了。三根指针是整个 vector 的全部状态所有 bug 最终都会映射到它们身上直接从它们入手排查效率最高。