C++ 中的 vector

核心特性与底层原理#

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

初始化与构造#

1
#include <vector>
2

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

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

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

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

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

容量与大小#

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

增删查改#

迭代器失效#

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

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

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

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

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

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

后果：

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

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

现代化操作#

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

3
// 删除所有偶数
4
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 内部元素的引用，一旦扩容，引用就变成悬空指针了。