1.1. 动态数组
有些时候想开一个数组，但是却不知道应该开多大长度合适，因为我们需要用到的数组可能会根据情
况变动。这时候我们就需要用到动态数组。所谓动态数组，也就是不定长数组，数组的长度是可以根
据我们的需要动态改变的。动态数组的实现也不难，在 C++ 里面有已经写好的标准模板库（Standard
Template Library），就是我们常说的 STL 库，实现了集合、映射表、栈、队列等数据结构和排序、
查找等算法。我们可以很方便地调用标准库来减少我们的代码量。
C++ 中动态数组写作 vector ，C 语言中没有标准库，这也是为什么参加比赛推荐用 C++ 而不用 C 的
原因。
1.1.1. 引用库
C++ 中 vector 的实现在一个 头文件中，在代码开头引入这个头文件，并在引入所有头文件
之后加上一句 using namespace std 。

#include <vector>
using namespace std;
int main() {
return 0;
}

1.1.2. 构造一个动态数组
现在我们来构造一个动态数组。
C++ 构造一个 vector 的写法为： vector vec 。这样我们定义了一个名字为 vec 的动态数组，其
中 T 是我们数组要储存的数据类型，可以是 int 、 long long 、 double ,也可以是自己定义的结构体类
型。初始的时候 vec 是空的。比如 vector a 定义了一个储存整数的动态数组 a 。
1.1.3. 插入元素
C++ 中通过 push_back() 函数在数组最后面插入一个新的元素。

#include <vector>
using namespace std;
int main() {
vector<int> vec; // []
vec.push_back(1); // [1]
vec.push_back(2); // [1, 2]
vec.push_back(3); // [1, 2, 3]
return 0;
}

1.1.4. 获取长度并且访问元素
C++ 中通过 size() 函数获取 vector 的长度，通过 [] 操作直接访问 vector 中的元素，这一点和数组
是一样的。

#include <vector>
#include <stdio.h>
using namespace std;
int main() {
vector<int> vec; // []
vec.push_back(1); // [1]
vec.push_back(2); // [1, 2]
vec.push_back(3); // [1, 2, 3]
for (int i = 0; i < vec.size(); i++) {
cout << v[i] << endl;
}
return 0;
}

1.1.5. 修改元素
C++ 中修改 vector 中某个元素很简单，只需要用 = 给它赋值就好了，比如 vec[1] = 3 。

#include <vector>
#include <stdio.h>
using namespace std;
int main() {
vector<int> vec; // []
vec.push_back(1); // [1]
vec.push_back(2); // [1, 2]
vec.push_back(3); // [1, 2, 3]
vec[1] = 3; // [1, 3, 3]
vec[2] = 2; // [1, 3, 2]
for (int i = 0; i < vec.size(); i++) {
cout << v[i] << endl;
}
return 0;
}

1.1.6. 删除元素
和插入一样，删除元素也只能在动态数组的末端进行操作。C++ 中通过 pop_back() 函数删动态数组的
最后一个元素。

#include <vector>
using namespace std;
int main() {
vector<int> vec; // []
vec.push_back(1); // [1]
vec.push_back(2); // [1, 2]
vec.push_back(3); // [1, 2, 3]
vec.pop_back(); // [1, 2]
vec.pop_back(); // [1]
return 0;
}

1.1.7. 清空
C++ 中都只需要调用 clear() 函数就可清空 vector 。
C++ 中 vector 的 clear() 只是清空 vector ，并不会清空开的内存。用一种函数可以清空 vector 的内
存：
// vector v;
vector().swap(v);
C++ vector 函数小结：
函数 功能
函数 功能
push_back 在末尾加入一个元素
pop_back 在末尾弹出一个元素
size 获取长度
clear 清空
通过上面列举的函数，可以满足我们平时做题时的大多数需求。关于 vector 的更多函数，可以去参考
文档，或者在网络上搜索资料查看。对于比赛来说，上面的函数已经足够了。
C++ vector 官方参考文档
【实践操作】vector 的基础使用
首先我们引入需要的头文件 vector ，在代码头部写下
#include
在 main 函数里面通过 vector v 来定义一个储存整数的空的 vector 。当然 vector 可以存任何类
型的数据，比如 vector v 等等。在本课中我们用 int 来举例。我们在 main 函数的开头定义一
个储存整数的动态数组 v 。
在 main 函数的开头写下

