1. 项目概述为什么我们要“手撕”一个vector如果你正在学习C尤其是学到STL标准模板库这一块那么“vector”这个容器绝对是你绕不开的坎。它被称作“动态数组”是C中使用频率最高的容器之一。很多教程会教你如何使用push_back、size、operator[]这些接口这当然没错但如果你只停留在“会用”的层面那就像只学会了开车却不知道发动机是怎么工作的。一旦遇到迭代器失效、内存泄漏或者需要定制化容器行为时就会一头雾水。“手撕vector”或者说模拟实现一个简化版的vector类正是从“司机”进阶为“机械师”的关键一步。这不是为了造一个比标准库更好的轮子而是为了彻底理解这个轮子是怎么造出来的。通过自己从零开始一步步实现reserve、resize、insert、erase等核心功能你会对内存管理、迭代器本质、异常安全、深浅拷贝等C核心概念有刻骨铭心的理解。这个过程能帮你扫清很多面试中关于“vector底层原理”的八股文障碍更重要的是它能让你在以后使用任何容器时心里都更有底。这个项目特别适合已经了解vector基本用法但对它的内部机制感到好奇的新手。我们不会实现标准库那么复杂、全面的版本那涉及分配器、异常处理、类型萃取等高级主题而是聚焦于核心逻辑打造一个教学意义大于工程意义的MyVector。你将看到一个看似复杂的动态数组其骨架其实非常清晰。2. 核心设计思路与类框架搭建动手之前我们先想清楚一个vector最核心的东西是什么。本质上它就是一个能够动态管理内存的数组。因此我们的类需要三个最基础的成员变量来刻画这个状态。2.1 成员变量设计三根“顶梁柱”一个最简单的vector其内部可以仅由三个指针或与之等效的指针运算来定义_start: 指向动态开辟的数组空间的起始位置。_finish: 指向当前已存储的最后一个有效数据的下一个位置。_finish - _start就等于size()。_end_of_storage: 指向整个动态开辟空间末尾的下一个位置。_end_of_storage - _start就等于capacity()。为什么用指针而不用size_t类型的_size和_capacity指针方案在实现迭代器时会有巨大的优势因为vector的迭代器本质上就是原生指针T*。这样我们的begin()可以直接返回_startend()直接返回_finish完美契合。基于这个设计我们的类框架雏形就出来了namespace my { templateclass T class vector { public: // 后续将在这里添加各种类型别名和成员函数 typedef T* iterator; typedef const T* const_iterator; private: iterator _start nullptr; // 指向数据块开头 iterator _finish nullptr; // 指向有效数据的末尾 iterator _end_of_storage nullptr; // 指向存储空间的末尾 }; }这里我们使用了nullptr进行默认初始化这是一个好习惯。同时我们将迭代器类型定义为T*这简化了实现。注意我们使用了模板template这是为了能让我们的vector存储任意类型的数据就像标准库的std::vector一样。2.2 基础成员函数规划围绕这三个指针我们需要实现一系列功能来操作它们。我们可以将这些功能分为几大类构造与析构负责对象的“生”与“死”管理资源的获取与释放。容量相关查询和调整size与capacity核心是reserve和resize。元素访问像数组一样通过[]访问以及获取首尾元素。迭代器提供begin()和end()支持范围for循环。增删改查最核心的部分包括push_back、pop_back、insert、erase等这里也是迭代器失效问题的“重灾区”。运算符重载实现operator完成深拷贝。我们的实现顺序通常会从构造函数、析构函数和最简单的size()、capacity()开始搭建起一个基本可用的架子然后再去实现那些会引起内存变化和迭代器变动的复杂操作。3. 从构造到析构资源管理的生命线一个对象的生命始于构造函数终于析构函数。对于管理动态资源的类来说这两个函数必须正确配对否则就会导致内存泄漏。3.1 构造函数多种初始化方式标准库的vector提供了多种构造函数。我们实现其中最常用的几种。默认构造函数创建一个空的vector。这很简单我们的成员指针已经用nullptr初始化了所以直接留空即可或者写出来更清晰。vector() default; // C11使用编译器生成的默认构造函数带初始个数和值的构造函数vector(size_t n, const T val T())。这个非常实用比如你想创建一个有10个0的vector。vector(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); // 再利用push_back填充值 } }这里有一个新手极易踩的坑T()是调用类型T的默认构造函数。对于内置类型如intint()的结果是0。这就是为什么vector(10)会创建10个0。我们利用reserve一次性分配好内存避免push_back中多次扩容的开销。迭代器范围构造函数这是一个模板函数允许你用其他容器的[first, last)迭代器区间来初始化vector。这是STL“泛型”思想的体现。template class InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); // 解引用迭代器获取值 first; } }注意这个构造函数和上面的(n, val)构造函数在特定情况下会产生歧义。例如vector(10, 5)编译器会优先匹配(InputIterator, InputIterator)版本因为10和5都是int更匹配迭代器类型非模板函数优先级低于模板函数这里有个微妙的重载决议问题。实际上10会被当作迭代器去解引用导致编译错误或运行时错误。标准库通过复杂的SFINAE或标签分发来解决我们教学版可以简单提供另一个重载vector(int n, const T val T())。3.2 拷贝构造与深拷贝这是C类管理的重中之重。默认的拷贝构造函数浅拷贝只会复制指针的值导致两个vector对象指向同一块内存。当其中一个析构释放内存后另一个就成了“悬空指针”再次析构或访问会导致程序崩溃。我们必须实现深拷贝为新对象重新申请一块同样大小的内存并将原对象的数据逐个拷贝过去。vector(const vectorT v) : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { // 1. 申请新空间 _start new T[v.capacity()]; // 2. 拷贝数据 (这里不能用memcpy因为对于自定义类型可能需要调用拷贝构造函数) for (size_t i 0; i v.size(); i) { _start[i] v._start[i]; // 调用T的operator进行拷贝 } // 3. 更新指针 _finish _start v.size(); _end_of_storage _start v.capacity(); }关键点第2步的拷贝必须用循环赋值_start[i] v._start[i]而不是memcpy。memcpy是内存的二进制拷贝对于内置类型如int没问题但对于自定义类型如string、vector它只是拷贝了指针等浅层数据没有调用拷贝构造函数或赋值运算符会导致两个对象共享资源同样引发问题。这体现了C中“深拷贝”的真正含义。3.3 析构函数安全释放资源析构函数相对简单但至关重要。它的任务就是释放构造函数和后续操作中申请的所有资源。~vector() { if (_start) { // 检查是否为空避免对nullptr进行delete delete[] _start; // 释放数组注意是 delete[] _start _finish _end_of_storage nullptr; // 置空防止野指针 } }delete[]会调用数组中每个元素的析构函数对于自定义类型然后释放整块内存。最后将指针置空是一个良好的防御性编程习惯。4. 容量操作reserve与resize的玄机capacity容量和size大小是vector的两个核心概念。size是当前元素数量capacity是当前内存最多能容纳的元素数量。当size capacity时再添加元素就需要扩容。4.1 size()、capacity()与简单的reserve()获取大小和容量非常简单就是指针相减。size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start _finish; }reserve(size_t n)的功能是如果n大于当前capacity则重新分配一块能至少容纳n个元素的新内存否则什么都不做。void reserve(size_t n) { if (n capacity()) { // 1. 申请新空间 T* tmp new T[n]; // 2. 拷贝旧数据 size_t old_size size(); // 必须先保存旧的size因为后续_start会变 if (_start) { for (size_t i 0; i old_size; i) { tmp[i] _start[i]; // 依然是深拷贝赋值 } // 3. 释放旧空间 delete[] _start; } // 4. 更新指针 _start tmp; _finish _start old_size; // 使用保存的old_size _end_of_storage _start n; } // 如果 n capacity(), 标准库规定什么都不做不缩容 }踩坑记录在释放旧空间_start之前必须先把旧的size()保存下来old_size。因为一旦_start被delete_finish和_end_of_storage就成了指向已释放内存的野指针此时再计算size()即_finish - _start是未定义行为程序可能崩溃或得到错误值。4.2 resize()调整大小的双面手resize(size_t n, const T val T())的行为比reserve复杂如果n size()将元素数量减少到n多出的元素被销毁调用析构函数。如果size() n capacity()将元素数量增加到n新增的元素用val初始化。如果n capacity()先扩容容量至少到n再增加并初始化元素。void resize(size_t n, const T val T()) { if (n size()) { // 情况1缩容只需调整_finish指针 // 对于缩小的部分需要调用析构函数。由于我们存储的是T类型 // 当T是自定义类型时调整指针并不会自动调用析构。 // 一个简单的处理方式是让多出的元素被后续覆盖时自然析构或者显示调用析构较复杂。 // 教学版本通常简化处理仅移动指针。 _finish _start n; } else { // 情况2 3扩容或填充 if (n capacity()) { reserve(n); // reserve会处理扩容 } iterator it _finish; _finish _start n; // 更新_finish到目标位置 // 将[原_finish, 新_finish)区间用val填充 while (it ! _finish) { *it val; it; } } }注意我们简化版的resize在缩容时没有显式调用元素的析构函数。在标准库中这会是一个问题特别是对于管理资源的自定义类型。更严谨的做法是从_startn到原_finish的区间内显式调用每个元素的析构函数如通过allocator。但对于理解核心流程当前的简化是可以接受的。5. 元素访问与迭代器让数据“可读可写”5.1 像数组一样访问operator[]为了让我们的MyVector用起来像数组和标准库vector一样顺手我们需要重载operator[]。T operator[](size_t pos) { assert(pos size()); // 越界检查非常重要 return _start[pos]; } const T operator[](size_t pos) const { // const版本用于const对象 assert(pos size()); return _start[pos]; }assert是调试的好帮手它在发布版本定义NDEBUG宏中会被移除。我们还需要提供front()和back()的快速访问。T front() { assert(!empty()); return *_start; } T back() { assert(!empty()); return *(_finish - 1); } const T front() const { assert(!empty()); return *_start; } const T back() const { assert(!empty()); return *(_finish - 1); }5.2 迭代器兼容范围for循环由于我们将迭代器定义为T*实现起来非常简单。iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } const_iterator cbegin() const { return _start; } const_iterator cend() const { return _finish; }有了begin()和end()我们的MyVector就可以直接使用C11的范围for循环了这是语法糖底层就是调用这两个函数。my::vectorint v; for (auto e : v) { // 这里会调用 v.begin() 和 v.end() // 对e进行操作 }6. 增删操作核心中的核心失效问题的根源这是vector模拟实现最精彩也最易出错的部分涉及内存管理和迭代器失效。6.1 push_back与pop_back尾部的简单操作push_back的逻辑是如果空间不足_finish _end_of_storage就先扩容然后在_finish位置构造新元素最后_finish。void push_back(const T val) { if (_finish _end_of_storage) { // 扩容 size_t new_capacity capacity() 0 ? 4 : capacity() * 2; // 经典2倍扩容策略 reserve(new_capacity); } *_finish val; // 在_finish位置赋值 _finish; // 更新_finish指针 }pop_back则更简单只需确保非空然后_finish--。但要注意对于自定义类型被“弹出”的元素应该被析构。简化版我们只移动指针。void pop_back() { assert(!empty()); --_finish; // 严格来说这里应该调用 (_finish)-~T() 来析构对象。简化处理。 }6.2 insert与erase迭代器失效的“案发现场”insert(iterator pos, const T val)在指定位置pos前插入一个元素。这需要将pos之后的所有元素向后移动一位。iterator insert(iterator pos, const T val) { assert(pos _start pos _finish); // 检查pos合法性 // 1. 检查容量 if (_finish _end_of_storage) { // 扩容会导致_start地址改变原来的pos会失效 // 必须计算pos与_start的相对距离 size_t len pos - _start; size_t new_capacity capacity() 0 ? 4 : capacity() * 2; reserve(new_capacity); // 扩容后更新pos为新空间的正确位置 pos _start len; } // 2. 移动元素 [pos, _finish) 区间整体后移一位 iterator end _finish - 1; while (end pos) { *(end 1) *end; // 后一个位置 前一个位置 --end; } // 3. 在pos位置插入新元素 *pos val; // 4. 更新_finish _finish; // 5. 返回指向新插入元素的迭代器 return pos; }迭代器失效详解注意代码中注释的部分。如果发生扩容_start指向了新的内存块而传入的pos迭代器仍然指向旧的、已经被释放的内存地址它就成了一个“野指针”失效了。后续对pos的解引用和操作都是未定义行为。我们的解决方案是在扩容前计算pos相对于_start的偏移量len扩容后用新的_start加上这个偏移量得到在新内存空间中的正确位置并更新pos。这也是为什么标准库中insert的返回值指向新插入元素的迭代器非常重要调用者应该使用这个新的迭代器而不是之前保存的那个。erase(iterator pos)删除指定位置的元素需要将pos1之后的元素向前移动一位。iterator erase(iterator pos) { assert(pos _start pos _finish); // pos不能等于_finish // 1. 移动元素 [pos1, _finish) 区间整体前移一位 iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } // 2. 更新_finish --_finish; // 3. 返回指向被删除元素下一个位置的迭代器 return pos; }erase的失效问题对于vectorerase操作同样会导致迭代器失效但范围略有不同。被删除元素及其之后的所有迭代器、指针、引用都会失效。因为元素向前移动了原来pos1位置的元素跑到了pos后续所有元素的位置都变了。所以在循环中使用erase时必须使用它的返回值来更新迭代器而不是简单地it。// 错误写法it在erase后失效it行为未定义 for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) { v.erase(it); // it失效 } } // 正确写法使用erase的返回值更新it for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) { it v.erase(it); // it被更新为指向被删元素的下一个位置 } else { it; } }7. 赋值运算符重载现代C的写法我们需要重载operator来实现深拷贝。传统写法是“拷贝-交换”但这里介绍一种更现代、更安全的写法利用“传值”和“交换”。vectorT operator(vectorT v) { // 注意这里参数是传值会调用拷贝构造函数 swap(v); // 交换当前对象和临时对象v的资源 return *this; } // 需要实现一个swap成员函数 void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }这种写法的妙处在于参数v是实参的一个副本深拷贝来的。然后我们交换当前对象和这个副本的资源。函数结束时副本v现在持有当前对象原来的资源被析构自动释放旧内存。这个过程是异常安全的并且代码非常简洁。这就是所谓的“拷贝-交换”惯用法copy-and-swap idiom。8. 模拟实现中的常见“坑”与调试技巧自己动手实现一遍你会遇到各种编译错误和运行时错误。这里总结几个高频问题内存泄漏最可能发生在reserve和operator中。确保new和delete[]配对并且在重新分配内存前正确释放旧内存。使用ValgrindLinux或Visual Studio的内存诊断工具来检查。浅拷贝问题如果你在拷贝构造或赋值时用了memcpy或者默认的拷贝构造函数那么对于存储string或嵌套vector的vector一定会出问题。务必使用循环进行深拷贝。迭代器失效这是面试必问点。务必理解insert和erase在可能引起扩容和元素移动时如何使之前的迭代器失效。记住解决方案保存偏移量或使用返回值更新迭代器。越界访问在operator[]、front、back、insert、erase中一定要对输入位置进行合法性检查使用assert或抛出异常。类型萃取与模板编程我们的简化版跳过了allocator内存分配器和iterator_traits等。在更严格的实现中需要使用std::allocator来分配和构造对象使用std::is_trivially_copyable等类型萃取来判断是否可以用memmove优化拷贝这属于进阶内容。调试时建议在MyVector的每个成员函数开始和结束处打印_start、_finish、_end_of_storage的值观察指针的变化。写一个小测试程序覆盖构造、拷贝、插入、删除、扩容等各种场景一步步跟踪。最后将你的MyVector与std::vector在相同操作下的行为进行对比这是检验你实现正确性的最好方法。通过这个“手撕”过程vector对你将不再是一个黑盒它的每一次push_back每一次扩容你都能在脑海中清晰地映射出内存和指针的变化图景。这份理解是只看书和文档永远无法获得的。