💻 上手代码
insert 和 erase 实战
#include <vector>
#include <iostream>int main() {std::vector<int> v = {1, 2, 3, 4, 5};// 在开头插入v.insert(v.begin(), 0); // [0,1,2,3,4,5]// 在下标 2 处插入v.insert(v.begin() + 2, 99); // [0,1,99,2,3,4,5]// 删除下标 3 的元素v.erase(v.begin() + 3); // [0,1,99,3,4,5]// 删除 [1, 3) 范围的元素v.erase(v.begin() + 1, v.begin() + 3); // [0,3,4,5]for (int x : v) std::cout << x << ' ';// 输出：0 3 4 5
}
reserve 的正确用法
std::vector<int> v;
v.reserve(1000); // 提前预留 1000 个位置// 之后 1000 次 push_back 都不会触发扩容
for (int i = 0; i < 1000; ++i)v.push_back(i); // 全部 O(1)，无额外拷贝开销
缩小容量：shrink_to_fit
C++11 引入了 shrink_to_fit：
std::vector<int> v(1000); // size=1000, capacity=1000
v.resize(10); // size=10, capacity 可能还是 1000
v.shrink_to_fit(); // 请求释放多余空间（不保证一定释放）
老派 trick（C++98 兼容）：
std::vector<int>(v).swap(v); // 用临时 vector 交换，强制紧缩
安全的删除模式
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};// 删除所有值为 2 的元素——正确方式
for (auto it = v.begin(); it != v.end(); ) {if (*it == 2)it = v.erase(it); // erase 返回下一个有效迭代器else++it;
}
// v: [1, 3, 4, 5]
⚠️ 经典错误写法：
for (auto it = v.begin(); it != v.end(); ++it)然后在里面erase(it)。erase 后it已失效，再++it就是未定义行为。
✍️ 练手题
题 1：去重（保持原序）
给定 vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}，删除所有重复元素，保持第一次出现的顺序。结果应为 {3, 1, 4, 5, 9, 2, 6}。
💡 提示：外层循环锁定当前元素为基准，内层循环在后面的部分查找并删除重复项。
题 2：性能对比实验
分别用 reserve 和不用的方式，向 vector 插入 100 万个元素。用 <chrono> 计时，看看差多少倍。
💡 提示：如果
int差距不明显，可以换成std::string，每次 push_back 一个长字符串。元素越重，扩容搬迁的代价越大，差距越明显。
#include <chrono>
auto start = std::chrono::high_resolution_clock::now();
// ... 你的代码 ...
auto end = std::chrono::high_resolution_clock::now();
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
题 3：实现一个简单的"撤销"功能
用 vector<int> 模拟一个支持撤销的列表。push_back 添加，undo 删除最后一个并保留在"回收站"里，redo 从回收站恢复最近一次撤销的元素。
⚠️ 注意：执行新的
push_back添加操作后，回收站应该清空（常规撤销功能都是这样——新操作让旧的撤销历史作废）。
❓ 自测 3 问
Q1：下面代码安全吗？
auto it = v.begin();
v.push_back(42);
std::cout << *it;
Q2：reserve(100) 后能不能直接用 v[50] = 42？为什么？
Q3：为什么扩容时通常选择 1.5 倍或 2 倍增长，而不是每次固定加 10 个？提示：从均摊复杂度角度分析。
点击查看答案
Q1：不安全。如果 push_back 触发扩容，it 指向的旧内存已被释放，*it 是未定义行为。
Q2：不能。reserve 只分配空间不创建元素，v[50] 访问的是不存在的元素。应该用 resize(100) 或先 push_back。
Q3：固定加 10 个的话，插入 n 个元素的均摊复杂度是 O(n²)（每次扩容拷贝得越来越多）。按倍数增长，均摊复杂度是 O(1)——因为扩容次数是指数级递减的（容量翻到 n 只需要约 log₂n 次扩容）。
📋 速查卡
| 项目 | 内容 |
|---|---|
| insert | 任意位置插入，O(n)，可引发扩容 |
| erase | 任意位置删除，O(n)，返回下一个有效迭代器 |
| reserve(n) | 预留空间，不创建元素。size() 不变，capacity() >= n |
| resize(n) | 改变元素数量。多则补默认值，少则截断 |
| 扩容策略 | 通常 1.5x 或 2x，均摊 O(1) |
| 移动优化 | 扩容搬迁时优先使用移动语义，减少深拷贝 |
| 迭代器失效 | 扩容 → 全部失效；insert/erase → 插入点/删除点之后失效 |
| 安全删除 | it = v.erase(it) 模式，不要 erase(it) 后 ++it |
| shrink_to_fit | 请求释放多余 capacity（C++11，不保证） |
| 下一课 | std::array |