一份面向刷题的 C++ STL 使用指南

前言

一直以来，我都是优先选择 C++ 作为刷算法题的语言，这并不是因为它的语法多么现代化，而是因为它出色的运行速度和具有封装了各种数据结构的 STL。

本文主要介绍常见 STL 的使用，为有使用 C++ 刷题需求的朋友提供一份总结。

常用容器类型

这里主要对 STL 提供的常用容器类型的使用进行介绍，它们通常在写题中有比较高的实用频率。

vector

vector 是 STL 中封装的「动态数组」结构，和普通的静态数组相比，它可以动态添加元素、还具有相应的扩容机制。通常在 LeetCode 刷题的时候作为数组使用，它被包含在下面的头文件中。

#include 
1

下面是 vector 的常用方法，它的随机访问方式和普通数组一致。

// 声明一个空的存储 int 类型的动态数组
vector<int> ans;

// c++11
vector<int> nums{0, 1, 2, 3};

// 声明一个长度为 n，存储 int 类型的动态数组，并将元素初始化为 0
vector<int> dp(n, 0);

// 将元素 a 添加到动态数组末尾
ans.push_back(a);
// 将动态数组末尾的元素移除
ans.pop_back();
1
2
3
4
5
6
7
8
9
10
11
12
13

如果想深入了解 vector 可以看这篇文章：C++ STL容器总结之vector（超详细版）

stack

stack 是 STL 中封装的「栈」数据结构，它具有后进先出的特性，常用应用在树的非递归遍历、单调栈算法和逆序操作等场景中。使用 stack 需要先导入下面头文件：

#include 
1

下面是 stack 的使用方法：

// 初始化一个空的栈
stack<int> s;
// 判断栈是否为空，返回 bool
s.empty()

// 将元素 a 压入栈中
s.push(a);

// 获取栈顶元素，赋值给 b 变量
int b = s.top();

// 将栈顶元素弹出栈中
s.pop();
1
2
3
4
5
6
7
8
9
10
11
12
13

queue

queue 是 STL 中封装的「队列」数据结构，它具先进先出的特性，常用应用在广度优先算法、spfa等场景中。使用 queue 需要先导入下面头文件：

#include 
1

下面是 queue 的使用方法：

// 初始化一个空的队列
queue<int> q;

// 判断队列是否为空，返回 bool
q.empty()

// 将元素 a 加入到队列中
q.push(a);

// 获取队首元素，赋值给 b 变量
int b = q.front();

// 将队首元素移出队列
q.pop();
1
2
3
4
5
6
7
8
9
10
11
12
13
14

priority_queue

priority_queue 是 STL 中封装的优先队列，也就是我们常说的「堆」结构，它常应用在堆优化 Dijkstra 算法、Top K 问题等场景中。priority_queue 和 queue 一样，是包含在下面的头文件中。

#include 
1

下面是 priority_queue 的使用方法，要注意的是，它的 push 和 pop 操作的时间复杂度是 $O(logn)$ 的。

// 大根堆
priority_queue<int> pq;
// 小根堆
priority_queue<int, vector<int>, greater<int>> pq;

// 判断堆是否为空，返回 bool
pq.empty()

// 将元素 a 加入到堆中
pq.push(a);

// 获取堆顶元素，赋值给 b 变量
int b = pq.top();

// 将堆顶元素移出堆
pq.pop();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

set 和 unordered_set

set 是 C++ STL 中封装的「集合」类型，其中 set 的底层实现是红黑树，它是有序的，插入和删除的复杂度都是 $O(logn)$；unordered_set 的底层实现是哈希表，它是无序的，插入和删除的复杂度都是 $O(1)$。

// 导入 set
#include 
// 导入 unordered_set
#include 
1
2
3
4

set 和 unordered_set 提供的借口基本一致，下面是使用简单方法：

// 集合声明
set<int> s;
// 集合声明
unordered_set<int> s;

// 将 a 放入集合中
s.insert(a);

// 将 a 移出集合
s.erase(a);

// 返回 a 在集合中的个数
s.count(a);
1
2
3
4
5
6
7
8
9
10
11
12
13

map 和 unordered_map

map 是 STL 中提供的「key-value（键值对）」结构。和 set 相似，map 的底层实现是红黑树，它存储的键值对是按键排序的，访问、插入和删除的复杂度都是 $O(logn)$；unordered_map 的底层实现是哈希表，它是无序的，插入和删除的复杂度都是 $O(1)$。

