单链表
//head 链表头
//e[]节点的值
//ne[]节点的next指针
//idx当前用到了哪个节点
int head,e[N],ne[N],idx;//数组模拟单链表
void init(){//初始化
head=-1;
idx=0;
}
void insert(int a){//在链表头插入一个数a
e[idx]=a,ne[idx]=head,head=idx++;
}
void remove(){//将头结点删除，需要保证头结点存在
head=ne[head];
}双链表
//e[]节点的值
//l[]节点的左指针
//r[]节点的右指针
//idx当前用到了哪个节点
int e[N],l[N],r[N],idx;//数组模拟双链表
void init(){// 初始化
r[0]=1,l[1]=0;//0是左端点，1是右端点
idx=2;
}
void insert(int a,int x){//在节点a的右边插入一个数x
e[idx]=x;
l[idx]=a,r[idx]=r[a];
l[r[a]]=idx,r[a]=idx++ ;
}
void remove(int a){//删除节点a+
l[r[a]]=l[a];
r[l[a]]=r[a];
}栈
int stk[N],tt=0;//数组模拟栈，tt表示栈顶
stk[++tt]=x;//向栈顶插入一个数
tt--; //从栈顶弹出一个数
stk[tt]; //栈顶的值
if(tt>0){ }//判断栈是否为空，如果tt>0，则表示不为空普通队列
int q[N],hh=0,tt=-1;//数组模拟队列：hh表示队头,tt表示队尾
q[++tt]=x;//向队尾插入一个数
hh ++ ; //从队头弹出一个数
q[hh]; //队头的值
if(hh<=tt){ }//判断队列是否为空，如果hh<=tt，则表示不为空循环队列
int q[N],hh=0,tt=0;//hh表示队头,tt表示队尾的后一个位置
q[tt++]=x;// 向队尾插入一个数
if(tt==N) tt=0;
hh++; // 从队头弹出一个数
if(hh==N) hh=0;
q[hh]; // 队头的值
if(hh!=tt){ }//判断队列是否为空，如果hh!=tt，则表示不为空单调栈
//常见模型：找出每个数左边离它最近的比它大/小的数
int tt=0;
for (int i=1;i<=n;i++){
while(tt&&check(stk[tt],i)) tt--;
stk[++tt]=i;
}单调队列
//常见模型：找出滑动窗口中的最大值/最小值
int hh=0,tt=-1;
for (int i=0;i<n;i++ ){
while(hh<=tt&&check_out(q[hh])) hh++;//判断队头是否滑出窗口
while(hh<=tt&&check(q[tt],i)) tt-- ;
q[++tt]=i;
}堆
//h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x+1
//ph[k]存储第k个插入的点在堆中的位置
//hp[k]存储堆中下标是k的点是第几个插入的
int h[N],ph[N],hp[N],size;
void heap_swap(int a,int b){//交换两个点，及其映射关系
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int u){ //下沉
int t=u;
if(u*2<=size&&h[u*2]<h[t]) t=u*2;
if(u*2+1<=size&&h[u*2+1]<h[t]) t=u*2+1;
if(u!=t){
heap_swap(u,t);
down(t);
}
}
void up(int u){ //上浮
while(u/2&&h[u]<h[u/2]){
heap_swap(u,u/2);
u>>=1;
}
}
for(int i=n/2;i;i--) down(i); //O(n)建堆C++ STL常用函数
vector //变长数组，倍增的思想
size() //返回元素个数
empty() //返回是否为空
clear() //清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
//支持比较运算，按字典序
pair<int, int>
first //第一个元素
second //第二个元素
//支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string //字符串
size()/length() //返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) //返回子串
c_str() //返回字符串所在字符数组的起始地址
queue //队列
size()
empty()
push() //向队尾插入一个元素
front() //返回队头元素
back() //返回队尾元素
pop() //弹出队头元素
priority_queue //优先队列，默认是大根堆
size()
empty()
push() //插入一个元素
top() //返回堆顶元素
pop() //弹出堆顶元素
priority_queue<int, vector<int>, greater<int> > q;//定义小根堆
stack //栈
size()
empty()
push() //向栈顶插入一个元素
top() //返回栈顶元素
pop() //弹出栈顶元素
deque //双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set,map,multiset,multimap //基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- //返回前驱和后继，时间复杂度O(logn)
set/multiset
insert() //插入一个数
find() //查找一个数
count() //返回某一个数的个数
erase()
// (1) 输入是一个数x，删除所有x O(k + logn)
// (2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) //返回大于等于x的最小的数的迭代器
upper_bound(x) //返回大于x的最小的数的迭代器
map/multimap
insert()//插入的数是一个pair
erase() //输入的参数是pair或者迭代器
find()
[] //注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set,unordered_map,unordered_multiset,unordered_multimap,哈希表
//和上面类似，增删改查的时间复杂度是 O(1)
//不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset //方便地管理一系列的bit位而不用程序员自己来写代码
bitset<10000> s; //s为变量名
~, &, |, ^
>>, <<
==, !=
[] //访问某一位
count() //返回有多少个1
any() //判断是否至少有一个1
none() //判断是否全为0
set() //把所有位置成1
set(k, v) //将第k位变成v
reset() //把所有位变成0
flip() //等价于~
flip(k) //把第k位取反