C vector 模拟实现一从三个指针开始理解动态数组的骨架前言上一篇我们梳理了 vector 的常用接口和避坑点但“会用”和“懂”之间还差一层——底层实现。很多人背过“vector 底层是三个指针”但被追问“为什么是三个指针而不是 sizecapacity 两个变量”“指针相减为什么能得到 size”时就卡壳了。本文作为模拟实现系列的开篇先搭好 vector 的骨架成员变量设计、构造、析构、容量接口和迭代器。骨架立住了后续的增删查改就是往上填肉。本文所有代码均可直接运行建议边看边手敲一遍。一、为什么是三个指针先看结论vector 的成员变量设计如下templatetypenameTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;private:iterator _start;// 指向数据块的起始位置iterator _finish;// 指向最后一个有效元素的下一个位置iterator _end_of_storage;// 指向已分配内存的末尾};1.1 三指针 vs sizecapacity有读者会问用T* _data; size_t _size; size_t _capacity;不是更直观吗为什么 STL 要用三个指针核心原因有三个① 迭代器天然就是指针vector 的迭代器本质上就是原生指针T*。begin()返回_startend()返回_finish这是 O(1) 且零成本的。如果用 sizecapacitybegin 需要返回_dataend 需要返回_data _size虽然也不复杂但三指针的设计让迭代器和成员变量完全统一。② 指针相减直接得到 size无需额外存储size_tsize()const{return_finish-_start;}size_tcapacity()const{return_end_of_storage-_start;}指针相减是编译器原生支持的运算不占额外内存。而 sizecapacity 方案需要两个size_t各 8 字节在 64 位平台上反而更占空间。③ 扩容时指针更新更自然扩容时需要申请新空间、拷贝数据、释放旧空间。三指针方案下只需重新赋值三个指针sizecapacity 方案则需要同时维护数据指针和两个计数值出错概率更高。一句话总结三指针设计让迭代器、容量计算、内存管理三者统一代码更简洁空间更省。二、迭代器与容量接口有了三个指针容量相关的接口就是一行代码的事public:// 迭代器 iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}// 容量 size_tsize()const{return_finish-_start;}size_tcapacity()const{return_end_of_storage-_start;}boolempty()const{return_start_finish;}注意这里提供了const 版本和非 const 版本的 begin/end。const 对象调用时返回const_iterator保证不能通过迭代器修改元素。这是 C 中常见的 const 重载技巧。此时可以写个简单测试验证一下vectorintv;coutv.size() v.capacity() v.empty()endl;// 输出0 0 1但此时还没有构造函数_start等指针是未初始化的野指针直接调用 size() 会得到垃圾值。所以下一步必须写构造函数。三、构造函数从零开始3.1 默认构造默认构造要做的唯一一件事把三个指针置空。vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}使用初始化列表而不是在函数体内赋值是因为指针是内置类型初始化列表才是真正的“初始化”函数体内是“赋值”。虽然对指针来说差别不大但养成好习惯。3.2 填充构造n 个 valvector(size_t n,constTvalT()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);// 先开够空间for(size_t i0;in;i){push_back(val);// 逐个构造}}这里有两点需要说明① 为什么用 push_back 而不是直接赋值因为 vector 存储的可能是自定义类型如 string内存分配后这块空间是未初始化的原始内存不能直接_start[i] val必须通过拷贝构造来初始化对象。push_back 内部会调用拷贝构造是安全的做法。②const T val T()是什么这是 C 的默认参数写法T()会调用 T 的默认构造函数。对 int 来说T()就是 0对 string 就是空串。这样vectorint v(5);就会得到 5 个 0。⚠️注意此时 push_back 和 reserve 还没实现文章后面会补上。这里先建立“构造 开空间 构造元素”的思路。3.3 拷贝构造深拷贝拷贝构造是最容易踩坑的地方。先看错误写法// ❌ 错误浅拷贝vector(constvectorTv):_start(v._start),_finish(v._finish),_end_of_storage(v._end_of_storage){}这样写会导致两个 vector 指向同一块内存。当其中一个析构时释放了内存另一个就变成了悬空指针再次访问或析构就会崩溃double free。正确写法传统写法vector(constvectorTv):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());// 开同样大的空间for(constautoe:v){push_back(e);// 逐个深拷贝}}更简洁的现代写法后续讲到赋值重载时会重点讲vector(constvectorTv):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){vectorTtmp(v.begin(),v.end());// 用迭代器区间构造临时对象swap(tmp);// 交换指针}现代写法依赖迭代器区间构造和 swap我们后面再实现这里先掌握传统写法。3.4 迭代器区间构造这个构造函数非常通用可以从数组、其他容器、甚至 vector 自身的区间构造templateclassInputIteratorvector(InputIterator first,InputIterator last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){while(first!last){push_back(*first);first;}}为什么用模板而不是直接写const T*因为这样不仅能接受指针还能接受其他容器的迭代器如listint::iterator通用性更强。四、析构函数析构要做两件事释放元素 释放内存。~vector(){if(_start){// 1. 先析构所有有效元素对自定义类型必须for(size_t i0;isize();i){_start[i].~T();}// 2. 再释放整块内存delete[]_start;}_start_finish_end_of_storagenullptr;}为什么不能只 delete[]delete[] _start会释放内存但对于自定义类型如 string它不会调用每个元素的析构函数因为_start是T*delete[] 只对“真正的数组”负责。所以必须手动循环调用析构。对 int、double 这类内置类型.~T()是空操作没有额外开销。注意这里用delete[]而非delete因为内存是通过new T[]分配的后续扩容时会看到。两者必须配对否则是未定义行为。五、reserve扩容的核心reserve是整个 vector 性能的关键也是迭代器失效的根源。先看实现voidreserve(size_t n){if(ncapacity()){// 只有 n 大于当前容量才扩容size_t oldSizesize();// 记录旧 size关键T*tmpnewT[n];// 1. 申请新空间// 2. 拷贝旧元素到新空间if(_start){for(size_t i0;ioldSize;i){tmp[i]_start[i];// 拷贝赋值}delete[]_start;// 3. 释放旧空间}// 4. 更新三个指针_starttmp;_finishtmpoldSize;_end_of_storagetmpn;}}这段代码有几个极其关键的细节5.1 为什么先保存 oldSize如果先更新_start tmp那么size()计算的是_finish - _start而_finish还没更新结果就是负数或巨大值循环会出错。所以必须先保存旧的 size。5.2 为什么不用 memcpy很多初学者会写memcpy(tmp, _start, oldSize * sizeof(T))这在存储内置类型时没问题但对自定义类型是灾难vectorstringv;v.push_back(hello);v.push_back(world);v.reserve(10);// 如果内部用 memcpymemcpy 是按字节拷贝会把 string 对象内部的指针原样复制。结果是新旧两个 string 的指针指向同一块堆内存。当旧 vector 析构时这块内存被释放新 vector 里的 string 就成了悬空指针后续访问直接崩溃。正确做法是用拷贝赋值tmp[i] _start[i]它会调用 string 的赋值运算符完成真正的深拷贝。结论只要 T 不是 trivially copyable 的类型就绝不能用 memcpy。5.3 扩容倍数标准库实现的扩容倍数VS 是 1.5 倍GCC 是 2 倍。模拟实现时我们通常简化为 2 倍。为什么是指数增长因为这样可以把 n 次 push_back 的总拷贝次数控制在 2n 以内均摊复杂度为 O(1)。如果固定增长如每次 10总拷贝次数是 O(n²)。六、push_back串起一切最后实现 push_back把上面所有东西串起来voidpush_back(constTx){// 1. 检查是否需要扩容if(_finish_end_of_storage){size_t newCapacitycapacity()0?4:capacity()*2;reserve(newCapacity);}// 2. 在 _finish 位置构造元素*_finishx;_finish;}扩容策略说明空 vector 首次插入分配 4 个空间避免频繁小扩容之后每次按 2 倍增长注意*_finish x是拷贝赋值。严格来说这块内存还没构造对象应该用 placement new但对于大多数类型拷贝赋值也能工作。真正的 STL 会用 allocator 的 construct 函数这个我们放到进阶篇讲。七、完整代码与测试把上面所有代码整合起来#includeiostream#includestringusingnamespacestd;namespacemy_vector{templatetypenameTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;// 构造 / 析构 vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}vector(size_t n,constTvalT()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);for(size_t i0;in;i)push_back(val);}templateclassInputIteratorvector(InputIterator first,InputIterator last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){while(first!last){push_back(*first);first;}}vector(constvectorTv):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());for(constautoe:v)push_back(e);}~vector(){if(_start){for(size_t i0;isize();i)_start[i].~T();delete[]_start;}_start_finish_end_of_storagenullptr;}// 迭代器 iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}// 容量 size_tsize()const{return_finish-_start;}size_tcapacity()const{return_end_of_storage-_start;}boolempty()const{return_start_finish;}voidreserve(size_t n){if(ncapacity()){size_t oldSizesize();T*tmpnewT[n];if(_start){for(size_t i0;ioldSize;i)tmp[i]_start[i];delete[]_start;}_starttmp;_finishtmpoldSize;_end_of_storagetmpn;}}// 增 voidpush_back(constTx){if(_finish_end_of_storage){reserve(capacity()0?4:capacity()*2);}*_finishx;_finish;}// 访问 Toperator[](size_t i){return_start[i];}constToperator[](size_t i)const{return_start[i];}private:iterator _start;iterator _finish;iterator _end_of_storage;};}// namespace my_vector// 测试 intmain(){my_vector::vectorintv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);coutsizev.size() capacityv.capacity()endl;// 输出size5 capacity8第5个元素触发扩容到 8for(size_t i0;iv.size();i)coutv[i] ;coutendl;// 输出1 2 3 4 5// 测试拷贝构造深拷贝my_vector::vectorintv2(v);v2[0]100;coutv[0]v[0] v2[0]v2[0]endl;// 输出v[0]1 v2[0]100互不影响证明深拷贝成功// 测试自定义类型my_vector::vectorstringvs;vs.push_back(hello);vs.push_back(world);for(autos:vs)couts ;coutendl;// 输出hello worldreturn0;}运行结果size5 capacity8 1 2 3 4 5 v[0]1 v2[0]100 hello world总结本文搭好了 vector 的骨架核心要点回顾要点结论成员变量三指针_start/_finish/_end_of_storage容量计算指针相减O(1) 且零额外空间构造默认构造置空指针填充构造用 push_back 保证正确初始化拷贝构造必须深拷贝否则 double free析构先循环析构元素再 delete[] 释放内存reserve先保存 oldSize用拷贝赋值而非 memcpy指数扩容push_back满则扩容未满则赋值并移动 _finish下篇预告骨架有了接下来实现 vector 的完整增删查改——insert、erase、resize、pop_back重点讲清楚insert/erase 的迭代器失效问题以及返回值设计。这是面试和实战中最容易出错的部分敬请期待。如果这篇帮你搞懂了三个指针的设计欢迎点赞 收藏。有任何疑问欢迎评论区交流我会逐条回复。