STL的使用

STL

STL 即标准模板库（Standard Template Library），是 C++ 标准库的一部分，里面包含了一些模板化的通用的数据结构和算法。

C++ 标准：

C++ 自 1985 年诞生以来，一共由国际标准化组织（ISO）发布了 5 个正式的 C++ 标准，依次为 C++98、C++03、C++11（亦称 C++0x）、C++14（亦称 C++1y）、C++17（亦称 C++1z）、C++20（亦称 C++2a）。C++ 标准草案在 open-std 网站上，最新的标准 C++23（亦称 C++2b）仍在制定中。此外还有一些补充标准，例如 C++ TR1。

每一个版本的 C++ 标准不仅规定了 C++ 的语法、语言特性，还规定了一套 C++ 内置库的实现规范，这个库便是 C++ 标准库。C++ 标准库中包含大量常用代码的实现，如输入输出、基本数据结构、内存管理、多线程支持等。C++ 标准库中的函数或者对象都是在命名空间std中定义的。

ICPC 支持 C++20 标准。

STL（标准模板库）：

STL 是 C++ 标准库的一部分，里面包含了一些模板化的通用的数据结构和算法。

STL 容器：

容器是一个模板类，它用于存放各种类型的数据

序列式容器：

• 向量（vector）后端可高效增加元素的顺序表。
• 数组（array）定长的顺序表，C 风格数组的简单包装。（C++11 标准）
• 双端队列（deque）双端都可高效增加元素的顺序表。
• 列表（list）可以沿双向遍历的链表。
• 单向链表（forward_list）只能沿一个方向遍历的链表。

有序关联式容器：

• 集合（set）有序地存储互异元素的容器。
• 多重集合（multiset）元素可以相等的 set。
• 映射（map）由（键，值）对（二元组）组成的容器，要求键互异，按键有序存储。
• 多重映射（multimap）键可以相等的 map。

无序关联式容器：

• unordered_set/unordered_multiset/unordered_map/unordered_multimap，元素乱序，用于判断元素是否存在。使用哈希实现。（C++11 标准）

容器适配器：

容器适配器并不是容器，它们不具有容器的部分特点。

• 栈（stack）后进先出的容器，默认是对双端队列（deque）的包装。
• 队列（queue）先进先出的容器，默认是对双端队列（deque）的包装。
• 优先队列（priority_queue）元素的有序的一种队列，默认是对向量（vector）的包装。

容器声明：

containerName<typeName> name。

迭代器：

在 STL 中，迭代器用来访问和检查 STL 容器中元素的对象，它的行为模式和指针类似。

迭代器可以看作一个数据指针，主要支持两个运算符：自增 (++) 和解引用（*），其中自增用来移动迭代器，解引用可以获取或修改它指向的元素。

指向某个 STL 容器 container 中元素的迭代器的类型一般为 container::iterator。

例如：

vector<int> a(10);
For(i,1,a.size()) cout<<a[i-1]<<'\n';
for(vector<int>::iterator it=a.begin();it!=a.end();it++) cout<<*it<<'\n';

在 C++11 后，可使用 auto it=a.begin(); 的方式自动识别迭代器类型。

容器共有成员函数：

• =：拷贝。
• begin()：返回指向开头元素的迭代器。
• end()：返回指向末尾的下一个元素的迭代器。end() 不指向某个元素，但它是末尾元素的后继。
• size()：返回容器内的元素个数。
• empty()：返回容器是否为空。
• swap()：交换两个容器。
• clear()：清空容器。

vector：

动态数组。

• vector 基于字典序重载了比较运算符。
• vector 支持 = 初始化。

以下是 vector 常用方法：

• v.resize(x,y)将 v 的大小重设为 x，若原本大小不足 x，则用 y 填充。y 可不写，默认为 0。
• vector<int> v(x,y)创建一个初始大小为 x 的 vector，并用 y 填充。y 可不写，默认为 0。
• vector v1(v2)创建一个 v2 的拷贝 v1。
• v.front() v 的首元素。
• v.back() v 的尾元素。
• v.rbegin() 指向 v 逆向的首元素的迭代器。
• v.rend()指向 v 逆向的尾元素后继的迭代器。
• v.push_back(x)在 v 的末尾加入 x。
• v.pop_back()删除 v 的末尾元素。
• swap(v1,v2)交换 v1,v2。

array：

静态数组。

略。

deque：

