vector 动态数组

读完能做什么

• 能创建 vector，用下标读出、改写里面的元素，并说清下标从几开始。
• 能用 push_back、pop_back、insert、erase 增删元素，用 assign 整体换一批数据，并说出每一步操作后 size() 是多少。
• 能区分“长度 size()”和“预留空间 capacity()”，知道 reserve 不会增加元素、resize / assign 才会改变元素个数。
• 能解释为什么在尾部增删很快，而在中间插入、删除要移动元素。

为什么需要它

数组的长度在写代码时就定死了：

int a[10];   // 只能放 10 个数

开小了不够用，开大了浪费。更麻烦的是竞赛题常把长度放在输入里：先读一个 n，再读 n 个数。n 要运行到那一行才知道，用它开数组不是标准 C++ 的写法：

// 错误示例：数组长度必须是编译期常量，不能是运行时才读到的变量
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];        // 变长数组不是标准 C++：本机编译器只当作扩展放过，严格模式会报错
    return 0;
}

这段不能作为标准写法使用。本机编译器把它当成扩展接受了（在 -pedantic-errors 严格模式下会直接报 ISO C++ forbids variable length array），但换一个编译器、换一种编译选项就可能编不过。我们需要一个“长度可以变、用起来还像数组”的容器，这就是 vector。

它是什么

一句话：vector 是标准库提供的能改变长度的数组，也叫动态数组。

直观模型是一排连续的格子，每个格子放一个同类型的数据，格子从左到右编号 0、1、2……：

我们可以像数组一样用 v[1] 读写某个格子，也可以在右端接上新格子、把末尾的格子去掉。

模板尖括号。 vector<int> 中的 <int> 是在告诉编译器“每个格子放什么类型”。vector<int> 是整数的 vector，vector<double>、vector<string> 同理。这是 C++ 的模板语法：同一份 vector 的代码可以给不同类型使用，尖括号里填具体类型即可。vector<vector<int>> 表示每个格子本身也是一个 vector<int>（C++17 里最右边的 >> 不用加空格）。

下标。 第 i 个元素写作 v[i]，下标从 0 开始，最后一个元素的下标是 size() - 1。

size() 与 capacity()。 size() 是“现在有几个元素”，capacity() 是“当前已经申请下来的存储空间能放几个元素”。size() 永远不超过 capacity()。reserve(n) 只把 capacity() 提到至少 n，元素个数一个也不会变。

适用场景：需要按下标随机访问（想读第几个就读第几个），并且主要在尾部增删数据。使用时要 #include <vector>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

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

int main() {
    vector<int> v = {10, 20, 30};          // 3 个元素，下标是 0、1、2

    cout << "size = " << v.size() << '\n';
    for (int i = 0; i < (int)v.size(); i++) {
        cout << "v[" << i << "] = " << v[i] << '\n';
    }
    cout << "front = " << v.front() << ", back = " << v.back() << '\n';

    v[1] = 25;                             // 用下标直接改元素
    cout << "改后 v[1] = " << v[1] << '\n';
    return 0;
}

输出：

size = 3
v[0] = 10
v[1] = 20
v[2] = 30
front = 10, back = 30
改后 v[1] = 25

逐行看：

• vector<int> v = {10, 20, 30}; 创建一个 vector<int>，按顺序放入 3 个元素。
• v.size() 返回元素个数，类型是无符号整数 size_t。循环条件写成 (int)v.size() 是为了把它转成 int，和 int i 比较时不会出现“有符号与无符号比较”的警告。
• v[i] 用下标取元素，可以用来读，也可以放在等号左边改写。
• v.front() 返回第一个元素，v.back() 返回最后一个元素。
• 输出里 v[1] = 25 说明下标 1 的位置被改掉了，长度仍是 3。

一步步看变化

下面用同一组数据 [10, 20, 30] 依次做四步。先把整条路线列出来：

每一步都写成独立的小程序，输出就是这一步操作前后的状态。

第 1 步：尾部加入 40

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

int main() {
    vector<int> v = {10, 20, 30};
    cout << "操作前：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';

    v.push_back(40);                       // 在尾部加入 40

    cout << "操作后：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';
    return 0;
}

输出：

操作前：10 20 30 size = 3
操作后：10 20 30 40 size = 4

push_back(40) 把 40 接到最右端，长度从 3 变成 4。原来的三个元素下标没变，新元素的 size()-1 就是它的下标。

第 2 步：删除尾部

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