// 导入 map
#include 
// 导入 unordered_map
#include 
1
2
3
4

访问 map 和 unordered_map 中元素的方法和访问数组相同，直接使用下标访问，如 a[0]。下面演示的是它的遍历方法：

unordered_map<int, int> hash;

// k 表示键，v 表示对应的值
for (auto [k, v]: hash) {
	cout << k << " " << v << endl;
}
1
2
3
4
5
6

pair

pair 是一个可以保存两个值的机构体，它的主要功能将一对值(类型T1和T2)组合成一个值，可以通过访问 first 和 second 两个属性来访问存的两个值。它的存储结构像下面这样：

template<class _T1, class _T2>
struct pair {
	_T1 first;       // std::pair中保存的第一个值
	_T2 second;      // std::pair中保存的第二个值
	// ...
};
1
2
3
4
5
6

pair 的常用方法如下：

// 创建
pair<int, int> a;
pair<int, int> b(10, 24);
pair<int, int> c = make_pair(10, 24);

// 访问元素
a.first
b.second
1
2
3
4
5
6
7
8

还有个需要学习的点，pair 中实现的 < 运算符如下，是优先比较第一个值，得不出结果再去进行第二个元素的比较。

template<class _T1, class _T2>
inline bool operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) { 
	return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second); 
}
1
2
3
4

常用算法封装

排序

sort 是 STL 中对排序算法的封装，它内部使用的是快速排序算法，是一种不稳定的排序算法，时间复杂度是 $O(nlogn)$。

// 需要排序的数组
vector<int> nums;

// 升序排序（从小到大）
sort(nums.begin(), nums.end());

// 降序排序（从大到小）
sort(nums.begin(), nums.end(), greater<int>());
sort(nums.begin(), nums.end(), [](const int &a, const int &b) {
	return a > b;
});
1
2
3
4
5
6
7
8
9
10
11

sort 也可以对自定义类型进行排序，下面是自定义结构体进行排序的例子。

struct Edge {
	int u, v, w;
};

vector<Edge> edges;

// 按照边的权值降序排序
sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
	return a.w > b.w;
});
1
2
3
4
5
6
7
8
9
10

二分查找

STL 对二分查找的常用封装有 binary_search、lower_bound 和 upper_bound，二分查找的时间复杂度是 $O(logn)$，使用的时候要注意保证查找的数组是有序的。下面是使用场景的总结：

vector<int> nums; // 需要先进行排序

// 查找 nums 中是否有等于 target 的数
binary_search(nums.begin(), nums.end(), target);

// 返回 nums 中第一个大于或等于 target 元素位置的迭代器
lower_bound(nums.begin(), nums.end(), target);
// 返回 nums 中第一个大于 target 元素位置的迭代器
upper_bound(nums.begin(), nums.end(), target);

// 返回 nums 中第一个小于或等于 target 元素位置的迭代器
lower_bound(nums.begin(), nums.end(), target, greater<int>());
// 返回 nums 中第一个小于 target 元素位置的迭代器
upper_bound(nums.begin(), nums.end(), target, greater<int>());

// 通过这种方式可得到下标
int index = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

逆序

reverse 是 STL 提供的「对容器中元素逆序」算法的封装，时间复杂度是 $O(n)$。

reverse(nums.begin(), nums.end());
1

求和

accumulate 是 STL 提供的「对容器中元素进行区间求和」算法的封装。

int sum = accumulate(nums.begin(), nums.end(), 0);
1

求和函数的效果和下面相同，时间复杂度是 $O(n)$。

int sum = 0;
for (int i = 0; i < nums.size(); i++) {
	sum += nums[i];
}
1
2
3
4

区间赋值

fill 是 STL 提供的「对容器中元素进行区间赋相同值」算法的封装。

fill(dp.begin(), dp.end(), -1);
1

fill 函数的效果和下面相同，时间复杂度是 $O(n)$。

for (int i = 0; i < dp.size(); i++) {
	dp[i] = -1;
}
1
2
3

---

iota 是 STL 提供的「对容器中元素进行区间赋递增值」算法的封装。

// 第三个参数为第一个元素的值，之后元素的值以此 +1 递增
iota(fa.begin(), fa.end(), 0);
1
2

iota 函数的效果和下面相同，时间复杂度是 $O(n)$。

int val = 0;
for (int i = 0; i < fa.size(); i++) {
	fa[i] = val;
	val++;
}
1
2
3
4
5

参考资料

• 《C++ Primer Plus 第6版中文版（2020年）》
• 《STL源码剖析》