参考学习视频：

在线文档查看地址：https://io.zouht.com/154.html
Markdown 原文件下载地址：https://run.sh.cn/stlmd

---

1 前言

STL（Standard Template Library，标准模板库）是 C++ 标准库的一部分，提供了一系列高效且封装良好的数据结构和算法模板。STL 在算法竞赛中应用广泛，灵活且正确地使用 STL 不仅能大幅节省代码编写时间，还能让代码更简洁、可读性更高、调试更方便。

注意：

• STL 功能丰富，但其实现复杂，效率通常不及专门针对题目手写的数据结构与算法。
• 使用 STL 是以运行时间为代价换取开发效率。
• 在实际比赛中要根据题目需求和时间限制权衡是否使用 STL。

本文重点介绍算法竞赛中常用的 STL 容器和算法，不对仿函数和迭代器展开细讲。

---

2 常用容器

2.1 内容总览

类别	容器名称	是否讲解	备注
顺序容器	array	未讲解
	vector	✔ 已讲解	常用且重要
	deque	未讲解
	forward_list	未讲解
	list	未讲解
关联容器	set	✔ 已讲解	常用且重要
	map	✔ 已讲解	常用且重要
	multiset	未讲解
	multimap	未讲解
无序关联容器	unordered_set	未讲解
	unordered_map	未讲解
	unordered_multiset	未讲解
	unordered_multimap	未讲解
容器适配器	stack	✔ 已讲解
	queue	✔ 已讲解
	priority_queue	✔ 已讲解
	flat_set	未讲解
	flat_map	未讲解
字符串	string (basic_string<char>)	✔ 已讲解
元组	pair	✔ 已讲解
	tuple	未讲解

---

2.2 向量 vector

#include <vector>

2.2.1 概述

vector 是一种连续存储的顺序容器（类似数组），但支持动态调整长度。数据存储在堆上，安全且方便，常用于替代普通数组。

2.2.2 常用方法

• 构造

vector<int> arr;               // 空vector
vector<int> arr(100);          // 长度为100，元素默认初始化
vector<int> arr(100, 1);       // 长度为100，元素初值为1
vector<vector<int>> mat(100);  // 二维vector，100行，列未指定
vector<vector<int>> mat(100, vector<int>(666, -1)); // 100行666列，初值-1

注意：
下面两种写法是错误的！

vector<int> arr[100](100, 1);   // 错误
vector<int> arr(100, 1)[100];   // 错误

• 尾接和尾删

arr.push_back(1);   // 在末尾添加元素1
arr.pop_back();     // 删除末尾元素

• 访问元素

int x = arr[0];     // 获取第一个元素
arr[1] = 100;       // 修改第二个元素

• 获取长度

int n = arr.size();

• 清空

arr.clear();

• 判空

bool empty = arr.empty();

• 改变长度

arr.resize(50);         // 改为长度50，超出部分被删除或填默认值
arr.resize(50, 2);      // 扩展时新增元素初值为2

2.2.3 适用场景

• 动态数组，长度不确定时首选。
• 二维或多维数组，堆上分配，防止栈溢出。
• 需要频繁尾部插入或删除的场合。

2.2.4 注意事项

• 提前指定长度，减少重分配

vector<int> a(1e8);
for (int i = 0; i < a.size(); i++) a[i] = i;

• 注意 size_t 溢出，尤其在 32 位编译器中：

size_t n = a.size();
long long x = n * n;   // 可能溢出，导致错误结果

---

2.3 栈 stack

#include <stack>

2.3.1 概述

基于双端队列 deque 实现的先进后出（LIFO）数据结构。

2.3.2 常用方法

操作	语法	示例
构造	stack<T> stk;	stack<int> stk;
进栈	.push(x)	stk.push(1);
出栈	.pop()	stk.pop();
取栈顶	.top()	int x = stk.top();

2.3.3 注意事项

• 不能访问内部元素，只能操作栈顶。
• 错误示例：