int main() {
    vector<int> v = {10, 20, 30, 40};
    cout << "操作前：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';

    v.pop_back();                          // 删掉最后一个元素 40

    cout << "操作后：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';
    cout << "back = " << v.back() << '\n';
    return 0;
}

输出：

操作前：10 20 30 40 size = 4
操作后：10 20 30 size = 3
back = 30

pop_back() 只能删最后一个元素，长度减 1，新的 back() 变成 30。它不返回被删掉的元素，删除前想用这个值就先 v.back() 取出来。

第 3 步：在下标 1 之前插入 15

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

int main() {
    vector<int> v = {10, 20, 30};
    cout << "操作前：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';

    v.insert(v.begin() + 1, 15);           // 在下标 1 的元素之前插入 15

    cout << "操作后：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';
    return 0;
}

输出：

操作前：10 20 30 size = 3
操作后：10 15 20 30 size = 4

这里出现了新写法 v.begin() + 1。v.begin() 返回一个迭代器：可以把它理解成“指向某个位置的游标”。v.begin() 指向下标 0，v.begin() + 1 指向下标 1，v.end() 指向最后一个元素后面一个位置。迭代器在容器、迭代器与区间里有系统讲解，这里先记住“它表示一个位置，可以和整数相加往后移”。

insert(pos, value) 的含义是“把 value 插到位置 pos 之前”。插入位置是下标 1，所以 15 落在 20 前面，原来的 20、30 各自往后挪一格：

第 4 步：删除值为 20 的位置

上一步之后 20 在下标 2 上，所以删除的是 v.begin() + 2：

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

int main() {
    vector<int> v = {10, 15, 20, 30};
    cout << "操作前：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';

    v.erase(v.begin() + 2);                // 删除下标 2 上的 20

    cout << "操作后：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';
    return 0;
}

输出：

操作前：10 15 20 30 size = 4
操作后：10 15 30 size = 3

erase(pos) 删掉位置 pos 上的元素，后面的元素整体左移一格，长度减 1。注意 erase 接收的是位置，不是值：如果只知道“值为 20”而不知道它在下标几，需要先找到位置，查找可以用 find，见 find 查找。

逐项扩展核心操作

遍历：下标、范围 for 与引用

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