vector<int> v;

我们把 到 的平方依次储存到刚才定义的 vector 里面。这里我们需要借助一个循环来完成，循环
枚举 到 。
在刚才的定义下面写下

for (int i = 1; i <= 10; i++) {
v.push_back(i * i);
}

接下来我们依次输出刚才压入 vector 的值。在刚才写下的代码后面继续写

for (int i = 0; i < v.size(); i++) { // 通过v.size()来获取数组长度。
cout << v[i] << " ";
}
cout << endl;

这一节完成了，现在编译运行，看一看效果。
前一节课程，我们学习了简单的 vector 使用和操作。在这一节，我们将要学习一些更高级的用法。
1.1.8. 用动态数组储存自定义数据
动态数组不仅仅可以储存基本的数据类型，还能储存自定义数据类型，比如结构体。
1 10
1 10

struct Ren {
string mingzi; // 名字
int nianling; // 年龄
};
int main() {
vector<Ren> banji; // 班级
Ren xuesheng1, xuesheng2; // 学生1，学生2
xuesheng1.mingzi = "小红";
xuesheng1.nianling = 12;
xuesheng2.mingzi = "yuhaoran";
xuesheng2.nianling = 25;
banji.push_back(xuesheng1);
banji.push_back(xuesheng2);
return 0;
}

1.1.9. 构造函数
我们知道可以通过 push_back() 来向动态数组添加一个元素。如果我们需要一个长度为 的，全是
的动态数组。我们可以像下面这样写。

int n = 10;
vector<int> vec;
for (int i = 0; i < n; i++) {
vec.push_back(1);
}

其实，我们可以通过一个构造函数快速构建这样的一个动态数组。所谓构造函数，就是在定义一个数
据结构的时候可以通过它给这个结构赋予初始值。

int n = 10;
vector<int> vec(n, 1);

上面的代码，我们在定义一个 vector 的时候，调用了构造函数，第一个参数表示初始的动态数组的长
度，第二个参数表示初始的数组里面每个元素的值。如果不传入第二个参数，那么初始的默认是 。
上面用构造函数的写法和用循环是等价的，通过合理的使用构造函数，可以减少代码量，让代码看起
来更优雅。
1.1.10. 二维动态数组
我们都知道，数组可以开二维的，那么动态数组能用二维的吗？答案是肯定的，动态数组也支持二维
的。 vector<vector > vec2 ，这样就定义了一个二维的动态数组。注意， > 中间有一个空
格，这个空格一定要加上，否则在一些老版本的编译器上不能通过编译。
通过上面的方法定义的二维数组，每一维都是空的，我们必须要一维一维的赋值。比如我们规定第一
维的大小为 。
n 1
0
n

int n = 5;
vector<vector<int> > vec2;
for (int i = 0; i < n; i++) {
vector<int> x(i + 1, 1);
vec2.push_back(x);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < vec2[i].size(); j++) {
cout << vec2[i][j] << " ";
}
cout << endl;
}

可以看到，二维动态数组的访问和一维一样。上面代码定义的二维数组如下图
二维动态数组的每一维的长度都可以不一样，可以是任意形状的。借助构造函数，我们可以快速构造
一个 行 列的动态数组， vector<vector > vec2(n, vector(m, 1)) 。
注意 动态数组有一种非常容易写错的写法。

int n = 10;
vector<vector<int> > vec2;
for (int i = 0; i < n; i++) {
vec2[i].push_back(i);
}

这份代码看上去没有什么问题，那我们看看下面的代码

