STL 与奇技淫巧——考场上的好帮手

langmouren · 2025-11-20 17:09:21 · 算法·理论

STL 与奇技淫巧——考场上的好帮手

本文对 STL 和部分函数相关的知识进行了总结和梳理，作为一篇在赛前完成的文章，希望它对你的 NOIP 有所帮助。

可以通过此文进行查漏补缺，可能一个甜甜的语法糖或者发现了自己记错的复杂度就能在考场上拯救自己。

本文包括但不限于 STL 容器、STL 函数以及许多少见函数。

全文完全手打，无任何 AI 生成内容。截至本文完结，洛谷上应该没有比本篇文章更全的总结。

欢迎大家在评论区对本文提出意见！

vector

vector 方法

方法	作用	示例	时间复杂度	注意点
size	获取元素个数	`v.size()`	O(1)
empty	容器是否为空	`v.empty()`	^
push_back	末尾插入	`v.push_back(x)`	^	均摊 O(1)。
emplace_back	末尾插入	`v.emplace_back(x)`	^	效果相同，常数略小。
pop_back	删除末尾	`v.pop_back()`	^
back	获取末尾元素	`v.back()`	^
front	获取开头元素	`v.front()`	^
begin	返回开头迭代器	`v.begin()`	^
end	返回末尾迭代器	`v.end()`	^	返回末尾更后的一位。
[]	下标访问元素	`v[x]`	^	`v.at(pos)` 作用相同。
clear	清空容器	`v.clear()`	O(n)	O2 优化下为 O(1) 或 O(n)。不释放空间。
resize	调整容器大小	`v.resize(x)`	^	不释放空间。
shrink_to_fit	尝试释放空间	`v.shrink_to_fit()`	^	尝试释放未使用空间。
insert	插入元素	`v.insert(pos,x)`	^	将大量元素向后移动。
erase	删除元素	`v.erase(pos)`	^	将大量元素向前移动。

注：

@CommonAnts 在讨论区中提到 reserve() 函数可以进行缩容，但经查阅 cppreference，此函数只进行扩容而不缩容，只有 shrink_to_fit() 函数会尝试缩容。
在 O2 优化下，vector::clear() 对于 trivial 类型（如 int、long long、double 等）为 O(1)，对于非 trivial 类型（如 string、vector、结构体等）为 O(n)。下面 deque 相同。

迭代器

一个保存 int 的 vector 迭代器声明为：vector<int>::iterator it=v.begin();，事实上，迭代器的声明可以使用 auto 代替：auto it=v.begin();，后文不再阐述。

可以使用 it++ 或 it-- 对 vector 的迭代器进行遍历，同时，可以使用 *it 对迭代器解引用：

for(auto it=v.begin();it!=v.end();it++){
    cout<< *it <<"\n";
}

queue

queue 又叫队列，是一种先进先出的结构。

queue 方法

方法	作用	示例	时间复杂度
size	获取元素个数	`q.size()`	O(1)
empty	容器是否为空	`q.empty()`	^
push	入队（队尾）	`q.push(114514)`	^
pop	出队（队头）	`q.pop()`	^
front	获取队头	`q.front()`	^
back	获取队尾	`q.back()`	^

queue 没有迭代器，其默认下是 deque 的一种封装。

stack

stack 又叫栈，是一种后进先出的结构。

stack 方法

方法	作用	示例	时间复杂度
size	获取元素个数	与 vector 类似	O(1)
empty	容器是否为空	^	^
top	返回栈顶元素	`stk.top()`	^
pop	弹出栈顶元素	`stk.pop()`	^
push	压入元素到栈顶	`stk.push(x)`	^

stack 没有迭代器，其默认下是 deque 的一种封装。

冷知识：stack 和 queue 在 STL 都规定了三种实现方式：deque、list 和 vector，默认下使用 deque。

priority_queue

priority_queue 优先队列是一个堆，默认下是大根堆。

priority_queue 方法

方法	作用	示例	时间复杂度
size	获取元素个数	`q.size()`	O(1)
empty	容器是否为空	`q.empty()`	^
top	询问堆顶元素	`q.top()`	^
push	把元素插入堆	`q.push(114514)`	O(\log n)
pop	删除堆顶元素	`q.pop()`	^

重载运算符

当优先队列需要放入结构体时，我们需要重载运算符：

struct Node{
    int x,y,k;

    bool operator<(const Node &other)const{
        return k>other.k;
    }
};

priority_queue<Node> q;

注意到，优先队列的大小是相反的，在上文代码中，以 k 为关键字进行排序时，使用的是大于号，但实际上实现了小根堆。

