STL容器：
通有的：size(),empty()//O(1)的
auto可以遍历所有容器

1.vector（变长数组）：
基本思想：
倍增：
由于系统分配空间的时间是由申请次数决定而不是由申请空间大小决定的
所以vector一开始先申请32的空间当不足时，倍增空间之后将原来的元素copy进入新的v，以此类推。
当申请1e6的长度时需要额外copy的数大约是1e6（假设初始是1）所以可以近似看成O(1)的插入，开辟空间大约O(logn)
初始化vector：
vector<int> a;
vector<int> a(10);//初始化容量为10的vector
vector<int> a(10,-3)//初始化容量为10并且全部填充3
vector<int> a[10] vector数组，相当于10个vector
函数：
clear()
front(),back()
push_back(),pop_back()
迭代器：begin(),end()//看成指针 *解引用

遍历：
数组下标遍历
迭代器遍历：
for(vector<int>::it = a.begin();it!=a.end();it++ )cout<<*it；
for(auto it = a.begin();it!=a.end();it++ )cout<<*it；
范围遍历：
for(auto x:a)cout<<x<<" ";

支持比较运算：(字典序比较)
vector<int> a(4,3),b(3,4);
a<b（字典序比较：从第一位开始比较如果第一位小于那么整个小于，相等向后看）

2.pair(二元组):
初始化：
c++11：pair<int,string>p; p=(10,"yxc");
支持比较运算：
按字典序，以first为第一关键字
pair存储三个：pair[HTML_REMOVED]>;

3.string：
支持+运算符（拼接字符串）
常用substr(1,2)从下标1开始返回长度为2的子串
substr(1)下标1开始返回整个子串x
不用cout输出string:printf("%s\n",str.c_str();(c_str():返回转化为c语言字符数组的头指针)
lenth()==size()作用相同

4.queue：
front(),back()
push(),pop()
没有clear()函数
如果想要清空直接重新构造：queue<int> q; q=queue<int>();

5.priority_queue:
默认是大根堆
push()
pop()
top()//取堆顶
priority_queue<int> q;//默认
priority_queue<int,vector<int>,greater<int>> heap;//小根堆，类型-用什么方式存储-？？
另一种变成小根堆的方式：每个元素取反存储

6.stack:
top()//取出栈顶
//string 也可以用作栈 string a a.back();

7.deque(加强vector):
支持clear()
push_back/pop_back 队尾加入/弹出元素
push_front/pop_front 队首加入/弹出元素
支持随机寻址
front/back 返回队首队尾元素
缺点：稍慢

8.set/multiset，map/multimap（基于平衡二叉树-红黑树，动态维护有序序列）：
clear()
set/multiset:
multiset 允许有重复元素
insert()// O(logn)
erase()
find() 没有查找到则返回end()迭代器
erase： //O(logn)
输入一个数，那么删除所有等于这个数的节点
输入一个迭代器，删除这个迭代器
核心：
lower_bound()//返回大于等于x的最小的迭代器
upper_bound()//返回大于x的最小的迭代器
如果不存在返回end()迭代器

begin(),end() //支持++ – 操作返回前驱后继

map/multimap：

insert() 插入pair
erase() 迭代器或者pair
数组类似寻址 O(logn)
lower_bound()//返回大于等于x的最小的迭代器
upper_bound()//返回大于x的最小的迭代器

9.unordered_set/unordered_multiset，unordered_map/unordered_multimap:

基于哈希表内部无序，不支持upper/lower，不支持迭代器++/–

好处：所有增删改差复杂度O(1)

10.bitset：
压位
省空间，只关注位上的关系
eg：bool 数组 bool量 1B 用bitset可以压为1/8
定义：
bitset <个数> 变量名;
支持：
~，&，|，^
>>，<<
==，!=
[]
常用函数：
count(); 返回某一个数的个数
any(); 判断是否至少有一个1
none(); 判断是否全为0
set(); 把所有位置赋值为1
set(k,v); 将第k位变成v
reset(); 把所有位变成0
flip(); 把所有位取反，等价于~
flip(k); 把第k位取反