int n = 10;
vector<int> vec;
for (int i = 0; i < n; i++) {
cout << vec[i] << endl;
}

下面的代码明显会访问非法内存，因为我们没有 push_back 过任何元素。再回到上面的代码，我们尝试
访问 vec2[i] 的时候，也会访问非法内存，因为第一维的大小为 。
vector 的维度可以像数组一样多，但是超过两维以后操作起来会比较麻烦，所以一般用 vector 都只到
两维。
n m
0
【小练习】vector 构造函数
我们要定义一个长度为 的，全是 的动态数组 x ，下面哪种方法是错误的。[*1]

vector<int> x(0, n);
vector<int> x(n);

【小练习】Bug 修复
尝试修复下面的代码，使得代码不会访问非法内存。

vector<vector<int> > vec2;
for (int i = 0; i < 10; i++) {
vec2[i].push_back(i);
}

选出下列所有已修复正确的代码。[*2]
n 0

【实践操作】二维 vector 的使用
这一节我们学习二维的 vector 的使用。二维的 vector 就是一个 vector 里面在套一个 vector 。请你尝
试定义一个二维的储存整数的动态数组 v2d 。
在 main 函数里面写下

vector<vector<int> > v2d;

特别注意：里面的 vector 后面有一个空格，这个空格不能少，因为可能会被识别成一个 >> ，
在低版本的编译器下有可能编译不通过。
接下来我们给第一维赋值，第一位的长度为 。
第一维是一个一维的 vector ，在定义后面写下：

for (int i = 0; i < 5; i++) {
v2d.push_back(vector<int>());
}

这里我们通过 vector() 快速够造一个一维的 vector 。
我们用这个二维的 vector 来记录一个 到 的乘法表。
我们让第 行第 列的元素的值为 。
继续写下下面的代码：

for (int i = 0; i < v2d.size(); i++) {
for (int j = 0; j <= i; j++) {
v2d[i].push_back((i + 1) * (j + 1));
}
}

接下里我们输出这个乘法表。
在刚才后面接下来继写

for (int i = 0; i < v2d.size(); i++) {
for (int j = 0; j < v2d[i].size(); j++) {
cout << i + 1 << " * " << j + 1 << " = " << v2d[i][j] << "\t";
}
cout << endl;
}

这一节已经完成了，赶紧编译运行一下，看看效果。
聪明的你一定学会了 vector 怎么使用了。
5
1 5
i j (i + 1) × (j + 1)

1.2. 集合
集合是数学中的一个基本概念，通俗地理解，集合是由一些不重复的数据组成的。比如 就是
一个有 三个元素的集合。
在 C++ 中我们常用的集合是 set 。
1.2.1. 引用库
C++ 中 set 的实现在一个 头文件中，在代码开头引入这个头文件，并且同样加上一
句 using namespace std 。

#include <set>
using namespace std;

1.2.2. 构造一个集合
现在我们来构造一个集合。
C++ 中直接构造一个 set 的语句为： set s 。这样我们定义了一个名为 s 的、储存 T 类型数据的集
合，其中 T 是集合要储存的数据类型。初始的时候 s 是空集合。比如 set aa ， set bbb
等等。
1.2.3. 插入元素
C++ 中用 insert() 方法向集合中插入一个新的元素。注意如果集合中已经存在了某个元素，再次插
入不会产生任何效果，集合中是不会出现重复元素的。

#include <set>
#include <string>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
country.insert("China"); // {"China", "America", "France"}
return 0;
}

1.2.4. 删除元素
C++ 中通过 erase() 方法删除集合中的一个元素，如果集合中不存在这个元素，不进行任何操作。
{1, 2, 3}
1, 2, 3

#include <set>
#include <string>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
country.erase("America"); // {"China", "France"}
country.erase("England"); // {"China", "France"}
return 0;
}

1.2.5. 查找元素
C++ 中如果你想知道某个元素是否在集合中出现，你可以直接用 count() 方法。如果集合中存在我们
要查找的元素，返回 true ，否则会返回 false 。

