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、迭代器