deque

deque 又叫双端队列，它支持两端插入、删除，随机访问，功能和函数都像是 vector 和 queue 的结合版。

deque 方法

方法	作用	示例	时间复杂度	注意点
size	获取元素个数	与 vector 类似	O(1)
empty	容器是否为空	^	^
push_back	末尾插入	^	^
push_front	开头插入	^	^
pop_back	删除末尾	^	^
pop_front	删除开头	^	^
begin	返回开头迭代器	^	^
end	返回末尾迭代器	^	^	返回末尾更后的一位。
[]	下标访问元素	^	^	`v.at(pos)` 作用相同。
clear	清空容器	^	O(n)	O2 优化下可视为 O(1)。
insert	插入元素	^	^	将大量元素向后移动。
erase	删除元素	^	^	将大量元素向前移动。
back	获取末尾元素	与 queue 类似	O(1)
front	获取开头元素	^	^

set & multiset

set 和 multiset 又被称为“有序集合”和“有序多重集合”，前者内元素不可以重复，后者可以。其底层实现为红黑树。

与优先队列一样，set 和 multiset 储存的元素必须要定义小于运算。

set & multiset 方法

方法	作用	示例	时间复杂度	注意点
size	获取元素个数	与 vector 类似	O(1)
empty	容器是否为空	^	^
begin	返回开头迭代器	^	^
end	返回末尾迭代器	^	^	返回末尾更后的一位。
insert	插入元素	`s.insert(x)`	O(\log n)
lower_bound	查找 \geq x 的最小的元素	`s.lower_bound(x)`	^
upper_bound	查找 > x 的最小的元素	`s.upper_bound(x)`	^
erase	删除元素	`s.erase(x)`	^	multiset 会删除所有相同元素。若删除单个可用 `s.erase(find(x))`。
count	查找等于 x 的元素个数	`s.count(x)`	O(k + \log n)
clear	清空元素	`s.clear()`	O(n)	严格 O(n)。

重载运算符

和优先队列相同，两者可以通过重载运算符实现自定义元素排序。

struct Node{
    int x,y,k;

    bool operator<(const Node &other)const{
        return k<other.k;
    }
};

set<Node> q;

上面实现了一个从小到大排序的 set。

迭代器

set 和 multiset 的迭代器仅支持 it++ 和 it-- 两个操作，不支持随机访问，单次复杂度 O(\log n)，遍历时均摊复杂度 O(1)。

map

map 是一对映射，即 key-value，其底层实现为红黑树。

同上，map 的 key 必须定义了小于运算。

map 方法

方法	作用	示例	时间复杂度	注意点
size	获取元素个数	与 vector 类似	O(1)
empty	容器是否为空	^	^
begin	返回开头迭代器	^	^
end	返回末尾迭代器	^	^	返回末尾更后的一位。
insert	插入元素	`s.insert(x)`	O(\log n)
find	查找元素	`s.find(x)`	^	不存在返回 `s.end()`。
erase	删除元素	`s.erase(x)`	^
lower_bound	查找 \geq x 的最小的元素	`s.lower_bound(x)`	^
upper_bound	查找 > x 的最小的元素	`s.upper_bound(x)`	^
[]	访问 key 对应 value	`s[x]`	^	x 不存在时插入一个空值。
clear	清空容器	`s.clear()`	O(n)	严格 O(n)。

在使用 s[x] 查询前，应先使用 s.find(x) 判断该值是否存在，防止插入大量空值拖累时空复杂度，对程序优化效果极其显著。

重载运算符

struct Node{
    int x,y,k;

    bool operator<(const Node &other)const{
        return k<other.k;
    }
};

map<Node,int> q;

上面实现了一个 key 值为结构体，value 值为 int，从小到大排序的 map。

迭代器

map 和 set 相同，只支持 it++ 和 it--，想要获取当前的 key-value 值，可以使用指针。

以上面的结构体为例，想要获取结构体中的 k，可以使用 it->first.k，想要获取 value，可以使用 it->second。

unordered_set & unordered_map

两者在 set 和 map 的基础上变成了无序形式，其底层实现为哈希，事实上，下面会介绍自定义哈希的方式。

unordered_set & unordered_map 方法

方法	作用	示例	时间复杂度	注意点
size	获取元素个数	与 vector 类似	O(1)
empty	容器是否为空	^	^
begin	返回开头迭代器	^	^
end	返回末尾迭代器	^	^	返回末尾更后的一位。
insert	插入元素	与 set/map 类似	^
find	查找元素	^	^	不存在返回 `s.end()`。
erase	删除元素	^	^
clear	清空元素	^	O(n)	严格 O(n)。