for (int i = 0; i < stk.size(); i++) cout << stk[i];   // 错误
for (auto x : stk) cout << x;                          // 错误

---

2.4 队列 queue

#include <queue>

2.4.1 概述

基于双端队列 deque 实现的先进先出（FIFO）数据结构。

2.4.2 常用方法

操作	语法	示例
构造	queue<T> que;	queue<int> que;
入队	.push(x)	que.push(1);
出队	.pop()	que.pop();
取队首	.front()	int x = que.front();
取队尾	.back()	int x = que.back();

2.4.3 注意事项

• 不能访问队列中间元素。
• 错误示例：

for (int i = 0; i < que.size(); i++) cout << que[i];   // 错误
for (auto x : que) cout << x;                          // 错误

---

2.5 优先队列 priority_queue

#include <queue>

2.5.1 概述

基于二叉堆实现，支持对数时间插入和取出最大/最小元素。

2.5.2 常用方法

• 构造

priority_queue<int> pque1;                            // 默认大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 小顶堆

• 操作

pque.push(3);    // 插入元素
pque.pop();      // 弹出堆顶元素
int x = pque.top(); // 访问堆顶元素

2.5.3 适用场景

• 维护动态数据集中的最大/最小元素。
• 需要频繁插入和删除同时快速访问最大/最小元素。

2.5.4 注意事项

• 只能访问堆顶元素，不能随机访问

下面是你提供内容的整理版，条理更清晰，方便阅读和记忆：

---

2.6 集合 set

#include <set>

提供对数时间的插入、删除、查找操作。底层实现是红黑树。

特性	解释	set	multiset	unordered_set
确定性	一个元素要么在集合中，要么不在	✔	✔	✔
互异性	一个元素仅出现一次	✔	❌（可重复）	✔
无序性	集合元素是否有顺序	❌（有序，从小到大）	❌（有序）	✔（无序）

2.6.1 常用方法

构造

set<类型, 比较器> st;

• 类型：存储的数据类型。
• 比较器：比较元素大小，默认是 less<类型>（升序），可自定义。

示例：

set<int> st1;               // 默认升序
set<int, greater<int>> st2; // 降序

自定义比较器涉及重载函数调用运算符或lambda，初学者可暂时不深入。

遍历

使用迭代器：

for (set<int>::iterator it = st.begin(); it != st.end(); ++it)cout << *it << endl;

基于范围的循环（C++11）：

for (auto &ele : st)cout << ele << endl;

其他常用操作

作用	用法	示例
插入元素	.insert(元素)	st.insert(1);
删除元素	.erase(元素)	st.erase(2);
查找元素	.find(元素)	auto it = st.find(1);
判断元素存在	.count(元素)	st.count(3);
查看大小/清空/判空	略	略

插入、删除、查找时间复杂度均为 $O(\log n)$。

2.6.2 适用场景

• 元素去重
• 维护有序元素
• 判断元素是否出现过（当元素范围大或数量大时，vis数组不可行，set可用）

2.6.3 注意事项

• 无下标访问：set没有索引，不支持 st[0] 访问。
• 元素只读：set的迭代器返回的是const元素，不能修改元素值。修改需先 erase 再 insert。
• 迭代器不可算下标：set迭代器不支持相减，不能算出元素索引。

---

2.7 映射 map

#include <map>

提供对数时间的键值对存储，底层是红黑树。

特性	解释	map	multimap	unordered_map
互异性	一个键仅出现一次	✔	❌（键可重复）	✔
无序性	键是否有序	❌（有序，升序）	❌（有序）	✔（无序）

2.7.1 常用方法

构造

map<键类型, 值类型, 比较器> mp;

• 键类型：键的数据类型。
• 值类型：值的数据类型。
• 比较器：键比较方式，默认 less。

示例：

map<int, int> mp1;               // 升序
map<int, int, greater<int>> mp2; // 降序

遍历

for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)cout << it->first << ' ' << it->second << endl;

