1. 项目概述为什么我们要手撕 vector如果你写过 C那std::vector绝对是你最熟悉的老朋友。它几乎是所有现代 C 项目的基石从存储一堆整数到管理复杂的对象无处不在。但很多时候我们只是把它当做一个“会自动变长的数组”来用push_back、pop_back、[]操作用得不亦乐乎。直到某一天面试官问你“vector 的底层是怎么实现的它的迭代器失效有哪些情况能自己写一个吗” 或者你在处理高性能计算时发现std::vector的某些行为比如扩容策略成了性能瓶颈你才猛然意识到对这个朝夕相处的伙伴了解得还远远不够。这个项目就是要彻底揭开std::vector的神秘面纱。我们不满足于仅仅使用它而是要深入其最核心的“三指针模型”并亲手从零开始实现一个功能完整的Vector类。这不仅仅是为了应付面试更是为了真正理解动态数组这一数据结构的精髓掌握内存管理的艺术以及培养写出工业级健壮代码的能力。当你能够自己实现一个vector时你对 C 中 RAII、异常安全、迭代器、模板、内存分配器等核心概念的理解将会达到一个全新的层次。2. 核心原理三指针模型与动态数组的奥秘std::vector的底层并非魔法它本质上是一段动态分配的、连续的线性内存空间。标准库的实现如 GCC 的 libstdc 或 Clang 的 libc通常使用三个指针来高效地管理这片内存。理解这三个指针就抓住了 vector 的命脉。2.1 三指针模型详解想象你有一块地皮堆内存用来盖房子存储元素。你需要知道这块地的信息。_M_start或_begin指向已分配内存块的起始位置。这是你地皮的“门牌号”是所有元素的“家”的起点。它永远指向那块内存的首地址除非整个 vector 被移动或重新分配swap或移动构造。_M_finish或_end指向最后一个有效元素的下一个位置。它标记了当前已经“住人”的区域边界。size()函数返回的值本质上就是_M_finish - _M_start。当你push_back一个元素时就是在_M_finish指向的位置构造新元素然后让_M_finish向后移动一位。_M_end_of_storage或_end_cap指向已分配内存块的末尾最后一个可用位置的下一个位置。它标记了你这块地皮的“边界围墙”。capacity()函数返回的值就是_M_end_of_storage - _M_start。这个指针决定了当前内存还能容纳多少元素无需重新申请土地。这三个指针的关系可以用一个简单的图示来理解低地址 高地址 [_M_start] - | 已用元素1 | 已用元素2 | ... | 已用元素N | 空闲空间 | ... | - [_M_end_of_storage] ^ [_M_finish][_M_start, _M_finish) 是有效元素区间对应begin()到end()。[_M_finish, _M_end_of_storage) 是预分配但尚未使用的空闲容量capacity。[_M_start, _M_end_of_storage) 是整个已分配的内存区间。注意 这里使用的是常见的内部命名如 libstdc 的风格。不同的标准库实现可能命名略有不同例如 MSVC STL 可能用_Myfirst_Mylast_Myend但思想完全一致。我们自己的实现可以选用更清晰的名称如m_datam_sizem_capacity但本质上还是管理着起始、大小、容量这三个核心信息。2.2 动态扩容策略摊还分析下的智慧当_M_finish _M_end_of_storage时意味着空闲容量用完了下一次push_back就必须扩容。std::vector采用的是一种指数扩容策略通常但不保证是增长为原来的 2 倍GCC或 1.5 倍MSVC。为什么是指数增长而不是固定大小增长假设每次扩容只增加固定大小如 10 个元素。那么插入 N 个元素的总时间成本将与 N² 成正比因为需要频繁地重新分配和拷贝。而采用指数扩容比如 2 倍虽然单次扩容的成本可能很高需要分配新内存并移动所有现有元素但摊还分析表明执行 N 次push_back操作的平均时间复杂度是 O(1)。简单来说昂贵的扩容操作发生的频率会随着元素增多而指数级降低均摊到每次插入操作上的成本就很小了。手写实现时的选择 我们通常选择 2 倍扩容因为它实现简单且在大多数现代内存分配器下表现良好。1.5 倍增长黄金比例相关有时被认为能更好地利用之前释放的内存块但对于我们自己实现的教学版本2 倍是更直观的选择。2.3 迭代器本质与失效问题vector的迭代器通常就是原生指针的别名typedef T* iterator。因为内存是连续的begin()返回_M_startend()返回_M_finish操作就是指针的。迭代器失效是 vector 使用中最常见的坑根本原因在于内存的重新分配。插入操作insert,push_back 如果导致扩容所有迭代器、指针、引用都会失效因为元素被搬到了全新的内存地址。即使未扩容在插入点之后的迭代器、指针、引用也会失效因为元素被向后移动了。删除操作erase,pop_back 被删除元素及其之后的所有迭代器、指针、引用都会失效。swap操作 两个 vector 的内容交换迭代器、指针、引用会交换归属指向另一个容器的内容。实操心得 在循环中修改 vector尤其是插入/删除时要格外小心。一个常见的技巧是使用索引而非迭代器进行遍历和修改或者使用while循环并谨慎更新迭代器位置。例如删除所有偶数// 方法1使用索引安全 for (size_t i 0; i vec.size(); ) { if (vec[i] % 2 0) { vec.erase(vec.begin() i); } else { i; } } // 方法2使用迭代器和 erase 返回值正确用法 for (auto it vec.begin(); it ! vec.end(); ) { if (*it % 2 0) { it vec.erase(it); // erase 返回被删除元素之后元素的新迭代器 } else { it; } }3. 手写 Vector 类设计与基础框架现在我们开始动手实现自己的Vector类。我们将遵循 RAII 原则并尽可能模拟std::vector的接口和行为。3.1 类模板定义与成员变量首先我们的Vector必须是一个模板类以支持存储任意类型。三个核心成员变量直接对应三指针模型。#ifndef MY_VECTOR_H #define MY_VECTOR_H #include cstddef // for size_t, ptrdiff_t #include algorithm // for std::swap, std::copy, etc. #include initializer_list #include stdexcept // for std::out_of_range namespace my { template typename T class Vector { public: // 类型别名 (仿照 STL) using value_type T; using size_type std::size_t; using difference_type std::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 m_data nullptr; // 对应 _M_start 分配内存的起始地址 size_type m_size 0; // 当前元素数量 可以通过 m_finish - m_data 计算但存储它更方便 size_type m_capacity 0; // 当前分配的内存容量元素个数 // 辅助函数重新分配内存 void reallocate(size_type new_capacity); public: // 构造函数、析构函数、成员函数将在后续实现... }; } // namespace my #endif // MY_VECTOR_H我们选择存储m_size和m_capacity而不是两个指针因为size()和capacity()是高频调用函数直接返回成员变量比指针相减更高效。m_data就是我们的“起始指针”。3.2 构造函数与析构函数RAII构造函数需要处理多种情况默认构造、指定大小构造、指定大小和初始值构造、拷贝构造、移动构造、初始化列表构造等。析构函数则负责释放资源。public: // 默认构造函数 Vector() noexcept default; // 指定大小和初始值 explicit Vector(size_type count, const T value T()) { if (count 0) { m_data static_castpointer(::operator new(count * sizeof(T))); // 分配原始内存 m_capacity count; // 在分配的内存上构造对象 for (m_size 0; m_size count; m_size) { new (m_data m_size) T(value); // placement new } } } // 拷贝构造函数深拷贝 Vector(const Vector other) { if (other.m_size 0) { m_data static_castpointer(::operator new(other.m_size * sizeof(T))); m_capacity other.m_size; for (m_size 0; m_size other.m_size; m_size) { new (m_data m_size) T(other.m_data[m_size]); // 拷贝构造每个元素 } } } // 移动构造函数C11 Vector(Vector other) noexcept : m_data(other.m_data), m_size(other.m_size), m_capacity(other.m_capacity) { other.m_data nullptr; other.m_size 0; other.m_capacity 0; } // 初始化列表构造函数 (C11) Vector(std::initializer_listT init) { if (init.size() 0) { m_data static_castpointer(::operator new(init.size() * sizeof(T))); m_capacity init.size(); for (const auto elem : init) { new (m_data m_size) T(elem); m_size; } } } // 析构函数 ~Vector() { clear(); // 先析构所有对象 ::operator delete(m_data); // 释放原始内存 }这里有几个关键点内存分配 我们使用::operator new分配原始、未初始化的内存而不是new T[]。因为new T[]会同时分配内存并调用每个元素的默认构造函数这对于像int这样的 POD 类型没问题但对于非默认构造的类型或者当我们想用placement new精确控制构造过程时::operator new更底层、更灵活。对象构造 在分配好的原始内存上我们使用placement new来构造对象。new (address) T(args...)在指定的address调用T的构造函数。这实现了内存分配与对象构造的分离是 STL 容器的标准做法。拷贝构造 必须进行深拷贝为每个元素调用拷贝构造函数而不是简单地进行内存拷贝memcpy。这对于管理自身资源的类如std::string至关重要。移动构造 直接“窃取”右值对象的资源并将其置为空状态高效且异常安全。析构顺序 先调用clear()后面会实现来析构所有已构造的对象然后再用::operator delete释放原始内存。绝不能反过来否则会导致在已释放的内存上调用析构函数引发未定义行为。3.3 基础容量相关函数这些函数实现起来相对直接因为它们只是返回成员变量或进行简单比较。public: // 容量相关 bool empty() const noexcept { return m_size 0; } size_type size() const noexcept { return m_size; } size_type capacity() const noexcept { return m_capacity; } // 预留容量确保至少能容纳 new_capacity 个元素 void reserve(size_type new_capacity) { if (new_capacity m_capacity) { reallocate(new_capacity); } } // 调整大小 void resize(size_type new_size, const T value T()) { if (new_size m_size) { // 增大如果容量不足则扩容然后填充新元素 if (new_size m_capacity) { reallocate(std::max(new_size, m_capacity * 2)); } for (size_type i m_size; i new_size; i) { new (m_data i) T(value); // 在新增位置构造元素 } } else if (new_size m_size) { // 减小析构多余的元素 for (size_type i new_size; i m_size; i) { (m_data i)-~T(); // 显式调用析构函数 } } m_size new_size; }reserve是性能优化的关键。如果你事先知道要存入大量元素提前reserve足够的空间可以避免多次扩容带来的性能损耗和数据拷贝。resize的逻辑需要仔细处理增大可能需要扩容然后在新增的位置上构造新元素用提供的value或默认值。减小需要手动析构那些不再属于容器的对象。注意这里只调用析构函数并不释放多余的内存capacity不变。这是std::vector的标准行为即shrink_to_fit不是强制的。4. 核心功能实现增删改查与迭代器有了基础框架我们来实现最核心的成员函数。4.1 元素访问与迭代器public: // 元素访问带边界检查 reference at(size_type pos) { if (pos m_size) { throw std::out_of_range(Vector::at - index out of range); } return m_data[pos]; } const_reference at(size_type pos) const { if (pos m_size) { throw std::out_of_range(Vector::at - index out of range); } return m_data[pos]; } // 元素访问不检查边界行为类似数组 reference operator[](size_type pos) noexcept { // 断言常用于调试模式发布模式可能被禁用 // assert(pos m_size); return m_data[pos]; } const_reference operator[](size_type pos) const noexcept { // assert(pos m_size); return m_data[pos]; } reference front() noexcept { return m_data[0]; } const_reference front() const noexcept { return m_data[0]; } reference back() noexcept { return m_data[m_size - 1]; } const_reference back() const noexcept { return m_data[m_size - 1]; } // 数据指针 pointer data() noexcept { return m_data; } const_pointer data() const noexcept { return m_data; } // 迭代器 iterator begin() noexcept { return m_data; } const_iterator begin() const noexcept { return m_data; } const_iterator cbegin() const noexcept { return m_data; } iterator end() noexcept { return m_data m_size; } const_iterator end() const noexcept { return m_data m_size; } const_iterator cend() const noexcept { return m_data m_size; }at()和operator[]的区别是 STL 的经典设计at()进行边界检查越界时抛出std::out_of_range异常operator[]不进行检查追求最大性能但要求使用者保证下标合法。迭代器就是简单的指针别名这使得我们的Vector与标准算法库完美兼容。4.2 插入与删除操作这是Vector实现中最需要小心处理异常安全性和迭代器失效问题的部分。public: // 在末尾添加元素 void push_back(const T value) { if (m_size m_capacity) { // 容量已满需要扩容。注意扩容会导致所有迭代器失效。 // 扩容因子为2但需处理初始容量为0的情况。 reallocate(m_capacity ? m_capacity * 2 : 1); } new (m_data m_size) T(value); // 在尾部构造新元素 m_size; } // 移动版本的 push_back (C11) void push_back(T value) { if (m_size m_capacity) { reallocate(m_capacity ? m_capacity * 2 : 1); } new (m_data m_size) T(std::move(value)); // 移动构造 m_size; } // 删除末尾元素 void pop_back() { if (m_size 0) { --m_size; (m_data m_size)-~T(); // 析构最后一个元素 } } // 清空所有元素但不释放容量 void clear() noexcept { for (size_type i 0; i m_size; i) { (m_data i)-~T(); } m_size 0; } // 在指定位置插入元素 iterator insert(const_iterator pos, const T value) { // 计算插入点的索引 size_type index pos - begin(); if (index m_size) { // 允许在 end() 位置插入 throw std::out_of_range(Vector::insert - iterator out of range); } // 检查是否需要扩容 if (m_size m_capacity) { // 扩容注意扩容会重新分配内存使 pos 迭代器失效。 // 我们需要在扩容后重新计算插入位置。 size_type new_capacity m_capacity ? m_capacity * 2 : 1; pointer new_data static_castpointer(::operator new(new_capacity * sizeof(T))); // 1. 将 [begin(), pos) 的元素移动到新内存 for (size_type i 0; i index; i) { new (new_data i) T(std::move_if_noexcept(m_data[i])); } // 2. 在新位置构造新元素 new (new_data index) T(value); // 3. 将 [pos, end()) 的元素移动到新内存 for (size_type i index; i m_size; i) { new (new_data i 1) T(std::move_if_noexcept(m_data[i])); } // 4. 清理旧内存 for (size_type i 0; i m_size; i) { (m_data i)-~T(); } ::operator delete(m_data); // 5. 更新成员变量 m_data new_data; m_capacity new_capacity; m_size; return begin() index; } else { // 无需扩容在原有内存中操作 // 将插入点及之后的元素向后移动一位从后往前移动避免覆盖 for (size_type i m_size; i index; --i) { new (m_data i) T(std::move_if_noexcept(m_data[i - 1])); (m_data i - 1)-~T(); } // 在插入点构造新元素 new (m_data index) T(value); m_size; return begin() index; } } // 删除指定位置的元素 iterator erase(const_iterator pos) { if (pos begin() || pos end()) { throw std::out_of_range(Vector::erase - iterator out of range); } size_type index pos - begin(); // 析构待删除元素 (m_data index)-~T(); // 将后面的元素向前移动一位从前往后移动 for (size_type i index; i m_size - 1; i) { new (m_data i) T(std::move_if_noexcept(m_data[i 1])); (m_data i 1)-~T(); } --m_size; return begin() index; // 返回被删除元素之后的位置 }push_back相对简单核心逻辑是“检查容量 - 构造元素 - 更新大小”。insert和erase则复杂得多insert 需要考虑是否扩容。如果扩容整个内存地址都变了传入的pos迭代器会失效必须根据索引index在新内存中重新定位插入点。我们使用了std::move_if_noexcept这是一个 C11 的优化它会在移动构造函数声明为noexcept时优先使用移动更高效否则使用拷贝保证强异常安全。元素移动的顺序至关重要必须确保不会覆盖尚未被移动的原始数据。erase 需要先析构目标元素然后将后面的元素前移覆盖。注意移动元素后原最后一个元素的位置m_data[m_size-1]仍然有一个已移动的对象需要调用析构函数清理。注意事项 我们实现的insert和erase是简化版本标准库的版本通常有多个重载如插入多个元素、插入迭代器范围等并且异常安全保证更严密。我们的版本旨在阐明核心流程。在实际使用中频繁在 vector 中间插入/删除元素是低效的O(n) 复杂度如果这种操作很多应考虑使用std::list或std::deque。4.3 重新分配内存的辅助函数reallocate这是Vector内存管理的核心引擎被reserve、push_back扩容时、insert扩容时等函数调用。private: void reallocate(size_type new_capacity) { // 1. 分配新的原始内存块 pointer new_data static_castpointer(::operator new(new_capacity * sizeof(T))); // 2. 将旧数据移动或拷贝到新内存尝试移动失败则拷贝 for (size_type i 0; i m_size; i) { try { // 使用移动构造如果移动构造函数是 noexcept 的否则使用拷贝构造 new (new_data i) T(std::move_if_noexcept(m_data[i])); } catch (...) { // 如果构造过程中发生异常需要析构已经成功构造的新元素并释放新内存 for (size_type j 0; j i; j) { (new_data j)-~T(); } ::operator delete(new_data); throw; // 重新抛出异常 } } // 3. 析构旧内存中的所有对象 for (size_type i 0; i m_size; i) { (m_data i)-~T(); } // 4. 释放旧内存 ::operator delete(m_data); // 5. 更新指针和容量 m_data new_data; m_capacity new_capacity; // m_size 保持不变 }reallocate函数必须保证强异常安全性即如果操作因异常失败容器应保持原有状态不变。我们通过“先构造新再销毁旧”的顺序并在新内存构造失败时进行清理来做到这一点。std::move_if_noexcept在这里再次发挥了关键作用它确保了在可能抛出异常的移动操作中我们回退到更安全的拷贝操作从而在扩容失败时原始数据不会被破坏。5. 赋值操作符、交换与非成员函数为了完善我们的Vector类还需要实现拷贝赋值、移动赋值运算符以及swap函数。5.1 拷贝赋值与移动赋值public: // 拷贝赋值运算符copy-and-swap 惯用法 Vector operator(const Vector other) { if (this ! other) { Vector temp(other); // 拷贝构造一个临时副本 swap(temp); // 交换当前对象和副本的内容 } // 临时对象 temp 离开作用域析构旧资源 return *this; } // 移动赋值运算符 Vector operator(Vector other) noexcept { if (this ! other) { clear(); ::operator delete(m_data); // 释放当前资源 m_data other.m_data; m_size other.m_size; m_capacity other.m_capacity; other.m_data nullptr; other.m_size 0; other.m_capacity 0; } return *this; }拷贝赋值运算符采用了copy-and-swap惯用法。它先通过拷贝构造创建一个临时对象temp这可能会抛异常然后与*this交换。交换操作通常是noexcept的。最后临时对象temp现在持有*this的旧内容在作用域结束时被析构。这种方法自动提供了强异常安全保证并且代码简洁。移动赋值则直接接管右值对象的资源。5.2 交换函数swap函数对于很多 STL 算法和操作至关重要它应该是高效且noexcept的。public: void swap(Vector other) noexcept { using std::swap; swap(m_data, other.m_data); swap(m_size, other.m_size); swap(m_capacity, other.m_capacity); } }; // 非成员函数 swap 用于支持 ADL 和 std::swap template typename T void swap(VectorT lhs, VectorT rhs) noexcept { lhs.swap(rhs); }成员函数swap简单地交换三个成员变量成本极低。我们还提供了非成员函数版本的swap这是 STL 容器的常见做法使得std::swap能通过 ADL参数依赖查找找到我们这个更高效的专用版本。6. 测试、常见问题与性能考量实现完成后必须进行全面的测试。6.1 基础功能测试编写测试代码验证构造、析构、增删改查、迭代器等基本功能。#include iostream #include cassert #include my_vector.h // 我们实现的 Vector int main() { my::Vectorint vec1; // 默认构造 assert(vec1.empty()); assert(vec1.size() 0); my::Vectorint vec2(5, 42); // 填充构造 assert(vec2.size() 5); assert(vec2[0] 42 vec2[4] 42); vec2.push_back(100); assert(vec2.size() 6); assert(vec2.back() 100); my::Vectorint vec3 vec2; // 拷贝构造 assert(vec3.size() vec2.size()); assert(vec3[5] 100); vec3.pop_back(); assert(vec3.size() 5); assert(vec3.back() 42); // 现在最后一个元素是42 auto it vec3.begin() 2; vec3.insert(it, 999); assert(vec3.size() 6); assert(vec3[2] 999); assert(vec3[3] 42); // 原位置元素后移 it vec3.erase(vec3.begin() 1); // 删除索引1的元素 assert(*it 42); // it 应指向原索引2的元素现在是42 assert(vec3.size() 5); // 测试迭代器范围 for 循环 for (const auto num : vec3) { std::cout num ; } std::cout \n; // 测试异常安全例如 at 函数 try { vec3.at(100); } catch (const std::out_of_range e) { std::cout Caught exception: e.what() \n; } std::cout All basic tests passed!\n; return 0; }6.2 内存与异常安全测试更深入的测试需要检查内存泄漏和异常安全。可以使用工具如 Valgrind 或 AddressSanitizer。// 测试包含动态内存的类 class TestObj { public: int* data; TestObj(int val) : data(new int(val)) {} ~TestObj() { delete data; } // 必须定义拷贝构造和拷贝赋值遵循三五法则 TestObj(const TestObj other) : data(new int(*other.data)) {} TestObj operator(const TestObj other) { if (this ! other) { delete data; data new int(*other.data); } return *this; } // 移动操作 TestObj(TestObj other) noexcept : data(other.data) { other.data nullptr; } TestObj operator(TestObj other) noexcept { if (this ! other) { delete data; data other.data; other.data nullptr; } return *this; } }; void test_with_complex_type() { my::VectorTestObj vec; vec.reserve(10); for (int i 0; i 10; i) { vec.push_back(TestObj(i)); // 测试拷贝/移动 } // vec 离开作用域应正确调用 10 次 TestObj 的析构函数无内存泄漏 }运行这个测试并用内存检测工具检查确保没有内存泄漏。特别是要验证在push_back导致扩容时旧的TestObj被正确析构其内部的int*被正确delete。6.3 常见问题与避坑指南迭代器失效 这是我们实现和使用Vector时最需要警惕的。任何可能引起内存重新分配的操作如insert、push_back导致扩容都会使所有迭代器、指针、引用失效。在循环中修改容器时务必使用erase返回的新迭代器或者改用索引。异常安全 我们的reallocate和insert实现了基本保证。但在更复杂的场景下比如元素的构造函数可能抛出异常需要更精细的控制。工业级实现会使用std::uninitialized_copy、std::uninitialized_move等算法并利用 RAII 包装器来管理临时资源。移动语义优化 我们使用了std::move_if_noexcept这是一个重要的优化。确保你存储的类类型定义了正确的移动构造函数和移动赋值运算符并尽可能将它们标记为noexcept这样vector在扩容时才能高效地移动元素而非拷贝。shrink_to_fit 标准库的vector有shrink_to_fit请求减少capacity以适应size但这是一个非强制性的请求。我们自己实现时可以添加一个类似的函数其内部实现就是reallocate(m_size)但需要注意这可能导致一次内存分配和元素移动。与std::vector的差异 我们的实现是教学性质的省略了很多边缘情况和优化比如分配器Allocator支持标准vector的第二个模板参数是分配器允许自定义内存分配策略。更完善的迭代器类型如reverse_iterator。emplace_back/emplace 直接原地构造避免临时对象拷贝。insert/erase的重载支持范围操作。max_size、get_allocator等成员函数。6.4 性能考量与优化建议预分配reserve 这是提升vector性能最有效的手段。在已知元素数量时提前reserve避免多次扩容。元素类型选择 对于小型、平凡的 POD 类型如intdoublevector效率极高。对于大型对象可以考虑存储指针如std::vectorstd::unique_ptrBigObj以减少扩容时的移动/拷贝成本但这会引入间接访问开销和内存碎片。移动语义 确保你的类支持移动语义这能让vector在扩容和重新分配时大幅提升性能。emplace_back优于push_back 在 C11 及以上emplace_back直接在容器尾部构造对象省去了创建临时对象的步骤更高效。我们的简化实现未包含emplace_back但其思想是在push_back中直接使用完美转发。通过这个从零手写Vector的过程我们不仅复现了一个核心容器更重要的是深入理解了 C 内存管理、对象生命周期、异常安全、模板编程和算法效率的方方面面。下次当你再使用std::vector时你看到的将不再是一个黑盒而是一个由三指针精巧掌控的动态数组你知道它的每一次push_back背后可能发生的扩容知道迭代器为何失效也知道如何写出与之高效、安全协作的代码。这才是深入底层带来的真正力量。