由于其底层实现为哈希，可能存在被卡的情况，最坏单次添删查的复杂度会退化到 O(n)。（实际上 CCF 系列比赛卡 STL 容器的概率为 0。）

自定义哈希

当我们自定义了结构体等内容时，STL 容器无法对其进行自动哈希，此时需要我们手写哈希。

需要对内容判断相等，所以需要重载 == 运算符。

需要“定位桶”，所以需要提供哈希函数。

例如我们拥有一个结构体，想要其中的 x 和 y 参与哈希：

struct Node{
    int x,y,k;
};

重载 == 运算符只需要判定所有参与哈希的值相等即可：

struct Node{
    int x,y,k;

    bool operator==(const Node &other)const{
        return x==other.x && y==other.y;
    }
};

而哈希函数，只需要将每个值分别乘一个无符号大质数后异或起来即可，自己背几个大质数并不困难。

注意，哈希函数的返回值应该为 size_t 类型：

struct Node{
    int x,y,k;

    bool operator==(const Node &other)const{
        return x==other.x && y==other.y;
    }
};
struct Hash{
    size_t operator()(const Node &a)const{
        return ((size_t)a.x*1145141u) ^ ((size_t)a.y * 1315423911u);
    }
};
unordered_set<Node,Hash> s;

以上实现了一个以 x 和 y 为哈希内容的 unordered_set。

事实上，将哈希函数放到 Node 内部，整理成以下形式：

struct Node{
    int x,y,k;

    bool operator==(const Node &other)const{
        return x==other.x && y==other.y;
    }

    size_t operator()(const Node &a)const{
        return ((size_t)a.x*1145141u) ^ ((size_t)a.y * 1315423911u);
    }
};
unordered_set<Node,Node> s;

也是可以通过编译且效果相同的。

在能够自动哈希的情况下，请不要手写哈希，效率较自动更低。

bitset

bitset 其实是一串二进制数，通过按位储存将自己的常数降低至 \dfrac{1}{w}，其中 w 为计算机位数，适合特殊情况下的卡常操作。

可以通过 bitset<114514> b 来定义一个长度为 114514 的 bitset。

bitset 方法

方法	作用	示例	时间复杂度	注意点
[]	访问第 x 位	`b[x]`	O(1)
set	全部置 1	`b.set()`	O(\dfrac{n}{w})	有参数 x 时对第 x 位进行操作，复杂度 O(1)。
reset	全部置 0	`b.reset()`	^	^
flip	全部取反	`b.flip()`	^	^
any	是否有 1	`b.any()`	^
none	是否全 0	`b.none()`	^
count	统计 1 的数量	`b.count()`	^
&	按位与	`c=a&b`	^	对整个 bitset 按位操作。
\|	按位或	`c=a\\|b`	^	^
“^”	按位异或	`c=a^b`	^	^
~	按位取反	`c=~b`	^	^
<<	左移	`c=b<<2`	^	溢出丢弃，低位补 0。
>>	右移	`c=b>>2`	^	溢出丢弃，高位补 0。
_Find_first	找到第一个为 1 的位置	`b._Find_first()`	^	GCC 私货。
_Find_next	找到 pos 后下一个为 1 的位置	`b._Find_next(pos)`	^	^
to_string	转换为字符串	`b.to_string()`	O(n)

注：洛谷的表格合并会使异或符号渲染错误，故加引号。

string

string 为我们提供了许多有用的函数，下面只列举非常常用的一部分。

string 方法

方法	作用	示例	时间复杂度	注意点
size	获取元素个数	与 vector 类似	O(1)
empty	容器是否为空	^	^
[]	下标访问	^	^
clear	清空 string	^	^	严格O(1)。
swap	交换两个字符串	`s1.swap(s2)`	^	实际交换字符串指针。
back	获取末尾元素	与 queue 类似	^
front	获取开头元素	^	^
substr	返回定长字串	`s.substr(pos,len)`	O(len)
+=	末尾添加字符串	`s+=str`	^
erase	删除定长字串	`s.erase(pos,len)`	O(n)
insert	插入指定字串	`s.insert(pos,str)`	O(n+k)
replace	替换指定字串	`s.replace(pos,len,str)`	^
find	查找指定字串	`s.find("abc")`	O(nm)	最坏 O(nm)。

STL 函数（包含 GNU）

接下来总结一部分引用 bits/stdc++.h 时可以使用的函数，CCF 系列比赛均可使用。

