（以前记住是以前！）有时候我让别人帮我调个代码，别人说：“你直接用$STL$库的blablabla……之类的不就好了吗？？？绕来绕去的干什么？”

what？什么东西？你刚刚说什么？$STL$是什么？我万脸懵……

于是，我决定来学习下$STL$……

一、vector

$vector$可以理解为变长数组，内部实现基于倍增思想。
设$n$为$vector$的实际长度，$m$为$vector$的最大长度
在加入元素之前，如果$n == m$就再内存中申请$2 \times m$的新空间，把内容转到新的连续空间上，同时释放旧的空间，然后再加入元素
删除元素的话在删除后如果$n \leqslant m/4$，就释放一半的空间。

感谢@SKG_G大佬给的这些函数~

1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6．front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据

声明：

#include <vector>   //头文件
vector<int> a;      //可以理解为定义一个长度动态变化的int数组
vector<int> b[100]  //可以理解为定义一个第一维长度100，第二位长度动态变化的int数组
vector<blabla...>   //其他的类型也可以放在vector（包括自定义的struct，甚至是另一个vector，也就是多维动态数组）

也就是说：

vector<vector<vector<vector<blabla...>>>>   //这样也可以！！！

size/empty

$size$函数返回的是$vector$的实际长度，$empty$函数返回的是$vector$是否为空
二者的时间复杂度都是$O(1)$
所有的$STL$容器都有这两个函数，并且含义都一样~

clear

把vector清空

front/back

$front$函数返回的是$vector$的第一个元素，等价于*a.begin() 和 $a[0]$
$back$函数返回的是$vector$的最后一个元素，等价于*--a.end() 和 $a[a.size() - 1]$

push_back/pop_back

a.push_back(x) 把元素$x$插入到$vector$$a$的尾部。
a.pop_back() 删除掉$vector$$a$的最后一个元素。

二、pair（二元组）

用法：

pair<blabla1, blabla2> p;
p = make_pair<类型为blabla1, 类型为bleble2>;
中间两个类型blabla1和blabla2可以是int string char long    long long ……还有其他的类型。

$pair$也可以理解为结构体，把两个数据合并成一个数据。
访问两个成员的方法：

p.first       //访问第一个成员
p.second      //访问第二个成员

三、string

天哪！不搜不知道，一搜吓一跳！
绕了老半天我才发现$string$也是$STL$的容器！

声明：

#include <string>     //头文件
string s;             //定义字符串s
s = "blablabla...";   //给字符串赋值
s = "";               //空串也可以
s += 'S';             //在字符串末尾加上一个字符
s += 'T';
s += 'L';
s += "zhen hao yong"; //在字符串末尾加上一个字符串
cout << s[1];         //随机访问元素
int len = s.size();
int l = s.length();   //size 和 length 都可以返回字符串的长度
bool f = s.empty();   //若字符串为空则返回1，否则返回0

四、queue

#include <queue>这个头文件包含两个容器：
循环队列queue 和 优先队列priority_queue
声明：

queue<blablabla...> q;
priority_queue<blablabla......> q;
queue< pair<int, int> > q;
                    ~~~
    这里要空格，不然会识别成位运算右移符号

循环队列queue

优先队列priority_queue

五、stack

$stack$就是栈啦，是$STL$中一个先进后出（$FILO$）的容器。

头文件：#include <stack>
声明：stack<元素的类型> s;

六、deque

$deque$是双端队列

danshi

我每次都会把它记成：duque❌,dqeue,❌deqeu❌之类的┭┮﹏┭┮
哎，我怎么这么奇葩啊……

头文件：#include <deque>
声明：deque<元素类型> q;
deque就像是vector和queue的结合（是这样说，但是我咋觉得是栈和队列的结合啊。。。）
它支持随机访问（直接[]访问某个元素）

front/back

用法与queue类似，$O(1)$

qush_back

从队尾入队，$O(1)$

qush_front

从队头入队，$O(1)$

pop_front

从队头出队，$O(1)$

pop_back

从队尾出队，$O(1)$

clear

清空队列，$O(n)$

上面的这些函数用法都是：q.blablabla()

七、map

#include <map>
map太好用了~

小小声：我二分第一次出现的位置都直接用上了map……（别给我乱传出去啊！！！）

用法：

map<key_type, value_type> m;
m[key_type类型的变量] = value_type类型的变量;

八、set

#include <set>这个头文件主要包括了$set$和$multiset$这两个容器
$set$是有序集合
$multiset$是有序多重集

s.size()    //元素个数
s.empty()   //是否为空
s.clear()   //清空
s.begin()   //集合中最小元素的迭代器
s.end()     //集合中最大元素的下一个位置的迭代器
//所以--s.end()指向集合中最大元素的迭代器
s.insert(x) //把元素x插入到集合s中，时间复杂度O(log n)
s.find(x)   //在集合中查找等于x的元素，并返回指向该元素的迭代器，不存在则返回s.end()，时间复杂度O(log n)
s.count(x)  //返回集合中等于x的元素个数，时间复杂度为O(k + log n)，k是元素x的个数

九、bitset

$bitset$可以看作是一个多位二进制数，每八位占用了一个字节，支持基本的位运算。
$n$位$bitset$执行一次位运算的时间复杂度可以视为$n/32$，效率还是蛮高滴~
头文件：#include <bitset>
声明：

bitset<10000> s;
//表示声明一个10000位的二进制数，<>当中填写的是位数，下面用n来表示位数

位运算：

~s      //对bitset s按位取反的结果
& | ^   //返回对两个位数相同的bitset进行按位与、或、异或运算的结果
<<  >>  //返回把一个bitset左移或右移若干位的结果
== !=   //比较两个bitset代表的二进制数是否相等

[]操作符
$s[k]$表示$s$的第$k$位，可以取值，也可以直接赋值
最低位为s[0]，最高位为s[n - 1]

s.count()返回的是有多少位为1

如果s所有位都是0，则s.any()返回$false$，s.none返回$true$。
如果s至少一位为1，则s.any()返回$true$，s.none返回$false$。

s.set()      //把s的所有位变成1
s.set(k, v)  //把s的第k位改成v，即s[k] = v
s.reset()    //把s所有位变为0
s.reset(k)   //把s的第k位改为0，即s[k] = 0
s.flip()     //把s的所有位取反，即s = ~s
s.flip(k)    //把s的第k位取反，即s[k] ^= 1

们有什么意见欢迎在评论区留言O~

接下来我还会按照大佬们的意见来修改O~