基于范围循环（C++11）：

for (auto &pr : mp)cout << pr.first << ' ' << pr.second << endl;

结构化绑定（C++17）：

for (auto &[key, val] : mp)cout << key << ' ' << val << endl;

其他常用操作

作用	用法	示例
增改查元素	中括号访问	mp[1] = 2;
查找元素(迭代器)	.find(键)	auto it = mp.find(1);
删除元素	.erase(键)	mp.erase(2);
判断元素存在	.count(键)	mp.count(3);

增删查时间复杂度均为 $O(\log n)$。

2.7.2 适用场景

• 维护键值对映射
• 统计字符串出现次数等

2.7.3 注意事项

• 中括号访问会自动插入键（值为默认值）
• 迭代器不可算下标（不支持相减）

---

2.8 字符串 string

#include <string>

字符串类，方便操作文本。

2.8.1 常用方法

构造

string s1;           // 空字符串
string s2 = "awa!";  // 赋值初始化
string s3(10, '6');  // 构造字符串，内容为 "6666666666"

输入输出

string s;
cin >> s;
cout << s;

C语言兼容：

char buf[100];
scanf("%s", buf);
s = buf;
printf("%s", s.c_str());

其他操作

作用	用法	示例
修改/访问字符	[]	s[1] = 'a';
字符串比较	==	if (s1 == s2) ...
字符串拼接	+	string s = s1 + s2;
尾接字符串	+=	s += "awa";
取子串	.substr(起点, 长度)	string sub = s.substr(2, 10);
查找字符串	.find(子串, 起点)	int pos = s.find("awa");

数值与字符串互转（C++11起）

来源类型	目标类型	函数
数值转字符串	string	to_string()
string转int	int	stoi()
string转long long	long long	stoll()
string转float	float	stof()
string转double	double	stod()
string转long double	long double	stold()

2.8.2 适用场景

• 强烈推荐替代传统字符数组
• 方便安全处理字符串

2.8.3 注意事项

• 字符串拼接用 += 性能更好，+ 会产生临时对象，易导致超时。

  // 慢
  string s;
  for (int i = 0; i < 5e5; i++)s = s + "a";// 快
  string s;
  for (int i = 0; i < 5e5; i++)s += "a";
  

• .substr() 第二个参数是子串长度，不是终点位置，需区分Java等语言。

• .find() 是暴力实现，时间复杂度 $O(nm)$，无内置KMP。

---

2.9 二元组 pair

#include <utility>

用于存储两个值的组合。

2.9.1 常用方法

构造

pair<类型1, 类型2> pr;
pair<int, int> p1;
pair<int, long long> p2;
pair<char, int> p3;

赋值

pair<int, char> pr = make_pair(1, 'a');  // 传统
pair<int, char> pr = {1, 'a'};           // C++11列表初始化

访问

int awa = pr.first;
char bwb = pr.second;

结构化绑定（C++17）：

auto &[awa, bwb] = pr;

判同

pair<int,int> p1 = {1,2};
pair<int,int> p2 = {1,3};
if (p1 == p2) { ... }  // false

2.9.2 适用场景

• 需要存储一对相关数据
• 性能和自定义结构体相近

好的，我帮你继续整理以下内容，保持原文简洁明了，方便阅读和理解：

---

3 迭代器简介

3.1 迭代器是什么？

举例说明：

vector<int> a{1, 2, 3, 4};
for (int i = 0; i < a.size(); i++)cout << a[i] << endl;  // 下标遍历

使用迭代器遍历：

for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)cout << *it << endl;

• a.begin()：返回指向第一个元素的迭代器
• a.end()：返回指向最后一个元素后面一位的迭代器
• 迭代器支持自增（++it）操作，向后移动到下一个元素
• 迭代器类似指针，使用 *it 访问当前元素的值

3.2 为何需要迭代器？

