STL
vector, 变长数组
string，字符串，substr(), c_str()
queue, 队列push(), front(), pop()
priority_queue, 优先队列，push(), top(), pop()
stack, z栈，push(), top(), pop()
deque, 双端队列
set, map, multiset, multimap, 基于平衡二叉树（红黑树）， 动态维护有序序列
unordered_set, unordered_map, unorder_multiset, unordered_multimap
bitset 压位
vector（变长数组），倍增的思想，支持比较运算（按字典序）
定义：
- vector <int> a; 定义：一个vector数组a
-
vector <int> a(10); 定义：一个长度为10的vector数组a
-
vector <int> a(10,3); 定义：一个长度为10的vector数组a，并且所有元素都为3
-
常用函数：
-
size(); 返回元素个数
- empty(); 返回是否是空
- clear(); 清空
- front(); 返回vector的第一个数
- back(); 返回vector的最后一个数
- push_back(); 向vector的最后插入一个数
- pop_back(); 把vector的最后一个数删掉
- begin(); vector的第0个数
-
end(); vector的最后一个的数的后面一个数
-
支持比较运算
c++
vector<int> a(4, 3), b(3, 4);
if(a < b) cout << "a < b";
-
倍增的思想：
系统为某一程序分配空间是，所需时间，与空间大小无关，与申请次数有关 -
遍历方法
假设有个vector <int> a; -
第一种：
c++ for(int i = 0; i < a.size(); i ++ ) cout << a[i] << " "; -
第二种：
for(vector<int>::iterator i = a.begin; i != a.end(); i ++ ) cout << *i << " "; -
第三种：
c++ for(auto x : a) cout << x << " ";
pair，支持比较运算，以first为第一关键字，以second为第二关键字（按字典序）
- 定义：：
pair <类型,类型> 变量名; 两个类型可以不同 - 初始化方式：
假设有个pair [HTML_REMOVED] p;
第一种：
p = make_pair(10,”abc”);
第二种：
p = {10,”abc”); -
常用函数：：
first(); 第一个元素（通常需要把排序的放到
second(); 第二个元素 -
pair存储三个不同东西
c++
pair<int, pait<int, int>>p;
string（字符串）
-
常用函数：：
substr(); 返回每一个子串
c_str(); 返回这个string对应的字符数组的头指针
size(); 返回字母个数
length(); 返回字母个数
empty(); 返回字符串是否为空
clear(); 把字符串清空 -
```c++
string a = “abc”;
cout << a.substr(1, 10);//输出到最大为止，输出abc(起始位置，长度)
cout << a.substr(1); //输出从1开始的整个子串
printf(“%s”, a.c_str());//输出字符串
```
-
queue（队列）
-
定义：：
queue <类型> 变量名; -
常用函数：：
size(); 这个队列的长度
empty(); 返回这个队列是否为空
push(); 往队尾插入一个元素
front(); 返回队头元素
back(); 返回队尾元素
pop(); 把队头弹出
注意：队列没有clear函数！！！
c++
queue<int> q;
q = queue<int>();//需要清空的话直接重新构造
- 清空：
变量名 = queue <int> ();
priority_queue（优先队列，堆）
-
注意：默认是大根堆！！！
-
定义：：
-
大根堆：priority_queue <类型> 变量名;
-
小根堆：priority_queue <类型,vector <类型>,greater <类型>> 变量名
c++ //小根堆 //法一直接插入-x priority_queue<int> heap; heap.push(-x); //法二直接定义小根堆 priority_queue<int, vector<int>, greater<int>> heap; -
常用函数：
size(); 这个堆的长度
empty(); 返回这个堆是否为空
push();往堆里插入一个元素
top(); 返回堆顶元素
pop(); 弹出堆顶元素
注意：堆没有clear函数！！！
stack（栈）
- 常用函数：
size(); 这个栈的长度
empty(); 返回这个栈是否为空
push(); 向栈顶插入一个元素
top(); 返回栈顶元素
pop(); 弹出栈顶元素
deque（双端队列）
- 常用函数：
size(); 这个双端队列的长度
empty(); 返回这个双端队列是否为空
clear(); 清空这个双端队列
front(); 返回第一个元素
back(); 返回最后一个元素
push_back(); 向最后插入一个元素
pop_back(); 弹出最后一个元素
push_front(); 向队首插入一个元素
pop_front(); 弹出第一个元素
begin(); 双端队列的第0个数
end(); 双端队列的最后一个的数的后面一个数
set，map，multiset，multimap 基于平衡二叉树（红黑树），动态维护有序序列
size(); 返回元素个数
empty(); 返回set是否是空的
clear(); 清空
begin(); 第0个数，支持++或--，返回前驱和后继
++，– 返回前驱和后继
-
set/multiset
注意：set不允许元素重复，如果有重复就会被忽略，但multiset允许！！！ -
set所有操作时间按复杂度logn
-
常用函数：
end(); 最后一个的数的后面一个数，支持++或--，返回前驱和后继 insert(); 插入一个数 find(); 查找一个数 count(); 返回某一个数的个数 erase(); （1）输入是一个数x，删除所有x O(k + log n), k是x的个数 （2）输入一个迭代器，删除这个迭代器 ***lower_bound(x);*** 返回大于等于x的最小的数的迭代器，不存在返回end ***upper_bound(x);*** 返回大于x的最小的数的迭代器 -
map/multimap
-
常用函数：
insert(); 插入一个数，插入的数是一个pair
erase();
（1）输入是pair
（2）输入一个迭代器，删除这个迭代器
find(); 查找一个数
lower_bound(x); 返回大于等于x的最小的数的迭代器
upper_bound(x); 返回大于x的最小的数的迭代器 -
```c++
//像数组一样用map,时间复杂度是logn
map[HTML_REMOVED] a;
a[“yxc”] = 1;
cout << a[“yxc”] << endl;return 0;
```
unordered_set，unordered_map，unordered_muliset,unordered_multimap 基于哈希表
- 和上面类似，增删改查的时间复杂度是O(1)
不支持lower_bound()和upper_bound()，不支持迭代器加加减减
bitset 压位，省八倍空间
- 定义：
bitset <个数> 变量名;
支持：
~，&，|，^
>>，<<
==，!=
[] - 常用函数：
count(); 返回某一个数的个数
any(); 判断是否至少有一个1
none(); 判断是否全为0
set(); 把所有位置赋值为1
set(k,v); 将第k位变成v
reset(); 把所有位变成0
flip(); 把所有位取反，等价于~
flip(k); 把第k位取反
