C++ 中的 vector

std::vector 是 C++ 中最重要、最常用的容器，没有之一。它的本质是动态数组（Dynamic Array）。

std::vector 是在堆（Heap）上管理一块连续的内存，可以存放任意类型的对象。

核心特性与底层原理

• 头文件：#include <vector>
• 内存模型：连续内存。这意味着它和 C 数组一样，支持通过指针偏移量快速访问，并且对 CPU 缓存（Cache）非常友好。
• 自动扩容：当存入数据量超过当前容量时，std::vector 就会申请一块更大的内存（通常是原来的 1.5 倍或 2 倍），将旧数据移动/拷贝过去，然后释放旧内存。

初始化与构造

#include <vector>

// 1. 默认构造（空 vector）
std::vector<int> v1;

// 2. 指定大小和默认值
std::vector<int> v2(10);        // 10 个元素，默认初始化 0
std::vector<int> v3(10, 5);     // 10 个元素，每个都是 5

// 3. 列表初始化（C++11）
std::vector<int> v4 = {1, 2, 3, 4};

// 4. 拷贝构造
std::vector<int> v5(v4);

// 5. 迭代器范围构造（常用与从其他容器拷贝）
int arr[] = {10, 20, 30}
std::vector<int> v6(arr, arr + 3);

容量与大小

函数	说明	备注
size()	当前元素个数	实际存了多少个
capacity()	当前分配的内存能存多少个	capacity $\geqslant$ size
empty()	是否为空	推荐使用，比 size() == 0 更语义化
reserve()	预分配内存	仅改变 capacity，不改变 size
resize(n)	改变元素个数	改变 size，如果变大则填充默认值
shrink_to_fit()	释放未使用的内存（C++11）	让 capacity 搜索到 size 大小

为什么 reserve 非常重要？

std::vector<int> v;
v.reserve(1000); // 一次性分配好内存
for (int i = 0; i < 1000; i++) {
    v.push_back(i); // 这里不会再发生内存重新分配，效率极高
}

增删查改

插入与添加

• push_back(val)：在尾部添加元素（会发生拷贝或移动）。
• emplace_back(arg...)（C++11）：原地构造。直接在 std::vector 尾部构造对象，省去了一次临时对象的构造和拷贝 / 移动，效率通常更高。
• insert(it, val)：在迭代器指向的位置插入。效率为 $O(N)$，因为要移动后续所有元素。

删除

• pop_back：删除尾部元素（$O(1)$）。
• erase(it)：删除指定位置元素（$O(N)$，后续元素前移）。
• clear()：清空所有元素，szie 变为 0，但 capacity 通常不变（内存不释放）。

访问

• v[i]：下标访问，不检查越界。
• v.at[i]：检查越界，越觉抛 std::out_of_range。
• v.front() / v.back()：访问首尾。
• v.data()：返回指向底层数组首元素的指针（T*）。常用于和 C 语言 API 交互。

迭代器失效

由于 std::vector 是连续内存，当结构发生变化时，指向旧内存的迭代器、指针、引用可能会失效。

1. 扩容时失效：当 push_back 导致 std::vector 扩容（reallocate）时，原内存被释放，所有指向原数据的迭代器 / 指针瞬间全部失效。
2. 插入 / 删除时失效：当 insert 或 erase 一个位置时，该位置之后的所有迭代器都会失效（因为数据移动了）。

std::vector<int> v = {1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it); // 错误！erase 后 it 已失效，下一次 ++it 会崩溃
    }
}

// 正确写法（利用 erase 返回值更新迭代器）
for (auto it =  v.begin(); it != v.end()) {
    if (*it % 2 == 0) {
        it = v.erase(it); // erase 返回指向下一个元素的迭代器
    } else {
        ++it;
    }
}

特殊版本：std::vector<bool>

这是一个历史遗留的 “坑”。为了节省空间，C++ 标准库特化了 std::vector<bool>，它不是存储 bool（1 字节），而是存储 bit（1 比特）。

后果：

• 你无法获得元素的地址：&v[0] 是非法的，因为无法寻址单个比特。
• 它的 operator[] 返回的不是 bool&，而是一个代理对象。
• 非线程安全：并发读写邻近的 bit 可能会导致数据竞争（因为它们位于同一个字节内）。

建议：如果需要存布尔值且不缺那点内存，用 std::vector<char> 或 std::deque<bool> 代替。如果确实需要位操作，考虑使用 std::bitset。

现代化操作

C++20：std::erase 和 std::erase_if

在 C++20 之前，要从 std::vector 中删除满足特定条件的所以元素，需要使用 “Erase-Remove Idiom”（v.erase(std::remove(...), v.end()），非常啰嗦。

C++20 简化了：

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// 删除所有偶数
std::erase_if(v, [](int x) { return x % 2 == 0; });

最佳实践

1. 优先使用 emplace_back：代替 push_back，特别是存放复杂对象时。
2. 善用 reserve：如果你能预估数据量，一定要先 reserve，在数据量较大时，能够极大的优化性能。
3. 避免头部/中间插入：在 std::vector 头部插入数据（insert(begin(), val)）是非常慢的（$O(N)$），如果有这种需求，请改用 std::deque 或 std::list。
4. 慎用 std::vector<bool>：除非你清楚你自己在做什么。
5. 小心引用失效：在循环中做 push_back 时，千万不要同时持有指向该 std::vector 内部元素的引用，一旦扩容，引用就变成悬空指针了。