• 许多数据结构（如红黑树实现的 set）不支持下标访问
• 迭代器定义了遍历数据结构的统一接口，无论线性还是非线性
• 例如遍历 set：

for (set<int>::iterator it = st.begin(); it != st.end(); ++it)cout << *it << endl;

3.3 迭代器用法

以 vector 迭代器为例：

• .begin()：头迭代器（指向第一个元素）
• .end()：尾迭代器（指向最后一个元素后面一位）
• .rbegin()：反向头迭代器（指向最后一个元素）
• .rend()：反向尾迭代器（指向第一个元素前面一位）

迭代器支持：

• it + n：向后移动 n 个元素（随机访问迭代器）
• it - n：向前移动 n 个元素
• ++it：向后移动 1 位
• --it：向前移动 1 位
• it1 - it2：计算两个迭代器间距离（并非所有迭代器支持）
• prev(it)：返回 it 的前一个迭代器
• next(it)：返回 it 的后一个迭代器

注意：例如 set 的迭代器不支持随机访问操作，不能用 it + n 或 it1 - it2

3.4 常见问题

• .end() 和 .rend() 指向的是不可访问的位置（超出有效范围）
• 例如长度为 10 的容器，访问下标 10 会越界，迭代器到 .end() 也是不可解引用的
• 不同容器迭代器支持的操作可能不同（正向迭代器、反向迭代器、双向迭代器等）

删除操作示例及风险

vector<int> a{1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ++it)if (*it == 2 || *it == 3)a.erase(it);
// 结果：a = [1, 3, 4]，为何没删掉3？

这是因为 erase 后迭代器失效，++it 访问已失效迭代器导致问题。

更严重的是：

vector<int> a{1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ++it)if (*it == 4)a.erase(it);
// 运行时错误（RE）

建议： 如果要在遍历中删除元素，推荐使用如下写法：

for (auto it = a.begin(); it != a.end(); )
{if (*it == 2 || *it == 3)it = a.erase(it);  // erase 返回下一个有效迭代器else++it;
}

或者尽量避免边遍历边删除。

---

4 常用算法

4.1 内容总览

算法库 Algorithm	说明	是否讲解
count()	计数	否
find()	查找	否
fill()	填充	否
swap()	交换	是
reverse()	反转	是
shuffle() (C++11)	随机乱序	否
unique()	去除相邻重复元素	是
sort()	排序	是
lower_bound()/upper_bound()	二分查找	是
max()/min()	最大值/最小值	是
max_element()/min_element()	返回最大/最小元素迭代器	否
prev_permutation()/next_permutation()	上一个/下一个排列	否

数学函数 cmath（部分讲解）：

• abs()
• exp()
• log() / log10() / log2()
• pow()
• sqrt()
• ceil() / floor()
• round()

数值算法 numeric：

• gcd() (C++17)
• lcm() (C++17)

伪随机数生成 random：

• mt19937
• random_device()

4.2 swap()

交换两个变量的值

template< class T >
void swap(T& a, T& b);int a = 0, b = 1;
swap(a, b); // a = 1, b = 0int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
swap(arr[4], arr[6]); // arr = {0,1,2,3,6,5,4,7,8,9}

注意： 参数是引用，不需要取地址。

4.3 sort()

快速排序，默认升序

template< class RandomIt, class Compare >
void sort(RandomIt first, RandomIt last, Compare comp = std::less<>());vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end());
// arr = [0, 1, 1, 1, 8, 9, 9]

降序排序：

sort(arr.begin(), arr.end(), greater<int>());
// arr = [9, 9, 8, 1, 1, 1, 0]

自定义比较器：

bool cmp(pair<int,int> a, pair<int,int> b)
{if (a.second != b.second)return a.second < b.second;return a.first > b.first;
}vector<pair<int,int>> arr{{1,9}, {2,9}, {8,1}, {0,0}};
sort(arr.begin(), arr.end(), cmp);
// arr = {(0,0), (8,1), (2,9), (1,9)}

比较器规则：

