1. 项目概述为什么我们要“手撕”vector如果你正在学习C尤其是学到STL标准模板库这一块那么“模拟实现vector”几乎是一个绕不开的经典练习。这就像学武功要先扎马步学编程到一定深度就得去拆解这些基础又强大的“轮子”。vector作为STL中最常用、最核心的序列容器之一它那看似简单的push_back、pop_back背后隐藏着动态内存管理、迭代器抽象、异常安全、类型萃取等一系列C核心思想。网上的八股文可能会告诉你vector的扩容因子是1.5或2但如果不亲手实现一遍你很难真正理解为什么是这些数字以及在拷贝构造、赋值运算符重载时稍有不慎就会掉进哪些深坑。我当年第一次尝试自己写一个简易的vector时光是处理迭代器失效的问题就调试了大半天。市面上很多教程和面试题都停留在表面只讲“是什么”不讲“为什么”和“怎么办”。这篇内容我就结合自己踩过的坑和多年使用C的经验带你从零开始构建一个功能完整、考虑周全的MyVector。我们不仅会实现增删改查更会深入探讨深拷贝与浅拷贝的陷阱、迭代器失效的根源与解决方案、利用RAII资源获取即初始化思想管理资源以及如何模拟STL的allocator空间配置器行为。目标是让你做完这个练习后不仅能应对面试中“请实现一个vector”这类问题更能深刻理解C面向对象和泛型编程的精髓写出更健壮、高效的代码。2. 整体设计与核心思路拆解在动手写代码之前我们必须先想清楚这个MyVector类应该长什么样以及它需要遵循哪些设计原则。一个合格的vector模拟实现绝不是简单封装一个动态数组它需要体现C的几大核心特性。2.1 类的骨架与数据成员首先vector是一个模板类这意味着它需要能容纳任意类型的元素。因此我们的类声明应该是这样的templatetypename T class MyVector { public: // 各种成员函数声明... private: T* _start; // 指向数组首元素的指针 T* _finish; // 指向最后一个有效元素的下一个位置 T* _end_of_storage; // 指向分配的内存空间末尾的下一个位置 };这三个指针是vector实现的核心它们清晰地划分了三个关键区域_start到_finish: 当前已使用的、存储有效元素的空间。_finish到_end_of_storage: 当前已分配但尚未使用的预留空间capacity。_end_of_storage之后: 未分配的内存。使用三个指针而非“起始指针大小容量”三个整数是为了与STL的迭代器设计保持兼容。_start和_finish天然就是迭代器原生指针begin()和end()函数可以直接返回它们。2.2 关键设计原则RAII资源获取即初始化这是C管理资源的黄金法则。我们的类需要在构造函数中获取资源内存在析构函数中释放资源。确保任何情况下包括发生异常资源都不会泄漏。异常安全在可能抛出异常的操作如内存分配、元素构造中要保证操作的原子性。例如在push_back时如果扩容失败vector应该保持原有状态不变。深拷贝这是模拟实现中最容易出错的地方。拷贝构造函数和赋值运算符必须进行深拷贝即复制内容而非指针。否则两个vector会共享同一块内存一个被析构后另一个就成了“悬空指针”导致未定义行为。迭代器失效规则我们需要模拟STL vector的迭代器失效行为。简单来说任何可能引起内存重新分配的操作如insert导致扩容、erase导致元素移动都会使指向该vector的所有迭代器、引用和指针失效。我们的实现必须明确这一点。3. 基础架构与资源管理实现有了清晰的设计图我们就可以开始搭建基础了。这部分是vector的“地基”如果没打好后面的所有功能都会摇摇欲坠。3.1 构造函数、析构函数与基本接口我们先实现最基础的几个函数让MyVector对象能够被创建、销毁并查看其状态。templatetypename T class MyVector { public: // 默认构造函数 MyVector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {} // 带初始大小和值的构造函数 MyVector(size_t n, const T value T()) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { reserve(n); // 先分配足够空间 for (size_t i 0; i n; i) { push_back(value); // 在已分配的空间上构造对象 } } // 析构函数 - RAII的核心 ~MyVector() { if (_start) { // 1. 析构已构造的对象 for (T* p _start; p ! _finish; p) { p-~T(); // 显式调用析构函数 } // 2. 释放内存 delete[] reinterpret_castchar*(_start); _start _finish _end_of_storage nullptr; } } // 迭代器 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } // 容量相关 size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start _finish; } private: T* _start; T* _finish; T* _end_of_storage; };注意在析构函数中我们做了两件事先调用每个有效元素的析构函数再释放内存。这是因为我们使用new[]分配的是“原始内存”对于非平凡类型如含有动态成员的类直接delete[]指针可能导致其内部资源泄漏。先析构对象是更安全的做法。当然更现代、更推荐的做法是使用std::allocator但为了理解原理我们先从最底层的方式开始。3.2 内存管理核心reserve与resizereserve和resize是vector动态能力的体现也是很多问题的源头。reserve(n)确保vector的容量至少为n。如果当前容量小于n则重新分配一块更大的内存并将原有元素移动或拷贝到新内存。void reserve(size_t n) { if (n capacity()) { size_t old_size size(); // 1. 分配新内存 T* new_start reinterpret_castT*(new char[n * sizeof(T)]); // 分配原始字节 // 2. 搬运数据考虑异常安全 // 如果T的拷贝构造函数可能抛出异常我们需要保证旧数据不被破坏 T* new_finish new_start; try { for (size_t i 0; i old_size; i) { // 使用“定位new”在指定内存地址构造对象 new (new_finish) T(_start[i]); // 拷贝构造 new_finish; } } catch (...) { // 如果构造过程中发生异常需要析构已构造的新对象并释放新内存 while (new_finish ! new_start) { (--new_finish)-~T(); } delete[] reinterpret_castchar*(new_start); throw; // 重新抛出异常 } // 3. 释放旧内存先析构旧对象 for (T* p _start; p ! _finish; p) { p-~T(); } delete[] reinterpret_castchar*(_start); // 4. 更新指针 _start new_start; _finish new_finish; _end_of_storage _start n; } }实操心得这里的异常处理是关键。如果在搬运数据第2步时发生异常我们必须确保已经构造的新对象被正确析构新内存被释放同时旧数据保持完好。这就是“强异常安全保证”操作要么成功要么像什么都没发生过。在实际项目中我们通常会使用std::uninitialized_copy等标准库算法来简化这部分逻辑它们内部已经处理好了异常安全。resize(n, value T())改变vector的size。如果n size()则在末尾添加元素如果n size()则删除末尾的元素。void resize(size_t n, const T value T()) { if (n size()) { // 需要扩容 if (n capacity()) { reserve(n); // 扩容 } // 在[_finish, _startn)区间构造新元素 for (T* p _finish; p ! _start n; p) { new (p) T(value); // 定位new构造 } _finish _start n; } else { // 需要缩容析构多余元素 for (T* p _start n; p ! _finish; p) { p-~T(); } _finish _start n; // 注意这里只析构对象不释放内存capacity不变 } }4. 增删改查操作与迭代器失效基础打好后我们就可以实现vector最常用的功能了添加、删除、访问元素。这部分是使用频率最高的也是迭代器失效问题的重灾区。4.1 push_back 与 pop_backpush_back是vector的招牌函数它的实现直接关系到性能和安全性。void push_back(const T value) { // 检查是否需要扩容 if (_finish _end_of_storage) { // 计算新容量常见的策略是翻倍避免频繁扩容 size_t new_capacity capacity() 0 ? 4 : capacity() * 2; reserve(new_capacity); } // 在_finish位置构造新元素 new (_finish) T(value); // 拷贝构造 _finish; }为什么扩容因子常用2这是一个时间与空间的权衡。因子太小如1.5会导致频繁扩容每次扩容后拷贝原有元素的成本摊还下来较高。因子太大又会浪费内存。2是一个在多数场景下取得较好平衡的经验值。一些实现如MSVC使用1.5能更好地利用之前释放的内存块。pop_back相对简单但要注意对空vector的操作。void pop_back() { if (!empty()) { --_finish; _finish-~T(); // 析构最后一个元素 } // 如果vector为空什么也不做或者可以抛出异常但STL未定义 }4.2 insert 与 erase迭代器失效的根源insert和erase是导致迭代器失效的典型操作因为它们可能引起元素的移动和内存的重新分配。insert(iterator pos, const T value): 在指定位置前插入一个元素。iterator insert(iterator pos, const T value) { // 检查pos是否在有效范围内 [begin(), end()] assert(pos begin() pos end()); // 1. 检查扩容扩容会导致所有迭代器失效 if (_finish _end_of_storage) { // 扩容前计算pos的相对位置因为扩容后_start会变 size_t len pos - _start; size_t new_capacity capacity() 0 ? 4 : capacity() * 2; reserve(new_capacity); // 扩容后pos需要更新到新内存的对应位置 pos _start len; } // 2. 从后往前移动元素为插入腾出位置 iterator end _finish; while (end pos) { *end *(end - 1); // 赋值操作如果T的赋值运算符有异常...复杂暂不考虑 --end; } // 3. 在pos位置构造新元素 *pos value; // 这里也是赋值更严谨的做法是用构造但涉及已存在内存的构造/赋值情况复杂 _finish; // 4. 返回指向新插入元素的迭代器 return pos; }重要警告上面的实现为了清晰使用了简单的赋值。但在实际中如果T的赋值运算符可能抛出异常这个操作就不满足“强异常安全保证”。更严谨的做法是先将插入点之后的元素移动到新位置如果T有移动语义且noexcept或者使用更复杂的“旋转”算法。这也是为什么STL的实现如此复杂的原因之一。erase(iterator pos): 删除指定位置的元素。iterator erase(iterator pos) { assert(pos begin() pos end()); // pos不能是end() // 从pos1开始将元素前移一位 iterator it pos 1; while (it ! _finish) { *(it - 1) *it; // 同样存在异常安全问题 it; } --_finish; // 析构最后一个位置现在是多余的空位的对象 _finish-~T(); // 返回被删除元素之后的位置 return pos; }迭代器失效总结表操作是否导致迭代器失效失效范围原因push_back可能所有迭代器、指针、引用如果触发reserve重新分配内存则全部失效。否则只有end()失效。pop_back是end()及其之前的迭代器可能失效最后一个元素被析构指向它的迭代器/引用失效。insert可能所有迭代器、指针、引用如果触发扩容则全部失效。否则插入位置及之后的迭代器失效。erase是被删除元素及之后的所有迭代器、指针、引用元素前移后面的迭代器指向的元素位置变了。reserve是所有迭代器、指针、引用内存地址改变。resize(增大)可能同push_back可能触发扩容。resize(缩小)是被删除元素及其之后的迭代器、引用同erase。避坑技巧一个非常实用的习惯是在调用可能使迭代器失效的函数后立即更新你的迭代器或者避免在循环中直接使用旧的迭代器。例如for (auto it vec.begin(); it ! vec.end(); /* 这里不递增 */) { if (*it value_to_remove) { it vec.erase(it); // erase返回新的有效迭代器 } else { it; } }4.3 访问操作operator[] 与 at提供像数组一样的随机访问是vector的一大优势。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 at(size_t pos) { if (pos size()) { throw std::out_of_range(MyVector::at - pos out of range); } return _start[pos]; } const T at(size_t pos) const { if (pos size()) { throw std::out_of_range(MyVector::at - pos out of range); } return _start[pos]; }operator[]和at的主要区别在于边界检查。operator[]通常不检查或只在调试模式检查追求速度at()会进行严格的检查并在越界时抛出std::out_of_range异常更安全。5. 深拷贝与赋值运算符避免“双胞胎”的灾难这是模拟实现中最经典的陷阱。默认的拷贝构造函数和赋值运算符是“浅拷贝”只复制指针导致两个对象共享同一块内存。我们需要实现“深拷贝”。5.1 拷贝构造函数// 拷贝构造函数 MyVector(const MyVectorT other) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { // 先分配足够大的空间 reserve(other.capacity()); // 然后拷贝构造每一个元素 for (const auto e : other) { push_back(e); // 这里会调用T的拷贝构造函数 } }5.2 赋值运算符重载现代写法传统的写法是先检查自赋值然后释放旧内存再分配新内存并拷贝。这里介绍一种更安全、更清晰的“拷贝-交换”惯用法。MyVectorT operator(MyVectorT other) { // 注意参数是值传递会调用拷贝构造函数 swap(other); // 交换当前对象和临时对象other的内容 return *this; } // 函数结束临时对象other被析构释放掉旧的资源这个实现妙在哪里参数other是值传递它本身就是other的一个副本深拷贝完成。我们只需交换this和other的内部指针。交换操作是O(1)的且不会抛出异常。函数返回时临时对象other被析构它现在持有的是this原来的资源被安全释放。它天然就正确处理了自赋值v v的情况因为传参时已经创建了副本。当然我们需要实现一个swap成员函数void swap(MyVectorT other) noexcept { std::swap(_start, other._start); std::swap(_finish, other._finish); std::swap(_end_of_storage, other._end_of_storage); }6. 完善与优化从“能用”到“好用”一个基础的MyVector已经完成了。但要让它更接近标准库的vector我们还需要考虑一些细节和优化。6.1 完善构造函数支持迭代器范围初始化STL的vector可以用另一个容器的迭代器范围来初始化这非常方便。templatetypename InputIterator MyVector(InputIterator first, InputIterator last) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { // 遍历迭代器范围逐个插入 while (first ! last) { push_back(*first); first; } }6.2 实现移动语义C11及以上移动构造函数和移动赋值运算符可以避免不必要的深拷贝大幅提升性能。// 移动构造函数 MyVector(MyVectorT other) noexcept : _start(other._start), _finish(other._finish), _end_of_storage(other._end_of_storage) { // 将源对象置于有效但可析构的状态空状态 other._start other._finish other._end_of_storage nullptr; } // 移动赋值运算符 MyVectorT operator(MyVectorT other) noexcept { if (this ! other) { // 释放当前资源 this-~MyVector(); // 接管资源 _start other._start; _finish other._finish; _end_of_storage other._end_of_storage; // 置空源对象 other._start other._finish other._end_of_storage nullptr; } return *this; }6.3 使用allocator空间配置器我们之前一直用new char[]和delete[]来分配原始内存。标准库的vector使用了一个叫allocator的模板参数来分离内存分配和对象构造的逻辑。这是更灵活、更专业的设计。templatetypename T, typename Alloc std::allocatorT class MyVectorWithAlloc { // ... 使用Alloc来allocate/deallocate内存construct/destroy对象 };实现allocator版本是一个更高级的练习它要求你理解std::allocator_traits并妥善处理对齐等问题。这能让你对STL的内存管理机制有更深的认识。7. 常见问题与调试技巧实录在实现和测试这个MyVector的过程中你几乎一定会遇到下面这些问题。这里我把它们和解决方法记录下来。7.1 内存泄漏与双重释放症状程序运行一段时间后内存占用不断增长或在析构时崩溃double free or corruption。根因构造函数中分配内存失败但未将指针置空如果reserve在分配内存后、构造元素前抛出异常构造函数退出但_start等指针可能已被赋值非nullptr。析构函数会对一个无效指针调用delete[]。拷贝/赋值未实现深拷贝两个对象共享内存一个析构后另一个的指针就悬空了。移动操作后源对象仍持有资源移动后没有将源对象的指针置空导致源对象析构时释放了已被移动的资源。排查使用Valgrind、AddressSanitizer等内存检查工具。它们能精准定位内存泄漏和非法访问的位置。解决遵循RAII在构造函数初始化列表中就将所有指针初始化为nullptr。在释放内存后立即将指针置为nullptr。确保拷贝操作是深拷贝。在移动操作中转移资源后务必置空源对象指针。7.2 迭代器失效导致的崩溃或逻辑错误症状在循环中插入或删除元素后程序崩溃或输出结果不符合预期。根因使用了因insert、erase、push_back可能扩容而失效的迭代器。示例MyVectorint vec {1, 2, 3, 4, 5}; for (auto it vec.begin(); it ! vec.end(); it) { if (*it % 2 0) { vec.erase(it); // 错误erase后it失效后续的it行为未定义 } }解决使用erase的返回值更新迭代器如4.2节所述。7.3 模板编译错误症状编译器报出一大堆看不懂的错误指向模板内部。常见原因类型不支持你尝试对没有默认构造函数、拷贝构造函数或赋值运算符的类型使用MyVector。链接错误模板类的成员函数定义在.cpp文件中。模板的定义必须放在头文件里因为编译器需要在实例化模板时看到完整的定义。解决确保你的MyVector类及其所有成员函数的定义都在一个.hpp或.h头文件中。在测试时使用int、std::string等简单类型开始。7.4 性能问题症状push_back大量数据时速度很慢。根因频繁扩容。每次扩容都需要分配新内存和拷贝所有旧元素时间复杂度是O(N)。优化如果事先知道大概要存多少元素使用reserve预分配空间可以避免多次扩容。考虑使用更高效的搬运方式。在C11后如果元素类型有移动构造函数且标记为noexcept在扩容时可以使用std::move来移动而非拷贝元素效率更高。这需要在reserve的实现中增加对std::is_nothrow_move_constructible的类型判断。完成这个“手撕vector”的项目后你收获的不仅仅是一个可以运行的容器类。你深入理解了动态数组的内存管理、RAII、异常安全、深浅拷贝、迭代器抽象、模板编程等C核心概念。下次当你再使用std::vector时你会对它的每一个行为都有一种“了然于胸”的感觉。这才是练习的真正目的——不是重复造轮子而是通过造轮子来理解汽车是如何跑起来的。
C++ STL vector模拟实现：从内存管理到迭代器失效的深度解析
1. 项目概述为什么我们要“手撕”vector如果你正在学习C尤其是学到STL标准模板库这一块那么“模拟实现vector”几乎是一个绕不开的经典练习。这就像学武功要先扎马步学编程到一定深度就得去拆解这些基础又强大的“轮子”。vector作为STL中最常用、最核心的序列容器之一它那看似简单的push_back、pop_back背后隐藏着动态内存管理、迭代器抽象、异常安全、类型萃取等一系列C核心思想。网上的八股文可能会告诉你vector的扩容因子是1.5或2但如果不亲手实现一遍你很难真正理解为什么是这些数字以及在拷贝构造、赋值运算符重载时稍有不慎就会掉进哪些深坑。我当年第一次尝试自己写一个简易的vector时光是处理迭代器失效的问题就调试了大半天。市面上很多教程和面试题都停留在表面只讲“是什么”不讲“为什么”和“怎么办”。这篇内容我就结合自己踩过的坑和多年使用C的经验带你从零开始构建一个功能完整、考虑周全的MyVector。我们不仅会实现增删改查更会深入探讨深拷贝与浅拷贝的陷阱、迭代器失效的根源与解决方案、利用RAII资源获取即初始化思想管理资源以及如何模拟STL的allocator空间配置器行为。目标是让你做完这个练习后不仅能应对面试中“请实现一个vector”这类问题更能深刻理解C面向对象和泛型编程的精髓写出更健壮、高效的代码。2. 整体设计与核心思路拆解在动手写代码之前我们必须先想清楚这个MyVector类应该长什么样以及它需要遵循哪些设计原则。一个合格的vector模拟实现绝不是简单封装一个动态数组它需要体现C的几大核心特性。2.1 类的骨架与数据成员首先vector是一个模板类这意味着它需要能容纳任意类型的元素。因此我们的类声明应该是这样的templatetypename T class MyVector { public: // 各种成员函数声明... private: T* _start; // 指向数组首元素的指针 T* _finish; // 指向最后一个有效元素的下一个位置 T* _end_of_storage; // 指向分配的内存空间末尾的下一个位置 };这三个指针是vector实现的核心它们清晰地划分了三个关键区域_start到_finish: 当前已使用的、存储有效元素的空间。_finish到_end_of_storage: 当前已分配但尚未使用的预留空间capacity。_end_of_storage之后: 未分配的内存。使用三个指针而非“起始指针大小容量”三个整数是为了与STL的迭代器设计保持兼容。_start和_finish天然就是迭代器原生指针begin()和end()函数可以直接返回它们。2.2 关键设计原则RAII资源获取即初始化这是C管理资源的黄金法则。我们的类需要在构造函数中获取资源内存在析构函数中释放资源。确保任何情况下包括发生异常资源都不会泄漏。异常安全在可能抛出异常的操作如内存分配、元素构造中要保证操作的原子性。例如在push_back时如果扩容失败vector应该保持原有状态不变。深拷贝这是模拟实现中最容易出错的地方。拷贝构造函数和赋值运算符必须进行深拷贝即复制内容而非指针。否则两个vector会共享同一块内存一个被析构后另一个就成了“悬空指针”导致未定义行为。迭代器失效规则我们需要模拟STL vector的迭代器失效行为。简单来说任何可能引起内存重新分配的操作如insert导致扩容、erase导致元素移动都会使指向该vector的所有迭代器、引用和指针失效。我们的实现必须明确这一点。3. 基础架构与资源管理实现有了清晰的设计图我们就可以开始搭建基础了。这部分是vector的“地基”如果没打好后面的所有功能都会摇摇欲坠。3.1 构造函数、析构函数与基本接口我们先实现最基础的几个函数让MyVector对象能够被创建、销毁并查看其状态。templatetypename T class MyVector { public: // 默认构造函数 MyVector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {} // 带初始大小和值的构造函数 MyVector(size_t n, const T value T()) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { reserve(n); // 先分配足够空间 for (size_t i 0; i n; i) { push_back(value); // 在已分配的空间上构造对象 } } // 析构函数 - RAII的核心 ~MyVector() { if (_start) { // 1. 析构已构造的对象 for (T* p _start; p ! _finish; p) { p-~T(); // 显式调用析构函数 } // 2. 释放内存 delete[] reinterpret_castchar*(_start); _start _finish _end_of_storage nullptr; } } // 迭代器 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } // 容量相关 size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start _finish; } private: T* _start; T* _finish; T* _end_of_storage; };注意在析构函数中我们做了两件事先调用每个有效元素的析构函数再释放内存。这是因为我们使用new[]分配的是“原始内存”对于非平凡类型如含有动态成员的类直接delete[]指针可能导致其内部资源泄漏。先析构对象是更安全的做法。当然更现代、更推荐的做法是使用std::allocator但为了理解原理我们先从最底层的方式开始。3.2 内存管理核心reserve与resizereserve和resize是vector动态能力的体现也是很多问题的源头。reserve(n)确保vector的容量至少为n。如果当前容量小于n则重新分配一块更大的内存并将原有元素移动或拷贝到新内存。void reserve(size_t n) { if (n capacity()) { size_t old_size size(); // 1. 分配新内存 T* new_start reinterpret_castT*(new char[n * sizeof(T)]); // 分配原始字节 // 2. 搬运数据考虑异常安全 // 如果T的拷贝构造函数可能抛出异常我们需要保证旧数据不被破坏 T* new_finish new_start; try { for (size_t i 0; i old_size; i) { // 使用“定位new”在指定内存地址构造对象 new (new_finish) T(_start[i]); // 拷贝构造 new_finish; } } catch (...) { // 如果构造过程中发生异常需要析构已构造的新对象并释放新内存 while (new_finish ! new_start) { (--new_finish)-~T(); } delete[] reinterpret_castchar*(new_start); throw; // 重新抛出异常 } // 3. 释放旧内存先析构旧对象 for (T* p _start; p ! _finish; p) { p-~T(); } delete[] reinterpret_castchar*(_start); // 4. 更新指针 _start new_start; _finish new_finish; _end_of_storage _start n; } }实操心得这里的异常处理是关键。如果在搬运数据第2步时发生异常我们必须确保已经构造的新对象被正确析构新内存被释放同时旧数据保持完好。这就是“强异常安全保证”操作要么成功要么像什么都没发生过。在实际项目中我们通常会使用std::uninitialized_copy等标准库算法来简化这部分逻辑它们内部已经处理好了异常安全。resize(n, value T())改变vector的size。如果n size()则在末尾添加元素如果n size()则删除末尾的元素。void resize(size_t n, const T value T()) { if (n size()) { // 需要扩容 if (n capacity()) { reserve(n); // 扩容 } // 在[_finish, _startn)区间构造新元素 for (T* p _finish; p ! _start n; p) { new (p) T(value); // 定位new构造 } _finish _start n; } else { // 需要缩容析构多余元素 for (T* p _start n; p ! _finish; p) { p-~T(); } _finish _start n; // 注意这里只析构对象不释放内存capacity不变 } }4. 增删改查操作与迭代器失效基础打好后我们就可以实现vector最常用的功能了添加、删除、访问元素。这部分是使用频率最高的也是迭代器失效问题的重灾区。4.1 push_back 与 pop_backpush_back是vector的招牌函数它的实现直接关系到性能和安全性。void push_back(const T value) { // 检查是否需要扩容 if (_finish _end_of_storage) { // 计算新容量常见的策略是翻倍避免频繁扩容 size_t new_capacity capacity() 0 ? 4 : capacity() * 2; reserve(new_capacity); } // 在_finish位置构造新元素 new (_finish) T(value); // 拷贝构造 _finish; }为什么扩容因子常用2这是一个时间与空间的权衡。因子太小如1.5会导致频繁扩容每次扩容后拷贝原有元素的成本摊还下来较高。因子太大又会浪费内存。2是一个在多数场景下取得较好平衡的经验值。一些实现如MSVC使用1.5能更好地利用之前释放的内存块。pop_back相对简单但要注意对空vector的操作。void pop_back() { if (!empty()) { --_finish; _finish-~T(); // 析构最后一个元素 } // 如果vector为空什么也不做或者可以抛出异常但STL未定义 }4.2 insert 与 erase迭代器失效的根源insert和erase是导致迭代器失效的典型操作因为它们可能引起元素的移动和内存的重新分配。insert(iterator pos, const T value): 在指定位置前插入一个元素。iterator insert(iterator pos, const T value) { // 检查pos是否在有效范围内 [begin(), end()] assert(pos begin() pos end()); // 1. 检查扩容扩容会导致所有迭代器失效 if (_finish _end_of_storage) { // 扩容前计算pos的相对位置因为扩容后_start会变 size_t len pos - _start; size_t new_capacity capacity() 0 ? 4 : capacity() * 2; reserve(new_capacity); // 扩容后pos需要更新到新内存的对应位置 pos _start len; } // 2. 从后往前移动元素为插入腾出位置 iterator end _finish; while (end pos) { *end *(end - 1); // 赋值操作如果T的赋值运算符有异常...复杂暂不考虑 --end; } // 3. 在pos位置构造新元素 *pos value; // 这里也是赋值更严谨的做法是用构造但涉及已存在内存的构造/赋值情况复杂 _finish; // 4. 返回指向新插入元素的迭代器 return pos; }重要警告上面的实现为了清晰使用了简单的赋值。但在实际中如果T的赋值运算符可能抛出异常这个操作就不满足“强异常安全保证”。更严谨的做法是先将插入点之后的元素移动到新位置如果T有移动语义且noexcept或者使用更复杂的“旋转”算法。这也是为什么STL的实现如此复杂的原因之一。erase(iterator pos): 删除指定位置的元素。iterator erase(iterator pos) { assert(pos begin() pos end()); // pos不能是end() // 从pos1开始将元素前移一位 iterator it pos 1; while (it ! _finish) { *(it - 1) *it; // 同样存在异常安全问题 it; } --_finish; // 析构最后一个位置现在是多余的空位的对象 _finish-~T(); // 返回被删除元素之后的位置 return pos; }迭代器失效总结表操作是否导致迭代器失效失效范围原因push_back可能所有迭代器、指针、引用如果触发reserve重新分配内存则全部失效。否则只有end()失效。pop_back是end()及其之前的迭代器可能失效最后一个元素被析构指向它的迭代器/引用失效。insert可能所有迭代器、指针、引用如果触发扩容则全部失效。否则插入位置及之后的迭代器失效。erase是被删除元素及之后的所有迭代器、指针、引用元素前移后面的迭代器指向的元素位置变了。reserve是所有迭代器、指针、引用内存地址改变。resize(增大)可能同push_back可能触发扩容。resize(缩小)是被删除元素及其之后的迭代器、引用同erase。避坑技巧一个非常实用的习惯是在调用可能使迭代器失效的函数后立即更新你的迭代器或者避免在循环中直接使用旧的迭代器。例如for (auto it vec.begin(); it ! vec.end(); /* 这里不递增 */) { if (*it value_to_remove) { it vec.erase(it); // erase返回新的有效迭代器 } else { it; } }4.3 访问操作operator[] 与 at提供像数组一样的随机访问是vector的一大优势。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 at(size_t pos) { if (pos size()) { throw std::out_of_range(MyVector::at - pos out of range); } return _start[pos]; } const T at(size_t pos) const { if (pos size()) { throw std::out_of_range(MyVector::at - pos out of range); } return _start[pos]; }operator[]和at的主要区别在于边界检查。operator[]通常不检查或只在调试模式检查追求速度at()会进行严格的检查并在越界时抛出std::out_of_range异常更安全。5. 深拷贝与赋值运算符避免“双胞胎”的灾难这是模拟实现中最经典的陷阱。默认的拷贝构造函数和赋值运算符是“浅拷贝”只复制指针导致两个对象共享同一块内存。我们需要实现“深拷贝”。5.1 拷贝构造函数// 拷贝构造函数 MyVector(const MyVectorT other) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { // 先分配足够大的空间 reserve(other.capacity()); // 然后拷贝构造每一个元素 for (const auto e : other) { push_back(e); // 这里会调用T的拷贝构造函数 } }5.2 赋值运算符重载现代写法传统的写法是先检查自赋值然后释放旧内存再分配新内存并拷贝。这里介绍一种更安全、更清晰的“拷贝-交换”惯用法。MyVectorT operator(MyVectorT other) { // 注意参数是值传递会调用拷贝构造函数 swap(other); // 交换当前对象和临时对象other的内容 return *this; } // 函数结束临时对象other被析构释放掉旧的资源这个实现妙在哪里参数other是值传递它本身就是other的一个副本深拷贝完成。我们只需交换this和other的内部指针。交换操作是O(1)的且不会抛出异常。函数返回时临时对象other被析构它现在持有的是this原来的资源被安全释放。它天然就正确处理了自赋值v v的情况因为传参时已经创建了副本。当然我们需要实现一个swap成员函数void swap(MyVectorT other) noexcept { std::swap(_start, other._start); std::swap(_finish, other._finish); std::swap(_end_of_storage, other._end_of_storage); }6. 完善与优化从“能用”到“好用”一个基础的MyVector已经完成了。但要让它更接近标准库的vector我们还需要考虑一些细节和优化。6.1 完善构造函数支持迭代器范围初始化STL的vector可以用另一个容器的迭代器范围来初始化这非常方便。templatetypename InputIterator MyVector(InputIterator first, InputIterator last) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { // 遍历迭代器范围逐个插入 while (first ! last) { push_back(*first); first; } }6.2 实现移动语义C11及以上移动构造函数和移动赋值运算符可以避免不必要的深拷贝大幅提升性能。// 移动构造函数 MyVector(MyVectorT other) noexcept : _start(other._start), _finish(other._finish), _end_of_storage(other._end_of_storage) { // 将源对象置于有效但可析构的状态空状态 other._start other._finish other._end_of_storage nullptr; } // 移动赋值运算符 MyVectorT operator(MyVectorT other) noexcept { if (this ! other) { // 释放当前资源 this-~MyVector(); // 接管资源 _start other._start; _finish other._finish; _end_of_storage other._end_of_storage; // 置空源对象 other._start other._finish other._end_of_storage nullptr; } return *this; }6.3 使用allocator空间配置器我们之前一直用new char[]和delete[]来分配原始内存。标准库的vector使用了一个叫allocator的模板参数来分离内存分配和对象构造的逻辑。这是更灵活、更专业的设计。templatetypename T, typename Alloc std::allocatorT class MyVectorWithAlloc { // ... 使用Alloc来allocate/deallocate内存construct/destroy对象 };实现allocator版本是一个更高级的练习它要求你理解std::allocator_traits并妥善处理对齐等问题。这能让你对STL的内存管理机制有更深的认识。7. 常见问题与调试技巧实录在实现和测试这个MyVector的过程中你几乎一定会遇到下面这些问题。这里我把它们和解决方法记录下来。7.1 内存泄漏与双重释放症状程序运行一段时间后内存占用不断增长或在析构时崩溃double free or corruption。根因构造函数中分配内存失败但未将指针置空如果reserve在分配内存后、构造元素前抛出异常构造函数退出但_start等指针可能已被赋值非nullptr。析构函数会对一个无效指针调用delete[]。拷贝/赋值未实现深拷贝两个对象共享内存一个析构后另一个的指针就悬空了。移动操作后源对象仍持有资源移动后没有将源对象的指针置空导致源对象析构时释放了已被移动的资源。排查使用Valgrind、AddressSanitizer等内存检查工具。它们能精准定位内存泄漏和非法访问的位置。解决遵循RAII在构造函数初始化列表中就将所有指针初始化为nullptr。在释放内存后立即将指针置为nullptr。确保拷贝操作是深拷贝。在移动操作中转移资源后务必置空源对象指针。7.2 迭代器失效导致的崩溃或逻辑错误症状在循环中插入或删除元素后程序崩溃或输出结果不符合预期。根因使用了因insert、erase、push_back可能扩容而失效的迭代器。示例MyVectorint vec {1, 2, 3, 4, 5}; for (auto it vec.begin(); it ! vec.end(); it) { if (*it % 2 0) { vec.erase(it); // 错误erase后it失效后续的it行为未定义 } }解决使用erase的返回值更新迭代器如4.2节所述。7.3 模板编译错误症状编译器报出一大堆看不懂的错误指向模板内部。常见原因类型不支持你尝试对没有默认构造函数、拷贝构造函数或赋值运算符的类型使用MyVector。链接错误模板类的成员函数定义在.cpp文件中。模板的定义必须放在头文件里因为编译器需要在实例化模板时看到完整的定义。解决确保你的MyVector类及其所有成员函数的定义都在一个.hpp或.h头文件中。在测试时使用int、std::string等简单类型开始。7.4 性能问题症状push_back大量数据时速度很慢。根因频繁扩容。每次扩容都需要分配新内存和拷贝所有旧元素时间复杂度是O(N)。优化如果事先知道大概要存多少元素使用reserve预分配空间可以避免多次扩容。考虑使用更高效的搬运方式。在C11后如果元素类型有移动构造函数且标记为noexcept在扩容时可以使用std::move来移动而非拷贝元素效率更高。这需要在reserve的实现中增加对std::is_nothrow_move_constructible的类型判断。完成这个“手撕vector”的项目后你收获的不仅仅是一个可以运行的容器类。你深入理解了动态数组的内存管理、RAII、异常安全、深浅拷贝、迭代器抽象、模板编程等C核心概念。下次当你再使用std::vector时你会对它的每一个行为都有一种“了然于胸”的感觉。这才是练习的真正目的——不是重复造轮子而是通过造轮子来理解汽车是如何跑起来的。