int main() {
    vector<int> v = {10, 20, 30};

    cout << "下标遍历：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << '\n';

    cout << "范围 for：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    for (int& x : v) x *= 2;               // 引用：改的是容器里的元素

    cout << "每个元素乘 2 后：";
    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

下标遍历：10 20 30 
范围 for：10 20 30 
每个元素乘 2 后：20 40 60 

for (int x : v) 叫范围 for，意思是“把 v 里的元素逐个取出来，每次放到 x 里”。它从下标 0 走到最后一个元素，不用自己写循环变量。

int& x 中的 & 表示引用，即 x 就是容器里那个元素本身，不是它的复制品。所以 x *= 2 会真的改到 v 里的数据，输出变成 20 40 60。写成 for (int x : v) x *= 2; 只会改到一个临时副本，容器内容不变。

size() 与 capacity()：长度和预留空间

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

int main() {
    vector<int> v;
    cout << "新建：size = " << v.size() << ", empty = " << v.empty() << '\n';

    v.reserve(5);                          // 预留空间，但没有元素
    cout << "reserve(5) 后：size = " << v.size() << '\n';
    cout << "capacity 至少为 5：" << (v.capacity() >= 5) << '\n';

    v.push_back(10);
    v.push_back(20);
    cout << "push_back 两次后：size = " << v.size() << '\n';
    cout << "capacity 至少为 5：" << (v.capacity() >= 5) << '\n';
    return 0;
}

输出：

新建：size = 0, empty = 1
reserve(5) 后：size = 0
capacity 至少为 5：1
push_back 两次后：size = 2
capacity 至少为 5：1

这段说明了三点：

• 空 vector 的 size() 是 0，empty() 返回 true，打印成 1（bool 输出默认是 0/1）。
• reserve(5) 之后 size() 还是 0：预留的只是空间，不是元素。此时 v[0] 是越界访问，不能读。
• 加入两个元素后 size() 变成 2，而 capacity() 仍然至少是 5，不需要再申请空间。

容量增长到多少由实现决定，标准只保证 capacity() >= size()，所以本页只打印“至少为 5”这个能确定的事实，不打印具体容量值。

clear() 与 empty()

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

int main() {
    vector<int> v = {10, 20, 30};
    cout << "clear 前：size = " << v.size() << ", empty = " << v.empty() << '\n';

    v.clear();

    cout << "clear 后：size = " << v.size() << ", empty = " << v.empty() << '\n';
    v.push_back(99);                       // 清空之后还能继续用
    cout << "再 push_back(99)：size = " << v.size() << ", v[0] = " << v[0] << '\n';
    return 0;
}

输出：

clear 前：size = 3, empty = 0
clear 后：size = 0, empty = 1
再 push_back(99)：size = 1, v[0] = 99

clear() 一次删掉所有元素，size() 变成 0。清空后的容器可以继续使用，不需要重新创建。

assign()：整体换一批数据

assign 的作用是整体换掉内容：它先去掉原来的所有元素，再按参数填新的。三种常用形式：

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

int main() {
    vector<int> v = {10, 20, 30};
    cout << "初始：size = " << v.size() << "，内容：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    v.assign(4, 7);                        // 换成 4 个 7：原来的 10 20 30 全被丢掉
    cout << "assign(4, 7) 后：size = " << v.size() << "，内容：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    v.assign({1, 2, 3});                   // 用一组初值整体替换
    cout << "assign({1, 2, 3}) 后：size = " << v.size() << "，内容：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    vector<int> src = {5, 6};
    v.assign(src.begin(), src.end());      // 用另一段区间的值整体替换
    cout << "assign(src 的区间) 后：size = " << v.size() << "，内容：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    v.assign(0, 0);                        // 个数为 0：等于清空
    cout << "assign(0, 0) 后：size = " << v.size() << ", empty = " << v.empty() << '\n';
    return 0;
}

输出：

初始：size = 3，内容：10 20 30 
assign(4, 7) 后：size = 4，内容：7 7 7 7 
assign({1, 2, 3}) 后：size = 3，内容：1 2 3 
assign(src 的区间) 后：size = 2，内容：5 6 
assign(0, 0) 后：size = 0, empty = 1

三点要记住：

• 原来的元素一个不留。 第一次 assign(4, 7) 之后 10 20 30 就没了，size() 从 3 变成 4。
• size() 由参数决定。 assign(0, 0) 是“填 0 个元素”，效果就是清空，和 clear() 一样。
• 旧位置全部失效。 内容整个换过，assign 之后要重新取 v.begin()。

容易和它混的是 resize(n)：resize 只把长度改成 n，原有元素保留，多出来的位置用默认值（或 resize(n, x) 里的 x）填；assign 则是把内容整体替换。想“按个数调整长度”用 resize，想“整批换掉”用 assign。

两种写法的复杂度都是 O(n)：assign(n, x) 要写 n 个元素，assign(first, last) 要写区间长度那么多个。

竞赛写法：全局 vector 与运行时定长度

竞赛代码常把容器写成全局变量，因为它要绐 read_input()、solve()、dfs() 这些函数共用，写成全局就不用一层层传参；元素存在堆上，也不占函数的栈空间。

但全局声明的位置在 main 之前，那时 n 还没读进来，所以不能写 vector<int> a(n + 1);（n 不是常量）。做法是：先声明一个空的全局 vector，读入 n 之后用 resize 或 assign 把长度定下来。

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

vector<int> a;          // 全局容器：多个函数都能直接用，不用来回传参

int main() {
    int n;
    cin >> n;

    a.resize(n + 1);    // 长度定成 n+1：下标 0 空着，a[1]..a[n] 对应题目里的第 1..n 个数
    cout << "resize 后：size = " << a.size() << "，a[1] = " << a[1] << '\n';

    for (int i = 1; i <= n; i++) cin >> a[i];

    int sum_value = 0;
    for (int i = 1; i <= n; i++) sum_value += a[i];
    cout << "读入 " << n << " 个数，和 = " << sum_value << '\n';

    a.assign(3, 123);   // 整体换掉：变成 3 个 123，原来的数据全丢
    cout << "assign(3, 123) 后：size = " << a.size() << "，内容：";
    for (int x : a) cout << x << ' ';
    cout << '\n';

    a.resize(5, 7);     // 长度改成 5：前 3 个保留，后面补 7
    cout << "resize(5, 7) 后：size = " << a.size() << "，内容：";
    for (int x : a) cout << x << ' ';
    cout << '\n';
    return 0;
}

输入：

3
5 1 4

输出：

resize 后：size = 4，a[1] = 0
读入 3 个数，和 = 10
assign(3, 123) 后：size = 3，内容：123 123 123 
resize(5, 7) 后：size = 5，内容：123 123 123 7 7 

逐行看：

• resize(n + 1) 把 size() 定成 n+1，新长出来的元素是默认值（int 是 0，string 是空串）——所以还没读入时 a[1] 就是 0。下标 0 空着、数据放在 a[1]..a[n]，这就是竞赛里常见的“下标从 1 开始”写法。
• 读入 5 1 4 后求和得到 10，说明 resize 出来的格子可以直接当数组用。
• assign(3, 123) 把内容整体换成 3 个 123：长度变 3，原来的 5 1 4 全被丢掉。
• resize(5, 7) 只把长度从 3 改到 5：前 3 个保留，新长出的两个位置用 7 填。

三个容易混的操作，放一起对比：

最后提醒一句：resize 的参数就是新的元素个数。写成 a.resize(100) 就是长度变成 100，不要把它当成“下标”或“容量”。

什么时候选它、哪里容易错

下标必须有效。 只有 3 个元素时 v[3] 是越界访问，结果不确定，不能拿它当“读到 0”。v.at(3) 会做检查并在越界时抛异常，但竞赛代码一般用 []，越界责任在自己。用 v[i] 之前确认 i 在 [0, size()) 内。

reserve 不增加元素个数。 reserve(100) 之后 size() 仍是原来的值，v[0] 在 size() == 0 时不能读。

assign 会丢掉原来的内容。 v.assign(n, x) 之后 v 里只剩 n 个 x，原来的元素一个不留，size() 也跟着变。想保留元素只改长度用 resize，想追加内容用 push_back 或 insert。

全局容器要先声明、再定长度。 想给多个函数共用而把容器写成全局变量时，不能写 vector<int> a(n + 1);（那时 n 还没读入，不是常量）；要先写 vector<int> a;，读入 n 后用 a.resize(n + 1); 或 a.assign(n + 1, 0); 把长度定下来。给全局容器忘了定长度就直接 a[i] 赋值，是典型的“空容器越界”。

插删之后不要盲用旧的位置。 扩容、insert、erase 都可能让之前记下的迭代器（begin() 这类游标）失效。要接着用就重新取一次 v.begin()。

复杂度要分清位置。 尾部的 push_back、pop_back 是摊还常数时间（“摊还”指偶尔一次扩容比较贵，但把这次开销平摊到前面许多次操作上，平均下来每次仍是常数）；在中间 insert、erase 一般要把后面的元素整体搬动，是 O(n)，和数组里挪元素一样慢。

扩容倍数不是标准规定。 不要依赖“翻倍”之类的具体值，也不要比较不同环境下的 capacity()。

选读。 vector 底层是一整块连续内存。元素超过现有空间时会申请一块更大的内存，把元素搬过去再释放旧的，这就是“旧迭代器失效”的原因。不了解这些细节也可以正常使用 vector。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

vector<int> v = {1, 2, 3};
v.push_back(4);                  // 尾部加 4
v.insert(v.begin(), 0);          // 头部插入 0
v.pop_back();                    // 删掉尾部
v.assign(3, 9);                  // 整体换掉：变成 3 个 9
v.push_back(8);                  // 再在尾部加 8

cout << v.size() << ' ' << v[0] << ' ' << v.back() << '\n';

第 2 题：修改代码

下面这段片段把 4 个数存进 vector，请补上删除首个元素的操作，让输出变成 20 30 40，size() 变成 3：

vector<int> v = {10, 20, 30, 40};
// 在这里补一行：删掉首个元素
cout << "size = " << v.size() << '\n';
for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';

验证条件：先说出补完之后 size() 是多少、剩下哪些元素，再运行核对。

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

int main() {
    vector<int> v = {1, 2, 3};
    v.push_back(4);                        // 尾部加 4
    v.insert(v.begin(), 0);                // 头部插入 0
    v.pop_back();                          // 删掉尾部
    v.assign(3, 9);                        // 整体换掉：变成 3 个 9
    v.push_back(8);                        // 再在尾部加 8

    cout << v.size() << ' ' << v[0] << ' ' << v.back() << '\n';
    return 0;
}

4 9 8

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

int main() {
    vector<int> v = {10, 20, 30, 40};
    v.erase(v.begin());                    // 删除首个元素

    cout << "size = " << v.size() << '\n';
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << '\n';
    return 0;
}

size = 3
20 30 40 

立即练习

两道题都只需要数组、循环和本页讲过的 vector 操作，不需要其他数据结构。做完后请说明：为什么这里用 vector 比用固定长度的数组更省事。