1. 先想清楚要做什么模拟vector的核心思路1.1 为什么拿vector练手我接触C大概一年多的时候发现一个很奇怪的现状——写了几百道题、调了不少接口但真要说清楚vector里到底发生了什么脑子里其实是一片空白。后来跟着项目代码看的时候发现很多性能问题、诡异崩溃和unsigned char到底存了什么根本对不上号归根结底就是“会用但不理解”。拿vector做练手项目是我见过性价比最高的选择。它不像map那样要考虑红黑树旋转变色也不像shared_ptr那样牵扯控制块和原子操作vector的底层核心其实就三件事一块连续内存、一个记录有效元素个数的变量、一个记录最多能放几个的变量。把这三个东西管明白了整个容器就落地了一大半。更关键的是模拟实现vector能让你把“值语义”这个概念彻底变成肌肉记忆。C最容易被黑的地方就是隐式拷贝、临时对象和资源泄漏而这些坑在vector实现里几乎全都能踩一遍。我自己写完这个项目之后再看普通的业务代码哪里会隐式拷贝、哪里会悬垂一眼就能扫出来这种感觉三百道练习题都给不了。1.2 三个指针一亩地存储结构设计正经的vector实现里三个指针基本是标配start指向数组起始位置finish指向当前有效元素的末尾也就是最后一个元素的下一个位置end_of_storage指向整个容量空间的末尾size就是finish - startcapacity就是end_of_storage - start。这个做法不只是为了省两个成员变量而是让迭代器可以直接退化成裸指针。你想想如果迭代器是一个封装好的类对象每次遍历都走迭代器的重载函数即便编译优化开了也没法保证百分之百内联性能损耗是实打实的。使用原生指针作为vector迭代器还有一个隐藏好处能直接和C语言接口对接。比如你要把vector的数据传给一个void*参数的老牌C库函数直接传vec[0]就好。这个特性在新手写代码时特别容易被忽略等到实际工程里要接第三方库的时候才发现当初设计的迭代器结构帮忙省了不少事。1.3 从使用端倒推接口清单动手写代码之前我习惯先把平时用vector的习惯列一个清单构造空vector然后不断加数据用下标随机访问某个元素用范围for遍历所有数据取首尾元素、获取元素个数在指定位置插入一条数据删除末尾或者中间某个位置的数据预先知道大概容量时直接reserve避免频繁扩容从这份清单倒推回去我至少需要实现这些成员template typename T class my_vector { public: // 类型别名 using value_type T; using iterator T*; // 原生指针即迭代器 using const_iterator const T*; using reference T; using const_reference const T; using size_type size_t; // 构造与析构 my_vector(); my_vector(size_type n, const T val T()); my_vector(const my_vector other); my_vector operator(const my_vector other); ~my_vector(); // 容量相关 size_type size() const; size_type capacity() const; bool empty() const; void reserve(size_type n); void resize(size_type n, const T val T()); // 元素访问 reference operator[](size_type i); const_reference operator[](size_type i) const; reference front(); reference back(); // 修改操作 void push_back(const T val); void pop_back(); iterator insert(iterator pos, const T val); iterator erase(iterator pos); void clear(); // 迭代器 iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; };这个清单不算长但每一个接口背后都有坑。比如resize和reserve很多人分不清insert的迭代器参数在插入之后为什么会失效这些我都会在后面的实现细节里展开说。2. 从零手写成员变量与基础骨架2.1 模板参数与三个指针的定义模板参数这里我直接用template typename T先不做allocator模板参数的适配。为什么因为std::allocatorT本身又会对operator new和operator delete包一层如果不理解底层分配逻辑直接照着实现反而更糊涂。先从裸内存开始等跑通基础功能后再回头研究定制化分配器顺路还能理解内存池是怎么回事。三个指针的定义如下template typename T class my_vector { private: T* start_; T* finish_; T* end_of_storage_; };从一个空vector的角度思考三个指针全为nullptr是合理的初始状态。但有一个细节值得一提——当vector为空时begin()应该等于end()而且end()返回的仍是合法指针。因此很多实现会把空vector的指针统一指向同一块占位地址而不是全部置nullptr。我自己的简易版本直接在构造函数里统一设为nullptr保证begin() end()成立也就是空容器满足end() - begin() 0多数场景下够用。finish_指向的是最后一个元素的下一个位置这个设计决定了很多操作的写法size() finish_ - start_end() finish_push_back时先写数据再让finish_向后移动一位理解这个“半开区间”的语义后面写insert和erase才不会晕。2.2 构造与析构RAII思想构造主要分两种情况。一种是无参构造空vector另一种是给定初始大小并填充默认值。如果已经给了初始大小n就得一次性分配n个元素的空间template typename T my_vectorT::my_vector(size_type n, const T val) : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) { if (n 0) { start_ new T[n]; finish_ start_ n; end_of_storage_ finish_; for (size_type i 0; i n; i) { start_[i] val; } } }这里有个很多新手会踩的坑局部变量T temp在堆上创建是有代价的如果T是一个重量级类型比如一个内部持有vector的类那么每次填充都要触发一次临时构造和拷贝。在标准库的vector(size_type n, const T val)实现里这种问题通常用uninitialized_fill_n配合placement new解决——只调用拷贝构造而不产生额外的中间临时变量。不过在简易版本里先用赋值初始化没毛病把逻辑先跑通才是重点。析构函数则是释放整块数组template typename T my_vectorT::~my_vector() { delete[] start_; start_ finish_ end_of_storage_ nullptr; }直接delete[] start_就能正确释放是因为new T[n]和delete[]彼此配对。如果当初用malloc分配的内存就不能这么释放得手动调用析构函数再free。这里其实预告了一个大问题标准库vector为了支持不完整类型、异常安全和自定义分配器用的是allocator::allocate加placement new的组合而不是简单的new T[n]。等你想让模拟vector支持reserve之后插入元素而不默认构造对象时就会逼着自己去了解placement new。2.3 拷贝控制深拷贝与赋值运算符拷贝构造其实是一个思维分水岭。浅拷贝的写法就是把三个指针直接赋值几秒钟就写完了但这种做法会让新旧两个vector指向同一块堆内存。接下来任何一个对象的析构函数先执行另一个对象的指针就成了悬垂指针使用它直接引发未定义行为。正确实现深拷贝的代码如下template typename T my_vectorT::my_vector(const my_vector other) { if (other.empty()) { start_ finish_ end_of_storage_ nullptr; return; } size_type n other.size(); start_ new T[n]; for (size_type i 0; i n; i) { start_[i] other.start_[i]; } finish_ start_ n; end_of_storage_ finish_; }赋值运算符可以走一个经典写法——拷贝并交换。先构造一个临时对象再把它和当前对象交换因为临时对象析构时会释放旧资源这样既保证了异常安全构造临时对象失败时当前对象不变代码量还特别少template typename T my_vectorT my_vectorT::operator(const my_vector other) { if (this ! other) { my_vector temp(other); swap(temp); } return *this; } template typename T void my_vectorT::swap(my_vector other) noexcept { using std::swap; swap(start_, other.start_); swap(finish_, other.finish_); swap(end_of_storage_, other.end_of_storage_); }这里的swap为什么不能偷懒直接赋值因为如果先释放当前资源再赋值一旦分配新内存失败当前对象已经处于半损坏状态异常安全性就被破坏了。而先构造temp再swap保证“要么全部成功要么保持原样”这是C异常安全里强保证实现的基础思路。3. 核心操作实现与细节3.1 push_back与扩容机制push_back的实现逻辑非常直观如果还有剩余容量就直接放进去容量不足就扩容。template typename T void my_vectorT::push_back(const T val) { if (finish_ end_of_storage_) { size_type old_capacity capacity(); size_type new_capacity old_capacity 0 ? 1 : old_capacity * 2; reserve(new_capacity); } *finish_ val; finish_; }扩容为什么是翻倍而不是固定加一个固定值这涉及均摊时间复杂度的经典判断。假设初始容量为1每次容量不够时扩大到2倍那么插入第n个元素时总共的需要拷贝次数是1 2 4 ... n/2等比级数求和大约是2n均摊下来每次push_back的时间复杂度还是O(1)。但如果固定加10个拷贝次数就会是10 20 30 ...均摊是O(n)。我在项目里实际试过当数据量达到几十万级别时固定增量扩容比倍增扩容慢了一个数量级这就是为什么标准库选择指数增长而非线性增长。不过现实中大多数标准库也不会一直翻倍而是用1.5倍这种更保守的因子来缓解内存碎片和浪费但原理殊途同归。扩容时要注意元素搬移。很多人直接写memcpy这碰到内置类型比如int、double没问题但碰到string或自定义类就是灾难——memcpy是逐字节浅拷贝会导致两个对象指向同一块内部缓冲析构时造成double free。正确的做法是循环赋值让拷贝赋值运算符来介入。代码里也可以用uninitialized_copy来干这件事那是标准库的底层函数后面几节我会单独提。3.2 reserve的核心逻辑reserve的作用是提前分配足够的内存空间避免多次扩容的拷贝成本。它的实现逻辑是template typename T void my_vectorT::reserve(size_type n) { if (n capacity()) return; T* new_start new T[n]; size_type old_size size(); for (size_type i 0; i old_size; i) { new_start[i] start_[i]; } delete[] start_; start_ new_start; finish_ start_ old_size; end_of_storage_ start_ n; }你留意到没有我这里的做法用了new T[n]意味着那n个元素全部被默认构造了。对内置类型来说几乎没有成本但对自定义类型来说哪怕你只往里塞一个元素都要白做n次默认构造——这是一种浪费。标准库的做法是先用allocator::allocate分配一块裸内存然后在目标位置用placement new调拷贝构造跳过默认构造这一步。这部分我在后面“常见问题”里细说因为它直接关系到你能不能处理那些无法默认构造的类型。3.3 insert插入与元素搬移insert的实现是所有操作里最容易翻车的。它分为两步先判断容量够不够不够就扩容然后把pos到finish_之间的元素依次后移一位最后在pos处赋值新元素。template typename T typename my_vectorT::iterator my_vectorT::insert(iterator pos, const T val) { if (pos start_ || pos finish_) { throw std::out_of_range(invalid insert position); } if (finish_ end_of_storage_) { size_type new_capacity capacity() 0 ? 1 : capacity() * 2; size_type offset pos - start_; // 记录偏移 reserve(new_capacity); pos start_ offset; // 扩容后修正指针 } for (iterator it finish_; it ! pos; --it) { *it *(it - 1); } *pos val; finish_; return pos; }这段代码里最容易忽略的一个细节是在reserve之后原来的pos指针已经失效了——旧内存被delete新内存已经分配完毕原指针指向的地址是垃圾数据。所以必须提前记录offset扩容完成后用start_ offset重新定位。还有一个细节要说明for循环向前搬移数据时是从后往前搬的。如果你从前往后搬就会把后一个元素覆盖掉还没搬走的前一个元素整个数组就乱了。这类细节只靠阅读代码很容易漏掉自己动手时出一次bug就再也不会忘了。这里再强调一个点insert时的插入位置其实可以是end()位置即“尾巴后面”这时候pos finish_循环体直接跳过再执行*finish_ val; finish_这其实就是一次push_back。所以insert本身是一个比push_back更泛化的操作但直接调insert的频繁往复里显然不如专门的push_back实现简洁高效。3.4 erase删除与元素搬移erase操作的核心是“把后面的元素往前搬”然后让finish_减一。template typename T typename my_vectorT::iterator my_vectorT::erase(iterator pos) { if (pos start_ || pos finish_) { throw std::out_of_range(invalid erase position); } for (iterator it pos; it ! finish_ - 1; it) { *it *(it 1); } --finish_; return pos; }这个版本有几个问题要斟酌第一被删除位置的元素析构其实不用因为finish_减一后最后那个元素只是“逻辑上”被移出了容器——它的老值还活在那一格内存里但容器根本碰不到它也不会主动释放它。等整体析构时delete[]会把整块内存回收这时候那个格的析构只触发一次不需要特殊处理。第二T本身可能有内部资源比如string对象的堆缓冲如果我一直往前搬旧缓冲还在吗只要析构函数正确执行搬运过程中产生的临时对象和最后被覆盖的对象都会自动释放它们持有的资源。这里要特别留意代入自定义类实战时的“自赋值”现象——比如*it *(it 1)里两个位置不是同一对象时没问题但自己对自己赋值时某些实现可能会先释放右侧的buffer导致右侧数据先被毁掉之后是从未定义行为里拷贝的。标准库的string::operator通常有自赋值保护但你自己写的类可未必有。所以如果目标类型是自定义且自带operator重载时最好也写成if (this ! rhs)保护一下。3.5 operator[]与迭代器接口operator[]的实现非常简单template typename T T my_vectorT::operator[](size_type i) { return start_[i]; }返回引用是必须的否则你无法通过vec[0] x来修改元素。const版本返回const T保护数据不被修改。迭代器接口就更有意思了template typename T typename my_vectorT::iterator my_vectorT::begin() { return start_; } template typename T typename my_vectorT::iterator my_vectorT::end() { return finish_; }因为我把迭代器定义为裸指针所以范围for循环、反向迭代器、std::sort函数模板都天然支持。std::distance这类泛型算法直接在指针上调就行不需要额外适配。这也是vector迭代器和list迭代器最大的差别vector的迭代器一旦失效所有依赖它的算法全都白搭list的操作则相对独立。4. 常见问题与踩坑实录4.1 迭代器失效规则必须刻进脑子里的记忆点迭代器失效是模拟vector过程中绕不开的核心问题。翻翻cppoerator的文档就知道push_back或insert一旦触发扩容整个迭代器全部失效pop_back会让指向末尾元素的迭代器失效insert会在插入点之后失效erase会让被删位置及之后的迭代器全部失效。我用一个非常惨痛的实际案例来记住这条规则。当时我的项目代码里有个循环for (auto it vec.begin(); it ! vec.end(); it) { if (condition(*it)) { vec.erase(it); } }这段代码在Debug模式下时好时坏Release模式必崩典型未定义行为。问题是erase之后it已经失效再执行it就是拿失效指针自增这是内存破坏的来源。正确写法是for (auto it vec.begin(); it ! vec.end();) { if (condition(*it)) { it vec.erase(it); } else { it; } }因为erase返回的是删除位置的下一个元素位置这样就能继续迭代。我建议你自测时写一个小测试边push_back边记录一个迭代器扩容后打印迭代器指向的内容你会发现数据全都乱了。这个过程印象远胜于背规则。4.2 扩容时内存搬移为什么不能无脑memcpy这里必须把memcpy和循环赋值的区别讲透。memcpy做的是逐字节拷贝不调用任何构造函数、赋值运算符。对内置类型来说完全没问题因为int、double的表示就是一个比特序列拷贝出来就是合法值。但T如果是std::string呢string内部包含一个指向堆内存的指针和长度等信息memcpy会把指针值原样复制一份结果就是新旧两个string对象指向同一块字符缓冲区。接着旧string析构释放缓冲区新string就悬了新string析构再释放一次直接double free程序崩得莫名其妙。// 错误的做法直接memcpy搬移元素 // memcpy(new_start, start_, sizeof(T) * old_size); // 正确的做法逐个调用拷贝赋值 for (size_type i 0; i old_size; i) { new_start[i] start_[i]; }说到底C对象是有构造和析构语义的但memcpy是C语言时代的思维它只认字节。只有通过专门的std::is_trivially_copyableT::value判断之后才能在某些场景下安心memcpy。标准库的std::vector在实现时通常会做类型萃取对平凡可拷贝类型走memcpy路径对复杂类型走构造赋值路径。这样性能和安全才能兼得。4.3 无法默认构造的元素类型标准库的实现可以在reserve时只分配裸内存不构造对象这个“魔法”依赖的是allocator::allocate和placement new的组合。假如你没有这一步模拟vector就有一个隐藏限制元素类型必须可以默认构造。写过Qt或某些特殊框架的开发者应该能体会这个问题——有些类型根本没有默认构造函数只有定了参数才能构造。你写new T[n]时编译器要求T有默认构造函数才能分配内存否则代码直接编译不过。标准库vector就没有这个限制因为它在reserve阶段不构造任何元素。更严谨的处理方式是引入std::allocator和placement new#include memory template typename T class my_vector { std::allocatorT alloc_; T* start_; T* finish_; T* end_of_storage_; }; // reserve 重新实现 T* new_start alloc_.allocate(n); // 只分配内存不构造对象 for (size_type i 0; i old_size; i) { alloc_.construct(new_start i, start_[i]); // placement new 构造 } // 释放旧内存之前先逐个析构旧元素 for (size_type i 0; i old_size; i) { alloc_.destroy(start_ i); } alloc_.deallocate(start_, old_capacity);alloc_.construct实际上就是在指定地址上调用::new((void*)p) T(args...)。这就是标准的placement new用法。它允许你在一块未初始化的裸内存上显式构造对象。整个流程相当于“挖地基→砌砖→装修→拆房”而不是“边盖房边决定要几层”。我把这个步骤放在最后讲是因为如果你直接学习标准库版本的实现很容易被allocator、construct、destroy这些术语劝退。先写简单版跑通逻辑再升级内存管理模型尤其适合做这个项目来渐进式理解C抽象层次。4.4 自赋值与异常安全赋值运算符很容易被忽略的边界情况是vec vec自己给自己赋值。如果实现里先释放旧内存再拷贝自己给自己赋值时会直接释放掉自己的数据再拷贝就是空拷贝。这种问题在代码审查时不仔细看根本发现不了只有数据量大、触发特定分支时才会露头。我实现operator时的策略是“拷贝后交换”前面已经展示过了。这不仅是自赋值安全的在构造临时对象失败时也能保证当前对象数据不丢。C社区管这个叫“copy-and-swap”是异常安全的标准范式。顺带提醒一句reserve时需要先构造新内存再删除旧内存这个顺序不能反过来。否则一旦循环赋值时抛出异常旧数据已经没了对象就处于半更新状态。所以reserve里的顺序永远是申请新数组→逐个赋值→删除旧数组。4.5 验证方案和最终完整代码写完后建议建一个测试用例集数据量从1到几万依次压测每次增删后打印size、capacity和全部元素void print(my_vectorint v) { std::cout size v.size() cap v.capacity() : ; for (auto x : v) std::cout x ; std::cout \n; }测试用例至少覆盖这些场景空vector的begin/end、front/back是否越界push_back触发扩容后旧迭代器是否失效预期失效insert到begin、end、中间位置三种情况erase到头、尾、中间三种情况拷贝构造、赋值运算符在数据量很大时是否正确用自定义类如std::string测试元素搬移观察是否出现double free我实际跑下来发现写测试花费的时间和写实现差不多但帮助非常大。因为很多边界情况和断言失败只有在实测中才能暴露出来也正因如此我才真正理解了为什么标准库会把“迭代器失效”写得那么细。整个项目做完后可以继续扩展的方向还有右值引用版本的push_back和构造函数、移动语义支持、emplace_back函数、对自定义分配器的支持、反向迭代器适配。每一步都是新的深入点但最核心的地基始终是这三件事连续内存的管理、三个指针的维护、元素生命周期控制。把这三件事吃透再回头看linux内核链表、Rust的Vec实现甚至Go的slice设计都会有一种豁然开朗的亲近感。