目录前言一、vector 的核心结构1.1 简介作用1.2 【代码实现】核心结构定义1.3 新手坑点提醒二、默认成员函数实现2.1 无参构造函数简介作用【代码实现】无参构造函数2.2 带 n 个 val 的构造函数简介作用【代码实现】带 n 个 val 的构造函数新手坑点提醒2.3 迭代器区间构造简介作用【代码实现】迭代器区间构造2.4 拷贝构造函数【面试高频考点】简介作用【代码实现】拷贝构造函数深拷贝经典 Bug 和坑点2.5 析构函数简介作用【代码实现】析构函数2.6 赋值运算符重载【面试高频考点】简介作用【代码实现】传统写法【代码实现】现代写法推荐两种写法对比总结三、容量相关接口实现3.1 size()、capacity()、empty()简介作用【代码实现】基础容量查询3.2 reserve ()【面试高频考点】简介作用【代码实现】reserve 扩容函数经典 Bug 和坑点3.3 resize()简介作用【代码实现】resize 函数四、迭代器模拟实现4.1 简介作用4.2 【代码实现】迭代器定义与接口五、增删查改接口实现5.1 push_back () 尾插简介作用【代码实现】push_back 尾插5.2 pop_back () 尾删简介作用【代码实现】pop_back 尾删5.3 insert () 任意位置插入【面试高频考点】简介作用【代码实现】insert 插入函数5.4 erase () 删除元素【面试高频考点】简介作用【代码实现】erase 删除函数迭代器失效详解5.5 swap () 交换函数简介作用【代码实现】swap 交换函数5.6 operator [] 下标访问简介作用【代码实现】operator [] 重载六、常见问题与坑点总结6.1 深浅拷贝问题6.2 迭代器失效问题6.3 自赋值问题6.4 reserve 扩容的坑结语前言大家好我是你们的小小风呀临近期末小风不得不开始恶补学校课程了哎~~当初欠下的终究是要还的呀所以小风的博客只能不定时更新啦望大家理解小风也不想挂课呀言归正传 今天我们来到【从零开始学 C】专题的第十篇这篇可以说是 STL 容器学习的重中之重 ——vector 的模拟实现。为什么要模拟实现 vector因为这是面试必考题90% 的 C 面试都会问到能真正理解底层内存管理机制能搞懂深浅拷贝、迭代器失效这些 坑为学习其他容器打下坚实基础本文将手把手带你实现一个完整的 vector所有代码都可以直接运行所有面试重点我都会用【面试高频考点】标注出来。新手小白也能轻松看懂一、vector 的核心结构1.1 简介作用vector 本质上就是一个动态数组和普通数组的区别就是它可以自动扩容为了管理这个动态数组vector 内部用了三个指针来维护指针名作用大白话理解_start指向数组的起始位置数组的 头_finish指向最后一个有效元素的下一个位置数组的 尾巴_endofstorage指向整个容量的末尾位置数组的 天花板这三个指针的关系size() _finish - _start有效元素个数capacity() _endofstorage - _start总容量大小永远满足_start ≤ _finish ≤ _endofstorage1.2 【代码实现】核心结构定义#pragma once #include iostream #include assert.h using namespace std; namespace my_vector { templateclass T class vector { public: // 后面会实现各种成员函数... private: T* _start; // 指向数组起始位置 T* _finish; // 指向最后一个有效元素的下一个位置 T* _endofstorage; // 指向整个容量的末尾 }; }1.3 新手坑点提醒❌常见错误新手容易把_finish理解成 指向最后一个元素这是错的 ✅正确理解_finish指向的是最后一个元素的下一个位置这样设计是为了方便计算 size 和判断是否为空。二、默认成员函数实现2.1 无参构造函数简介作用创建一个空的 vector三个指针都初始化为 nullptr表示还没有分配任何内存。【代码实现】无参构造函数// 无参构造函数 vector() : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {}2.2 带 n 个 val 的构造函数简介作用创建一个 vector里面有 n 个值为 val 的元素。比如vectorint v(5, 10)就创建了 5 个 10。【代码实现】带 n 个 val 的构造函数// 带n个val的构造函数 vector(size_t n, const T val T()) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { // 先开n个空间 reserve(n); // 然后插入n个val for (size_t i 0; i n; i) { push_back(val); } } // 为了避免int类型的匹配问题再重载一个版本 vector(int n, const T val T()) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(n); for (int i 0; i n; i) { push_back(val); } }新手坑点提醒❌经典 Bug如果只写vector(size_t n, ...)当你写vectorint v(5, 10)时5 是 int 类型会优先匹配迭代器区间构造导致奇怪的错误 ✅解决方案重载一个 int 版本的构造函数。2.3 迭代器区间构造简介作用用另一个容器的迭代器区间来初始化 vector非常灵活可以接收各种容器的数据。【代码实现】迭代器区间构造// 迭代器区间构造模板函数 template class InputIterator vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { // 遍历迭代器区间一个个插入 while (first ! last) { push_back(*first); first; } }2.4 拷贝构造函数【面试高频考点】简介作用用一个已有的 vector 来创建新的 vector。这里必须深拷贝否则会出大问题什么是浅拷贝就是两个对象共用同一块内存一个释放了另一个就变成野指针了。什么是深拷贝重新开辟一块内存把数据完整复制过去两个对象互不干扰。【代码实现】拷贝构造函数深拷贝// 拷贝构造函数深拷贝 vector(const vectorT v) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { // 1. 先开辟和v一样大的空间 reserve(v.capacity()); // 2. 把数据一个个拷贝过来 for (auto e : v) { push_back(e); } }经典 Bug 和坑点❌浅拷贝的灾难如果不写拷贝构造编译器默认生成的是浅拷贝会导致两个对象析构时释放同一块内存double free一个对象修改数据会影响另一个对象程序直接崩溃✅记住只要涉及资源管理必须自己写深拷贝2.5 析构函数简介作用释放 vector 占用的内存把三个指针置空。【代码实现】析构函数// 析构函数 ~vector() { if (_start) { delete[] _start; _start nullptr; _finish nullptr; _endofstorage nullptr; } }2.6 赋值运算符重载【面试高频考点】简介作用实现v1 v2这样的赋值操作。这里有传统写法和现代写法两种面试经常对比【代码实现】传统写法// 赋值运算符重载 - 传统写法 vectorT operator(const vectorT v) { // 1. 防止自赋值v v if (this ! v) { // 2. 释放原来的空间 delete[] _start; // 3. 开辟新空间 _start new T[v.capacity()]; _finish _start; _endofstorage _start v.capacity(); // 4. 拷贝数据 for (size_t i 0; i v.size(); i) { *(_finish) v[i]; } } return *this; }【代码实现】现代写法推荐// 赋值运算符重载 - 现代写法简洁又安全 vectorT operator(vectorT v) // 注意这里是传值不是传引用 { // 直接交换就这么简单 swap(v); return *this; }两种写法对比总结对比项传统写法现代写法代码量多容易写错极少3 行搞定自赋值检查需要手动检查天然避免传值已经拷贝了一份异常安全可能异常new 失败异常安全拷贝失败不影响原对象推荐度⭐⭐⭐⭐⭐⭐⭐现代写法原理利用传值参数自动调用拷贝构造生成临时对象然后交换临时对象和 this 对象的资源临时对象出作用域自动析构 —— 完美三、容量相关接口实现3.1 size()、capacity()、empty()简介作用这三个是最基础的查询接口size()返回有效元素个数capacity()返回总容量大小empty()判断是否为空【代码实现】基础容量查询// 返回有效元素个数 size_t size() const { return _finish - _start; } // 返回总容量 size_t capacity() const { return _endofstorage - _start; } // 判断是否为空 bool empty() const { return _start _finish; }3.2 reserve ()【面试高频考点】简介作用扩容核心函数当空间不够时开辟更大的空间把旧数据移过去。扩容策略一般是按 2 倍扩容VS 下是 1.5 倍g 下是 2 倍。【代码实现】reserve 扩容函数// 扩容函数只扩不缩 void reserve(size_t n) { // 只有当n大于当前容量时才扩容 if (n capacity()) { // 1. 记录原来的有效元素个数很重要 size_t oldSize size(); // 2. 开辟新空间 T* tmp new T[n]; // 3. 拷贝旧数据到新空间 if (_start) // 原来有数据才拷贝 { for (size_t i 0; i oldSize; i) { tmp[i] _start[i]; } // 4. 释放旧空间 delete[] _start; } // 5. 更新三个指针 _start tmp; _finish _start oldSize; // 这里不能用size()_start已经变了 _endofstorage _start n; } }经典 Bug 和坑点❌致命错误_finish _start size()这样写会崩溃 因为计算size()的时候用的是新的_start减去旧的_finish结果完全错误✅正确做法扩容前先把oldSize保存下来3.3 resize()简介作用调整有效元素的个数如果 n size ()插入元素用默认值填充如果 n size ()删除尾部元素如果 n capacity ()先扩容再插入【代码实现】resize 函数// 调整有效元素个数 void resize(size_t n, const T val T()) { if (n size()) { // 情况1插入元素需要先检查扩容 reserve(n); while (_finish _start n) { *(_finish) val; } } else { // 情况2删除元素直接移动_finish指针 _finish _start n; } }四、迭代器模拟实现4.1 简介作用vector 的迭代器本质上就是原生指针因为 vector 的内存是连续的指针天然支持 、--、* 等操作。4.2 【代码实现】迭代器定义与接口public: // 正向迭代器就是原生指针 typedef T* iterator; typedef const T* const_iterator; // 普通迭代器接口 iterator begin() { return _start; } iterator end() { return _finish; } // const迭代器接口只读 const_iterator cbegin() const { return _start; } const_iterator cend() const { return _finish; }小知识有了迭代器范围 for 就自动支持了因为范围 for 底层就是用迭代器实现的。五、增删查改接口实现5.1 push_back () 尾插简介作用在 vector 尾部插入一个元素是最常用的接口。【代码实现】push_back 尾插// 尾插 void push_back(const T x) { // 1. 检查是否需要扩容 if (_finish _endofstorage) { size_t newCapacity capacity() 0 ? 4 : capacity() * 2; reserve(newCapacity); } // 2. 插入数据 *_finish x; _finish; }5.2 pop_back () 尾删简介作用删除 vector 的最后一个元素。【代码实现】pop_back 尾删// 尾删 void pop_back() { // 断言空vector不能尾删 assert(!empty()); _finish--; }5.3 insert () 任意位置插入【面试高频考点】简介作用在 pos 位置插入一个元素。这里最容易出现迭代器失效问题【代码实现】insert 插入函数// 在pos位置插入值为x的元素 iterator insert(iterator pos, const T x) { // 检查pos合法性 assert(pos _start); assert(pos _finish); // 1. 检查扩容这里会导致迭代器失效 if (_finish _endofstorage) { // 重点扩容前记录pos相对于_start的偏移量 size_t len pos - _start; size_t newCapacity capacity() 0 ? 4 : capacity() * 2; reserve(newCapacity); // 扩容后更新pos因为_start已经变了 pos _start len; } // 2. 挪动数据从后往前挪 iterator end _finish - 1; while (end pos) { *(end 1) *end; end--; } // 3. 插入数据 *pos x; _finish; return pos; // 返回新的迭代器解决失效问题 }❌为什么会失效因为扩容时_start指向了新的内存原来的 pos 还是指向旧内存变成野指针了✅解决方案扩容前记录pos - _start的偏移量扩容后用_start 偏移量重新计算 posinsert 函数返回新的迭代器给用户使用5.4 erase () 删除元素【面试高频考点】简介作用删除 pos 位置的元素。同样存在迭代器失效问题【代码实现】erase 删除函数// 删除pos位置的元素 iterator erase(iterator pos) { // 检查pos合法性 assert(pos _start); assert(pos _finish); // 1. 挪动数据覆盖从前往后挪 iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } _finish--; return pos; // 返回删除位置的下一个元素的迭代器 }迭代器失效详解❌经典错误// 错误写法erase后it失效了再会崩溃 for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) v.erase(it); }✅正确写法// 正确写法用erase的返回值更新迭代器 for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) it v.erase(it); // 接收返回值 else it; }5.5 swap () 交换函数简介作用交换两个 vector 的内容效率极高 —— 只需要交换三个指针就行【代码实现】swap 交换函数// 交换两个vector void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }5.6 operator [] 下标访问简介作用像数组一样用[]访问元素需要提供普通版本和 const 版本。【代码实现】operator [] 重载// 普通版本可读可写 T operator[](size_t pos) { assert(pos size()); return _start[pos]; } // const版本只读 const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; }六、常见问题与坑点总结6.1 深浅拷贝问题问题表现两个 vector 指向同一块内存析构时 double free 崩溃。根本原因默认拷贝构造是浅拷贝只复制指针不复制内容。解决方案自己实现深拷贝的拷贝构造和赋值重载。6.2 迭代器失效问题两种失效场景insert/erase 导致的失效插入删除后原来的迭代器指向的位置已经无效扩容导致的失效扩容后内存地址变了所有旧迭代器都变成野指针解决方案永远使用 insert/erase 的返回值来更新迭代器扩容后不要使用之前保存的迭代器6.3 自赋值问题问题表现v v自己赋值给自己传统写法中会先释放内存再拷贝结果拷贝的是已经释放的内存。解决方案传统写法加上if (this ! v)判断现代写法天然避免推荐使用6.4 reserve 扩容的坑经典错误忘记保存 oldSize直接用_finish _start size()导致指针计算错误。记住凡是涉及_start 变化的地方都要先保存偏移量结语恭喜你到这里一个完整的 vector 就实现完毕了回顾一下今天的【面试高频考点】✅ 深拷贝的实现拷贝构造、赋值重载✅ 赋值重载的传统写法 vs 现代写法✅ reserve 扩容逻辑✅ insert/erase 的迭代器失效处理这四个点面试 10 次有 9 次会问到建议大家亲手把代码敲一遍理解才会更深刻。下一篇我们将继续学习 list 的模拟实现敬请期待如果这篇文章对你有帮助别忘了点赞收藏关注三连哦
de风——【从零开始学 C++】（十）vector的模拟实现
目录前言一、vector 的核心结构1.1 简介作用1.2 【代码实现】核心结构定义1.3 新手坑点提醒二、默认成员函数实现2.1 无参构造函数简介作用【代码实现】无参构造函数2.2 带 n 个 val 的构造函数简介作用【代码实现】带 n 个 val 的构造函数新手坑点提醒2.3 迭代器区间构造简介作用【代码实现】迭代器区间构造2.4 拷贝构造函数【面试高频考点】简介作用【代码实现】拷贝构造函数深拷贝经典 Bug 和坑点2.5 析构函数简介作用【代码实现】析构函数2.6 赋值运算符重载【面试高频考点】简介作用【代码实现】传统写法【代码实现】现代写法推荐两种写法对比总结三、容量相关接口实现3.1 size()、capacity()、empty()简介作用【代码实现】基础容量查询3.2 reserve ()【面试高频考点】简介作用【代码实现】reserve 扩容函数经典 Bug 和坑点3.3 resize()简介作用【代码实现】resize 函数四、迭代器模拟实现4.1 简介作用4.2 【代码实现】迭代器定义与接口五、增删查改接口实现5.1 push_back () 尾插简介作用【代码实现】push_back 尾插5.2 pop_back () 尾删简介作用【代码实现】pop_back 尾删5.3 insert () 任意位置插入【面试高频考点】简介作用【代码实现】insert 插入函数5.4 erase () 删除元素【面试高频考点】简介作用【代码实现】erase 删除函数迭代器失效详解5.5 swap () 交换函数简介作用【代码实现】swap 交换函数5.6 operator [] 下标访问简介作用【代码实现】operator [] 重载六、常见问题与坑点总结6.1 深浅拷贝问题6.2 迭代器失效问题6.3 自赋值问题6.4 reserve 扩容的坑结语前言大家好我是你们的小小风呀临近期末小风不得不开始恶补学校课程了哎~~当初欠下的终究是要还的呀所以小风的博客只能不定时更新啦望大家理解小风也不想挂课呀言归正传 今天我们来到【从零开始学 C】专题的第十篇这篇可以说是 STL 容器学习的重中之重 ——vector 的模拟实现。为什么要模拟实现 vector因为这是面试必考题90% 的 C 面试都会问到能真正理解底层内存管理机制能搞懂深浅拷贝、迭代器失效这些 坑为学习其他容器打下坚实基础本文将手把手带你实现一个完整的 vector所有代码都可以直接运行所有面试重点我都会用【面试高频考点】标注出来。新手小白也能轻松看懂一、vector 的核心结构1.1 简介作用vector 本质上就是一个动态数组和普通数组的区别就是它可以自动扩容为了管理这个动态数组vector 内部用了三个指针来维护指针名作用大白话理解_start指向数组的起始位置数组的 头_finish指向最后一个有效元素的下一个位置数组的 尾巴_endofstorage指向整个容量的末尾位置数组的 天花板这三个指针的关系size() _finish - _start有效元素个数capacity() _endofstorage - _start总容量大小永远满足_start ≤ _finish ≤ _endofstorage1.2 【代码实现】核心结构定义#pragma once #include iostream #include assert.h using namespace std; namespace my_vector { templateclass T class vector { public: // 后面会实现各种成员函数... private: T* _start; // 指向数组起始位置 T* _finish; // 指向最后一个有效元素的下一个位置 T* _endofstorage; // 指向整个容量的末尾 }; }1.3 新手坑点提醒❌常见错误新手容易把_finish理解成 指向最后一个元素这是错的 ✅正确理解_finish指向的是最后一个元素的下一个位置这样设计是为了方便计算 size 和判断是否为空。二、默认成员函数实现2.1 无参构造函数简介作用创建一个空的 vector三个指针都初始化为 nullptr表示还没有分配任何内存。【代码实现】无参构造函数// 无参构造函数 vector() : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {}2.2 带 n 个 val 的构造函数简介作用创建一个 vector里面有 n 个值为 val 的元素。比如vectorint v(5, 10)就创建了 5 个 10。【代码实现】带 n 个 val 的构造函数// 带n个val的构造函数 vector(size_t n, const T val T()) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { // 先开n个空间 reserve(n); // 然后插入n个val for (size_t i 0; i n; i) { push_back(val); } } // 为了避免int类型的匹配问题再重载一个版本 vector(int n, const T val T()) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(n); for (int i 0; i n; i) { push_back(val); } }新手坑点提醒❌经典 Bug如果只写vector(size_t n, ...)当你写vectorint v(5, 10)时5 是 int 类型会优先匹配迭代器区间构造导致奇怪的错误 ✅解决方案重载一个 int 版本的构造函数。2.3 迭代器区间构造简介作用用另一个容器的迭代器区间来初始化 vector非常灵活可以接收各种容器的数据。【代码实现】迭代器区间构造// 迭代器区间构造模板函数 template class InputIterator vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { // 遍历迭代器区间一个个插入 while (first ! last) { push_back(*first); first; } }2.4 拷贝构造函数【面试高频考点】简介作用用一个已有的 vector 来创建新的 vector。这里必须深拷贝否则会出大问题什么是浅拷贝就是两个对象共用同一块内存一个释放了另一个就变成野指针了。什么是深拷贝重新开辟一块内存把数据完整复制过去两个对象互不干扰。【代码实现】拷贝构造函数深拷贝// 拷贝构造函数深拷贝 vector(const vectorT v) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { // 1. 先开辟和v一样大的空间 reserve(v.capacity()); // 2. 把数据一个个拷贝过来 for (auto e : v) { push_back(e); } }经典 Bug 和坑点❌浅拷贝的灾难如果不写拷贝构造编译器默认生成的是浅拷贝会导致两个对象析构时释放同一块内存double free一个对象修改数据会影响另一个对象程序直接崩溃✅记住只要涉及资源管理必须自己写深拷贝2.5 析构函数简介作用释放 vector 占用的内存把三个指针置空。【代码实现】析构函数// 析构函数 ~vector() { if (_start) { delete[] _start; _start nullptr; _finish nullptr; _endofstorage nullptr; } }2.6 赋值运算符重载【面试高频考点】简介作用实现v1 v2这样的赋值操作。这里有传统写法和现代写法两种面试经常对比【代码实现】传统写法// 赋值运算符重载 - 传统写法 vectorT operator(const vectorT v) { // 1. 防止自赋值v v if (this ! v) { // 2. 释放原来的空间 delete[] _start; // 3. 开辟新空间 _start new T[v.capacity()]; _finish _start; _endofstorage _start v.capacity(); // 4. 拷贝数据 for (size_t i 0; i v.size(); i) { *(_finish) v[i]; } } return *this; }【代码实现】现代写法推荐// 赋值运算符重载 - 现代写法简洁又安全 vectorT operator(vectorT v) // 注意这里是传值不是传引用 { // 直接交换就这么简单 swap(v); return *this; }两种写法对比总结对比项传统写法现代写法代码量多容易写错极少3 行搞定自赋值检查需要手动检查天然避免传值已经拷贝了一份异常安全可能异常new 失败异常安全拷贝失败不影响原对象推荐度⭐⭐⭐⭐⭐⭐⭐现代写法原理利用传值参数自动调用拷贝构造生成临时对象然后交换临时对象和 this 对象的资源临时对象出作用域自动析构 —— 完美三、容量相关接口实现3.1 size()、capacity()、empty()简介作用这三个是最基础的查询接口size()返回有效元素个数capacity()返回总容量大小empty()判断是否为空【代码实现】基础容量查询// 返回有效元素个数 size_t size() const { return _finish - _start; } // 返回总容量 size_t capacity() const { return _endofstorage - _start; } // 判断是否为空 bool empty() const { return _start _finish; }3.2 reserve ()【面试高频考点】简介作用扩容核心函数当空间不够时开辟更大的空间把旧数据移过去。扩容策略一般是按 2 倍扩容VS 下是 1.5 倍g 下是 2 倍。【代码实现】reserve 扩容函数// 扩容函数只扩不缩 void reserve(size_t n) { // 只有当n大于当前容量时才扩容 if (n capacity()) { // 1. 记录原来的有效元素个数很重要 size_t oldSize size(); // 2. 开辟新空间 T* tmp new T[n]; // 3. 拷贝旧数据到新空间 if (_start) // 原来有数据才拷贝 { for (size_t i 0; i oldSize; i) { tmp[i] _start[i]; } // 4. 释放旧空间 delete[] _start; } // 5. 更新三个指针 _start tmp; _finish _start oldSize; // 这里不能用size()_start已经变了 _endofstorage _start n; } }经典 Bug 和坑点❌致命错误_finish _start size()这样写会崩溃 因为计算size()的时候用的是新的_start减去旧的_finish结果完全错误✅正确做法扩容前先把oldSize保存下来3.3 resize()简介作用调整有效元素的个数如果 n size ()插入元素用默认值填充如果 n size ()删除尾部元素如果 n capacity ()先扩容再插入【代码实现】resize 函数// 调整有效元素个数 void resize(size_t n, const T val T()) { if (n size()) { // 情况1插入元素需要先检查扩容 reserve(n); while (_finish _start n) { *(_finish) val; } } else { // 情况2删除元素直接移动_finish指针 _finish _start n; } }四、迭代器模拟实现4.1 简介作用vector 的迭代器本质上就是原生指针因为 vector 的内存是连续的指针天然支持 、--、* 等操作。4.2 【代码实现】迭代器定义与接口public: // 正向迭代器就是原生指针 typedef T* iterator; typedef const T* const_iterator; // 普通迭代器接口 iterator begin() { return _start; } iterator end() { return _finish; } // const迭代器接口只读 const_iterator cbegin() const { return _start; } const_iterator cend() const { return _finish; }小知识有了迭代器范围 for 就自动支持了因为范围 for 底层就是用迭代器实现的。五、增删查改接口实现5.1 push_back () 尾插简介作用在 vector 尾部插入一个元素是最常用的接口。【代码实现】push_back 尾插// 尾插 void push_back(const T x) { // 1. 检查是否需要扩容 if (_finish _endofstorage) { size_t newCapacity capacity() 0 ? 4 : capacity() * 2; reserve(newCapacity); } // 2. 插入数据 *_finish x; _finish; }5.2 pop_back () 尾删简介作用删除 vector 的最后一个元素。【代码实现】pop_back 尾删// 尾删 void pop_back() { // 断言空vector不能尾删 assert(!empty()); _finish--; }5.3 insert () 任意位置插入【面试高频考点】简介作用在 pos 位置插入一个元素。这里最容易出现迭代器失效问题【代码实现】insert 插入函数// 在pos位置插入值为x的元素 iterator insert(iterator pos, const T x) { // 检查pos合法性 assert(pos _start); assert(pos _finish); // 1. 检查扩容这里会导致迭代器失效 if (_finish _endofstorage) { // 重点扩容前记录pos相对于_start的偏移量 size_t len pos - _start; size_t newCapacity capacity() 0 ? 4 : capacity() * 2; reserve(newCapacity); // 扩容后更新pos因为_start已经变了 pos _start len; } // 2. 挪动数据从后往前挪 iterator end _finish - 1; while (end pos) { *(end 1) *end; end--; } // 3. 插入数据 *pos x; _finish; return pos; // 返回新的迭代器解决失效问题 }❌为什么会失效因为扩容时_start指向了新的内存原来的 pos 还是指向旧内存变成野指针了✅解决方案扩容前记录pos - _start的偏移量扩容后用_start 偏移量重新计算 posinsert 函数返回新的迭代器给用户使用5.4 erase () 删除元素【面试高频考点】简介作用删除 pos 位置的元素。同样存在迭代器失效问题【代码实现】erase 删除函数// 删除pos位置的元素 iterator erase(iterator pos) { // 检查pos合法性 assert(pos _start); assert(pos _finish); // 1. 挪动数据覆盖从前往后挪 iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } _finish--; return pos; // 返回删除位置的下一个元素的迭代器 }迭代器失效详解❌经典错误// 错误写法erase后it失效了再会崩溃 for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) v.erase(it); }✅正确写法// 正确写法用erase的返回值更新迭代器 for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) it v.erase(it); // 接收返回值 else it; }5.5 swap () 交换函数简介作用交换两个 vector 的内容效率极高 —— 只需要交换三个指针就行【代码实现】swap 交换函数// 交换两个vector void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }5.6 operator [] 下标访问简介作用像数组一样用[]访问元素需要提供普通版本和 const 版本。【代码实现】operator [] 重载// 普通版本可读可写 T operator[](size_t pos) { assert(pos size()); return _start[pos]; } // const版本只读 const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; }六、常见问题与坑点总结6.1 深浅拷贝问题问题表现两个 vector 指向同一块内存析构时 double free 崩溃。根本原因默认拷贝构造是浅拷贝只复制指针不复制内容。解决方案自己实现深拷贝的拷贝构造和赋值重载。6.2 迭代器失效问题两种失效场景insert/erase 导致的失效插入删除后原来的迭代器指向的位置已经无效扩容导致的失效扩容后内存地址变了所有旧迭代器都变成野指针解决方案永远使用 insert/erase 的返回值来更新迭代器扩容后不要使用之前保存的迭代器6.3 自赋值问题问题表现v v自己赋值给自己传统写法中会先释放内存再拷贝结果拷贝的是已经释放的内存。解决方案传统写法加上if (this ! v)判断现代写法天然避免推荐使用6.4 reserve 扩容的坑经典错误忘记保存 oldSize直接用_finish _start size()导致指针计算错误。记住凡是涉及_start 变化的地方都要先保存偏移量结语恭喜你到这里一个完整的 vector 就实现完毕了回顾一下今天的【面试高频考点】✅ 深拷贝的实现拷贝构造、赋值重载✅ 赋值重载的传统写法 vs 现代写法✅ reserve 扩容逻辑✅ insert/erase 的迭代器失效处理这四个点面试 10 次有 9 次会问到建议大家亲手把代码敲一遍理解才会更深刻。下一篇我们将继续学习 list 的模拟实现敬请期待如果这篇文章对你有帮助别忘了点赞收藏关注三连哦
