C++第九讲:vector
C第九讲vectorvector 是STL 中最常用的序列式容器本质是一个动态数组彻底解决了 C 语言静态数组大小固定、手动管理内存的痛点。它支持随机访问、自动扩容是所有 C 开发者日常开发的首选容器也是面试第一高频考点。一、vector 简介1. 什么是 vectorvector 是 C 标准库提供的动态数组容器可以存储任意类型的元素底层是一段连续的内存空间。自动管理内存不需要手动申请 / 释放空间支持随机访问通过[]像数组一样访问元素时间复杂度 O (1)自动扩容当空间不足时自动申请更大的空间并拷贝元素丰富的接口提供了增删查改等常用操作2. 为什么不用 C 语言数组对比项C 语言静态数组C 语言动态数组C vector大小编译时固定不能改变运行时可改但手动管理自动扩容无需手动管理内存管理栈上自动释放堆上手动 malloc/free自动申请释放无内存泄漏越界检查无越界可能崩溃无部分编译器支持越界检查接口无需要自己实现无提供丰富的增删查改接口二、vector 常用接口重点使用 vector 需要包含头文件#include vector所有接口都在std命名空间中。1. 构造函数4 个最常用构造函数功能说明示例vectorT()无参构造创建空 vectorvectorint v1;vectorT(size_t n, const T val T())构造 n 个值为 val 的元素vectorint v2(5, 10); // 5个10vectorT(const vectorT v)拷贝构造vectorint v3(v2);vectorT(InputIterator first, InputIterator last)用迭代器区间构造vectorint v4(v2.begin(), v2.end());代码示例#include iostream #include vector using namespace std; ​ int main() { vectorint v1; // 空vector vectorint v2(5, 10); // 5个10 vectorint v3(v2); // 拷贝v2 vectorint v4(v2.begin(), v2.begin()3); // 前3个元素10,10,10 ​ // 用数组构造 int arr[] {1,2,3,4,5}; vectorint v5(arr, arrsizeof(arr)/sizeof(int)); ​ return 0; }2. 容量操作面试高频函数功能说明注意事项size_t size() const返回有效元素个数size_t capacity() const返回总容量能存多少元素容量≥sizebool empty() const判断是否为空空返回 truevoid reserve(size_t n)预留 n 个元素的空间✅ 只改容量不改 size提前预留避免频繁扩容void resize(size_t n, const T val T())把有效元素改为 n 个nsize用 val 填充nsize截断可能改变容量核心考点vector 的扩容机制当 vector 的 size 达到 capacity 时再插入元素会触发自动扩容申请一块更大的新空间VS 按1.5 倍扩容G 按2 倍扩容将旧空间的元素拷贝到新空间释放旧空间更新指针指向新空间代码验证扩容倍数void TestExpand() { vectorint v; size_t sz v.capacity(); cout 初始容量 sz endl; for (int i0; i100; i) { v.push_back(i); if (sz ! v.capacity()) { sz v.capacity(); cout 扩容到 sz endl; } } }VS 输出1→2→3→4→6→9→13→19→28→42→63→94→1411.5 倍G 输出1→2→4→8→16→32→64→1282 倍优化技巧提前 reserve 预留空间如果知道大概要存储多少元素提前用reserve预留空间避免频繁扩容扩容会拷贝元素效率低vectorint v; v.reserve(100); // 提前预留100个元素空间 for (int i0; i100; i) { v.push_back(i); // 不会触发扩容 }3. 增删查改操作函数功能说明时间复杂度void push_back(const T val)尾插元素O (1)扩容时 O (n)void pop_back()尾删元素O(1)iterator insert(iterator pos, const T val)在 pos 位置插入 valO (n)需要搬移元素iterator erase(iterator pos)删除 pos 位置的元素O (n)需要搬移元素void swap(vectorT v)交换两个 vector 的底层空间O (1)只交换指针T operator[](size_t pos)访问 pos 位置的元素O(1)注意find 不是 vector 的成员函数查找元素需要使用algorithm头文件中的find算法#include algorithm vectorint v {1,2,3,4,5}; // 查找3返回迭代器找不到返回v.end() auto it find(v.begin(), v.end(), 3); if (it ! v.end()) { cout 找到了 *it endl; }4. 迭代器vector 的迭代器本质是原生指针支持 、--、*、- 等操作。迭代器功能说明begin()/end()正向迭代器begin 指向第一个元素end 指向最后一个元素的下一个位置rbegin()/rend()反向迭代器rbegin 指向最后一个元素rend 指向第一个元素的前一个位置cbegin()/cend()const 正向迭代器只读代码示例三种遍历方式int main() { vectorint v {1,2,3,4,5}; ​ // 1. []访问推荐最简洁 for (int i0; iv.size(); i) { cout v[i] ; } cout endl; ​ // 2. 迭代器 vectorint::iterator it v.begin(); while (it ! v.end()) { cout *it ; it; } cout endl; ​ // 3. 范围forC11推荐 for (auto e : v) { cout e ; } cout endl; ​ return 0; }三、核心难点迭代器失效面试必考1. 什么是迭代器失效vector 的迭代器本质是指向底层数组的指针当底层空间被释放或元素位置发生改变时原来的迭代器就会变成野指针继续使用会导致程序崩溃或结果错误。2. 两种导致迭代器失效的场景场景 1底层空间改变扩容所有会导致扩容的操作都会使迭代器失效reserve、resize、insert、push_back、assign等。错误示例int main() { vectorint v {1,2,3,4,5}; auto it v.begin(); cout 扩容前容量 v.capacity() endl; // 5 ​ // 触发扩容旧空间被释放it变成野指针 v.reserve(100); cout 扩容后容量 v.capacity() endl; // 100 ​ // 错误使用失效的迭代器VS下直接崩溃G下结果错误 while (it ! v.end()) { cout *it ; it; } return 0; }场景 2指定位置删除元素erase删除 pos 位置的元素后pos 后面的元素会往前搬移导致pos 及之后的迭代器失效VS 下严格检测G 下部分情况可能运行但结果错误。错误示例删除所有偶数// 错误写法 int main() { vectorint v {1,2,3,4}; auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) { v.erase(it); // 删除后it失效 } it; // 访问失效的迭代器崩溃 } return 0; }正确写法erase会返回删除元素的下一个位置的迭代器用这个返回值更新 it// 正确写法 int main() { vectorint v {1,2,3,4}; auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) { it v.erase(it); // 用返回值更新it } else { it; } } return 0; }3. 迭代器失效的解决方法所有可能导致迭代器失效的操作后重新获取迭代器。扩容后重新调用begin()获取新的迭代器erase 后使用erase返回的迭代器四、vector 底层原理与模拟实现1. 底层结构vector 的底层非常简单只有三个指针_start指向数组的起始位置_finish指向最后一个有效元素的下一个位置_endofstorage指向数组容量的末尾位置templateclass T class vector { private: T* _start; T* _finish; T* _endofstorage; };核心关系size() _finish - _startcapacity() _endofstorage - _start2. 模拟实现核心函数2.1 构造与析构templateclass T class vector { public: // 无参构造 vector() : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} // 构造n个val vector(size_t n, const T val T()) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(n); for (size_t i0; in; i) { push_back(val); } } // 拷贝构造深拷贝 vector(const vectorT v) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (const auto e : v) { push_back(e); } } // 赋值运算符重载现代版 vectorT operator(vectorT v) { swap(v); return *this; } // 析构函数 ~vector() { if (_start) { delete[] _start; _start _finish _endofstorage nullptr; } } // 交换两个vector void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } // ... 其他成员函数 private: T* _start; T* _finish; T* _endofstorage; };2.2 容量操作reservevoid reserve(size_t n) { if (n capacity()) { size_t oldSize size(); // 1. 申请新空间 T* tmp new T[n]; // 2. 拷贝元素不能用memcpy自定义类型会浅拷贝 for (size_t i0; ioldSize; i) { tmp[i] _start[i]; } // 3. 释放旧空间 delete[] _start; // 4. 更新指针 _start tmp; _finish _start oldSize; _endofstorage _start n; } }易错点不能用 memcpy 拷贝自定义类型memcpy 是浅拷贝如果 vector 存储的是 string、vector 等自定义类型memcpy 会导致多个对象共享同一块内存析构时重复释放崩溃。必须用赋值运算符进行深拷贝。2.3 尾插push_backvoid push_back(const T val) { // 空间满了就扩容 if (_finish _endofstorage) { size_t newCapacity capacity() 0 ? 4 : capacity() * 2; reserve(newCapacity); } // 尾插元素 *_finish val; _finish; }2.4 访问与迭代器T operator[](size_t pos) { assert(pos size()); return _start[pos]; } const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; } iterator begin() { return _start; } iterator end() { return _finish; }五、动态二维数组vectorvectorTvector 可以嵌套使用实现动态二维数组比 C 语言的二维数组更灵活。1. 原理vectorvectorint vv(n)表示一个包含 n 个vectorint的 vector每个元素都是一个独立的 vector。2. 示例杨辉三角class Solution { public: vectorvectorint generate(int numRows) { // 创建numRows行的二维数组 vectorvectorint vv(numRows); // 每行的元素个数等于行号1初始化为1 for (int i0; inumRows; i) { vv[i].resize(i1, 1); } // 填充中间元素第i行第j列 第i-1行第j列 第i-1行第j-1列 for (int i2; inumRows; i) { for (int j1; ji; j) { vv[i][j] vv[i-1][j] vv[i-1][j-1]; } } return vv; } };六、经典 OJ 实战1. 只出现一次的数字// 要求线性时间复杂度不使用额外空间 class Solution { public: int singleNumber(vectorint nums) { int res 0; for (int e : nums) { res ^ e; // 异或相同为0不同为1 } return res; } };2. 删除排序数组中的重复项// 要求原地修改空间复杂度O(1) class Solution { public: int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast1; fastnums.size(); fast) { if (nums[fast] ! nums[slow]) { nums[slow] nums[fast]; } } return slow 1; } };七、本章核心总结vector 是动态数组底层是连续内存支持随机访问自动扩容扩容机制VS1.5 倍G2 倍提前 reserve 可优化性能迭代器失效扩容和 erase 会导致失效解决方法是操作后重新获取迭代器模拟实现核心是三个指针深拷贝避免浅拷贝问题不能用 memcpy 拷贝自定义类型常用接口push_back、pop_back、operator []、reserve、resize、迭代器

