在 OI 竞赛中,可以使用的语言有 C++、C、Pascal,其中 C++ 最大的优势是,它本身提供了一个模板库 —— Standard Template Library(标准模板库),简称 STL。STL 包含一系列算法和容器等,合理地使用 STL,可以在提高编写代码的效率。NOI 系列比赛自 2011 年起允许 C++ 选手使用 STL,所以我们应该利用好 STL,发挥 C++ 语言的优势。
分类
STL 可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。
本文主要讲解容器、迭代器、算法,其他的几个部分在竞赛中很少使用到。
命名空间
命名空间(namespace)是 C++ 的一个特性,它被用于解决名称冲突,比如假设 Menci 和 Fuxey 都在自己的头文件里编写了一个 work()
函数,如果这两个函数我们都要用,则名称会产生冲突,但如果两人都将自己的函数写在单独的命名空间内,就成了 Menci::work()
和 Fuxey::work()
,就不会冲突了。
STL 的所有内容都包含在 std
命名空间内。
如果我们要调用 STL 中的 sort
函数(下文会有提到),要这样写:
std::sort(a, a + n);
我们也可以将 std::sort
这个函数“导入”到全局中,就可以直接 sort(a, a + n)
这样调用了。
使用 using
关键字来“导入”命名空间中的函数或类。
using std::sort;
也可以将整个命名空间导入全局,这样就可以直接访问命名空间中的所有内容,但更容易产生名称冲突(比如你可能会声明一个叫做 max
的变量,但它会覆盖 STL 中的 max
函数)。
使用 using namespace
来“导入”整个命名空间。
using namespace std;
算法
STL 中的算法主要包含在 <algorithm>
头文件中,这个文件名要记住,每天念一遍。
排序
STL 中提供一系列与排序有关的函数,其中最常用到的是 sort
和 stable_sort
,sort
是不稳定的排序,它的期望时间复杂度为 ,stable_sort
是稳定的排序,它的时间复杂度为 。
sort
使用类似与快速排序的算法,在大多数情况下能获得最高的效率,stable_sort
使用多路归并排序算法,可以在稳定的前提下取得较高的效率。一般常用 sort
。
用法(以 sort
为例,stable_sort
相同):
对左闭右开区间 [l, r) 排序,使用 sort(l, r)
。其中 l 和 r 是指向元素的迭代器,在了解迭代器之前,我们可以将其理解为指向元素的指针。
注意这里的区间表示是一个左闭右开区间,STL 中经常会出现这种区间,如果我们要对一个数组 a 的前 n 个元素进行排序,则对应区间为 [a, a + n),因为 a 指向数组的第一个元素(下标为 0),a + n 指向数组的第 n 个元素之后。
sort
函数默认是升序排序,如果需要降序,可以通过自定义“比较函数”来实现。
bool compare(int a, int b) {
return a > b;
}
std::sort(a, a + n, &compare);
下面的代码演示了读入 n(n <= 100000)个数,并降序排序后输出。
#include <cstdio>
#include <algorithm>
const int MAXN = 100000;
int n;
int a[MAXN];
bool compare(int a, int b) {
return a > b;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
std::sort(a, a + n, &compare);
for (int i = 0; i < n; i++) {
printf("%d\n", a[i]);
}
return 0;
}
降序排序是大于号,升序排序是小于号(注意不能加等号变成大于等于、小于等于),如果不指定比较函数,默认为升序。
也可以通过重载运算符或者定义比较函数的方法对结构体进行排序:
struct student_t {
unsigned int id;
long double score;
bool operator<(const student_t &other) const {
return score < other.score;
}
} students[MAXN];
bool compare(const student_t &student1, const student_t &student2) {
return student1.score < student2.score;
}
std::sort(students, students + n, &compare);
写在结构体中的 operator<
即为重载运算符,这让我们的结构体支持小于号的比较操作。
结构体下面的 compare
是比较函数,比较函数和重载运算符只需要写一个就够了。
注意两种写法中的 const
和 &
都不能省略。
去重
使用 unique
函数来去除数组中的重复元素,其调用格式与 sort
类似,注意调用 unique
前必须保证数组是有序的(升序降序都可以)。
std::sort(a, a + n);
std::unique(a, a + n);
unique
函数返回去重后的数组的最后一个元素之后,一般通过用返回值减去首地址的方法获得不重复的元素数量:
int count = std::unique(a, a + n) - a;
下面的代码演示了读入 n(n <= 100000)个数,并升序排序并去重后输出。
#include <cstdio>
#include <algorithm>
const int MAXN = 100000;
int n;
int a[MAXN];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
std::sort(a, a + n);
int count = std::unique(a, a + n) - a;
for (int i = 0; i < count; i++) {
printf("%d\n", a[i]);
}
return 0;
}
较大、较小值
使用 max
和 min
来取得两个数中较大或较小的。
int a = -1, b = 890;
x = std::max(a, b); // 结果为 890
y = std::min(a, b); // 结果为 -1
查找
STL 中常用的用于查找的函数有三个:lower_bound
、upper_bound
、binary_search
,一般 lower_bound
最为常用。
lower_bound
用于在一个升序序列中查找某个元素,并返回第一个不小于该元素的元素的迭代器,如果找不到,则返回指向序列中最后一个元素之后的迭代器。
upper_bound
用于在一个升序序列中查找某个元素,并返回第一个大于该元素的元素的迭代器,如果找不到,则返回指向序列中最后一个元素之后的迭代器。
binary_search
用于确定某个元素有没有在一个升序序列中出现过,返回 true
或 false
。
三个函数的时间复杂度均为。
int a[8] = { -9, 5, -1, 2, 7, 1, -2, 2 }, n = 8;
std::sort(a, a + n);
// a = { -9, -2, -1, 1, 2, 2, 5, 7 }
int *p1 = std::lower_bound(a, a + n, 1);
// p1 指向 a 中第 4 个元素 a[3] = 1
int *p2 = std::lower_bound(a, a + n, 2);
// p2 指向 a 中第 5 个元素 a[4] = 2
int *p3 = std::upper_bound(a, a + n, 2);
// p3 指向 a 中第 7 个元素 a[6] = 5
int *p4 = std::lower_bound(a, a + n, 8);
// p4 = a + n,因为数组 a 中没有不小于 8 的元素,此时访问 *p4 会越界
bool flag = std::binary_search(a, a + n, 3);
// flag = false 因为数组 a 中没有 3
交换
使用 swap
函数交换两个变量的值。
int a = -1, b = 1;
std::swap(a, b);
// a = 1, b = -1
迭代器
迭代器是用于访问 STL 容器中元素的一种数据类型,一般迭代器的声明如下:
std::CONTAINER<T>::iterator p;
上述代码声明了一个迭代器 p
,其中 CONTAINER
是容器类型,可以是 vector
、set
等,T
是容器中元素的类型。
一般的,容器的 begin()
方法返回首个元素的迭代器,end()
方法返回最后一个元素之后的迭代器。这两个迭代器确定了一个包含容器内所有元素的左闭右开区间 [begin(), end())
。对于任何指向有效元素的迭代器都有其不等于 end()
,end()
并不指向任何一个元素,试图访问 end()
对应的元素是非法的。
在使用 STL 提供的算法时,可以用迭代器表示一个区间,如:
std::sort(v.begin(), v.end());
一些容器的迭代器可以支持随机访问,如指向 vector[i]
的迭代器为 vector.begin() + i
,而另一些容器如 set
不支持这种用法。
所有的迭代器都支持使用 ++
和 --
运算符将迭代器加一或减一。
迭代器的用法类似于指向数组元素的指针,对于迭代器 p
,用 *p
得到迭代器对应的元素;如果该迭代器所对应的元素类型为结构体,则可以直接使用 ->
访问其对应结构体中的元素。
一般的,使用迭代器遍历容器类似于下述代码:
for (std::CONTAINER<T>::iterator p = C.begin(); p != C.end(); p++) {
std::cout << *p << std::endl;
}
容器
数组 vector
STL 在头文件 <vector>
提供了一个可变长的数组 vector
,它支持动态的插入、删除操作。
以下代码声明了一个 vector
,它的每个元素类型为 int
,初始元素数量为 0。
std::vector<int> v;
以下代码声明了一个 vector
,它的每个元素类型为 int
,初始元素数量为 n。
std::vector<int> v(n);
vector
提供 begin()
和 end()
,分别获取指向第一个元素和最后一个元素之后的迭代器。
以下代码对 v 中的所有元素以升序排序:
std::sort(v.begin(), v.end());
使用 size()
得到 vector
的元素数量,使用 resize()
重新指定 vector
的元素数量。
分别使用 push_back()
和 pop_back()
在 vector
的尾部加入或删除元素,这两个过程的时间复杂度为。
使用 insert()
在某个特定的位置插入一个元素,时间复杂度为。
使用 erase()
删除某个位置的元素,时间复杂度为。
std::vector<int> v;
// v.size() = 0
v.push_back(23333);
// v.size() = 1, v = { 23333 }
v.insert(v.begin() + 0, 890);
// v.size() = 2, v = { 890, 23333 }
v.insert(v.begin() + 1, 12345);
// v.size() = 3, v = { 890, 12345, 23333 }
v.erase(v.begin() + 0);
// v.size() = 2, v = { 12345, 23333 }
for (nt i = 0; i < v.size(); i++) {
printf("%d\n", v[i]);
}
// 依次输出 12345、23333
v.pop_back();
// v.size() = 1, v = { 12345 }
注意,在加入元素时,如果 vector
拥有的内存空间不足以存放欲加入的元素,则 vector
会申请一块新的内存,并将旧数据拷贝过去,这个过程通常花费 的时间。
集合 set
STL 在头文件 <set>
中提供了一个有序集合 set
,其中的元素全部是唯一的,并且插入进的元素自动按照升序排列,但 set
不支持通过下标定位某个元素,只能通过迭代器遍历。
以下代码声明了一个 int
类型的集合。
std::set<int> s;
使用 insert()
在集合中加入一个元素,其时间复杂度为。
使用 erase()
删除集合中某个元素或某个位置的元素,其时间复杂度均为。
set
自身提供 lower_bound()
用于定位元素,其作用与前文中的同名函数类似,也可以使用 find()
来精确查找元素。
遍历 set
只能使用迭代器。set
的迭代器为 set<T>::iterator
,其中 T
为元素类型。
std::set<int> s;
s.insert(23333);
s.insert(23333); // 重复插入无效
s.insert(66666);
s.insert(890);
s.insert(-1);
// s.size() = 4, s = { -1, 890, 23333, 66666 }
s.erase(66666);
// s.size() = 3, s = { -1, 890, 23333 }
std::set<int>::iterator p1 = s.lower_bound(555);
// *p1 = 890
std::set<int>::iterator p2 = s.find(555);
// p2 = s.end(),因为未找到 555
s.erase(p1);
// s.size() = 2, s = { -1, 23333 }
for (std::set<int>::iterator p = s.begin(); p != s.end(); p++) {
printf("%d\n", *p);
}
// 依次输出 -1、23333
上述代码中运用的迭代器的方法在 STL 容器中较为常见。
字符串 string
STL 在头文件 <string>
中将一些与字符串有关的操作封装在了 string
内。
使用 cin
和 cout
来输入、输出字符串。
使用 find()
查找另一个字符串在该字符串中的出现位置,返回结果从 0 开始。
使用 c_str()
获得 string
对应的 const char *
类型数据,可用于向 C 库函数传递。
std::string s = "Menci";
int pos = s.find("23333");
// pos = string::npos,因为没有找到 23333
pos = s.find("ci");
// pos = 3,因为出现位置为第 4 个字符
char ch = s[0];
// ch = 'M'
std::cout << s << std::endl;
puts(s.c_str());
// 输出两次 Menci
队列 queue
STL 在头文件 <queue>
中提供了先入先出(FIFO)队列 queue
。
使用 push()
向队列中加入元素。
使用 front()
获取队首元素(并不删除)。
使用 pop()
删除队首元素。
使用 empty()
判断队列是否为空。
std::queue<int> q;
bool flag = q.empty();
// flag = true,队列初始为空
q.push(23333);
q.push(66666);
while (!q.empty()) {
printf("%d\n", q.front());
q.pop();
}
// 依次输出 23333,66666
栈 stack
STL 在头文件 <stack>
提供了后入先出(LIFO)栈 stack
。
使用 push()
向栈中加入元素。
使用 top()
获取栈顶元素(并不删除)。
使用 pop()
删除栈顶元素。
使用 empty()
判断栈是否为空。
std::stack<int> s;
bool flag = s.empty();
// flag = true,栈初始为空
s.push(23333);
s.push(66666);
while (!s.empty()) {
printf("%d\n", s.top());
s.pop();
}
// 依次输出 66666,23333
优先队列 priority_queue
STL 在头文件 <queue>
中提供优先队列 priority_queue
,在任意时间都能取出队列中的最大值。
使用 push()
向优先队列中加入元素,其时间复杂度为。
使用 top()
获取优先队列中最大的元素(并不删除),其时间复杂度为。
使用 pop()
删除优先队列中最大元素,其时间复杂度为。
使用 empty()
判断优先队列是否为空。
std::priority_queue<int> q;
bool flag = q.empty();
// flag = true,优先队列初始为空
q.push(23333);
q.push(-1);
q.push(66666);
while (!q.empty()) {
printf("%d\n", q.top());
q.pop();
}
// 依次输出 66666,23333,-1
priority_queue
默认提供队列中的最大值,也可以以以下声明方式让 priority_queue
提供最小值。
std::priority_queue<T, std::vector<T>, std::greater<T> > q;
注意把三个 T
换成优先队列中元素的类型(如 int
);std::greater<T>
的右边要加一个空格,否则会被编译器误认为是 >>
右移运算符。