STL的使用
题单介绍
在C++中，内置了一些标准的模板库，被称为STL（Standard Template Library）。平时经常使用的数据结构，比如栈、队列、向量（长度可变的数组）等。还有一些常用算法，比如排序、二分查找等。需要使用时可以直接拿过来用，不用自己实现。方便了代码的编写。
这里列举一些常用的模板，其他模板可以到[cplusplus.com](https://cplusplus.com/)或百度上搜索。
STL在使用前需加上对应头文件和using namespace std;
以下所有T都表示需要存放的数据类型，如int。
1. 栈
```
头文件：stack
定义：stack<T> s;
压入：s.push(x);//O(1)
弹出：s.pop();//O(1)
查看栈顶元素：s.top();//O(1)
查看栈里的元素个数：s.size();//O(1)
```
2. 队列
```
头文件：queue
定义：queue<T> q;
入队：q.push(x);//O(1)
出队：q.pop();//O(1)
查看队首元素：q.front();//O(1)
查看队列里的元素个数：q.size();//O(1)
```
3. 向量
```
头文件：vector
定义：vector<T> a;
尾部加入一个元素：a.push_back(x);//O(1)
查看元素个数：a.size();//O(1)
查看第i个元素：a[i];//O(1)
遍历：for(int i=0;i<a.size();i++)printf("%d ",a[i]);
```
4. 排序
```cpp
头文件：algorithm
如果要对a[l]~a[r]从小到大排序
sort(a+l,a+r+1);//O(nlogn) n为长度
如果要对a[l]~a[r]从大到小排序
bool cmp(T x,T y){
return x>y;
}
sort(a+l,a+r+1,cmp);
```
5. 字符串
```cpp
头文件：string
定义：string s;
长度：s.size();//O(1)
第i个字符（下标从0开始到size-1）:s[i];//O(1)
翻转：s.reverse();//O(n)
赋值：s=a;//O(n),a可以是一个string，一个char数组或char类型
在后面加一个字符或字符串：s+=a;//O(a的长度),a的类型同上
插入、删除、替换、查找、取子串、比较：insert、erase、replace、find、substr、compare
//参考： https://legacy.cplusplus.com/reference/string/string/?kw=string
按字典序比较：使用比较符号即可
连接两个字符串：s1+s2
输入：cin>>s;
输出：cout<<s;
输入一行：getline(cin,s);
```
以上为入门组要求掌握的STL用法
------------
[迭代器iterator](http://c.biancheng.net/view/338.html)
下面用it表示相应的迭代器
6. 集合
```cpp
该集合与数学中的集合定义类似，不存在相等的元素。
即不存在元素x与y，使得x<y与y<x同时不成立。
set使用红黑树实现，是一个平衡树。
头文件：set
定义：set<T> s;
插入：s.insert(x);//O(logn)
删除：s.erase(x);//O(logn)，x可以为值或者迭代器
元素个数：s.size();//O(1)
清空集合：s.clear();//O(n)
前一个元素：prev(it);//O(1)
后一个元素：next(it);//O(1)
使迭代器向后移动一个元素：++it;//O(1)
使迭代器向前移动一个元素：--it;//O(1)
从小到大遍历：for(set<T>::iterator it=s.begin();it!=s.end();++it)//O(n)
从大到小遍历：for(set<T>::reverse_iterator it=s.rbegin();it!=s.rend();++it)//O(n)
查找：s.find(x);//O(logn)，若找到了则会返回相应元素的迭代器，若没找到则会返回s.end()，下同
查找大于等于x的第一个元素：s.lower_bound(x);//O(logn)
查找大于x的第一个元素：s.upper_bound(x);//O(logn)
```
7. 多重集合
```cpp
与set类似，但是可以存在相等的元素。
要注意在erase时，最好使用迭代器删除。
若用值删除，则会把相等的元素全都删掉
头文件：set
定义：multiset<T> s;
统计x的个数：s.count(x);//O(logn)
```
8. 双端队列
```cpp
头文件：queue
定义：deque<T>q;
队尾push：q.push_back(x);
队首push：q.push_front(x);
队尾pop：q.pop_back();
队首pop：q.pop_front();
查看队尾：q.back();
查看队首：q.front();
复杂度均为O(1)
```
9. 优先队列（大根堆）
```cpp
头文件：queue
定义：priority_queue<T> q;
插入：q.push(x);//O(logn)
删除最大值：q.pop();//O(logn)
查看最大值：q.top();//O(1)
查看元素个数：q.size();//O(1)
```
10. 映射（字典）
```cpp
map是一个值到另一个值的映射，类似python里的字典。
每一对值分为键key和值value，以key当做查找的关键字。
map也是用红黑树实现的，各个操作复杂度同set
头文件：map
定义：map<T1,T2> a;
赋值：a[x]=y;//O(logn)若已有键x，那么将其对应的值改成y
//否则插入一对新的键值x和y
取x对应的值：a[x];//O(logn)
查找是否存在键x：a.find(x);O(logn)//若找到则会返回对应迭代器，否则返回a.end()
//若想看键x是否存在，一定要用find，而不要用中括号
查看该迭代器的键：it->first
查看该迭代器的值：it->second
删除元素：a.erase(it)//O(1)用法同set
```
11. 无序映射
```cpp
头文件：unordered_map
定义：unordered_map<T1,T2>a;
用法与map一样，但是是用哈希表实现的。
所以本来 O(logn)的复杂度的操作在平均情况下都为O(1)，但是在非常极端的情况下一次操作为O(n)
```