sort(st,ed)：对 [st,ed) 进行排序，复杂度 O(n \log n)，可以通过重载小于运算符或者传入比较函数自定义排序方式（以下两种方式效果相同）：

bool cmp(int a,int b){return a>b;}
sort(s+1,s+n+1,cmp);

struct Node{
    int a;
    bool operator<(const Node &other)const{
        return a>other.a;
    }
}s[MN];
sort(s+1,s+n+1);

lower_bound(st,ed,val)：在有序区间 [st,ed) 中查询第一个 \geq val 的位置，并返回迭代器，复杂度 O(\log n)。
upper_bound(st,ed,val)：同上，不过查询第一个 > val 的位置。
unique(st,ed)：除去 [st,ed) 的相邻相同项，一般配合 sort() 达到去重效果，复杂度 O(n)。
reverse(st,ed)：翻转 [st,ed) 的内容，复杂度 O(n)。
fill(st,ed,val)：将 [st,ed) 填充为 val，复杂度 O(n)。
find(st,ed,val)：返回 [st,ed) 中第一个等于 val 的指针，复杂度 O(n)。
memcpy(target,original,sz)：将以 original 起始 sz 字节的内容复制到 target，复杂度 O(sz)。
__lg(x)：返回 \lfloor \log_2x \rfloor，与 log2(x) 作用相同，复杂度 O(1)。
__gcd(x,y)：返回 \gcd(x,y)，复杂度 O(\log n)。
max(A)/min(A)：返回 A 中的最大值， |A| \geq 2，复杂度 O(|A|)。下面的代码就可以返回 5：
```
int mx=max({1,1,4,5,1,4});
```
hypot(x,y)：返回 \sqrt{x^2+y^2}，可以简便求出欧几里得距离，复杂度 O(1)，精度问题导致常数较大。
abs(x)/fabs(x)：返回整型/浮点型的 |x|，复杂度 O(1)。
floor(x)/ceil(x)：返回浮点型的 \lfloor x \rfloor 或 \lceil x \rceil，复杂度 O(1)。
advance(it,num)：将迭代器 it 前进 num 位，复杂度在随机访问迭代器（vector 和 deque）时为 O(1)，其他迭代器为 O(num)。
prev(it),next(it)：返回迭代器 it 的前驱/后继。
stoi(string)：将 string 转化为整数。
__gnu_cxx::power(x,k)：在 bits/extc++.h 库中，是自带的快速幂，类似 std::sort()，可以通过重载乘法运算符或提供乘法函数来自定义，复杂度 O(\log n)。

时间/随机化函数

时间/随机化的函数篇幅不小，故单独总结。

clock 函数

clock() 会返回当前程序运行的时间，不同系统得到的返回值单位不同，可以通过 (double)clock() / CLOCKS_PER_SEC 统一为秒。

time 函数

time(0) 会返回从 1970 年 1 月 1 日到现在的时间，单位为秒，所以每秒内的返回值相同，在随机化时使用容易影响复杂度。

chrono 类

chrono 类在 std::chrono，平时引用了 using namespace std; 后，可以通过以下方式使用：

chrono::steady_clock::now().time_since_epoch().count();

其精度达到 10^{14}，绝对够用，有人卡我吃。

rand 函数

rand() 函数在 Windows 下只能生成 [0,32767] 的随机数，随机化时使用容易影响复杂度。

需要使用 srand(seed) 设置随机数种子，可以直接使用 time(0)。

mt19937

~~其实我们机房喜欢叫它茅台一九九三七~~。

mt19937 可以生成 unsigned int 类型的随机数，mt19937_64 可以生成 unsigned long long 类型的随机数。

以前者举例，可以通过 mt19937 name(seed) 进行定义，使用时直接调用 name()。

与 rand() 相同，随机数种子可以直接使用 time(0)。

uniform_int_distribution

直接使用随机数对数据范围取模会使得答案分布不随机。

此时可以使用 uniform_int_distribution<int/long long>(L,R)(name)，它会返回一个 [L,R] 的整数，函数中的 name 是 mt19937/mt19937_64 函数。

mt19937 wdnmd(time(0));
int rnd=uniform_int_distribution<int>(1,50)(wdnmd);

上面这套丝滑小连招可以从获取一个 [1,50] 中的随机值。

uniform_real_distribution

这个函数可以生成一个 [L,R) 的浮点数，使用方式同上：

mt19937 wdnmd(time(0));
double rnd=uniform_real_distribution<double>(1,50)(wdnmd);

__builtin 函数

__builtin 是 GCC 独有的一系列操作，CCF 系列比赛可用。

