【STL】手撕 vector：从 0 到 1 模拟实现 STL 容器
前言
STL 容器是 C++ 开发中绕不开的 “神兵利器”，而vector作为最常用的动态数组容器，更是新手入门 STL 的核心内容。但多数时候，我们只是 “会用”vector，却对它的底层逻辑一知半解 —— 比如它如何动态扩容？push_back的内存管理是怎样的？构造函数的匹配规则为何如此复杂？
与其停留在 “黑盒调用” 的层面，不如亲手模拟实现一个 vector：从底层的指针管理（_start/_finish/_endofstorage），到核心接口（push_back/resize/operator[]），再到构造、拷贝等特殊函数的实现，一步步揭开 STL 容器的面纱。
本文不会纠结过于晦涩的标准细节，而是以 “实用、易懂” 为核心，带你用 C++ 手动实现一个具备基础功能的vector—— 既能加深对容器原理的理解，也能锻炼 C++ 的底层编程能力。
目录
一、vector的介绍
简单说，vector是 C++ 里可以动态变大小的数组—— 它既保留了普通数组 “连续存储、下标访问高效” 的优点，又解决了普通数组 “大小固定、不能自动扩容” 的痛点。
它的底层逻辑是动态分配的数组：
当你往vector里加新元素时，它会自动管理内存 —— 如果当前数组存满了，就会重新分配一块更大的空间，把旧元素全搬过去，再继续存新元素（不过这个 “搬家” 操作开销不低，所以vector会提前多分配一些额外空间，避免频繁搬家）。
它的特点可以总结成 “优劣势分明”：
优势：访问元素（用下标）、在末尾增删元素，效率都很高；
劣势：在中间 / 开头增删元素，效率很低（因为要挪动大量元素）；
对比其他容器（比如list）：vector的访问更快，但灵活增删不如list。
☃. vector的定义
namespace ayj // 避免与标准库std::vector命名冲突 { // 模板类：实现动态数组vector，T为存储的元素类型（支持int/string等任意可拷贝类型） template <class T> class vector { public: // 迭代器类型定义：vector的迭代器本质是原生指针（因底层连续内存） typedef T* iterator; // 普通迭代器：支持读写元素 typedef const T* const_iterator; // 常量迭代器：仅支持读元素，不可修改 private: // -------------------------- 核心指针（迭代器） -------------------------- // 1. 指向容器中第一个有效元素的起始位置 // 空容器时为nullptr，有效元素范围：[_start, _finish) iterator _start = nullptr; // 2. 指向容器中最后一个有效元素的下一个位置（尾后迭代器） // 空容器时为nullptr，_finish - _start = 有效元素个数（size） iterator _finish = nullptr; // 3. 指向容器已分配内存空间的最后一个位置的下一个位置 // 空容器时为nullptr，_endofstorage - _start = 总容量（capacity） // 当_finish == _endofstorage时，容器满，插入元素需扩容 iterator _endofstorage = nullptr; }; }
这就是 vector 的核心底层结构 —— 通过三个指针（_start/_finish/_endofstorage）管理连续内存，既实现了数组的高效访问，又能动态调整容量。
二、vector的默认成员函数
1、构造函数
/* ===================== 构造函数 ===================== */ // 空构造：初始化空容器，无元素 vector() : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} // 填充构造：创建n个值为val的元素 vector(size_t n, const T& val = T()) { resize(n, val); } // 范围构造：通过其他容器/序列的迭代器范围[first,last)初始化 template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } }讲一个特殊的场景：
按道理来说我们是想用10个1构造一个vector这没啥问题吧，那为啥会编译不通过那，而且报的错误还是和迭代器范围构造相关的
这是因为vector<int> v(10, 1) 会误匹配此版本（10/1被当作InputIterator），此时*first会把10当作指针解引用，触发未定义行为（崩溃）
这个时候有两种办法解决这个问题：
方法1：
将10显式指定为size_t类型（写成10u），这样编译器会优先匹配填充构造函数（而非范围构造函数），从而正常创建包含 10 个值为 1 的元素的 vector。
方法2：
新增一个以int类型为参数的填充构造函数重载版本，让vector<int> v(10, 1)这类传入int型数值的场景，能直接匹配该重载函数，避免编译器误匹配范围构造函数。
//vector<int> v(10, 1) vector(int n, const T& val = T()) { resize(n, val); }
C++函数匹配规则：
2、拷贝构造函数
/*=====================拷贝构造传统写法========================*/ vector(const vector<T>& v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { _start = new T[v.capacity()]; //浅拷贝 - 容器存储的是有动态资源的自定义类型，使用memcpy就会造成浅拷贝 //memcpy(_start,v._start,sizeof(T)* v.size()); //深拷贝 for (size_t i = 0; i < v.size(); i++) { _start[i] = v._start[i]; } _finish = _start + v.size(); _endofstorage = _start + v.capacity(); } /*=====================拷贝构造现代写法========================*/ vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (size_t i = 0; i < v.size(); i++) { push_back(v[i]); } }先来说传统写法：先给数组开辟对应空间，然后进行数据拷贝，最后更新_finish和_endofstorage指针。
这里需要注意：拷贝数据不能用memcpy。因为如果数据类型是带有动态资源的自定义类型（比如string），用memcpy拷贝会引发浅拷贝问题—— 它只会复制指针的值，不会复制指针指向的动态资源，最终导致多个对象共用同一块内存空间。
（图注：浅拷贝导致多个对象共用同一块动态空间的问题图例）
这个解决方案其实很简单：直接通过赋值操作完成拷贝即可。因为对于string这类自定义类型，赋值时会自动调用其赋值运算符重载函数，从而实现内部动态资源的深拷贝；而对于int、double等内置类型，赋值就是简单的数值拷贝，不会有任何额外影响。
3、赋值运算符重载
/*=====================赋值重载现代写法========================*/ void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } // v1 = v2 vector<T>& operator=(vector<T> v) { swap(v); return *this; }operator=的参数是值传递（vector<T> v），会自动调用拷贝构造函数生成实参的临时副本；
借助std::swap交换当前对象和临时对象的内部指针，临时对象出作用域时会自动释放原当前对象的旧资源，避免内存泄漏；
返回*this以支持连续赋值（如v1 = v2 = v3），符合赋值运算符重载的规范。
/*=====================赋值重载传统写法========================*/ vector<T>& operator=(vector<T>& v) { T* tmp = new T[v.capacity()]; for (size_t i = 0; i < v.size(); i++) { tmp[i] = v._start[i]; } delete[] _start; _start = tmp; _finish = _start + v.size(); _endofstorage = _start + v.capacity(); return *this; }这段赋值重载传统写法，先开辟临时空间深拷贝数据，再释放当前对象旧空间，最后更新指针并返回当前对象引用，实现安全且正确的深拷贝赋值。
4、析构函数
~vector() { if (_start) { delete[] _start; _start = _endofstorage = _finish = nullptr; } }三、vector iterator
/*==========================迭代器=============================*/ iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }迭代区间始终遵循[begin, end)的规则，以下是迭代器begin()与end()的边界定位示意图：
（图注：begin()指向容器的第一个有效元素，end()指向最后一个有效元素的下一个位置）
反向迭代器我们先暂时放一放，等后面学到list的反向迭代器时，vector的反向迭代器写法也就自然掌握了。
四、vector容量相关接口
1、size
size_t size() const { return _finish - _start; }2、capacity
size_t capacity() const { return _endofstorage - _start; } 3、empty
bool empty()const { return size() == 0; }4、reserve
/*==========================扩容接口============================*/ void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { //浅拷贝 -- 如果存储的是带动态资源的自定义类型将就会有浅拷贝问题 //memcpy(tmp, _start, sizeof(T) * sz); //每次调用赋值重载解决了浅拷贝问题 for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; //_finish = _start + size() 错误代码;因为size()中的_start和_finish指的不是同一块空间 _finish = _start + sz; _endofstorage = _start + n; } }该接口用于为vector预留至少n个元素的存储空间，仅当n大于当前容器容量时才执行扩容操作；扩容时先记录当前有效元素个数，开辟n个大小的临时空间，通过循环调用元素赋值重载完成深拷贝（解决自定义类型动态资源的浅拷贝问题），随后释放原空间，更新容器的_start、_finish、_endofstorage指针，使容器容量更新为n，且保留原有全部有效元素，有效避免频繁扩容带来的性能损耗。
扩容接口有两个特殊问题：
1、自定义类型动态资源的浅拷贝问题：当容器存储的是带动态资源的自定义类型时，直接用memcpy拷贝会导致浅拷贝，这一问题的解决思路在赋值运算符重载和拷贝构造的内容中已有说明，此处不再赘述；
2、必须提前用 sz 记录当前有效元素个数：因为扩容后原空间会被释放，_start指针会指向新空间，若此时再调用size()获取元素个数，会因_start和_finish不再指向原空间而计算错误，所以需要在扩容前先把当前元素个数存到 sz 变量中。
5、resize
/*=========================开空间+填值（resize接口）===========================*/ void resize(size_t n , const T& val = T()) { // 情况1：n小于当前有效元素个数，执行截断操作（保留前n个元素，后面的元素失效） if (n < size()) { // 直接调整_finish指针，指向第n个元素的下一个位置，实现逻辑截断（物理空间仍保留原有容量） _finish = _start + n; } // 情况2：n大于等于当前有效元素个数，执行扩容+填值操作 else { // 调用reserve接口预留n个元素的空间，reserve内部会判断n是否大于当前容量，仅需扩容时才会执行实际内存分配 reserve(n); // 循环填充：从当前_finish位置开始，到_start+n位置结束，将新增空间填充为指定val值 while (_finish != _start + n) { *_finish = val; // 给当前有效元素末尾的新位置赋值 _finish++; // 移动_finish指针，扩大有效元素范围 } } }这段resize接口用于调整vector的有效元素个数：
第二个参数的缺省值是调用默认构造，内置类型由于加入了模板，也有了自己的默认构造
当 n 小于当前元素数时，直接截断（仅调整_finish指针，保留前 n 个元素）；
当 n 更大时，先调用reserve预留空间，再将新增位置填充为指定值，最终更新_finish指针，既支持缩小容器，也能安全扩容并填充元素。
五、vector增删查改
1、push_back
void push_back(const T& x) { // 判断是否需要扩容：当有效元素末尾指针等于容量末尾指针时，说明当前内存已满 if (_finish == _endofstorage) { // 计算新容量：若当前容量为0则初始化为4，否则扩容为原来的2倍（常用扩容策略） size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; // 调用reserve接口完成扩容，预留新容量空间 reserve(newcapacity); } // 给当前有效元素末尾赋值（尾插核心操作） *_finish = x; // 移动有效元素末尾指针，扩大有效元素范围 ++_finish; }2、insert
//指定位置插入 iterator insert(iterator pos,const T& x) { assert(pos>=_start && pos<=_finish); //扩容 if (_finish == _endofstorage) { //记录pos相对位置 size_t len = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); //解决内部迭代器失效问题 pos = _start + len; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } *pos = x; ++_finish; //解决外部迭代器失效问题 - 指向新插入元素的位置 return pos; }迭代器失效场景 1：扩容引发的野指针问题
insert的参数pos在扩容时，原内存空间会被销毁回收，此时pos指向的旧地址会失效并变为野指针；而(*pos)++对这个野指针进行了解引用操作，最终导致程序崩溃。
那我们该如何解决这个问题呢？
我标记的这两步是为了解决pos迭代器在函数内部失效的问题，通过记录扩容前pos和_start的相对位置以便于在扩容后更新pos的位置，让其指向新空间的当前位置
返回更新后的pos，解决外部迭代器失效问题。
pos为啥不能传引用解决外部失效问题？
第一个调用v.insert(pos, 5)：传的是pos变量（左值迭代器），引用传参能直接修改外部pos，所以没问题；
第二个调用v.insert(v.begin(), 5)：传的是临时迭代器（右值），临时数据自带 “常性”（不可修改），而引用传参要求修改它，这属于 “权限放大”，因此会编译失败。
迭代器失效场景2：非扩容下的逻辑错位失效
若未触发扩容：插入点之后的迭代器全部失效（元素后移导致指向错位，属于逻辑错位）；
3、erase
// 指定位置删除元素 iterator erase(iterator pos) { // 断言：确保pos迭代器合法（在有效元素区间内），且vector非空，防止非法访问 assert(pos >= _start && pos < _finish && size()>0); // 定义迭代器it，从pos的下一个元素开始遍历 iterator it = pos + 1; // 循环：将pos之后的所有元素依次向前移动一位，覆盖待删除元素（实现逻辑删除） while(it != _finish) { *(it - 1) = *it; // 后一个元素的值赋给前一个元素，完成前移覆盖 it++; // 迭代器后移，处理下一个元素 } // 尾指针前移一位，缩小有效元素范围（底层内存未释放，仅标记该位置元素无效） --_finish; // 返回原pos迭代器（此时pos指向被删除元素的下一个有效元素，避免外部迭代器失效） return pos; }迭代器失效场景3：erase 导致的逻辑错位失效
情况 1：删除单个偶数（巧合没报错）
情况 2：删除连续偶数（迭代器失效导致跳过元素）
这个没删干净哦~，这是因为在删除第一个2后，这时候it指向第二个2，但是it++跳过了
情况 3：删除末尾偶数（迭代器失效导致崩溃）
删除末尾偶数会触发死循环，当遍历到末尾偶数6并执行erase(it)后，it迭代器失效且与更新后的vector尾指针重合，后续的it++无法正常推进迭代器，导致循环条件it != v.end()永远成立，循环无法退出而陷入死循环，部分运行环境中也可能因失效迭代器操作触发内存越界崩溃。
综上所述，上述所有问题（巧合未报错、跳过元素、死循环 / 崩溃），本质都是错误的遍历删除逻辑导致的迭代器失效：代码直接在erase后执行it++，没有利用erase返回的有效迭代器更新it，使得失效的迭代器参与后续操作，进而引发未定义行为（结果随机、逻辑错乱、程序异常）。
正确的写法应是用erase的返回值更新迭代器（删除元素时不执行it++，仅在未删除时推进），避免使用失效的旧迭代器，才能保证代码的正确性与稳定性。
迭代器失效解决方案
核心结论：对vector执行erase或insert操作后，原迭代器必然失效（可能因内存销毁成野指针，或因元素移位逻辑错位），此时再访问该迭代器的结果是未定义的（可能巧合运行、跳过元素、死循环甚至崩溃）。
解决方案：若需继续操作容器，必须用erase/insert返回的新有效迭代器替代旧迭代器 —— 这是 C++ 标准规定的唯一安全方式，确保每次操作都基于容器当前的有效状态。
简言之：旧迭代器作废，用返回的新迭代器续接操作。
不同编译器对失效迭代器的访问处理存在差异：比如在 VS 编译器中，一旦使用了失效的迭代器，程序会直接报错。
4、pop_back
//尾删 void pop_back() { earse(--end()); }5、operator[]
/*=====================[]运算符重载=====================*/ // 可读可写版本：返回非const引用，支持修改元素值 T& operator[](size_t pos) { assert(pos < size()); // 断言确保访问的下标合法，不越界 return _start[pos]; // 返回对应位置元素的引用，支持读和写 } // 仅读版本：const成员函数，返回const引用，禁止修改元素值 const T& operator[](size_t pos) const { assert(pos < size()); // 断言确保访问的下标合法，不越界 return _start[pos]; // 返回对应位置元素的const引用，仅支持读操作 }容器的 [] 访问比普通数组多了什么约束？
容器的 [] 访问多了逻辑 size 约束；
要求访问下标必须小于容器的 size（已初始化的有效元素数量），而普通数组仅受物理内存范围限制，无逻辑有效性检查。
问题：下面代码为啥会崩溃？
vector<int> v; v.reserve(10); for (int i = 0; i < 10; i++) { v[i] = i; }reserve(10) 仅预留内存，vector 的 size 仍为 0，直接用 v[i] = i （[ ]下标访问运算符重载规定，i < size）属于越界访问未初始化内存，会导致未定义行为（如崩溃）。
正确做法：用 resize(10) 初始化 10 个元素（size=10），再下标赋值；或 reserve 后用 push_back 添加元素。
6、find（算法模块的接口）
vector自身并没有提供find接口，因此如果需要查找元素，要调用算法库中的find接口来实现。
template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& val) { while (first != last) { if (*first == val) { return first; } first++; } return last; } 