#include <set>
#include <string>
#include <stdio.h>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
if (country.count("China")) {
cout << "China belong to country" << endl;
}
return 0;
}

1.2.6. 遍历元素
C++ 通过迭代器可以访问集合中的每个元素，迭代器就好像一根手指指向 set 中的某个元素。通过操
作这个手指，我们可以改变它指向的元素。通过 * (注意这里不是乘号的意思) 操作可以获取迭代器指
向的元素。通过 ++ 操作让迭代器指向下一个元素。
迭代的写法比较固定， set::iterator it 就定义了一个指向 set 这种集合的迭代器 it ， T 是任
意的数据类型。 ::iterator 是固定的写法。
如果你不了解迭代器，你只需要先记住用法。

#include <set>
#include <string>
#include <iostream>
using namespace std;
int main() {
set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
country.insert("France"); // {"China", "America", "France"}
for (set<string>::iterator it = country.begin(); it != country.end(); it++) {
cout << (*it) << endl;
}
return 0;
}

注意，在 C++ 中遍历 set 是从小到大遍历的，也就是说 set 会帮我们排序的。
1.2.7. 清空
C++ 中调用 clear() 方法就可清空 set ，同时会清空 set 占用的内存。
我们用 set 的而不用数组来维护集合有两个原因，第一是 set 非常方便，第二是在数组中查询，插入
效率非常的低，而 set 的插入和查询是非常高效的。
C++ set 方法总结
方法 功能
方法 功能
insert 插入一个元素
erase 删除一个元素
count 判断元素是否在 set 中
size 获取元素个数
clear 清空
通过上面列举的方法，可以满足我们平时大多数的需求。关于 set 的更多方法，可以去参考文档，或
者在网络上搜索资料查看。对于比赛来说，上面的方法已经足够了。
C++ set 官方参考文档
【小练习】使用 set
阅读下面的代码。

#include <set>
using namespace std;
int main() {
int a[6] = {10, 2, 3, 4, 2, 10};
set<int> x;
for (int i = 0; i < 6; i++) {
x.insert(a[i]);
}
int sum = 0;
for (set<int>::iterator it = x.begin(); it != x.end(); it++) {
sum += (*it);
}
cout << sum << endl;
return 0;
}

最后的输出是多少 ?
【实践操作】set 的基础使用
首先我们学习如何创建一个 set 。
在 main 函数里面通过 set country 来定义一个储存字符串的空的 set 。当然 set 可以存任何
类型的数据，比如 set s 等等。在本课中我们用 string 来举例。
在 main 函数第一行写下
set country;
我们把 China 、 America 、 France 这三个国家依次插入到 country 。
在刚才的定义下面写下

country.insert("China");
country.insert("America");
country.insert("France");
然后依次输出我们刚才插入的字符串。我们先定义一个迭代器，继续写下

set::iterator it;
然后用迭代器来遍历 country ，继续写下

for (it = country.begin(); it != country.end(); it++) {
cout << *it << " ";
}

cout << endl;
迭代器就像一个下标一样，可以直接 ++ 来访问下一个元素。 begin 代表 set 的开头， end 代表结尾。
我们之前提到 set 是排序的，这里就是按照字典序输出，所以 begin 对应的是字典序最小的串。
到这里，可以点击 运行 看看效果。
接下来我们学习 set 的删除操作。

country.erase("America");
country.erase("England");

接下来我们来判断 country 中是否还有 China ：

if (country.count("China")) {
cout << "China in country." << endl;
}

最后我们将使用完成的 set 清空。继续写下下面的代码：
country.clear();
这一节已经完成了，赶紧 运行 看看效果。
聪明的你一定学会了 set 怎么使用了。
1.2.8. set 和结构体
set 经常会配合结构体来使用，用 set 来储存结构体和 vector 有些区别。正如我们前面所说的那
样， set 是需要经过排序的。系统自带的数据类型有默认的比较大小的规则，而我们自定义的结构
体，系统是不可能知道这个结构体比较大小的方式的。
所以我们需要用一种方式来告诉系统怎么比较这个结构体的大小。其中一种方法叫做操作符重载。我
们需要重新定义小于符号。
下面的代码定义了一个重载了小于符号的结构体：

