1. 核心概念与内存模型#
1.1 基本定义#
#include <vector>
std::vector<int> v;cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
vector<int> v;cppvector<T> 的三个核心特征:
- 元素连续存储:普通
vector<T>的元素位于一段连续内存中,因此 cache 友好,遍历速度快。 - 支持下标随机访问:
v[i]、v.at(i)都是O(1)。 - 长度可动态变化:尾部插入通常为均摊
O(1);中间插入、删除需要移动后续元素,为O(n)。
1.2 size 与 capacity#
size():当前实际存在的元素个数。capacity():当前已分配内存最多能容纳多少个元素,不需要重新分配内存。- 永远有:
size() <= capacity()。 - 下标合法范围只由
size决定:只能访问[0, size()),不能因为 capacity 足够就访问空闲容量。
vector<int> v;
v.reserve(100);
cout << v.size() << endl; // 0
cout << v.capacity() << endl; // 至少为 100
// v[0] = 1; // 错误:当前没有元素
v.push_back(1); // 正确cpp1.3 自动扩容#
当 push_back 导致 size() + 1 > capacity() 时,通常发生:
- 申请一段更大的连续内存。
- 将原元素移动或复制到新内存。
- 释放旧内存。
- 插入新元素。
一次扩容为 O(n),但容量通常按几何倍数增长,常见实现约为 1.5 倍或 2 倍,标准不保证具体倍数。因此连续 n 次 push_back 的总成本为 O(n),单次为均摊 O(1),最坏 O(n)。
扩容后,原有迭代器、指针、引用可能全部失效,详见第 12 节。
2. 创建与初始化#
2.1 常见构造方式#
vector<int> a; // 空数组
vector<int> b(5); // 5 个 int,值均为 0
vector<int> c(5, 7); // 5 个 7:{7,7,7,7,7}
vector<int> d = {1, 2, 3, 4}; // 列表初始化
vector<int> e(d); // 拷贝构造,深拷贝
vector<int> f(d.begin(), d.end()); // 用迭代器区间构造cpp2.2 圆括号与花括号的重大区别#
vector<int> a(5); // 5 个元素:0 0 0 0 0
vector<int> b{5}; // 1 个元素:5
vector<int> c(5, 2); // 5 个元素:2 2 2 2 2
vector<int> d{5, 2}; // 2 个元素:5 2cpp竞赛中这是一个高频隐蔽错误。想创建长度为 n 的数组时,使用:
vector<int> a(n);
vector<int> b(n, -1);cpp2.3 不同元素类型#
vector<long long> sum(n);
vector<double> score(n);
vector<string> name(n);
vector<pair<int, int>> edges;
vector<vector<int>> g;cpp2.4 重新赋值:assign#
v.assign(n, 0); // 变为 n 个 0
v.assign({1, 2, 3}); // 变为 1 2 3
v.assign(a.begin(), a.end()); // 复制区间cppassign 会替换原有内容,不是在原数组后追加。
3. 元素访问与遍历#
3.1 下标访问#
v[i] = 10;
cout << v[i];cppoperator[]:不检查越界,越界产生未定义行为,竞赛最常用。at(i):检查越界,越界抛出std::out_of_range,调试时有用。
// v[v.size()] = 1; // 错误:合法下标最大为 size()-1cpp3.2 首尾元素#
int x = v.front(); // 等价于 v[0]
int y = v.back(); // 等价于 v[v.size()-1]cppfront()、back() 用于空 vector 是未定义行为。back() 配合 pop_back() 可将 vector 当作栈使用。
3.3 三种遍历方式#
下标遍历,适合需要位置或反向遍历:
for (int i = 0; i < (int)v.size(); ++i) {
cout << v[i] << ' ';
}cpp范围 for,适合只读:
for (const auto &x : v) {
cout << x << ' ';
}cpp范围 for,适合修改元素:
for (auto &x : v) {
x *= 2;
}cpp以下写法会复制每个元素,且修改副本不影响原数组:
for (auto x : v) {
x *= 2; // 不修改 v
}cpp对 long long、字符串、结构体等,只读遍历优先使用 const auto &,避免无意义拷贝。
3.4 指针与连续内存#
int *p = v.data();cpp对于非空普通 vector<int>,data() 指向首个元素;可配合需要连续内存的接口。插入、删除、扩容后必须重新考虑指针是否有效。空数组上不要解引用 data()。
4. 迭代器#
vector 提供随机访问迭代器,支持 +、-、下标和距离计算。
auto it = v.begin(); // 指向首元素
auto ed = v.end(); // 尾后位置,不能解引用
it = v.begin() + 2; // 指向 v[2]
int d = v.end() - v.begin(); // 元素个数cpp常用接口:
| 接口 | 含义 |
|---|---|
begin() / end() |
正向首迭代器 / 尾后迭代器 |
rbegin() / rend() |
反向首迭代器 / 反向尾后迭代器 |
cbegin() / cend() |
常量迭代器,不能通过它修改元素 |
逆向遍历:
for (auto it = v.rbegin(); it != v.rend(); ++it) {
cout << *it << ' ';
}cppend() 不等于最后一个元素的位置。最后一个元素应使用 v.end() - 1,前提是数组非空。
5. 长度、容量与内存管理#
5.1 常用查询#
v.empty(); // 是否为空
v.size(); // 元素个数
v.capacity(); // 当前容量cppsize() 的返回类型通常是无符号的 size_t,与 int 混用时需注意下溢和警告,详见易错点。
5.2 reserve:只预留容量,不增加元素#
vector<int> v;
v.reserve(n);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
v.push_back(x);
}cpp作用:
- 已知元素数量时,减少反复扩容和搬移。
- 不改变
size(),不会创建可访问元素。 - 若导致扩容,原有迭代器、指针、引用失效。
5.3 resize:改变元素个数#
v.resize(n); // 扩大到 n 时,新 int 元素为 0
v.resize(n, -1); // 扩大到 n 时,新 int 元素为 -1cpp- 扩大:新增元素。
- 缩小:销毁尾部多余元素,但通常不释放容量。
resize后可以通过v[i]访问[0, n)。
对比:
vector<int> a;
a.reserve(100); // size = 0,只能继续 push_back 等操作
vector<int> b;
b.resize(100); // size = 100,可访问 b[0] 到 b[99]cpp5.4 clear 与 shrink_to_fit#
v.clear(); // size 变为 0,capacity 通常不变
v.shrink_to_fit(); // 请求容量缩减至接近 sizecppclear()只清空元素,不保证释放内存。shrink_to_fit()是实现可以忽略的请求,不保证一定缩容。- 若确实需要通过交换释放一个不再使用的 vector,可写:
vector<int>().swap(v);cpp但更常见的是在变量离开作用域后自然释放,不必过度手动管理。
6. 增删改操作#
6.1 尾部操作:竞赛最常用#
v.push_back(x); // 尾部插入
v.emplace_back(x); // 原位构造元素
v.pop_back(); // 删除尾元素,不返回被删值
v.back(); // 读取尾元素cpp空数组上调用 pop_back() 是未定义行为。作为栈使用:
vector<int> st;
st.push_back(x);
int top = st.back();
st.pop_back();cpp6.2 push_back 与 emplace_back#
vector<pair<int, int>> a;
a.push_back({1, 2});
a.emplace_back(1, 2);
vector<string> s;
s.emplace_back(10, 'a'); // 直接构造 10 个 'a' 组成的字符串cpppush_back(x):插入已有对象或临时对象。emplace_back(args...):把参数传给元素构造函数,在容器内直接构造。- 对
int、double等基本类型通常没有性能区别,不必盲目使用emplace_back。
6.3 任意位置插入#
v.insert(v.begin(), x); // 在开头插入
v.insert(v.begin() + k, x); // 在下标 k 前插入
v.insert(v.begin() + k, 3, x); // 插入 3 个 x
v.insert(v.end(), a.begin(), a.end()); // 插入一个区间cpp插入点之后元素需要向后移动,中间插入为 O(n)。若频繁在头部插入,vector 通常不合适。
6.4 删除元素#
v.erase(v.begin() + k); // 删除下标 k 的元素
v.erase(v.begin() + l, v.begin() + r); // 删除区间 [l, r)
v.pop_back(); // 删除尾部
v.clear(); // 全部删除cpperase 返回指向被删除区间之后元素的迭代器。中间删除为 O(n)。
6.5 交换两个 vector#
a.swap(b);cpp通常为 O(1),交换内部存储,而不是逐元素复制。常用于释放空间、图论临时数组、滚动数组等场景。
7. 拷贝、移动与函数传参#
7.1 vector 是深拷贝#
vector<int> a = {1, 2, 3};
vector<int> b = a;
b[0] = 100;
// a[0] 仍然是 1cpp复制长度为 n 的数组通常需要 O(n)。竞赛中把大数组按值传入函数,容易增加时间和内存开销。
7.2 函数传参选择#
void readOnly(const vector<int> &a) {} // 只读,不拷贝
void modify(vector<int> &a) {} // 修改调用者的数组
void ownCopy(vector<int> a) {} // 明确需要自己的副本cpp推荐默认:
- 只读:
const vector<T>&。 - 需要修改:
vector<T>&。 - 确实需要独立副本或接管右值时,才按值传递。
返回局部 vector 在现代 C++ 中通常可依赖移动语义或返回值优化,不必为了性能强行返回指针:
vector<int> solve(int n) {
vector<int> ans(n);
return ans;
}cpp7.3 移动语义#
b = std::move(a);cpp通常可避免复制整段元素,但移动后的 a 仍处于有效但未指定状态;不要假设它一定为空,除非重新赋值或使用 clear() 后再使用。
8. 与 <algorithm> 的高频组合#
8.1 排序、反转、去重#
sort(v.begin(), v.end()); // 升序
sort(v.begin(), v.end(), greater<int>()); // 降序
reverse(v.begin(), v.end()); // 反转cpp排序后去重:
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());cppunique 只把相邻重复元素移到后面,并返回新的逻辑尾迭代器;它本身不改变容器大小,所以必须配合 erase。
8.2 删除指定元素:erase-remove 惯用法#
v.erase(remove(v.begin(), v.end(), x), v.end()); // 删除所有等于 x 的元素
v.erase(remove_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
}), v.end()); // 删除所有偶数cppremove 本身也不改变容器大小,只移动保留下来的元素并返回新尾部。
8.3 二分查找#
前提是区间已经按相应规则有序:
auto it = lower_bound(v.begin(), v.end(), x); // 第一个 >= x
int pos = it - v.begin(); // 转为下标
bool found = it != v.end() && *it == x;
auto jt = upper_bound(v.begin(), v.end(), x); // 第一个 > x
int cnt = upper_bound(v.begin(), v.end(), x)
- lower_bound(v.begin(), v.end(), x); // 有序数组中 x 的个数cppbinary_search(v.begin(), v.end(), x) 只返回是否存在;需要位置或统计个数时,通常直接使用 lower_bound / upper_bound。
8.4 其他常用算法#
fill(v.begin(), v.end(), -1);
int c = count(v.begin(), v.end(), x);
auto mn = *min_element(v.begin(), v.end());
auto mx = *max_element(v.begin(), v.end());
nth_element(v.begin(), v.begin() + k, v.end()); // 第 k 小的位置被正确放置,整体无序cpp对空数组不要直接解引用 min_element / max_element 的返回值。
求和要注意溢出:
long long sum = accumulate(v.begin(), v.end(), 0LL);cpp若写 0 作为初始值,累加类型是 int,即使结果存入 long long 也可能在中途溢出。
9. 二维与多维 vector#
9.1 创建二维数组#
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));cpp访问:
a[i][j] = 1;cpp读取:
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}cpp9.2 每行长度可以不同#
vector<vector<int>> a;
a.push_back({1, 2});
a.push_back({3, 4, 5});cpp二维 vector 的每一行内部连续,但所有行不一定共同位于一整段连续内存中。若竞赛中需要极规则的超大二维数组、更少间接访问,也可考虑一维展开:
vector<int> a(n * m);
a[i * m + j] = x;cpp注意计算 n * m、i * m + j 时的整数溢出与内存限制。
9.3 邻接表#
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1); // 1 号到 n 号点
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u); // 有向图删除这一行
}cpp带权图:
vector<vector<pair<int, int>>> g(n + 1);
g[u].emplace_back(v, w); // 边 u -> v,权值 wcpp遍历邻居:
for (auto [v, w] : g[u]) { // C++17
// 处理边 u -> v
}cpp固定最大点数时也常见:
const int MAXN = 200000;
vector<int> g[MAXN];cpp不要写运行期变量长度的普通数组 vector<int> g[n];,变长数组不是标准 C++;应使用 vector<vector<int>> g(n) 或固定上限数组。
10. 常用操作复杂度总表#
设当前元素数为 n,新增或构造 k 个元素:
| 操作 | 时间复杂度 | 备注 |
|---|---|---|
v[i]、at(i) |
O(1) |
随机访问 |
front()、back() |
O(1) |
空数组不可调用 |
begin()、end() |
O(1) |
迭代器 |
size()、empty()、capacity() |
O(1) |
查询 |
push_back() |
均摊 O(1) |
单次扩容最坏 O(n) |
emplace_back() |
均摊 O(1) |
另加元素构造代价 |
pop_back() |
O(1) |
销毁尾元素 |
中间 insert |
O(n) |
移动后续元素 |
中间 erase |
O(n) |
移动后续元素 |
resize |
通常与新增/删除元素数及搬移量相关 | 扩容可能为 O(n) |
reserve |
不扩容 O(1),扩容 O(n) |
不改变 size |
clear() |
O(n) |
销毁全部元素,容量通常保留 |
| 拷贝整个 vector | O(n) |
深拷贝 |
swap |
通常 O(1) |
交换内部存储 |
sort |
O(n log n) |
排序 |
find |
O(n) |
线性查找 |
| 有序区间二分 | O(log n) |
lower_bound 等 |
对含大对象的 vector,还要把单个元素的构造、拷贝、移动或析构成本计入实际开销。
11. 竞赛典型用法模板#
11.1 不确定数量的输入,逐个追加#
int n;
cin >> n;
vector<int> a;
a.reserve(n);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
a.push_back(x);
}cpp11.2 已知长度,直接按下标读入#
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;cpp已知长度时直接构造通常比空数组逐个插入更简洁;需要动态过滤、生成元素时用 push_back。
11.3 离散化:排序、去重、二分映射#
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (auto &x : a) {
x = lower_bound(b.begin(), b.end(), x) - b.begin(); // 0-based 离散值
}cpp总体复杂度 O(n log n),是 vector 与算法库配合的典型应用。
11.4 路径记录与回溯#
vector<int> path;
void dfs(int u) {
path.push_back(u);
// 搜索后续状态
path.pop_back(); // 回溯
}cpp11.5 BFS 使用 vector 作已扩展节点数组#
vector<int> q(n);
int head = 0, tail = 0;
q[tail++] = s;
while (head < tail) {
int u = q[head++];
for (int v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q[tail++] = v;
}
}
}cpp这种写法避免 queue 的额外抽象,前提是队列容量上界明确且不会越界。
11.6 输入输出加速#
大规模输入输出时:
ios::sync_with_stdio(false);
cin.tie(nullptr);cpp不要在竞赛中对每个元素都使用 endl,因为它会刷新缓冲区;通常使用 '\n'。
12. 迭代器、指针、引用失效规则#
这是 vector 最重要的易错部分之一。
| 操作 | 主要失效情况 |
|---|---|
push_back / emplace_back |
若扩容,全部迭代器、指针、引用失效;不扩容时已有元素的引用通常保持有效,但尾后迭代器失效 |
reserve 导致扩容 |
全部失效 |
resize 导致扩容 |
全部失效;缩小还会使被删除元素相关迭代器、引用失效 |
中间 insert |
若扩容则全部失效;不扩容时插入点及其后元素相关迭代器、引用通常失效 |
erase |
被删位置及其后元素相关迭代器、指针、引用失效 |
pop_back |
尾后迭代器和被删尾元素相关引用、指针失效 |
clear |
所有指向元素的迭代器、指针、引用失效,capacity 通常不变 |
swap |
通常不移动元素,但迭代器会继续指向原元素,而元素已属于另一个容器;不要混淆逻辑归属 |
危险示例:
vector<int> v = {1, 2, 3};
int &x = v[0];
auto it = v.begin();
v.push_back(4); // 可能扩容
// cout << x; // 危险:x 可能已失效
// cout << *it; // 危险:it 可能已失效cpp正确思路:修改容器后重新获取迭代器、引用或 data(),不要继续使用可能失效的旧值。
13. 高频错误与避坑清单#
13.1 reserve 后直接下标写入#
vector<int> v;
v.reserve(10);
// v[0] = 1; // 错:size 仍为 0
v.resize(10);
v[0] = 1; // 对cpp13.2 空数组调用 back() 或 pop_back()#
if (!v.empty()) {
cout << v.back();
v.pop_back();
}cpp13.3 无符号 size() 导致下溢#
vector<int> v;
// for (int i = 0; i < v.size() - 1; ++i) {} // v.size() 为 0 时下溢,危险cpp推荐:
for (int i = 0; i + 1 < (int)v.size(); ++i) {}cpp或者先转为有符号长度:
int n = v.size();
for (int i = 0; i + 1 < n; ++i) {}cpp反向遍历可写:
for (int i = (int)v.size() - 1; i >= 0; --i) {}cpp13.4 遍历时直接 erase 导致跳过元素或失效#
错误示例:
// for (auto it = v.begin(); it != v.end(); ++it) {
// if (*it == x) v.erase(it); // it 已失效,随后 ++it 更危险
// }cpp正确写法:
for (auto it = v.begin(); it != v.end();) {
if (*it == x) it = v.erase(it);
else ++it;
}cpp删除大量满足条件的元素通常优先 erase-remove_if,逻辑更简洁;中间反复 erase 可能累计为 O(n^2)。
13.5 范围 for 中修改容器结构#
for (auto x : v) {
v.push_back(x); // 危险:可能扩容,导致遍历所用迭代器失效,甚至无限增长
}cpp范围 for 中一般不要增删当前容器。可以记录新增内容到另一个 vector,循环后再合并。
13.6 意外复制大数组#
void f(vector<int> a); // 按值传递,可能 O(n) 拷贝
for (auto x : v) {} // 每个元素都拷贝cpp只读时改为:
void f(const vector<int> &a);
for (const auto &x : v) {}cpp13.7 clear() 不等于释放容量#
v.clear();
cout << v.size() << endl; // 0
cout << v.capacity() << endl; // 通常仍保留原容量cpp13.8 unique()、remove() 不直接缩短容器#
必须配合 erase:
v.erase(unique(v.begin(), v.end()), v.end());
v.erase(remove(v.begin(), v.end(), x), v.end());cpp13.9 忘记排序就二分或 unique 全局去重#
lower_bound/upper_bound要求有序。unique只处理相邻重复项;全局去重通常先sort。
13.10 越界访问与未初始化逻辑#
v[i] 不检查越界,错误可能表现为随机答案、崩溃甚至暂时看似正常。调试时可临时使用 v.at(i) 帮助定位,但竞赛最终代码通常使用 []。
14. vector<bool> 特化#
vector<bool> 是标准库中的特殊版本,通常按位压缩存储,而不是每个 bool 占一个普通对象。
vector<bool> vis(n, false);cpp优点:节省内存。代价与注意点:
operator[]返回代理对象,不是普通的bool&。- 某些依赖真实
bool*、bool&或连续bool对象的代码不能照搬。 - 位操作未必比
vector<char>更快,需结合场景。
算法竞赛中 vis 用 vector<bool> 很常见;如果需要普通字节数组语义或更方便地取地址,可使用:
vector<char> vis(n, 0);
// 或 vector<uint8_t> vis(n, 0);cpp普通 vector<T> 的连续存储结论不能直接套到这个特化版本上。
15. 选型:什么时候该用 vector#
适合:
- 需要按下标快速访问。
- 元素数量动态变化,主要在尾部追加、删除。
- 需要排序、二分、连续遍历。
- 存储邻接表、路径、答案、动态规划状态。
- 注重缓存局部性和较低内存开销。
不太适合:
- 频繁在头部或中间插入、删除:每次可能
O(n)。 - 需要任意位置稳定迭代器、引用:扩容和移动元素会破坏稳定性。
- 需要频繁按 key 快速查询:无序 vector 只能
O(n)查找,通常考虑set、map、unordered_set、unordered_map。 - 需要双端高频操作:通常考虑
deque,但它不保证整体连续存储。
一句话:vector 最擅长“连续存储、随机访问、尾部动态增长”,不是万能容器。
16. 一页速记#
vector<int> a; // 空
vector<int> b(n); // n 个 0
vector<int> c(n, -1); // n 个 -1
vector<int> d = {1, 2, 3}; // 列表初始化
a.push_back(x); // 尾插,均摊 O(1)
a.emplace_back(x); // 尾部原位构造
a.pop_back(); // 删尾,空数组禁止
a.back(); // 尾元素,空数组禁止
a.insert(a.begin() + k, x); // 中间插入 O(n)
a.erase(a.begin() + k); // 中间删除 O(n)
a.clear(); // 清空元素,容量通常保留
a.resize(n, 0); // 改变 size
a.reserve(n); // 只预留 capacity
a.size(); a.empty(); // 元素数 / 是否为空
a.capacity(); // 当前容量
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
a.erase(remove(a.begin(), a.end(), x), a.end());
auto it = lower_bound(a.begin(), a.end(), x); // 必须先有序
long long sum = accumulate(a.begin(), a.end(), 0LL);
for (int i = 0; i < (int)a.size(); ++i) {}
for (const auto &x : a) {} // 只读
for (auto &x : a) {} // 修改
vector<vector<int>> g(n + 1); // 邻接表
g[u].push_back(v);cpp最终必须牢牢记住:
size决定可访问范围,capacity只是已分配空间。reserve不创建元素,resize才改变元素数量。- 尾部插入均摊
O(1),中间插入删除O(n)。 - 扩容会让旧迭代器、指针、引用失效。
[]不检查越界;空数组不能front/back/pop_back。size()是无符号类型,警惕size()-1下溢。vector<int>(n)与vector<int>{n}含义完全不同。- 只读传参用
const vector<T>&,只读遍历用const auto&。 unique/remove后必须配合erase才真正缩短容器。- 已知数据规模时合理使用
reserve,减少扩容开销。