💻 上手代码

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 个？提示：从均摊复杂度角度分析。

📋 速查卡