vector 是动态数组，底层是一段连续的内存空间。
1
2
3
4
| ┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
size = 4 capacity = 8
|
- size：当前元素个数
- capacity：实际分配的内存容量
- 当
size == capacity 时再插入，会触发扩容
- 重新分配一块更大的内存（通常 1.5 倍或 2 倍）
- 把旧元素全部拷贝/移动到新内存
- 释放旧内存
- 更新内部指针
GCC 是 2 倍扩容，VS 是 1.5 倍扩容。
- 均摊 O(1)：大部分插入是 O(1)，偶尔扩容 O(n)，平均下来还是 O(1)
1
2
| vector<int> v;
v.reserve(1000); // 提前分配 1000 容量，避免中途扩容
|
1. 插入操作（push_back, insert）
- 触发扩容 → 所有迭代器、引用、指针全部失效
- 没扩容 → 插入位置之后的迭代器失效
2. 删除操作（erase, pop_back）
3. swap / clear
- swap：两个 vector 的迭代器互换
- clear：所有迭代器失效，但 capacity 不变
1
2
3
4
5
6
7
8
9
10
11
12
13
| // ❌ 错误写法：it 失效后 ++ 是未定义行为
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it == target) v.erase(it);
}
// ✅ 正确写法：erase 返回下一个有效迭代器
for (auto it = v.begin(); it != v.end(); ) {
if (*it == target) {
it = v.erase(it);
} else {
++it;
}
}
|
1
2
3
4
5
| vector<int> v1; // 空
vector<int> v2(10); // 10 个元素，默认 0
vector<int> v3(10, 5); // 10 个 5
vector<int> v4{1, 2, 3, 4}; // 列表初始化
vector<int> v5(v4.begin(), v4.end()); // 迭代器范围
|
我的疑问：vector<int> v(5, 0) 之后再 push_back，新元素是不是插不进"前面"？
是的——v(n, 0) 是"先定长填 n 个 0"，size 已经是 n；之后 push_back 永远追加在末尾（下标 n 开始），不会从头插：
1
2
3
4
5
| vector<int> v(5, 0); // {0,0,0,0,0}，size = 5
v.push_back(7); // {0,0,0,0,0,7}，7 在下标 5（第 6 位）
vector<int> w; // 空，size = 0
w.push_back(7); // {7}，7 在下标 0（第 1 位）
|
两种思路二选一，别混：
| 目的 | 正确写法 |
|---|
| 动态追加（数量不定） | 初始化为空 vector<int> v;，只 push_back |
| 固定长度按下标填 | vector<int> v(n, 0); 然后 v[i] = x;（下标改，不是 push_back） |
常见坑：先 v(n, 0) 又 push_back → 得到 n+1 个元素、前 n 个全是 0，数据全挤到后面；v[i] = x 越界是未定义行为（不会自动扩容，可能直接崩）。
1
2
3
4
5
6
| v.push_back(10); // 尾部插入 O(1) 均摊
v.pop_back(); // 尾部删除 O(1)
v.insert(it, 20); // 指定位置插入 O(n)
v.erase(it); // 删除指定位置 O(n)
v.clear(); // 清空所有元素，capacity 不变
v.shrink_to_fit(); // 释放多余空间，capacity = size
|
1
2
3
4
5
| v[0]; // 下标访问，不检查越界
v.at(0); // 带越界检查，越界抛 out_of_range
v.front(); // 第一个元素
v.back(); // 最后一个元素
v.data(); // 底层数组指针
|
1
2
3
4
5
| v.size(); // 元素个数
v.capacity(); // 容量
v.empty(); // 是否为空
v.reserve(n); // 预留容量
v.resize(n); // 改变 size，多删少补
|
1
2
| vector<int> v(1000);
v.clear(); // size = 0，但 capacity 还是 1000
|
1
2
3
4
5
6
| // 方法1：swap 空 vector
vector<int>().swap(v);
// 方法2：shrink_to_fit（C++11）
v.clear();
v.shrink_to_fit();
|
知道大概要存多少元素时，提前 reserve：
1
2
3
4
5
| vector<int> v;
v.reserve(10000); // 一次分配到位
for (int i = 0; i < 10000; i++) {
v.push_back(i); // 不会触发扩容
}
|
| 坑点 | 说明 |
|---|
| 迭代器失效 | 插入删除后旧迭代器不能再用 |
| 引用失效 | 扩容后所有引用都悬空 |
[] 越界 | 不检查，越界是 UB，用 at() 更安全 |
| resize vs reserve | resize 改 size，reserve 只改 capacity |
| 空 vector 调用 front/back | UB，先判断 empty |
| vector<bool> | 不是真正的 vector，是位压缩的特殊实现，尽量别用 |
| 操作 | 时间复杂度 |
|---|
| 随机访问 | O(1) |
| 尾插 push_back | O(1) 均摊 |
| 尾删 pop_back | O(1) |
| 中间插入 | O(n) |
| 中间删除 | O(n) |
| 扩容 | O(n) |
💡 能用 vector 就用 vector，连续内存缓存友好，是最快的序列容器。