C++ 中各种 Vector 写法彻底讲透：vector<int>、vector<vector<int>>、vector<pair<int,int>> 到底有什么区别？

对于刚接触 C++ 的同学来说，看到下面这些代码时，往往会有一种感觉：长得都差不多，但就是不知道区别在哪里。

vector<int> v;

vector<vector<int>> g(n);

vector<vector<int>> grid(n, vector<int>(m));

vector<pair<int,int>> pts;

vector<int> g[105];

vector<vector<int>> a;

vector<pair<int,int>> g[N];

尤其是在算法竞赛、CSP-J/S、NOIP 等题目中，这几种写法几乎每天都会遇到。

很多初学者都是死记硬背："二维数组用这个，图论用那个，坐标用另外一个……"

实际上完全没有必要。

只要理解了 vector 模板到底表示什么，以后看到任何复杂的模板写法，都能够一眼看懂。

一、先理解什么是 vector

学习 vector，只需要记住一句话：

vector 本质上就是一个能够自动扩容的数组。

普通数组：

int a[100];

大小一开始就已经固定。

如果放满了，就不能继续增加元素。

而 vector 不一样。

vector<int> v;

开始的时候可以什么都没有。

随着程序运行，可以不断增加元素。

v.push_back(10);
v.push_back(20);
v.push_back(30);

现在里面已经保存了三个整数。

如果继续加入

v.push_back(40);

vector 会自动申请更大的空间，不需要手工管理内存。

这也是 STL 中最常用的容器。

二、阅读 vector 的秘诀：从里面往外看

很多人看到

vector<vector<int>>

脑袋就开始发晕。

其实阅读模板只有一个诀窍。

永远先看最里面。

例如

vector<int>

表示

一个保存 int 的动态数组。

那么

vector<vector<int>>

里面保存的就不是 int，而是很多个 vector。

继续往外理解就是：

一个保存很多个动态数组的动态数组。

再例如

vector<pair<int,int>>

里面保存的是 pair。

所以它表示

一个保存很多个 pair 的动态数组。

以后无论模板写得多复杂，都按照"由里到外"的顺序阅读，基本不会出错。

三、vector v —— 最普通的一维动态数组

这是所有 vector 中最基础的一种。

vector<int> v;

表示：

创建一个名字叫 v 的动态整型数组。

刚创建时：

v

空

长度为

0

加入元素：

v.push_back(5);
v.push_back(8);
v.push_back(10);

现在变成

下标

0    1    2

5    8   10

访问元素：

cout << v[0];
cout << v[1];
cout << v[2];

遍历：

for(int i=0;i<v.size();i++)
{
    cout<<v[i]<<" ";
}

这是平时使用最多的一种 vector。

例如：

• 保存成绩

• 保存年龄

• 保存数据

• 保存答案

• 保存排序后的结果

几乎所有算法都会用到。

四、vector<vector> g(n)

这是算法竞赛中最容易让初学者困惑的一种写法。

先拆开来看。

里面：

vector<int>

表示一个动态数组。

外面：

vector<vector<int>>

表示

一个数组，里面每个元素又都是一个 vector。

例如：

vector<vector<int>> g(3);

可以理解成

g

第0行  空

第1行  空

第2行  空

注意：

这里只有三行。

但是每一行里面什么都没有。

例如：

g[0].push_back(3);
g[0].push_back(8);

g[1].push_back(5);

g[2].push_back(7);
g[2].push_back(9);
g[2].push_back(11);

最终变成

第0行

3 8

第1行

5

第2行

7 9 11

可以发现：

每一行长度完全不同。

第一行两个元素。

第二行一个元素。

第三行三个元素。

这种特点特别适合表示：

邻接表。

例如

1 -> 2 3

2 -> 5

3 -> 4 6 7

直接写成

g[1].push_back(2);
g[1].push_back(3);

g[2].push_back(5);

g[3].push_back(4);
g[3].push_back(6);
g[3].push_back(7);

所以图论里面经常出现

vector<vector<int>> g(n);

五、vector<vector> grid(n, vector(m))

如果说前面的 g(n) 每一行都是空的，那么这一种则是：

每一行一开始就已经分配好了空间。

例如

vector<vector<int>> grid(3, vector<int>(4));

表示

3 行

4 列

初始化以后：

0 0 0 0

0 0 0 0

0 0 0 0

所有元素默认都是 0。

访问方式和二维数组完全一样。

grid[1][2]=8;

得到

0 0 0 0

0 0 8 0

0 0 0 0

因此它通常用于：

• 地图

• 棋盘

• DP 数组

• 矩阵

• 图像处理

一句话区别：

vector<vector<int>> g(n);