struct node {
int x, y;
bool operator < (const node &a) const {
if (x == a.x) {
return y < a.y;
} else {
return x < a.x;
}
}
};

上面重载规定了排序方式为，优先按照 x 从小到大排序，如果 x 相同，那么再按照 y 从小到大排序。
经过了重载的结构体，我们就可以直接储存在 set 中了。
【实践操作】set 和结构体练习
这一节课程，我们将学会用 set 来储存一个二维坐标系上的点的集合。
第一步，我们首先使用定义一个用来储存点的结构体。这个结构里面有两个变量，分别用来存 X 坐标
和 Y 坐标。
在 main 函数的上方写下
struct Dian {
int x, y;
};
这一步，我们来给这个结构体添加重载函数，重载小于符号，让系统知道该怎么对这个结构体比较大
小。
在结构体的变量定义下下面接着写下

bool operator < (const Dian &a) const {
if (x == a.x) {
return y < a.y;
} else {
return x < a.x;
}
}

如果两个点的 x 相同，也就是 x == a.x ，那么我们用 y 来比较，否者就直接比较 x ，这一点和
用 sort 排序其实是一样的原理。
这一步我们先定义一个储存点的容器，然后从标准输入输入一个整数 ，然后从标准输入输入 个点
存储到 set 中。
在 main 函数里面写下下面代码
n n

int n;
set<Dian> v;
cin >> n;
for (int i = 0; i < n; i++) {
Dian temp;
cin >> temp.x >> temp.y;
v.insert(temp);
}

最后，我们输出集合中的点。通过 *it 可以获取迭代器指向的元素，而集合里面的元素是结构体，所
以 (*it).x 就是获取结构体的 x 变量的值。
最后输出的点的个数可能和输入的不一样，因为如果重复加入一个点是没有效果的哦。
继续在上一步代码后面写下
for (set::iterator it = v.begin(); it != v.end(); it++) {
cout << (*it).x << " " << (*it).y << endl;
}
这一节已经完成了，点击 运行，然后输入如下数据查看效果。
6
5 6
1 2
2 1
3 4
1 2
1 1
1.3. 映射表
映射是指两个集合之间的元素的相互对应关系。通俗地说，就是一个元素对应另外一个元素。比如有
一个姓名的集合 {“Tom”, “Jone”, “Mary”}，班级集合 。姓名与班级之间可以有如下的映射关系：
(“Tom”) ， (“Jone”) ， (“Mary”)
{1, 2}
class = 1 class = 2 class = 1

我们称其中的姓名集合为 关键字集合（key），班级集合为 值集合（value）。
在 C++ 中我们常用的映射是 map 。
1.3.1. 引用库
在 C++ 中 map 的实现在一个

#include <map>
using namespace std;

1.3.2. 构造一个映射
现在我们来构造一个映射。
在 C++ 中，我们构造一个 map 的语句为： map<T1, T2> m; 。这样我们定义了一个名为 m 的从 T1 类型
到 T2 类型的映射。初始的时候 m 是空映射。比如 map<string,int> m 构建了一个字符串到整数的映
射，这样我们可以把一个字符串和一个整数关联起来。
1.3.3. 插入一对映射
在 C++ 中通过 insert() 方法向集合中插入一个新的映射，参数是一个 pair 类型的结构。这里需要用
到另外一个 STL 模板——元组（ pair ）， pair 很像一个结构体。 pair<int, char>(1, ‘a’) 定义了
一个整数 和字符 a 的 pair 。我们向映射中加入新映射对的时候就是通过加入 pair 来实现的。如果
插入的 key 之前已经有了 value，将不会用插入的新的 value 替代原来的 value，也就是这次插入是无
效的。