双端队列。

内容与 vector 一致（底层实现不一致）。

多：

• q.push_front(x)在 q 头部插入一 x。
• q.pop_front()删除 q 的头部元素。

list：

双向链表。

使用与 deque 基本一致。

元素访问不一致：

不能随机访问，要从头或尾迭代器开始。

• l.front()返回首元素的引用。
• l.back()返回末尾元素的引用。

额外方法：

• l.splice()
• l.remove()
• l.sort()
• l.unique()
• l.merge()

forward_list：

单向链表。

与 list 几乎一致。

set：

集合。

set 底层逻辑为红黑树（是一种平衡二叉搜索树）。set 默认升序。

插入与删除：

• s.insert(x)将 x 插入 s。
• s.erase(x) 将 s 中的所有 x。
• s.erase(it)将 s 的迭代器 it 指向的元素删除，要求 it 必须合法。
• s.erase(begin,end)将 s 中迭代器 [begin,end)之间的元素删除。

迭代器：

与 vector 一致。

• s.begin()
• s.end()
• s.rbegin()
• s.rend()

查找：

• s.count(x)返回 s 中 x 的个数。
• s.find(x)返回 s 中 x 的迭代器，若不存在则返回 s.end()。
• s.lower_bound(x)返回首个大于等于 x 的元素的迭代器，若不存在则返回 s.end()。
• s.upper_bound(x)返回首个大于 x 的元素的迭代器，若不存在则返回 s.end()。

由于 set 作为平衡树的封装，其强大的功能和简单的使用，在很多场景下都有很好的应用，是使用最多的 STL。好好利用 set，能极大的帮助选手解决问题。

set 的注意点：

• set 迭代器的 ++/– 时间复杂度为均摊 $O(1)$，最坏 $O(\log n)$。
• 使用 algorithm 库的 lower_bound/upper_bound 对 set 的时间复杂度为 $O(n)$。
• 使用 algorithm 库的 nth_element 对 set 的时间复杂度为 $O(n)$。

multiset：

可重集。

与 set 完全一致。

map：

映射。

键和值之间一一对应且保证键升序，不能存在多个相同键。

若在 map 中插入多个相同键值对，保留第一个。

常常应用在 string 和 int 的映射上，例如学生成绩的查询；或是统计值较大的数字个数。

操作与 set 一致，替换成对 map 键的操作。

多：

• 可以使用 mp[key] 的方式访问键对应的值。
• 使用 mp[key] 时，若 mp 中没有键为 key 的元素则会自动加入一个，对应的值默认为 $0$。所以不建议使用 mp[key] 判断是否存在，而应使用 mp.find(key)。

multimap：

键可以重复的 map。

操作与 map 一致。

但因为键可以重复，所以 multimap 没有通过键访问值的方法。

unordered_set/unordered_multiset/unordered_map/unordered_multimap：

方法与有序关联式容器一致。

除了没有与“有序”有关的方法，例如：lower_bound 和 upper_bound。

由于是基于哈希实现的，一般情况下时间复杂度为 $O(1)$。

但在默认情况下，可以被构造数据卡时间复杂度，将 $O(1)$ 的时间复杂度卡成 $O(n)$。

但可以通过自定义哈希函数，在一定程度上防止被卡。

stack：

栈。

是一种后进先出的容器适配器，仅支持查询或删除最后一个加入的元素，不支持随机访问，不支持迭代器。

• q.top()访问栈顶元素。
• q.push(x)将 x 插入栈顶。
• q.pop()删除栈顶元素（栈不能为空）。
• q.size()查询栈内元素数量。
• q.empty()查询栈是否为空。

queue：

队列。

是一种先进先出的容器适配器，仅支持查询或删除第一个加入的元素，不支持随机访问，不支持迭代器。

• q.front()访问队首元素。
• q.push(x)向队列中插入 x。
• q.pop()删除队首元素（队列不能为空）。
• q.size()查询队列内元素数量。
• q.empty()查询队列是否为空。

priority_queue：

优先队列（本质是一种堆，一般为二叉堆）。

$O(\log n)$：

• q.push(x)在 q 中插入元素 x。
• q.pop()删除堆顶元素（优先队列不能为空）。

$O(1)$：

• q.top()查询堆顶元素（优先队列不能为空）。
• q.size()查询优先队列元素数量。
• q.empty()查询优先队列是否为空。

扩展：

string：

字符串。