相关新闻

操作系统EAL4+认证的范围界定与实战策略

操作系统EAL4+认证的范围界定与实战策略

1. 操作系统EAL4认证的核心挑战与范围界定价值 在信息技术安全领域,EAL4认证是Common Criteria(通用准则)评估体系中公认的"高保障级"门槛。我参与过三个操作系统内核的认证项目,深刻体会到范围界定(Scope D…

2026/11/1 7:44:41 阅读更多 →
如何在Zotero 7+中高效管理插件:智能插件市场全面指南

如何在Zotero 7+中高效管理插件:智能插件市场全面指南

如何在Zotero 7中高效管理插件:智能插件市场全面指南 【免费下载链接】zotero-addons Zotero Add-on Market | Zotero插件市场 | Browsing and installing plugins within Zotero 项目地址: https://gitcode.com/gh_mirrors/zo/zotero-addons Zotero插件市场…

2026/11/17 1:44:16 阅读更多 →
福州看诊多动症注意力问题哪家医院靠谱

福州看诊多动症注意力问题哪家医院靠谱

不少福州学龄儿童家长都有类似的困惑:孩子上课坐不住、写作业磨磨蹭蹭,到底是天性好动还是多动症?就诊时怎么选专业机构才能少走弯路?近年来公众对注意缺陷多动障碍(俗称多动症)的认知度不断提升&#xff0…

2026/11/13 13:06:01 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