#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> dict; // {}
dict.insert(pair<string, int>("Tom", 1)); // {"Tom"‐>1}
dict.insert(pair<string, int>("Jone", 2)); // {"Tom"‐>1, "Jone"‐>2}
dict.insert(pair<string, int>("Mary", 1)); // {"Tom"‐>1, "Jone"‐>2, "Mary"‐>1}
dict.insert(pair<string, int>("Tom", 2)); // {"Tom"‐>1, "Jone"‐>2, "Mary"‐>1}
return 0;
}

1.3.4. 访问映射
在 C++ 中访问映射和数组一样，直接用 [] 就能访问。比如 dict[“Tom”] 就可以获取 “Tom” 的班级了。
而这里有一个比较神奇的地方，如果没有对 “Tom” 做过映射的话，此时你访问 dict[“Tom”] ，系统将会
自动为 “Tom” 生成一个映射，其 value 为对应类型的默认值。并且我们可以之后再给映射赋予新的值，
1
2018/7/5 1.常用基础数据结构
file:///C:/Users/11027/AppData/Local/Temp/mume11865­10172­adnl4u.r1dit.html 17/24
比如 dict[“Tom”] = 3 ，这样为我们提供了另一种方便的插入手段。当然有些时候，我们不希望系统自
动为我们生成映射，这时候我们需要检测 “Tom” 是否已经有映射了，如果已经有映射再继续访问。这
时就需要用 count() 函数进行判断，在下一页中我们会详细介绍。

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main() {
map<string, int> dict; // {}
dict["Tom"] = 1; // {"Tom"‐>1}
dict["Jone"] = 2; // {"Tom"‐>1, "Jone"‐>2}
dict["Mary"] = 1; // {"Tom"‐>1, "Jone"‐>2, "Mary"‐>1}
cout << "Mary is in class " << dict["Mary"] << endl;
cout << "Tom is in class " << dict["Tom"] << endl;
return 0;
}

实际上，我们常常通过访问的方式来插入映射，而不是通过用 pair 插入来实现。
1.3.5. 查找关键字
在 C++ 中，如果你想知道某个关键字是否被映射过，你可以直接用 count() 方法。如果被映射过，返
回 ，否则会返回 。

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main() {
map<string, int> dict; // {}
dict["Tom"] = 1; // {"Tom"‐>1}
dict["Jone"] = 2; // {"Tom"‐>1, "Jone"‐>2}
dict["Mary"] = 1; // {"Tom"‐>1, "Jone"‐>2, "Mary"‐>1}
if (dict.count("Mary")) {
cout << "Mary is in class " << dict["Mary"] << endl;
} else {
cout << "Mary has no class" << endl;
}
return 0;
}

1.3.6. 遍历映射
C++ 通过迭代器可以访问集合中的每个元素。这里迭代器指向的元素是一个结构体，结构体
有 first 和 second 两个变量，分别代表一个映射的 key 和 value。 map 的迭代器的定义和 set 差不
多， map<string, int>::iterator it 就定义了一个迭代器，但是这个迭代器只能指
向 map<string, int> 类型的 map 。
1 0

如果你不了解迭代器，只需要先记住用法，之后慢慢理解即可。

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main() {
map<string, int> dict; // {}
dict["Tom"] = 1; // {"Tom"‐>1}
dict["Jone"] = 2; // {"Tom"‐>1, "Jone"‐>2}
dict["Mary"] = 1; // {"Tom"‐>1, "Jone"‐>2, "Mary"‐>1}
for (map<string, int>::iterator it = dict.begin(); it != dict.end(); it++) {
cout << (*it).first << " ‐> " << (*it).second << endl; // first 是关键字， second 是对应的值
}
return 0;
}

