概念
C++ 标准模板库（Standard Template Library，STL）是一套功能强大的 C++ 模板类和函数的集合，它提供了一系列通用的、可复用的算法和数据结构。
STL 的设计基于泛型编程，这意味着使用模板可以编写出独立于任何特定数据类型的代码。
STL 分为多个组件，包括容器（Containers）、迭代器（Iterators）、算法（Algorithms）、函数对象（Function Objects）和适配器（Adapters）等。
使用 STL 的好处:
- 代码复用：STL 提供了大量的通用数据结构和算法，可以减少重复编写代码的工作。
- 性能优化：STL 中的算法和数据结构都经过了优化，以提供最佳的性能。
- 泛型编程：使用模板，STL 支持泛型编程，使得算法和数据结构可以适用于任何数据类型。
- 易于维护：STL 的设计使得代码更加模块化，易于阅读和维护。
前言
因为 $C++ 11$ 有 auto 这一关键字的存在，本文不再介绍使用迭代器迭代，而只介绍一些在算法竞赛当中常用的容器以及算法函数等。
本文代码默认自带了using namespace std; 以减少 std:: 的出现。
并只介绍常用操作，更详细的操作请点进对应的文章。
vector
STL（标准模板库）中的 vector 是 C++ 中一个非常常用的容器类。它是一个动态数组，可以自动调整大小，并提供了类似于数组的随机访问功能。
详细操作:vector
常用操作
1
2
3
4
5
6
7
8
9
10
11
| .size() 返回元素个数
.empty() 返回是否为空
.clear() 清空
.front()/back()
.push_back()/pop_back()
.begin()/end()
[]
支持比较运算，按字典序
for(auto &el : v){} 迭代
for(int i=1;i<=n;++i){} 迭代
|
queue
STL（标准模板库）中的 queue 是 C++ 中的队列容器。实现了队列的基本功能 $FIFO$。
详细操作:queue
常用操作
1
2
3
4
5
6
7
8
| .size()
.empty()
.push() 向队尾插入一个元素
.front() 返回队头元素
.back() 返回队尾元素
.pop() 弹出队头元素
while(q.size()) q.pop(); 遍历
|
优先队列
会自动将大/小的放在队首。
1
2
3
4
5
6
7
8
9
| priority_queue, 优先队列，默认是大根堆
.size()
.empty()
.push() 插入一个元素
.top() 返回堆顶元素
.pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
|
双端队列
有迭代器，可以迭代，操作空间比queue更加大。
1
2
3
4
5
6
7
8
9
| deque, 双端队列
.size()
.empty()
.clear()
.front()/back()
.push_back()/pop_back()
.push_front()/pop_front()
.begin()/end()
[]
|
stack
STL（标准模板库）中的 stack 是 C++ 中的栈容器。实现了栈的基本功能。
详细操作:stack
常用操作
1
2
3
4
5
| .size()
.empty()
.push() 向栈顶插入一个元素
.top() 返回栈顶元素
.pop() 弹出栈顶元素
|
set 和 map
STL（标准模板库）中的 set 是 C++ 中的集合容器。实现了集合的基本功能。
而map则类似于py里面的字典
详细操作:set
常用操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
.size()
.empty()
.clear()
.begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
|
string
STL（标准模板库）中的 string 是 C++ 中的字符串容器。
详细操作:string
基本操作
1
2
3
4
5
| .size()/length() 返回字符串长度
.empty()
.clear()
.substr(起始下标，(子串长度)) 返回子串
.c_str() 返回字符串所在字符数组的起始地址
|
bitset
详细操作:% ### 基本操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
|
1
2
3
4
| pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
|