麦地

Back

1. 核心概念与内存模型#

1.1 基本定义#

#include <vector>
std::vector<int> v;
cpp

竞赛常用写法:

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
cpp

vector<T> 的三个核心特征:

  1. 元素连续存储:普通 vector<T> 的元素位于一段连续内存中,因此 cache 友好,遍历速度快。
  2. 支持下标随机访问:v[i]、v.at(i) 都是 O(1)。
  3. 长度可动态变化:尾部插入通常为均摊 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);                // 正确
cpp

1.3 自动扩容#

当 push_back 导致 size() + 1 > capacity() 时,通常发生:

  1. 申请一段更大的连续内存。
  2. 将原元素移动或复制到新内存。
  3. 释放旧内存。
  4. 插入新元素。

一次扩容为 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());   // 用迭代器区间构造
cpp

2.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 2
cpp

竞赛中这是一个高频隐蔽错误。想创建长度为 n 的数组时,使用:

vector<int> a(n);
vector<int> b(n, -1);
cpp

2.3 不同元素类型#

vector<long long> sum(n);
vector<double> score(n);
vector<string> name(n);
vector<pair<int, int>> edges;
vector<vector<int>> g;
cpp

2.4 重新赋值:assign#

v.assign(n, 0);                    // 变为 n 个 0
v.assign({1, 2, 3});               // 变为 1 2 3
v.assign(a.begin(), a.end());      // 复制区间
cpp

assign 会替换原有内容,不是在原数组后追加。


3. 元素访问与遍历#

3.1 下标访问#

v[i] = 10;
cout << v[i];
cpp
  • operator[]:不检查越界,越界产生未定义行为,竞赛最常用。
  • at(i):检查越界,越界抛出 std::out_of_range,调试时有用。
// v[v.size()] = 1;  // 错误:合法下标最大为 size()-1
cpp

3.2 首尾元素#

int x = v.front();  // 等价于 v[0]
int y = v.back();   // 等价于 v[v.size()-1]
cpp

front()、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 << ' ';
}
cpp

end() 不等于最后一个元素的位置。最后一个元素应使用 v.end() - 1,前提是数组非空。


5. 长度、容量与内存管理#

5.1 常用查询#

v.empty();     // 是否为空
v.size();      // 元素个数
v.capacity();  // 当前容量
cpp

size() 的返回类型通常是无符号的 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 元素为 -1
cpp
  • 扩大:新增元素。
  • 缩小:销毁尾部多余元素,但通常不释放容量。
  • 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]
cpp

5.4 clear 与 shrink_to_fit#

v.clear();          // size 变为 0,capacity 通常不变
v.shrink_to_fit();  // 请求容量缩减至接近 size
cpp
  • clear() 只清空元素,不保证释放内存。
  • 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();
cpp

6.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' 组成的字符串
cpp
  • push_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();                               // 全部删除
cpp

erase 返回指向被删除区间之后元素的迭代器。中间删除为 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] 仍然是 1
cpp

复制长度为 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;
}
cpp

7.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());
cpp

unique 只把相邻重复元素移到后面,并返回新的逻辑尾迭代器;它本身不改变容器大小,所以必须配合 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()); // 删除所有偶数
cpp

remove 本身也不改变容器大小,只移动保留下来的元素并返回新尾部。

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 的个数
cpp

binary_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];
    }
}
cpp

9.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,权值 w
cpp

遍历邻居:

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);
}
cpp

11.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(); // 回溯
}
cpp

11.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;      // 对
cpp

13.2 空数组调用 back() 或 pop_back()#

if (!v.empty()) {
    cout << v.back();
    v.pop_back();
}
cpp

13.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) {}
cpp

13.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) {}
cpp

13.7 clear() 不等于释放容量#

v.clear();
cout << v.size() << endl;     // 0
cout << v.capacity() << endl; // 通常仍保留原容量
cpp

13.8 unique()、remove() 不直接缩短容器#

必须配合 erase:

v.erase(unique(v.begin(), v.end()), v.end());
v.erase(remove(v.begin(), v.end(), x), v.end());
cpp

13.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

优点:节省内存。代价与注意点:

  1. operator[] 返回代理对象,不是普通的 bool&。
  2. 某些依赖真实 bool*、bool& 或连续 bool 对象的代码不能照搬。
  3. 位操作未必比 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. 一页速记#

最终必须牢牢记住:

  1. size 决定可访问范围,capacity 只是已分配空间。
  2. reserve 不创建元素,resize 才改变元素数量。
  3. 尾部插入均摊 O(1),中间插入删除 O(n)。
  4. 扩容会让旧迭代器、指针、引用失效。
  5. [] 不检查越界;空数组不能 front/back/pop_back。
  6. size() 是无符号类型,警惕 size()-1 下溢。
  7. vector<int>(n) 与 vector<int>{n} 含义完全不同。
  8. 只读传参用 const vector<T>&,只读遍历用 const auto&。
  9. unique/remove 后必须配合 erase 才真正缩短容器。
  10. 已知数据规模时合理使用 reserve,减少扩容开销。
Comment seems to stuck. Try to refresh?✨