1. 项目概述为什么我们要“手撕”一个vector在C的世界里std::vector几乎是每个开发者最熟悉、使用频率最高的容器没有之一。它就像一个动态的、智能的数组帮你自动管理内存让你可以安心地往里面塞数据而不用担心越界或者手动分配内存的繁琐。但是你有没有想过这个看似简单的“动态数组”内部到底是怎么工作的为什么它能动态扩容为什么在中间插入元素后之前的迭代器可能会失效这些问题仅仅通过调用push_back和operator[]是无法得到深刻理解的。这就是我们今天要做的——“模拟实现”一个自己的vector。这可不是一个简单的练习而是一次深入C核心机制的探险。通过亲手搭建一个MyVector你将彻底搞明白内存管理的本质new/delete与malloc/free的差异以及RAII资源获取即初始化思想如何优雅地管理资源。迭代器的抽象迭代器为什么能像指针一样使用它的底层究竟是什么动态扩容的算法为什么是1.5倍或2倍扩容这背后是时间与空间的权衡。异常安全在拷贝元素、扩容时如何保证操作失败后程序状态依然是可控的模板编程的实战如何编写一个通用的、能容纳任意类型数据的容器类对于正在准备面试的开发者来说vector的模拟实现是经典的“八股文”考题但它的价值远超应付面试。它能夯实你对C基础构造/析构、拷贝控制、操作符重载、模板的理解让你在后续使用STL时从一个“调用者”转变为“理解者”甚至“设计者”。无论你是想巩固基础、应对技术面试还是单纯对STL的实现感到好奇这次“手撕”之旅都将让你受益匪浅。2. 核心设计思路与类框架搭建动手之前我们必须先想清楚一个最简化的vector需要哪些核心部件。我们不追求与标准库实现百分之百一致那涉及分配器、异常规范等更复杂的内容而是抓住主干实现一个功能完整、原理清晰的MyVector。2.1 核心成员变量设计一个vector本质上管理着一块连续的内存空间。我们需要三个指针或等价物来标记这块内存的状态_start指向容器所使用的内存空间的起始位置。_finish指向当前已存储的最后一个元素的下一个位置。_finish - _start就等于当前容器中的元素数量即size()。_end_of_storage指向整个已分配内存空间的末尾的下一个位置。_end_of_storage - _start等于当前容器的总容量即capacity()。为什么用指针而不是直接存储size和capacity的整型值因为指针在进行元素访问、迭代器实现时更为直接和高效。迭代器本质上就是原生指针对于vector而言这样begin()可以直接返回_startend()返回_finish。2.2 类模板声明与基础构造函数我们的MyVector必须是一个模板类以支持存储任意类型T。templateclass T class MyVector { public: // 迭代器类型定义vector的迭代器就是原生指针 typedef T* iterator; typedef const T* const_iterator; // 默认构造函数初始化为空容器 MyVector() : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} // 带初始大小和值的构造函数 MyVector(size_t n, const T val T()) : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(n); // 先分配足够内存 for (size_t i 0; i n; i) { push_back(val); // 再填充元素 } } // 迭代器范围构造函数 [first, last) templateclass InputIterator MyVector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } } // 拷贝构造函数深拷贝 MyVector(const MyVectorT v) { // 先分配一块和v一样大的空间 _start new T[v.capacity()]; // 将v中的元素逐个拷贝过来使用placement new或直接赋值取决于T的类型 // 这里使用标准库的std::copy它对于平凡类型和自定义类型都适用 // 注意这里假设T类型有合适的拷贝语义 std::copy(v._start, v._finish, _start); _finish _start v.size(); _end_of_storage _start v.capacity(); } private: iterator _start; // 指向数据块开始 iterator _finish; // 指向最后一个有效元素的下一个位置 iterator _end_of_storage; // 指向存储空间末尾的下一个位置 };设计要点解析迭代器类型定义将iterator定义为T*这是vector迭代器高效的原因。const_iterator对应const T*。构造函数初始化列表务必在初始化列表中将所有指针置为nullptr这是一个好习惯可以避免野指针。迭代器范围构造函数这是一个模板函数它接受任意类型的输入迭代器只要支持*和操作。这体现了STL的泛型编程思想使得MyVector可以从其他容器如数组、list初始化。拷贝构造的深拷贝这是关键我们必须分配新内存并把旧容器的元素逐个拷贝过来。直接指针赋值 (_start v._start) 会导致两个对象共享同一块内存析构时会被重复释放造成程序崩溃。这里使用了std::copy它是一个泛型算法能正确处理内置类型和自定义类型调用其拷贝赋值运算符或拷贝构造函数。注意上面的std::copy实现对于某些非平凡类型如管理资源的类可能不够安全。更严谨的做法是使用std::uninitialized_copy或者在new之后使用placement new来构造对象。但为了代码清晰和聚焦主线我们暂时使用std::copy并假设类型T是“平凡的”或具有正确的拷贝语义。在“异常安全”章节我们会深入讨论。3. 核心功能实现增删改查与迭代器有了骨架我们开始填充血肉。vector最核心的功能就是元素的增删改查以及遍历容器的迭代器。3.1 迭代器相关函数迭代器让容器用起来像指针一样方便。// 迭代器获取 iterator begin() { return _start; } const_iterator begin() const { return _start; } iterator end() { return _finish; } const_iterator end() const { return _finish; } // 反向迭代器简易版标准库实现更复杂 typedef std::reverse_iteratoriterator reverse_iterator; typedef std::reverse_iteratorconst_iterator const_reverse_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } // 容量与大小 size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start _finish; } // 元素访问 T operator[](size_t pos) { assert(pos size()); // 断言检查防止越界 return _start[pos]; } const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; } T front() { assert(!empty()); return *_start; } T back() { assert(!empty()); return *(_finish - 1); }实现心得begin()和end()的const版本是必须的当MyVector对象被const修饰时只能调用这两个版本返回const_iterator保证了元素的不可修改性。operator[]的重载使得MyVector可以像数组一样使用v[i]进行访问非常直观。务必进行越界检查这里使用assert在调试阶段非常有用。生产代码可能会选择抛出异常。反向迭代器我们偷了个懒直接使用了标准库的std::reverse_iterator适配器。它接收一个正向迭代器类型自动生成反向迭代器。rbegin()对应end()rend()对应begin()这样*rbegin()就能拿到最后一个元素。3.2 内存管理reserve 与 resize这是vector动态性的核心。void reserve(size_t n) { if (n capacity()) { // 1. 申请新空间 T* tmp new T[n]; // 注意这里直接 new T[n] 会调用 n 次 T 的默认构造函数 size_t old_size size(); // 2. 拷贝旧数据 (如果存在) if (_start) { // 方法一使用memcpy仅对平凡类型安全如int, double // memcpy(tmp, _start, sizeof(T) * old_size); // 方法二使用std::copy调用赋值运算符更通用 std::copy(_start, _finish, tmp); // 3. 释放旧空间 delete[] _start; } // 4. 更新指针 _start tmp; _finish _start old_size; _end_of_storage _start n; } } void resize(size_t n, const T val T()) { if (n capacity()) { reserve(n); } if (n size()) { // 在尾部填充新元素 while (_finish ! _start n) { *_finish val; // 这里调用的是 T 的赋值运算符 _finish; } } else { // 缩小size但capacity不变 _finish _start n; // 注意这里并没有销毁多余元素的内存只是改变了_finish指针。 // 对于需要析构的类对象这可能造成资源泄漏。更严谨的做法是调用析构函数。 // 例如for (iterator it _start n; it ! _finish; it) { it-~T(); } // 然后再更新 _finish。 } }这是第一个大坑reserve的实现陷阱new T[n]的问题new T[n]不仅分配内存还会为这n个位置调用T的默认构造函数。如果T是一个没有默认构造函数的类或者默认构造函数开销很大这就是浪费。更重要的是之后我们用std::copy覆盖这些位置时相当于每个元素被构造了两次一次默认构造一次拷贝赋值这不符合预期且效率低下。更正确的做法应该只分配原始内存不进行构造。这需要用到operator new和placement new。void reserve(size_t n) { if (n capacity()) { size_t old_size size(); // 1. 分配原始内存不构造对象 T* tmp static_castT*(::operator new(n * sizeof(T))); // 2. 将旧元素“移动”或“拷贝”到新内存 if (_start) { // 假设T有移动构造函数C11后 // 对于不支持移动的尝试拷贝 for (size_t i 0; i old_size; i) { // placement new在指定内存地址构造对象 new (tmp i) T(std::move(_start[i])); // 尝试移动 // 或者 new (tmp i) T(_start[i]); // 拷贝构造 } // 3. 析构旧元素并释放内存 for (size_t i 0; i old_size; i) { _start[i].~T(); // 显式调用析构函数 } ::operator delete(_start); // 释放原始内存 } _start tmp; _finish _start old_size; _end_of_storage _start n; } }这个版本更接近标准库的实现思路但它涉及了更底层的内存操作和对象生命周期管理对初学者理解负担较重。我们最初的简化版使用new T[n]和std::copy在大多数简单场景下如vectorint也能工作但你需要知道它的局限性。resize的注意事项当n size()时我们只是移动了_finish指针。那些“逻辑上”被删除的元素其析构函数并没有被调用。如果T持有资源如动态内存、文件句柄就会导致资源泄漏。一个健壮的实现应该显式调用这些元素的析构函数。3.3 元素增删push_back, pop_back, insert, erasevoid push_back(const T val) { // 检查是否需要扩容 if (_finish _end_of_storage) { // 扩容策略如果为空分配1个空间否则扩容为原来的2倍 size_t new_capacity capacity() 0 ? 1 : capacity() * 2; reserve(new_capacity); } // 在_finish位置构造新元素 *_finish val; // 这里同样是赋值假设空间已构造。更严谨的是 placement new。 _finish; } // C11 移动语义版本 void push_back(T val) { if (_finish _end_of_storage) { size_t new_capacity capacity() 0 ? 1 : capacity() * 2; reserve(new_capacity); } *_finish std::move(val); // 移动赋值 _finish; } void pop_back() { assert(!empty()); --_finish; // 同样这里应该调用析构函数: _finish-~T(); } // 在pos位置插入元素val iterator insert(iterator pos, const T val) { assert(pos _start pos _finish); // pos可以在end()位置 // 检查容量 if (_finish _end_of_storage) { // 扩容会导致迭代器失效 // 记录pos的相对位置因为_start可能改变 size_t len pos - _start; size_t new_capacity capacity() 0 ? 1 : capacity() * 2; reserve(new_capacity); // 更新pos指向新空间的对应位置 pos _start len; } // 将pos及之后的元素向后移动一位 iterator end _finish; while (end pos) { *end *(end - 1); // 向后赋值 --end; } // 在pos位置插入新元素 *pos val; _finish; return pos; // 返回指向新插入元素的迭代器 } // 删除pos位置的元素 iterator erase(iterator pos) { assert(pos _start pos _finish); // 将pos1之后的元素向前移动一位 iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } --_finish; // 应该调用最后一个被覆盖位置的析构函数(原_finish位置) // (_finish)-~T(); // 因为_finish已前移原位置元素已无效 return pos; // 返回指向被删除元素下一个位置的迭代器 }核心难点与经验扩容策略常见的策略是2倍扩容如GCC的libstdc或1.5倍扩容如MSVC的STL。2倍扩容在摊还分析下能保证push_back操作的平均时间复杂度为O(1)。从0到1的初始分配也很重要。迭代器失效问题重中之重这是vector面试必考题。insert导致失效当发生扩容时reserve会申请新内存并拷贝数据然后释放旧内存。此时所有指向旧内存的迭代器、指针、引用都变得非法悬空。这就是为什么我们在insert中扩容后要重新计算pos的位置。调用insert后之前保存的任何迭代器包括传入的pos都不应再使用除非你使用函数返回的新迭代器。erase导致失效删除元素后被删除元素及其之后所有元素的迭代器、指针、引用都失效了。因为元素向前移动了。erase会返回下一个有效元素的位置这是一个良好的实践。push_back/pop_back只有push_back导致扩容时所有迭代器失效否则只有end()迭代器失效。pop_back使指向最后一个元素的迭代器失效。移动语义提供了push_back(T)的重载当传入临时对象右值时编译器会选择这个版本使用移动构造或移动赋值避免不必要的深拷贝提升性能。4. 完善与优化拷贝赋值、析构与非成员函数4.1 析构函数与拷贝赋值运算符遵循“Rule of Three”C11后是“Rule of Five”如果一个类需要自定义析构函数、拷贝构造函数或拷贝赋值运算符那么它通常需要全部三个。~MyVector() { // 1. 析构所有已构造的元素 if (_start) { for (iterator it _start; it ! _finish; it) { it-~T(); // 显式调用析构函数 } // 2. 释放内存 ::operator delete(_start); // 对应 operator new 的释放 // 如果是用 new T[] 分配的则用 delete[] _start; _start _finish _end_of_storage nullptr; } } // 拷贝赋值运算符现代写法copy-and-swap MyVectorT operator(MyVectorT v) { // 注意这里参数是传值 swap(v); // 交换当前对象和临时对象v的内容 return *this; // 离开作用域时临时对象v现在是旧数据被析构 } // 交换函数 void swap(MyVectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }拷贝赋值运算符的现代写法解析 这是非常优雅且异常安全的一种实现被称为copy-and-swap惯用法。参数MyVectorT v是传值。当调用v1 v2时会调用拷贝构造函数创建出一个v2的副本v。这个拷贝操作可能失败抛出异常但如果失败是在修改v1之前因此v1的状态保持不变这是强异常安全保证。然后我们调用swap成员函数将*this和v的内容进行交换。交换操作通常只是交换几个指针非常高效且不会抛出异常。函数返回时局部对象v现在持有*this的旧数据被析构自动释放旧内存。最终*this拥有了v2数据的副本而v2本身不受影响。这种方法避免了传统写法中先释放自身资源再拷贝时可能发生的异常安全问题代码也非常简洁。4.2 关系运算符重载与一些常用函数为了让MyVector用起来更像标准容器我们可以重载一些运算符。// 重载比较运算符 (, !, , , , ) bool operator(const MyVectorT v) const { if (size() ! v.size()) return false; for (size_t i 0; i size(); i) { if (!((*this)[i] v[i])) { // 使用T的运算符进行比较 return false; } } return true; } bool operator!(const MyVectorT v) const { return !(*this v); } // 其他比较运算符类似通常按字典序比较 // 清空容器 void clear() { // 析构所有元素 for (iterator it _start; it ! _finish; it) { it-~T(); } _finish _start; // 逻辑上清空内存不释放 } // 调整容量C11的shrink_to_fit思想 void shrink_to_fit() { if (size() capacity()) { // 分配一块刚好容纳当前元素的新内存 MyVectorT tmp(*this); // 利用拷贝构造 swap(tmp); // 交换 // tmp离开作用域释放多余内存 } }shrink_to_fit的注意点 这个函数请求容器减少capacity()到size()。但请注意这是一个非强制性请求。实现可以忽略它。我们的简易实现通过创建一个新的临时对象拷贝构造然后交换间接实现了“收缩”。这可能会引起一次元素拷贝和内存重分配。5. 模拟实现中的典型问题与深度思考5.1 迭代器失效的实战场景与排查让我们写一段代码来演示迭代器失效的坑MyVectorint vec; for (int i 0; i 10; i) { vec.push_back(i); } auto it vec.begin() 5; // 指向第6个元素值为5 std::cout Before insert, *it *it std::endl; // 插入大量元素导致扩容 vec.insert(vec.begin(), 100, 1); // 在头部插入100个1极大概率触发扩容 // 危险it已经失效 std::cout After insert, *it *it std::endl; // 未定义行为可能崩溃也可能输出垃圾值。 // 正确做法使用insert返回的新迭代器或者插入后重新获取 it vec.insert(vec.begin() 105, 999); // 在扩容后的新位置插入 // 此时it是有效的指向新插入的999排查技巧在调试时如果遇到访问vector元素时程序崩溃或数据错乱首先怀疑迭代器失效。仔细检查在可能引起内存重新分配的操作insert,push_back(可能),reserve,resize(增大)之后是否还在使用之前的迭代器。使用vector的capacity()和size()函数监控内存变化辅助判断。5.2 深拷贝与浅拷贝的陷阱如果我们没有正确实现拷贝构造函数和拷贝赋值运算符编译器会为我们生成默认的。默认版本进行的是浅拷贝成员-wise copy对于指针成员只是复制了指针值而不是指针指向的内存。// 错误示例使用编译器生成的默认拷贝构造 MyVectorint v1; v1.push_back(1); v1.push_back(2); { MyVectorint v2 v1; // 浅拷贝v2._start 和 v1._start 指向同一块内存 } // 离开作用域v2析构释放了那块内存 // 此时v1._start成了野指针后续对v1的任何操作都是未定义行为。 v1.push_back(3); // 程序很可能崩溃这就是为什么“Rule of Three”如此重要。当类管理着动态资源这里是堆内存时你必须自定义拷贝控制成员来管理资源的深拷贝。5.3 异常安全性的考量我们的简化版push_back和insert在异常安全方面是脆弱的。考虑以下场景void push_back(const T val) { if (_finish _end_of_storage) { reserve(capacity() * 2); // 可能抛出异常如bad_alloc } *_finish val; // 如果T的赋值运算符抛出异常呢 _finish; }如果reserve中的new抛出std::bad_allocpush_back整体失败但*this的状态没有改变强保证。但是如果*_finish val这个赋值操作抛出异常问题就大了。元素没有被成功添加但_finish指针还没有移动所以容器逻辑状态没变。然而如果T的赋值操作破坏了val或目标对象呢或者如果T的赋值不是“异常中立”的呢这可能导致容器处于一个不可预测的状态。更健壮的实现基本保证 一种提供“基本保证”操作失败后容器处于有效状态但内容可能改变的策略是使用“拷贝后交换”或仔细安排操作顺序。例如可以先在尾部构造一个临时对象如果成功再移动_finish指针。但这涉及更复杂的placement new和异常处理。对于学习目的我们通常假设T的拷贝/赋值操作是“异常安全”的至少提供基本保证并且不会在失败时留下无效状态。但在编写生产级别的通用容器时异常安全是必须严肃对待的问题。5.4 与标准库vector的差异我们的MyVector是一个教学性质的简化实现与std::vector的主要差异包括分配器Allocatorstd::vector有一个模板参数Allocator用于控制内存的分配与释放使得内存策略可定制。我们直接使用了new/delete。异常规范std::vector的成员函数有详细的异常规范noexcept。迭代器类型std::vector的迭代器是随机访问迭代器我们简单用指针实现但对于某些编译器调试模式或特殊的分配器可能不是原生指针。初始化与构造我们的reserve简化版使用了new T[n]而标准库会使用分配器来分配原始内存并在需要时用placement new构造对象。移动语义C11后std::vector有完整的移动构造函数和移动赋值运算符可以高效地转移资源所有权。emplace_back与emplaceC11引入了变参模板的emplace系列函数可以直接在容器内构造对象避免临时对象的创建和拷贝/移动。尽管有这些差异我们这个MyVector已经涵盖了std::vector最核心的设计思想、数据结构和算法理解了它你就掌握了动态数组容器的精髓。通过这次从零开始的模拟实现我们不仅得到了一个可用的MyVector类更重要的是我们深入理解了连续存储容器的内存管理、迭代器抽象、动态扩容策略以及C资源管理的核心思想RAII。下次当你再写下std::vectorint v;时你脑海中浮现的将不再是一个黑盒而是一个由三个指针精巧控制的、充满智慧的设计。这才是“手撕”代码带来的真正价值。