1. vector的介绍1.1 vector的文档介绍vector的文档介绍std::vector是一个标准模板类位于头文件vector中其声明简化格式如下第一个参数T存储的数据类型如int、std::string或自定义类型。第二个参数Alloc空间配置器内存池负责内存分配与管理通常使用默认值。1.2 vector 与相关概念的对比与进阶认知1. vector 能否替代 std::string✍️答不能。C 风格兼容string结尾保证隐含\0能无缝兼容 C 语言接口如printf(%s, str.c_str())而vectorchar是纯粹的数据容器没有以\0结尾的约定。接口丰富度string内置了拼接、查找find、截取substr等专有方法而vectorchar不具备这些针对字符串优化的接口。2. vectorvector 二维数组的构建与本质若要创建一个10 × 5 10 \times 510×510 行 5 列的二维数组初始化方式如下// 1. 先定义一个 5 个元素且值为 1 的一维 vectorintfuyo::vectorintv(5,1);// 2. 创建一个拥有 10 个元素的外层 vector每个元素都是一维的 vfuyo::vectorfuyo::vectorintvv(10,v);如图所示使用与底层本质当我们写下vv[2][1] 2;时看似简单的访问底层实际上是两次连续的operator[]函数调用vv[2][1]2;// 本质等价于vv.operator[](2).operator[](1)2;这两个[]作用的并不是同一个类第一个[]作用于外层fuyo::vectorfuyo::vectorint类返回第 2 行的fuyo::vectorint引用。第二个[]作用于内层fuyo::vectorint类返回该行第 1 列的int引用。3. 比较大小 与 流插入/流提取比较大小vector支持通过重载、等运算符比较大小按字典序逐元素比较不过实际开发中一般较少直接比较两个容器的大小。IO 流vector不支持直接使用cout v或cin v。如果需要可以通过重载全局的operator遍历输出。下面来进行vector的模拟实现2. 底层核心结构与内存模型在模拟实现vector时标准的做法是维护三个指针public:typedefT*iterator;typedefconstT*const_iterator;private:iterator _startnullptr;// 指向堆内存空间的起始位置iterator _finishnullptr;// 指向最后一个有效元素的下一个位置 (指向 size 边界)iterator _end_of_storagenullptr;// 指向已分配内存空间的末尾 (指向 capacity 边界)通过这三个指针我们可以很轻松地推导出容器的有效大小与容量// 有效大小size_tsize()const{return_finish-_start;}// 容量size_tcapacity()const{return_end_of_storage-_start;}3. 核心容量接口reserve() 与 resize()3.1 reserve(n) 预留空间作用扩充容量至大于等于n nn仅改变capacity不改变size也不会创建任何元素。代码实现voidreserve(size_t n){if(ncapacity()){size_t old_sizesize();// 必须提前保存旧的 sizeT*tmpnewT[n];// 数据搬移为什么不能用 memcpy - 见7.4for(size_t i0;iold_size;i){tmp[i]_start[i];}delete[]_start;// 释放旧空间//指向新空间_starttmp;_finishtmpold_size;_end_of_storagetmpn;}}关键要点分析必须提前备份old_size在更新指针时如果我们写成_finish tmp size();由于此时_start已经变成了tmp调用size()即_finish - _start计算出来的会是一个完全错误的负值或乱码。所以必须在改变_start之前把旧的元素个数保存下来。2.只扩容不缩容if (n capacity())的判断保证了当n ≤ capacity n \le \text{capacity}n≤capacity时reserve绝不会做任何操作vector绝不会缩容。⚖️vector与string的对比string::reserve(n)在某些编译器中当n capacity n \text{capacity}ncapacity时可能触发缩容但保证不丢数据。vector::reserve(n)不会缩容只会扩容即当n ≤ capacity n \le \text{capacity}n≤capacity时静默无操作。3.2 resize(n, val) 改变有效元素个数作用改变有效元素个数size相比stringresize在vector中的使用频率更高。假设当前size 10 , capacity 20 \text{size} 10, \text{capacity} 20size10,capacity20调用 resize(n) 的不同取值分为以下两类情况后两个行为可视为一类代码演示voidresize(size_t n,constTvalT()){if(nsize()){// 第一类截断数据直接将 _finish 前移_finish_startn;}else{// 第二类追加元素空间不够先触发 reserve 扩容reserve(n);while(_finish_startn){*_finishval;_finish;}}}4. 构造函数细节与“类型重载冲突”4.1 vector 构造函数声明与接口说明4.2 模拟实现中的构造函数结合底层代码实现vector的构造函数细节与避坑点如下namespacefuyo{templateclassTclassvector{public:// 1. 无参构造利用 C11 default 结合类内缺省值生成vector()default;// 2. 填充构造构造并初始化 n 个 valvector(size_t n,constTvalT()){reserve(n);for(size_t i0;in;i){Push_back(val);}}// 3. 特化重载构造解决 int 参数推导时的模板冲突关键扩展vector(intn,constTvalT()){reserve(n);for(size_t i0;in;i){Push_back(val);}}// 4. 迭代器区间构造成员函数模板支持任意容器的迭代器区间templateclassInputIteratorvector(InputIterator first,InputIterator last){while(first!last){Push_back(*first);first;}}// 5. 拷贝构造函数深拷贝vector(constvectorTv){reserve(v.capacity());for(constautoe:v){Push_back(e);}}};}4.3 构造函数的三大核心坑点剖析1. 缺省值 const T val T() 与内置类型伪构造在填充构造函数中缺省值写成了 T()。疑问如果 T 是 int 或指针等内置类型int() 这种写法合法吗答案是合法的。C 为了让模板能统一处理“内置类型”和“自定义类型”专门为内置类型扩展了“伪构造函数”语法int()初始值为0double()初始值为0.0int*()初始值为nullptr这样const T val T()就能无缝适配所有数据类型。2. 经典报错为什么非要单独重载 vector(int n, …)查看代码可以发现我们定义了两个貌似重复的构造函数vector(size_t n,constTvalT())vector(intn,constTvalT())疑问为什么一定要加上 int 版本的重载✍️当你写下这段代码时fuyo::vectorintv(10,1);// 传入两个 int 类型的字面量如果没有int版本的重载匹配填充构造(size_t)需要把第一个参数10从int隐式转换为size_t匹配区间构造(InputIterator)模板会将InputIterator精准推导为int两个参数均是int属于无需任何类型转换的精准匹配后果编译器会“自作聪明”地选择区间构造函数并在内部执行 Push_back(*first) 时尝试对整型 10 进行解引用*10从而引发致命的编译报错。✅️解决方案显式提供vector(int n, const T val T())阻断模板的过度推导。3. 迭代器区间构造的泛型优势区间构造函数采用了类模板中的成员函数模板templateclassInputIteratorvector(InputIterator first,InputIterator last);✅️优势打破了容器类型的界限不仅可以用fuyo::vector自己的迭代器还可以用std::list、std::string的迭代器甚至是原生指针如int*来初始化当前容器极大地增强了复用性。使用演示vectorintv1;v1.Push_back(1);v1.Push_back(2);v1.Push_back(3);v1.Push_back(4);vectorintv2(v1.begin(),v1.begin()3);// v2为v1的前三个元素5. 数据的增删改查、元素访问与迭代器失效5.1 元素访问operator[] 与 at() 的区别operator[]断言越界直接使用assert强行拦截性能极高。如果越界程序直接中断报错。Toperator[](size_t i){assert(isize());// 越界直接断言报错return_start[i];}at(i)抛异常越界安全访问方式。若越界会抛出std::out_of_range异常。Tat(size_t i){if(isize()){throwstd::out_of_range(vector::_M_range_check);// 越界抛异常}return_start[i];}5.2 尾部/头部的增删接口差异尾部操作支持直接尾插Push_back与尾删Pop_back时间复杂度O ( 1 ) O(1)O(1)。代码演示voidPush_back(constTx){if(_finish_end_of_storage){reserve(capacity()0?4:2*capacity());// 2 倍自动扩容}*_finishx;_finish;}voidPop_back(){assert(!empty());--_finish;// 仅移动指针时间复杂度 O(1)}5.3 insert 与内部迭代器失效代码演示iteratorinsert(iterator pos,constTx){assert(pos_start);assert(pos_finish);// 1. 扩容判断if(_finish_end_of_storage){size_t lenpos-_start;// 记录相对偏移量reserve(capacity()0?4:2*capacity());pos_startlen;// 解决内部 pos 野指针问题}// 2. 元素后移iterator end_finish-1;while(endpos){*(end1)*end;--end;}// 3. 插入新值并更新 _finish*posx;_finish;returnpos;// 返回更新后的 pos}测试代码用例intx;cinx;autopfind(v.begin(),v.end(),x);if(p!v.end()){// v.insert(p, 40);// (*p) * 10; // ❌ 错误如果 insert 内部触发了扩容实参 p 依然指向旧内存野指针pv.insert(p,40);// ✅ 正确接收 insert 返回的最新有效迭代器(*(p1))*10;}为什么实参p会失效✍️答insert内部的pos是按值传递的即使我们在函数内部通过pos _start len矫正了pos的指向外部的实参p依然指向已经被delete[]释放掉的旧内存空间因此必须接收返回值更新外部迭代器。总结迭代器失效的本质分为两种物理失效野指针由于扩容导致旧空间被释放迭代器指向了无效的野指针区域。逻辑失效意义偏移由于元素的插入/删除导致数据平移迭代器虽然依然指向有效内存但指向的已不再是原本的数据。5.4 erase 与外部逻辑失效代码演示iteratorerase(iterator pos){assert(pos_start);assert(pos_finish);iterator itpos1;while(it!end()){*(it-1)*it;// 元素整体向前挪动覆盖it;}--_finish;returnpos;// 返回指向被删除元素下一个位置的迭代器}测试代码用例vectorintv;// 假设数据为1, 2, 3, 4, 4, 5// 注意中间有连续偶数 4, 4autoitv.begin();while(it!v.end()){if(*(it)%20){// erase 删除当前值后后面的元素向前平移it 自动指向下一个元素itv.erase(it);}else{// 只有没删除元素时才进行 it 操作it;}}为何不能盲目it✍️答当删除第一个4时第二个4会向前平移占据第一个4的位置。如果删除后执行了it迭代器就会直接跳过第二个4导致连续偶数漏删。6. 容器打印与泛型迭代器遍历6.1 只能打印vector不推荐代码演示仅支持打印vectortemplateclassTvoidPrint_vector(constvectorTv)// 注意const引用{// 方式一显式类型声明依赖未实例化的模板类型时必须加 typename// typename vectorT::const_iterator cit v.begin();// 方式二使用 auto 自动推导推荐自动推导为 const_iteratorautocitv.begin();while(cit!v.end()){cout*cit ;cit;}coutendl;// 只需要打印所以加上const和修饰更好for(constautoe:v){coute ;}coutendl;}为什么要加typename✍️答因为vectorT是一个尚未实例化依赖于模板参数T的嵌套类型。编译器在没有实例化前无法判断vectorT::const_iterator到底是一个“静态成员变量”还是一个“内部类型”。加typename就是显式告诉编译器“这是一个类型请放行通过留到运行时去解析”。为什么下面的代码会报错citv.begin();for(autoe:cit){……}✍️答因为编译器会自己调用cit中的begin()和end()但是cit只是一个指针没有begin()和end()所以直接作用于v即可。原理解析C 的范围 forfor (auto e : v)是一个语法糖编译器在编译时会自动把它替换成类似下面的代码auto__beginv.begin();auto__endv.end();for(;__begin!__end;__begin){autoe*__begin;}范围 for 要求作用的对象必须拥有begin()和end()成员函数。而 cit 本身只是一个迭代器本质上类似于指针它并没有.begin()方法因此直接对cit使用范围 for 会引发编译错误。正确的对象应该是容器本身v。6.2 泛型容器打印推荐✅️上一节的Print_vector只能打印vector。如果我们想打印list、deque或set就不得不重新写新的函数。通过将参数直接抽象为容器模板参数Container可以实现打印任意容器代码演示可打印任意类型的 STL 容器templateclassContainervoidPrint_container(constContainerv){autocitv.begin();while(cit!v.end()){cout*cit ;cit;}coutendl;for(constautoe:v){coute ;}coutendl;}7. 深浅拷贝与内存崩溃陷阱7.1 拷贝构造拷贝构造的代码实现// 拷贝构造//也可以写成vector(const vector v)vector(constvectorTv){reserve(v.size());for(autoe:v){Push_back(e);}}7.2 现代赋值重载现代赋值重载代码演示voidswap(vectorTv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);}// 现代写法 - 赋值重载vectorToperator(vectorTv){swap(v);return*this;}7.3 代码使用案例vectorintv1;v1.Push_back(1);v1.Push_back(2);// 拷贝构造触发深拷贝vectorintv2v1;vectorintv3;v3.Push_back(10);// 赋值重载触发 operator 按值传参 - 拷贝构造生成临时变量 - swap 交换v1v3;7.4 不使用memcpy的原因 - memcpy导致浅拷贝在下述测试代码中vectorstringv;v.Push_back(11111111111111111);v.Push_back(11111111111111111);v.Push_back(11111111111111111);v.Push_back(11111111111111111);// 容量达到 4Print_container(v);v.Push_back(11111111111111111);// 触发第五次插入 - 触发 reserve 扩容若在reserve中使用的是memcpy- 会出现乱码// ❌ 源码隐患memcpy(tmp,_start,size()*sizeof(T));崩溃过程分解memcpy是按字节进行浅拷贝的。它只是把_start内部每个std::string对象的指针地址直接复制给了tmp。此时tmp里面的string对象与_start里面的string对象指向了同一块堆上的字符串文本内存。当执行delete[] _start;释放旧数组时旧数组中每一个string对象的析构函数会被调用从而释放了堆上的字符串文本。这导致新空间tmp里的每一个string对象的内部指针全部变成了野指针在接下来的访问或析构时程序必定遭遇崩溃野指针非法访问。8. 补充考点与核心避坑指南学习与看代码的规范顺序学习/模拟一个容器类时正确的看源码顺序是先看成员变量确认底层数据结构→ \rightarrow→再看构造函数确认初始化逻辑→ \rightarrow→最后看增删改查功能接口。模板类不可以将“声明”和“定义”分离写在.h和.cpp中模板在编译期需要根据调用的具体类型实例化代码。如果将定义写在.cpp中别的源码文件引用.h编译时看不到定义无法完成实例化最终会导致链接阶段Linking Error报错未定义的符号。解决方案模板类的声明与定义必须全部放在同一个头文件.h中。