vector(变长数组,倍增的思想)

头文件：#include <vector>
1.初始化
vector<int> a;   //定义了一个名字为a，用来存储int的vector
vector<int> a(10);  //a的长度为10
vector<int> a(10,3);  //长度为10，并且所有值为3
vector<int> a[10]; //定义了一个vector数组

2.常用函数
vector<int> a;
a.size();  //返回元素个数
a.empty(); //判断数组是否是空的(返回true/false)
a.clear(); //清空
a.front(); //返回第一个数
a.back();  //返回最后一个数
a.push_back(); //向最后边插入一个数
a.pop_back();  //把最后一个数删掉
a.begin();   //迭代器，a的第0个数
a.end();    //迭代器，a的最后一个数的下一个数
例：迭代器的遍历方法
for(vector<int>::iter i=a.begin(); i!=a.end(); i++)                 cout<<*i<<endl;

3.vector支持比较运算
vector是支持比较运算的，按照字典序来比
例如：vector<int> a(4,3),b(3,4);
因为按照字典序，4个3是大于3个4的，所以：
    (a<b) 的返回值是true;

pair(二元组)

可以看成一个结构体，并且自带了一个比较函数

头文件：#include <utility> //(写了<iostream>时，就不用写这个了)
1.初始化
pair<int, int> a;
a=make_pair(10,"yxc");
a={20,"abc"}; //C++11

2.常用函数
pair<int, int> a;
a.first;   //返回第一个元素
a.second;  //返回第二个元素

3.支持比较运算，按字典序
以first为第一关键字，以second为第二关键字()

4.扩展用法：用pair来存储三个东西
pair<int,pair<int, int>> a;

string(字符串)

头文件：#include <string>
1.声明
string s;

2.常用函数
string s;
s.size();
s.length(); //等于size();
s.empty();
s.clear();
s+="abc"; s+='c';  //string类型可以加上一个字符串或字符
s.substr(a,b);  
/*
返回从a开始，b个字母长的子串，如果b过大，则会返回到末尾
也可以省略b,则会直接从a开始，自动返回剩余的子串
*/
s.c_str(); 
/*返回s存储字符串的一个起始地址(常用于printf(%s) 输出)
例： printf("%s",s.c_str());
*/

3.拓展：string还可用作栈

queue, priority_queue(队列,优先队列(堆))

push(),front(),pop()

push(),top(),pop()

queue:
头文件：#include <queue>
1.初始化
queue
2.常用函数
quque<int> q;
q.size();
q.empty();
q.push();   //向队尾插入一个元素
q.front();  //返回队头元素
q.back();   //返回队尾元素
q.pop();    //弹出队头元素

priority_queue:
头文件：#include <queue>
1.初始化(默认是大根堆)
priority_queue<int> heap;

2.常用函数
priority_queue<int> heap;
heap.push();    //插入一个元素
heap.top();     //返回堆顶元素
heap.pop();     //弹出堆顶元素

3.构建小根堆的方法
    1.构建堆插入的时候，插入一个-x
        heap.push(-x);
    2.定义的时候直接定义小根堆(定义的时候多加两个参数)
        priority_queue<int, vector<int>, greater<int>> heap;

stack(栈)

头文件:#include <stack>
1.初始化
stack<int> s;
2.常用函数
stack<int> s;
s.size();
s.empty();
s.push();   //向栈顶插入一个元素
s.top();    //返回栈顶元素
s.pop();    //弹出栈顶元素

deque(双端队列)

头文件:#include <deque>
1.初始化
deque<int> dq;

2.常用函数
deque<int> dq;
dq.size();
dq.empty();
dq.front()/back();
dq.push_back()/pop_back();
dq.push_front()/pop_front();
dq.begin()/end();//支持begin()/end()两个迭代器
[]//支持随机询址

3.缺点！！deque速度慢，比一般的数组会慢好几倍

set,map,multiset,multimap(树和平衡树)

基于平衡二叉树实现的（红黑树），本质上是动态维护有序序列

set/multiset:
头文件:#include <set>
set中不可以有重复元素,multiset中可以有重复元素
1.初始化
set<int> s;
multiset<int> s;
2.常用函数
s.size();
s.empty();
s.clear();
s.begin()/end();   ++，--;       //返回前驱和后继，O(logn)
s.insert(x);        //插入一个数
s.find(x);      //查找一个数
s.count(x);     //返回某一个数的个数
s.erase(x/迭代器);     
//(1) 输入是一个x，删除所有x O(k+logn) (k是x的个数)
//(2) 输入是一个迭代器，删除这个迭代器
核心操作：
s.lower_bound() //返回大于等于x的最小的数 (最小上届)的迭代器，不存在返回end
s.upper_bound() //返回大于x的最小的数 (最大下届)的迭代器，不存在返回end

map/multimap:
映射
头文件:#include <map>
1.初始化
map<string, int> m;
2.常用函数
size();
empty();
clear();
begin()/end();   ++，--;     //返回前驱和后继，O(logn)
insert();   //插入的数是一个pair
erease();   //输入的参数是pair或者迭代器
find();
[];/*
核心操作，可以像数组一样使用map O(logn)
例：map<string, int> m;
m["yxc"] = 1;
cout<<m["yxc"]<<endl;
(输出的结果是1)*/
lower_bound()/upper_bound()

unordered_set,unordered_map,unordered_multiset,unordered_multimap(哈希表)

头文件：#incldue [HTML_REMOVED]，#incldue [HTML_REMOVED]

和上边类似，内部是无须的，好处是增删改查的时间复杂度是O(1)，缺点是不支持lower_bound()/upper_bound()，以及迭代器的++，–

bitset(压位，位存储，状态压缩)

适用于题目卡空间的情况

它的使用的空间是其他数组的八分之一，比如需要bool a[1024]，用普通方式存储则需要1024B=1Kb，但是bitset是按位存储的，所以只需要128b就可以了。

1.定义
bitset<10000> S;  //参数是个数
2.常用的操作
~,&,|,^,>>,<<;  //支持所有的位运算操作
==, !=;
[];      //可以取出来某一位是0还是1
count();    //返回有多少个1
any();      //判断是否至少有一个1
none();     //判断是否全为0
set();      //把所有位置置成1
set(k,v);   //把第k位变成v
reset()     //把所有为变成0
flip()      //把所有位取反，等价于~
flip(k)     //把第k位取反