想象你正在解决一道动态插入+随机访问的题目，如果用普通数组，每次插入都得O(n)挪动数据，而vector却能让你用push_back()轻松搞定，还能像数组一样a[i]秒查。这就是vector的魅力：兼顾动态扩容和随机访问，竞赛中简直是救场神库！
核心概念讲解
vector本质是动态数组，底层通过指针管理连续内存块：
[ | v0 | v1 | ... | vn-1 | ] ← capacity
size()：当前元素数量（
n）capacity()：预分配空间大小（总≥size）
resize(n)：调整大小，超出部分自动初始化（默认0）
扩容机制：当插入导致size > capacity时，vector会申请2倍新空间，复制旧数据并释放原内存（均摊时间复杂度O(1)！）。增长因子通常为2倍（具体取决于编译器），可通过reserve()自定义。
C++代码示例（含注释）
#include <bits/stdc++.h>
using namespace std;
int main() {
// 创建空vector（默认int类型）
vector<int> nums;
// 尾部插入（O(1)均摊时间）
for (int i = 1; i <= 10; ++i) {
nums.push_back(i * 2); // [2,4,...,20]
}
// 指定位置插入（注意：insert会导致后续迭代器失效！）
auto it = nums.begin() + 3; // 保存迭代器
nums.insert(it, 99); // [2,4,6,99,8,...]，此时it指向新插入元素
// 随机访问（O(1)，[]无边界检查，at()有越界异常）
cout << "nums[5] = " << nums.at(5) << endl;
cout << "nums[20] = " << nums[20] << endl; // 可能UB（未定义行为）
// 删除元素（pop_back是O(1)，其他位置删除都是O(n)）
nums.pop_back();
nums.erase(nums.begin()); // 删除第一个元素
// 遍历
for (auto x : nums) { // C++11范围for循环
cout << x << " ";
}
cout << endl;
// emplace_back vs push_back
nums.emplace_back(100); // 直接在原地构造，效率更高
nums.push_back(200); // 先构造临时对象再移动/拷贝
return 0;
}
算法分析
| 操作 | 时间复杂度 | 备注 |
|—————|——————|——————————-|
| push_back | O(1)均摊 | 实际扩容时为O(capacity) |
| insert/erase| O(n) | 涉及元素移动 |
| operator[] | O(1) | 无边界检查 |
| at() | O(1) | 有边界检查 |
| reserve(n) | O(n)（若需扩容） | 避免频繁扩容 |
| shrink_to_fit() | O(n) | 释放多余capacity |
适用场景：
✅ 高频尾部插入/删除
✅ 需要快速随机访问
✅ 未知数据量但需连续内存
局限性：
❌ 非尾部插入效率低（建议用list或链表）
❌ 频繁扩容浪费内存（可用reserve()预分配）
经典例题（修正后）
洛谷 P1046 《陶陶摘苹果》
思路：用vector存储苹果堆高度，模拟贪心取法，重点练习push_back和遍历。
CF 1462B 《Last Year’s Substring》
技巧：用vector存储字符串后缀，通过substr()高效提取子串，体现连续内存优势。
推荐练习（精选）
- 基础：洛谷 P1075 《校门外的树》（区间操作）
- 用vector存储树木位置，模拟砍树后的区间合并。
- 进阶：CF 1560B 《Who’s Opposite?》
- 用vector模拟圆桌座位交换，结合索引快速定位。
- 挑战：洛谷 P1908 【Hashing】
- 用vector模拟哈希表，处理冲突和动态扩容。
高级用法补充
emplace_back：直接在vector末尾构造对象，避免临时对象的移动/拷贝（尤其对复杂结构体）。shrink_to_fit()：释放多余的capacity，节省内存（如读取完文件后立即调用）。迭代器失效：在
insert/erase后，原有迭代器/引用会失效，必须重新获取。预分配优化：已知数据量大时，先用
reserve(n)避免多次扩容。
小结
记住：vector是竞赛中平衡速度与灵活性的首选容器，但要根据场景选择：
频繁中间操作？→ 考虑
list需要快速查找？→ 考虑
unordered_map
下期教你如何用vector玩转前缀和与差分——下期见！🚀