位运算相关

函数	作用	时间复杂度	注意点
`__builtin_popcount(x)`	统计 1 的个数	O(1)	x 可为 0。
`__builtin_ctz(x)`	统计末尾连续 0 的个数	^	x 不可为 0。
`__builtin_clz(x)`	统计前导连续 0 的个数	^	^
`__builtin_ffs(x)`	返回最低位 1 的位置	^	1-index，x=0 时返回 0。

以上函数结尾加 ll 均有 long long 版本，如 __builtin_popcountll(x)。

__builtin_clz(x) 可以用来求 \log_2x。

安全检查

函数	作用	时间复杂度	注意点
`__builtin_add_overflow(a,b,&res)`	检测加法溢出	O(1)	res 存放结果。
`__builtin_sub_overflow(a,b,&res)`	检测减法溢出	^	^
`__builtin_mul_overflow(a,b,&res)`	检测乘法溢出	^	^

inline 关键字

inline 关键字会建议编译器对函数进行内联展开。

内联展开可以产生两种作用：

省去函数调用开销。
- 不需要压栈、跳转、返回等操作，可以小幅度降低常数。
可能使编译器进行更多优化。
- 常量折叠、循环展开。

事实上，编译器会自动判断和完成内联展开。

inline 能用么

事实上，inline 的作用仅仅是“建议”，编译器可以拒绝你的建议，尤其在使用 O2 以上优化时基本没有效果。

怎么让编译器更听话

以 GCC 为例：

inline __attribute__((always_inline))：要求编译器进行内联。在递归等特殊函数时仍可能被拒绝。
__attribute__((noinline))：要求编译器不进行内联。

由于 CCF 使用的 GCC 版本过于老旧，你可能会碰到这种情况，触发条件比较诡异，比较吃运气，祝大家不碰到这种事情。

常见的卡常操作

关闭同步流：关闭同步流可以极大降低 cin 与 cout 的常数：
```
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
```
使用 \n 换行：将 endl 替换为 \n，可以极大降低 cout 的常数。
对于树之类的稀疏图，使用链式前向星而不是 vector 存图。
使用快读快写。
在快读快写的基础上，将 getchar() 和 putchar() 改为 getchar_unlocked() 和 putchar_unlocked()，约有 0.5 倍的性能提升，Windows 下无法使用。
在 Windows 下可以使用 _getchar_nolock() 与 _putchar_nolock()。
在常量取模时，使用 unsigned long long 代替 long long 会有约 1 倍的性能提升。
选用常数更小/复杂度更低的处理方式，例如将线段树改成树状数组，递归式线段树改为非递归式线段树，欧拉序 LCA 改为 DFS 序 LCA，map 改为 unordered_map 等。
pb_ds 库的哈希表对比 unordered_map 常数上有提升，可自行查阅相关文章。

常见的其他操作

linux 下，可以使用 time ./file_name 查看程序运行时间。
linux 下，可以使用 size ./file_name 查看程序占用内存。
linux 下，没有使用文件读写时，可以在命令后加上 <input_file_name 和 >output_file_name 实现自定义文件输入输出，例如下面就是一个读入 game.in，输出到 game.out 的，显示程序 game 运行时间的命令：
```
time ./game <game.in >game.out
```
linux 下，ccf 的标准编译指令为：g++ file_name.cpp -o file_name -std=c++14 -O2 -static。
结尾添加以下参数可以避免很多问题：-fsanitize=address,undefined -Wall -Wextra -Wshadow。
linux 下，可以使用以下命令取消栈空间限制：ulimit -s unlimited。如果你想要指定栈空间大小，可以使用：ulimit -s sz，其中 sz 单位为 KB。
linux 下，可以使用 diff 命令比较文件差异（-Bb 可以忽略行末空格与回车）；Windows 下，可以使用 fc 命令比较文件差异。
拒绝在任何情况下使用 vector<bool>，史山实现，极易出错。

特别鸣谢

感谢 @K8He，@llamn，@masonxiong，@W_SUN，@Laoshan_PLUS，@CommonAnts，@Kaf_yoU，@DaydreamWarrior，@Water_Flower，@ZMQ_Ink6556，@Lilingfeng，@Halberd_Cease 对本文的建议和纠错。

修改记录

$2025$ 年 $11$ 月 $24$ 日：改进 vector 相关内容，添加 inline 介绍，修改错误，添加 __builtin 少量函数。 $2025$ 年 $11$ 月 $24$ 日：再次修改交审，添加 bitset 相关内容，修改错误，添加函数。