string 可以动态分配内存，不用初始设定。支持 cin/cout 进行输入输出。

string 重载了加法运算符，使用 + 可以简单拼接两个字符串。

注意：

• a=a+b，时间复杂度为 $O(|a+b|)$。
• a+=b，时间复杂度为 $O(|b|)$。

string 基于字典序重载比较运算符。

string 转 char：

通过 s.c_str() 的方式将 string 转换成 char 数组。

成员函数：

• s.length()查询 s 的长度，返回和 s.size() 相同。
• s.size()查询 s 的大小，返回和 s.length() 相同。
• s.find(str,pos) 从 pos 起查询 s 中第一次出现 str 的位置，如果没有出现返回 -1。pos 可不传参，默认从 0 开始。
• s.substr(pos,len)在 s 中从 pos 起截取最多 len 个字符组成字符串。
• s.insert(pos,cnt,str)在 s 中从 pos 起插入 cnt 个 str 字符串。cnt 可不传参，默认为 1。
• s.erase(pos,len)在 s 中从 pos 起删除 len 个字符。len 可不传参，默认删除 pos 起的全部字符。
• s.replace(pos,len,str)将在 s 中从 pos 起 len 个字符替换成 str 字符串。
• s.replace(first,last,str)将在 s 中 [first,last) 之间的字符串替换成 str。

注意：

• s.length()/s.size() 返回值均为 unsigned。
• C 语言中对字符串长度的处理函数 strlen() 的时间复杂度关于字符串长度呈线性。而 s.length() 和 s.size() 均为 $O(1)$。

bitset：

bitset 是 C++ 标准库中的一个存储 0/1 的大小不可变容器。严格来说，bitset 并不属于 STL。

由于内存地址是按 byte 寻址，而非 bit。一个 bool 类型的变量，虽然只存储 0/1 但也占 1 byte 的内存。而 bitset 使得一个 byte 存储 8 位 0/1。

使用：

• bitset<size> s;定义了一个拥有 size 位的 bitset。

构造函数：

• bitset()默认每一位都是 $0$。
• bitset(unsigned int x)初始为 x 的二进制表示。
• bitset(const string &str)初始为 01 传 str（传入非 01 串会抛出异常）。

运算符：

bitset 支持许多独特的运算，由于 bitset 的 0/1 性质，使得其支持位运算。

• [] 访问 bitset 某一位。
• ==/!= 判断两个 bitset 内容是否完全相同。
• &、|、^、~、<<、>>，对整个 bitset 进行位运算。
• <> （流运算符，注意与位运算的区分）意味着可以通过 cin/cout 进行输入输出类似 string。

成员函数：

• count()查询 1 的数量。
• size()查询 bitset 的大小。
• test(x)查询第 x 位，和 [] 的区别是越界检查，test 越界后会抛出异常。
• any()查询是否存在 1。
• none()查询是否不存在 1。
• all()查询是否全是 1。（C++11 标准）
• set(x,y)将 bitset 第 x 位设置为 y。可以无参数，将整个 bitset 设置为 1。
• reset(x)将 bitset 第 x 位设置为 0。可以无参数，将整个 bitset 设置为 0。
• flip(x)翻转 bitset 第 x 位。可以无参数，默认翻转整个。
• to_string()返回将 bitset 转换为 string 的结果。
• to_ullong()返回将 bitset 转换为 unsigned long long 的结果。(C++11 标准)

pair：

二元组。

使用：

pair<Typename,Typename> a;

使用 a.first 访问 a 的第一个元素，a.second 访问 a 的第二个元素。

pair 相较于自定义 struct 的优势是自定义了比较运算符，按照先比较第一个元素，再比较第二个元素的原则进行。在部分情形下更加方便。（前提是 pair 内的 Type 存在对应的比较运算符）

tuple：

元组（C++11 标准）。

类似于 n 元的 pair，通常可以用 pair 套 pair 的方式做等价实现。

略。

rope：

块状链表（采用可持久化平衡树实现）。

rope 不是真正的块状链表，只是起到块状链表的作用，所以其时间复杂度为 $O(\log n)$。

使用：

rope 使用较特殊，需要使用以下代码来引入：

#include <ext/rope>
using namespace __gnu_cxx;

rope<Typename> a。