• 若需要 a < b，比较器返回 true
• 若 a == b 或 a > b，比较器返回 false
• 不能返回 true 表示相等的情况

4.4 lower_bound() / upper_bound()

在升序序列中二分查找元素

• lower_bound：查找第一个 ≥ value 的位置
• upper_bound：查找第一个 > value 的位置

返回迭代器，可减去 .begin() 得到索引

vector<int> arr{0, 1, 1, 1, 8, 9, 9};
auto it = lower_bound(arr.begin(), arr.end(), 7);
int idx = it - arr.begin(); // idx = 4

常见用法：

int idx1 = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
int idx2 = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4
int idx3 = upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
int idx4 = upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 5

4.5 reverse()

反转区间元素顺序

template<class BidirIt>
void reverse(BidirIt first, BidirIt last);vector<int> arr(10);
iota(arr.begin(), arr.end(), 1);  // 1, 2, ..., 10
reverse(arr.begin(), arr.end());  // 10, 9, ..., 1

好的，我帮你继续整理这部分内容，保持清晰有条理，适合笔记使用。

---

4.6 max() / min()

功能：返回两个值中的最大值或最小值。

int mx = max(1, 2);  // 返回 2
int mn = min(1, 2);  // 返回 1

C++11 之后的新用法

可以直接传入初始化列表，一次比较多个元素，不用嵌套调用：

// C++11 之前写法：
int mx = max(max(1, 2), max(3, 4));  // 4
int mn = min(min(1, 2), min(3, 4));  // 1// C++11 之后写法：
int mx = max({1, 2, 3, 4});  // 4
int mn = min({1, 2, 3, 4});  // 1

---

4.7 unique()

功能：移除容器中相邻重复的元素，返回去重后有效部分的尾迭代器。
注意：它只消除相邻的重复元素，不会删除所有重复项。

template< class ForwardIt >
ForwardIt unique(ForwardIt first, ForwardIt last);

示例

std::vector<int> v{1, 2, 2, 3, 3, 3, 4};
auto it = unique(v.begin(), v.end()); 
// v: {1, 2, 3, 4, ?, ?, ?}, 返回指向数字4后的位置

由于 unique 只移动了元素但不改变容器大小，尾部会有无效数据。通常配合 erase 使用：

v.erase(it, v.end());

去重示例（先排序，后去重）

std::vector<int> arr{1, 2, 1, 4, 5, 4, 4};
std::sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());

这样 arr 里就只剩下了不重复的元素。

---

4.8 数学函数

支持参数类型：int / long long / float / double / long double

函数	说明	示例
abs	绝对值	abs(-1.0)
exp	e 的幂	exp(2)
log	自然对数	log(3)
pow	幂	pow(2, 3)
sqrt	平方根	sqrt(2)
ceil	向上取整	ceil(2.1)
floor	向下取整	floor(2.1)
round	四舍五入	round(2.1)

注意事项（防止浮点误差导致 WA）

• 不要用 floor(1.0 * a / b)，改用整除 a / b。
• 不要用 ceil(1.0 * a / b)，改用 (a + b - 1) / b。
• 不要用 (int)sqrt(a)，建议用二分查找实现整数平方根。
• 不要用 pow(a, b)，建议用快速幂实现。
• 不要用 log2(a)，竞赛中常用 __lg(a) 或 C++20 的 bit_width。

参考原文地址：https://codeforces.com/blog/entry/107717

---

4.9 gcd() / lcm()

（C++17 标准）提供了计算最大公因数（GCD）和最小公倍数（LCM）的函数。

int x = gcd(8, 12);  // 4
int y = lcm(8, 12);  // 24

如果不是 C++17 环境，但使用 GNU 编译器（g++），可以使用内置函数 __gcd()。

欧几里得算法实现 gcd 和 lcm

int gcd(int a, int b)
{if (b == 0)return a;return gcd(b, a % b);
}int lcm(int a, int b)
{return a / gcd(a, b) * b;
}