每一行开始为空。

而

vector<vector<int>> grid(n, vector<int>(m));

每一行已经有 m 个元素。

这是最大的区别。

六、vector<pair<int,int>> pts

先认识 pair。

pair<int,int>

表示：

把两个整数打包成一个整体。

例如：

pair<int,int> p;

里面有两个成员：

p.first

p.second

赋值：

p.first=3;
p.second=5;

表示

(3,5)

那么

vector<pair<int,int>>

表示

保存很多个 pair。

例如：

vector<pair<int,int>> pts;

加入：

pts.push_back(make_pair(2,3));

pts.push_back(make_pair(5,8));

得到：

(2,3)

(5,8)

访问：

cout<<pts[0].first;

cout<<pts[0].second;

输出：

2

3

它最常见的用途有：

• 坐标

• 点集

• 边的信息

• BFS 队列

• DFS 搜索

例如迷宫问题：

(2,5)

(4,7)

(6,8)

每个元素就是一个坐标。

七、vector g[105]

第一次看到这种写法时，很多人都会误认为：

vector<vector<int>> g(105);

实际上它们并不是同一种声明方式。

这里：

vector<int> g[105];

表示：

创建一个数组。

数组里面共有 105 个元素。

而数组中的每一个元素，都是一个 vector。

可以理解成：

g[0]

g[1]

g[2]

...

g[104]

每个 g[i] 都是一个动态数组。

使用方式：

g[1].push_back(3);
g[1].push_back(8);

g[2].push_back(5);

是不是和前面的邻接表完全一样？

确实如此。

很多老版本的竞赛代码都喜欢这样写。

例如：

const int N=100005;

vector<int> g[N];

这是 NOI、NOIP 时代最经典的写法。

八、vector g[105] 和 vector<vector> g(105) 有什么区别？

很多同学最容易混淆的就是这里。

虽然使用方法几乎一样。

但是底层完全不同。

第一种：

vector<int> g[105];

105 是编译时期就确定好的。

属于数组。

不能改变大小。

第二种：

vector<vector<int>> g(105);

属于 vector。

大小可以运行时决定。

例如：

cin>>n;

vector<vector<int>> g(n);

程序运行以后才知道到底有多少行。

因此现代 C++ 更推荐第二种写法。

灵活性更高。

九、vector<vector> a

这一句经常出现在需要动态建立二维数组的时候。

vector<vector<int>> a;

注意：

这里没有指定大小。

所以刚开始：

a

空

长度：

0

如果需要增加一行：

vector<int> row;

row.push_back(3);
row.push_back(5);

a.push_back(row);

现在

3 5

再加入一行：

vector<int> row2;

row2.push_back(7);
row2.push_back(8);
row2.push_back(9);

a.push_back(row2);

最终：

3 5

7 8 9

这种写法最大的特点就是：

不知道有多少行。

也不知道每一行有多少列。

随着程序运行不断增加。

十、vector<pair<int,int>> g[N]

这是最短路算法里面最经典的一种写法。

先看：

pair<int,int>

通常表示：

(终点，边权)

例如：

(5,20)

表示：

到 5

权值为 20

那么：

vector<pair<int,int>> g[N];

就是：

每一个点，都保存若干条边。

例如：

1

├──2 权值5

├──3 权值8

└──6 权值1

代码：

g[1].push_back(make_pair(2,5));

g[1].push_back(make_pair(3,8));

g[1].push_back(make_pair(6,1));

那么：

g[1]

(2,5)

(3,8)

(6,1)

表示从 1 号点出发，共有三条边。

所以在下面这些算法中，经常能够看到它：

• Dijkstra

• Prim

• SPFA

• 最短路径

• 最小生成树

• 图论模板

十一、如何快速看懂复杂的 vector 模板？

很多人觉得 STL 难，其实只是阅读顺序没有掌握。

以后看到任何模板，都按照下面三步来看。

第一步：先看最里面。

看看真正存放的数据是什么。

例如：

int

pair<int,int>

vector<int>

第二步：再看外层 vector。

表示：

有很多个这种类型。

第三步：最后看变量声明。

例如：

g[N]

说明这是数组。

如果是

g(n)

说明这是 vector 对象。

掌握这三个步骤之后，绝大多数 STL 模板声明都能轻松读懂。

总结

学习 vector，千万不要死记硬背各种写法，而是要理解模板的组成方式。

可以把所有写法概括成下面这张表。

真正学会这些写法以后，再阅读各种图论、搜索、动态规划代码时，就不会再觉得 STL 神秘难懂。因为所有复杂的声明，本质上都是在描述："数组里面存放的到底是什么类型的数据。"