• a.push_back(x)在 a 的末尾插入 x。
• a.insert(pos,x)在 a 中的 pos 位置加入元素 x。
• a.erase(pos,len)在 a 中的 pos 位置起删除 len 个元素。
• a.at(x)或 a[x]查询 a 的第 x 个元素。
• a.length()或 a.size()查询 a 的大小。

STL 算法：

STL 提供了大约 100 个实现算法的模版函数，基本都包含在 <algorithm> 之中，还有一部分包含在 <numeric> 和 <functional> 中。

• find(s.first,s.last,v)在容器 s 中迭代器 [first,last) 之间查找 v，返回迭代器。若找不到，返回 s.last。
• reverse(s.first,s.last)翻转容器 s 中迭代器 [first,last) 之间的内容。
• unique(s.first,s.last)去除容器 s 中迭代器 [first,last) 之间相邻的重复元素。返回 s.last。
• shuffle(s.first,s.last,rng)随机打乱容器 s 中迭代器 [first,last) 之间元素。rng 随机数生成器，一般情况使用以真随机数生成器 random_device 播种的梅森旋转伪随机数生成器 mt19937。
• sort(s.first,s.last,compare)对容器 s 中迭代器 [first,last) 之间的元素排序，compare 为比较函数，可不传参。默认升序。（stable_sort 为稳定排序）
• binary_search(s.first,s.last,v)在容器 s 中迭代器 [first,last) 范围内二分查找 v。返回 1 表示存在 v，返回 0 表示不存在 v。
• lower_bound(s.first,s.last,v)返回容器 s 中迭代器 [first,last) 范围内找到第一个大于等于/小于等于（取决于范围内元素是升序还是降序，若范围内元素为无序，不会报错，但结果不一定正确） v 的迭代器，找不到返回 s.last。
• upper_bound(s.first,s.last,v)返回容器 s 中迭代器 [first,last) 范围内找到第一个大于/小于（取决于范围内元素是升序还是降序，若范围内元素为无序，不会报错，但结果不一定正确） v 的迭代器，找不到返回 s.last。
• merge(v1.first,v1.last,v2.first,v2.last,back_inserter(v3))把容器 v1 中迭代器 [first,last] 范围元素和容器 v2 中迭代器 [first,last) 范围内元素有序合并后插入到 v3 后。（要求 v1 v2 对应范围内均升序）线性时间复杂度。
• inplace_merge(v.first,v.middle,v.last)将容器 v 中迭代器 [first,middle) 和 [middle,last) 范围内的元素有序合并（要求 [first,middle) 和 [middle,last) 均升序）。线性时间复杂度。
• next_permutation(s.first,s.last) 将容器 s 中迭代器 [first,last) 范围的排列更改为全排列中的下一个排列。
• prev_premutation(s.firts,s.last) 将容器 s 中迭代器 [first,last) 范围的排列更改为全排列中的下一个排列。
• partial_sum(v.first,v.last)求容器 s 中迭代器 [first,last) 范围的前缀和。线性时间复杂度。

pb_ds：

pb_ds 库全称 Policy-Based Data Structures。

pb_ds 库封装了很多数据结构，比如哈希（Hash）表，平衡二叉树，字典树（Trie 树），堆（优先队列）等。

就像 vector、set、map 一样，其组件均符合 STL 的相关接口规范。部分（如优先队列）包含 STL 内对应组件的所有功能，但比 STL 功能更多。

pb_ds 只在使用 libstdc++ 为标准库的编译器下可以用。

堆：

在堆的实现上，pb_ds 比 STL 提供了更多的选择。

__gnu_pbds::priority_queue<Typename,Compare,Tag>

pb_ds 根据 Tag 参数的不同，支持五种类型的堆。

• pairing_heap_tag 配对堆。
• binary_heap_tag 二叉堆。
• binomial_heap_tag 二项堆。
• rc_binomial_heap_tag 冗余计数二项堆。
• thin_heap_tag 除了合并的复杂度都和 Fibonacci 堆一样。

平衡树：

pb_ds 实现了三种类型的平衡树。

• rb_tree_tag 红黑树。
• splay_tree_tag 伸展树。
• ov_tree_tag 有序向量树。

主要是和 STL 中 set 的比较。

pb_ds 更多地支持了：

• s.order_of_key(x)返回 s 中 x 的排名。
• s.find_by_order(x)返回 s 中排名为 x 的元素。
• s.join(S)把 S 合并到 s 中。
• s.split(x,S)小于等于 x 的属于当前树，其余的属于 S 树。