C++ STL那些事
仍在施工中
介绍C++ STL的一些函数和容器的用法。
简介
C++ Standard Template Library（标准模板库），简称 STL
成员
容器
map
有建立映射的关系。对于每一个 $key$ 有一个 $value$ 与之对应。
$$ key -> value $$
时间复杂度 $ O(log\_n) $
使用前包含头文件 <map>
#include比如我们新建了一个 map 叫 m，$key$ 是 string 类型，$key$ 是 int 类型，可以这么写：
map m;m.find(x)：传入 $key$。如果找到返回迭代器；否则返回 m.end()。由此可以发现，m.find(x)!=m.end() 可以判断 m[x] 是否存在
m.erase(x)：删除 m[x]
m.clear()：清空 m
如何遍历 map 中的元素？
for (auto it = m.begin(); it != m.end(); it++) {
string id = it->first;
int val = it->second;
cout << id << ':' << val << el;
}其中的 auto 会自动获取类型。在此样例中等价于map <string, int>::iterator
注：auto 需要在 C++11 下使用。正式赛中也可使用
#include<iostream>
#include<map>
#define el endl
using namespace std;
int main() {
ios::sync\_with\_stdio(false);
cin.tie(nullptr);
map <string, int>m;
m["aaa"] = 999;
m["bbb"] = 8;
m["uuu"] = 888;
m["haha"] = 888;
m["o"] = 23456;
//查询
bool find\_bbb = m.find("bbb") != m.end();
bool find\_ccc = m.find("ccc") != m.end();
cout << find\_bbb << ' ' << find\_ccc << el;
//1 0
//删除
bool find\_o\_before = m.find("o") != m.end();
m.erase("o");
bool find\_o\_after = m.find("o") != m.end();
cout << find\_o\_before << ' ' << find\_o\_after << el;
//1 0
//元素数量
cout << m.size() << el;
//4
//遍历
for (auto it = m.begin(); it != m.end(); it++) {
string id = it->first;
int val = it->second;
cout << id << ':' << val << el;
}
/\*
aaa:999
bbb:8
haha:888
uuu:888
\*/
return 0;
}unordered\_map
与map类似，但底层是通过Hash实现的，打CF比赛不要用，由于它的Hash模数是固定的所以容易被Hack。它的时间复杂度为 $ O(1) $
set
用以维护一个不可重集合
头文件<set>：
#include定义时：
set s;会定义一个名叫s的、存储元素类型为int的集合
与map类似，也有find、erase、size、clear函数
遍历元素：和 map 一样，也可以使用迭代器来遍历元素：
for (auto it=s.begin();it!=s.end();it++)
cout << \*it << " ";set 会自动对其中的元素做升序排列并去重
我觉得这样更方便：
for (int val : s)
cout << val << " ";set 与 map 一样，依赖与二叉平衡树。时间复杂度 $ O(log\_n) $
如果我们希望维护一个可重的集合如 $A=\{1,1,2,3\}$，可以使用 multiset 来实现
multiset
multiset 可以维护一个可重的集合
它也包含在 <set> 中。
m.lower_bound(val)：返回小于等于 val 中最大数的地址（-1就是 val的前驱）
m.upper_bound(val)：返回 val的后继
由于 multiset 可重的特性，删除元素有两种情况
- 删除所有值为
x的元素
m.erase(x);- 删除一个值为
x的元素
if (m.find(x) != m.end())
m.erase(m.find(x));注意判断 x 是否存在
priority\_set
优先队列。
给一个序列插入元素并及时获取最大值或最小值
以 $O(log\_n)$ 插入元素；$O(1)$ 获得最大/小值
头文件：<queue>
priority\_queue q;建立名为 q 的优先队列，存储元素类型为 int
priority\_queue , greater >q;同上，但这让队首从最大值变为最小值
q.top()：获取队首
q.pop()：弹出队首
q.size()：获取大小
q.push(x)：将 x 插入优先队列
优先队列不提供clear
这里有一道优先队列的例题：P3378 【模板】堆
函数
sort
传入排序的开始和结束的下一个地址。
排序类似 vector、string的容器排序时：调用
sort(s.begin(), s.end());unique
（英文单词独特）
对有序数组进行去重的功能
假设我们有：
$$ a\_1=1,a\_2=1,a+3=2,a\_4=2 $$
要对 $a\_1$ ~ $a\_4$ 去重，调用 unique(a+1,a+1+4)即可
unique(a+1,a+1+4)会返回
reverse
翻转。
传入翻转的开始和结束的下一个地址。同sort，如果是string等，使用
reverse(s.begin(), s.end());（会修改以前的数组！