注意，在 C++ 中遍历 map 是按照关键字从小到大遍历的，这一点和 set 有些共性。
1.3.7. 清空
C++ 中只需要调用 clear() 方法就可清空 map 和其占用的内存。
1.3.8. C++ 中 map 常用方法总结
方法 功能
方法 功能
insert 插入一对映射
count 查找关键字
size 获取映射对个数
clear 清空
通过上面列举的方法，可以满足我们平时大多数的需求。关于 map 的更多方法，可以去参考文档，或
者在网络上搜索资料查看。对于算法竞赛来说，上面的方法已经足够了。
C++ map 官方参考文档
【小练习】map 操作匹配测试
map<int, int> v v[1] = “xiaoqiang”
map<string, int> v v[“age”] = 13
map<int, string> v.insert(pair<int, int>(1, 1))

【实践操作】map 的使用
首先我们引入需要的头文件 map ，在代码头部写下
#include

if (dict.count("Mary")) {
cout << "Mary is in class " << dict["Mary"];
dict["Mary"] = 5;
}

到这里，你可以点击运行看看效果。
接下来我们学习 map 的遍历操作。还是通过迭代器来操作，迭代器指针对应的 first 是
key， second 是 value。

for (map<string, int>::iterator it = dict.begin(); it != dict.end(); it++) {
cout << (*it).first << " is in class " << (*it).second << endl;
}

输出完成以后，我们顺便清空这个 map 。调用 dict.clear() 进行清空。
dict.clear();
这一节已经完成了，赶紧 运行 看看效果。
聪明的你一定学会了 map 怎么用了。
5
2018/7/5 1.常用基础数据结构
file:///C:/Users/11027/AppData/Local/Temp/mume11865­10172­adnl4u.r1dit.html 20/24
1.3.9. 二维 map
前面我们学习了二维的 vector ，实际上就是一个 vector 套一个 vector 。 map 当然也有二维的用法。
为什么没有学习二维的 set 呢？因为没有二维 set 这个用法。
而二维的 map 不仅仅能 map 套 map ，还能 map 套 set 。实际上 map 套 set 更容易理解。所以我们先学
习 map 套 set ，然后再学习 map 套 map 。
1.3.10. map 套用 set
为了帮助理解，我们举用一个生活中实际例子。全校有很多班级，每个班级每个人都会有中文名。现
在我们需要用一种方式来记录全校的同学的名字。如果直接用一个 set 记录，对于重名的同学，那么
就没办法分辨了。
我们可以把全校的班级进行编号，对每一个班级建立一个 set ，也就是每个班级都映射成一个 set ，
这样就能分辨不同班级的同名同学了。对于同班的同学来说，一般很少有重名的。
map<int, set > s 就定义上面描述的数据结构，和二维 vector 一样，两个 > > 的空格不能少
了。
这样我们就可以进行插入和查询了。比如对 2 班的 xiaoqiang 同学，我们 s[2].insert(“xiaoqiang”) 。
然后查询 xiaoqiang 是不是一个 2 班的人， s[2].count(“xiaoqiang”) 。然后还可以把他从 2 班删
除， s[2].erase(“xiaoqiang”) 。
【实践操作】二维 map 的使用
这一节我们来是实际操作二维的 map 。首先把班级编号映射成为一个名字到人数的映射。在 main 函数
开头写下。
map<int, map<string, int> > s;
接下来，我么输入 个同学的信息，每个同学一个班级和名字，接下来写下

int n;
cin >> n;
for (int i = 0; i < n; i++) {
int banji;
string mingzi;
cin >> banji >> mingzi;
s[banji][mingzi]++;
}

然后我们遍历整个 map ，首先我们遍历第一维，也就是外层。这个比较简单
n
2018/7/5 1.常用基础数据结构
file:///C:/Users/11027/AppData/Local/Temp/mume11865­10172­adnl4u.r1dit.html 21/24
for (map<int, map<string, int> >::iterator it1 = s.begin(); it1 != s.end(); it1++) {
}
然后遍历第二维，这时候我们需要先分析一下第一维的 it1 迭代器哦，实际上， (*it1).first 是一
个 int ，而 (*it1).second 是一个 map<string, int> 的类型，所以，如果 (*it1).second.begin() 是内
层迭代器的起始位置， (*it1).second.end() 是结束位置。
在循环里面写下
for (map<string, int>::iterator it2 = (*it1).second.begin(); it2 != (*it1).second.end(); it2++)
}
最后我们按照 There are x people named xxx in class b 的格式输出每一条信息。
(*it2).second 对应的是 a 。
(*it2).first 对应的是 xxx 。
(*it1).first 对应的是 b 。
在最内层循环写下
cout << "There are " << (*it2).second << " people named " << (it2).first << " in class " << (
这一节已经完成了，点击 运行，然后输入如下的数据查看效果。
6
1 libai
2 xiaoqiang
2 xiaoqiang
1 jack
100 xxxx
50 xxxx
【例题1】打印锯齿矩阵
锯齿矩阵是指每一行包含的元素个数不相同的矩阵，比如：
3 5 2 6 1
2 3 4
1 6 2 7
读入若干对整数 ，表示在第 行的末尾加上一个元素 。输出最终的锯齿数组。初始时矩阵为
空。
输入格式
第一行输入两个整数 ，其中 表示锯齿数组的行数， 表示插入的元素
总数。
接下来一共 行，每行两个整数 ，表示在第 行的末尾插入一
个元素 。
输出格式
一共输出 行，每行若干个用空格分隔的整数。如果某行没有任何元素，则输出一个空行。
样例输入
3 12
1 3
2 2
2 3
2 4
3 1
3 6
1 5
1 2
1 6
3 2
3 7
1 1
样例输出
3 5 2 6 1
2 3 4
1 6 2 7
【例题2】蒜头君破案
最近某地连续发生了多起盗窃案件，根据监控和路人提供的线索得知，这是一个犯罪团伙。并且还知
道这个犯罪团伙中每个人的身高、体重、年龄。警察想知道这个犯罪团伙中的每个人是不是本市的
(x, y) x y
n, m(1 ≤ n, m ≤ 10000) n m
m x, y(1 ≤ x ≤ n, 0 ≤ y ≤ 10000) x
y
n

（如果本市有这个特征的人就视为是本市的）。但本市人口太多，又不能一个一个排查。警察又急需
这条信息来缩小范围，所以警察特来找到聪明的你来帮忙解决这个棘手的问题。
输入格式
第一行将会输入两个数字 和 。 代表本市的人口数目， 代
表犯罪团伙的数量。
后面 行每行有 个数字代表本市每个人的身高、体重、年龄。然后会有 行每行有 个数字代表
犯罪团伙每个人的身高、体重、年龄。
输出格式
输出 行，每行输出一个 “yes” 或 “no” ， “yes” 代表这个罪犯是本市的， “no” 代表这个罪犯不是本
市的。
样例输入
3 2
166 50 30
178 60 23
132 40 15
167 50 30
178 60 23
样例输出
no
yes
【例题3】蒜头君的藏书
蒜头君有个学霸同学，家中藏书真可谓汗牛充栋。小明想考一考学霸，给学霸出了一道难题。小明问
这么多书籍，到底有多少本不一样的书，每样书的名字是什么？（因为有的书名是一样的，所以我们
把它们视为同样的书）学霸就是学霸，张口就说出了答案。不知道你是否也是学霸？一起来挑战下？
输入格式
第一行是书籍总量 。
然后有 行书名（书名是一个英文字符串，字符串的长度小于 ，中间没有空格）。
输出格式
第一行是不同书籍的数量，然后按照书名的字典序输出书名和数量。
样例输入
n(1 ≤ n ≤ 10 )
6 m(1 ≤ m ≤ 1000) n m
n 3 m 3
m
n(1 ≤ n ≤ 10 )
6
n 100

4
English
Math
Chinese
Chinese
样例输出
3
Chinese 2
English 1
Math 1