手拆STL

vector

$vector$，动态数组。
先来看一下它的一些基本操作及其拆后残渣。
1.a.push_back(x)，将$x$加入动态数组$a$的末尾。
实现：a[++cnt]=x
2.a.size()，查询动态数组$a$中元素的数量。
实现：cnt
3.a.pop_back()，将动态数组$a$末尾的元素删除。
实现：cnt--
4.a.erase(a.begin()+x)，删除动态数组$a$中第$x+1$个元素。
实现：for(int i=x+1;i<=--cnt;i++)a[i]=a[i+1];
5.a.clear()，清空动态数组$a$。
实现：cnt=0
总体实现：

int a[N];
int cnt;
void Push_back(int x){a[++cnt]=x;
}
int Size(){return cnt;
}
void Pop_back(){cnt--;
}
void Erase(int x){for(int i=x+1;i<=--cnt;i++)a[i]=a[i+1];
}
void Clear(){cnt=0;
}

queue

$queue$，队列。
队列常用的操作：
1.q.push(x)，向队列$q$中加入一个元素$x$。
实现：q[++tail]=x
2.q.pop()，弹出队列$q$的队首。
实现： head++
3.q.front()，查询队列$q$的队首。
实现：q[head+1]
4.q.back()，查询队列$q$的队尾。
实现：q[tail]
5.q.empty()，判断队列$q$是否为空。
实现：(head==tail)
6.q.size()，查询队列$q$的元素个数
实现：tail-head
手写的思想：两个变量$head$和$tail$，$head$存队头前一个元素的下标，$tail$存队尾的下标。
总体实现：

int q[N];
int head,tail;
void Push(int x){q[++tail]=x;
}
void Pop(){head++;
}
int Front(){return q[head+1];
}
int Back(){return q[tail];
}
bool Empty(){return head==tail;
}
int Size(){return tail-head;
}

deque

$deque$，双端队列。
一些基本操作：
1.q.push_back(x)，在双端队列$q$的队尾加入一个元素$x$。
实现：q[++tail]=x
2.q.push_front(x)，在双端队列$q$的队头加入一个元素$x$。
实现：q[head--]=x
3.q.front()，查询双端队列$q$的队头。
实现：q[head+1]
4.q.back()，查询双端队列$q$的队尾。
实现：q[tail]
5.q.pop_back()，弹出双端队列$q$的队尾。
实现：tail--
6.q.pop_front()，弹出双端队列$q$的队头。
实现：head++
手写的思想：两个变量$head$和$tail$，开双倍的数组空间$N$，将$head$和$tail$都初始化为$\frac{N}{2}$，$head$存队头前一个元素的下标，$tail$存队尾的下标。
总体实现：

int q[N];
int head=N/2,tail=N/2;
void Push_back(int x){q[++tail]=x;
}
void Push_front(int x){q[head--]=x;
}
int Front(){return q[head+1];
}
int Back(){return q[tail];
}
void Pop_back(){tail--;
}
void Pop_front(){head++;
}

priority_queue

$priorit{y}_{q}ueue$，优先队列。
要拆优先队列，首先得明白优先队列的运行规则。
优先队列实际上是在维护一个二叉堆。
二叉堆就是一颗完全二叉树，那么要维护这个二叉堆的什么状态呢？
答案是维护二叉堆的每一个非叶子节点的值都大于等于（或者小于等于）它的两个儿子的值。
那么……开拆。（大根堆）
优先队列的常用操作：
1.q.push(x)，将元素$x$加入优先队列$q$。
对于一个元素，从左至右依次加入二叉堆，如果父亲节点有了这个儿子之后就违法了，那么它就当父亲了，父亲自然成了儿子。
例如向下面这个二叉堆加入一个元素$7$。

实现：

void Push(int x){q[++cnt]=x;int p=cnt;while(p>1&&q[p/2]<q[p])swap(q[p/2],q[p]),p/=2;//维护单调性
}

2.q.top()，返回优先队列$q$中的最值
实现：由于时刻都在维护二叉堆的单调性，所以最值就是q[1]
3.q.pop()，弹出优先队列$q$的队头（最值）。
实现：

void Pop(){q[1]=q[cnt--];q[cnt+1]=0;int p=1;while(p<=cnt&&q[p]<max(q[p*2],q[p*2+1])){//维护//判断左儿子和右儿子哪一个更大if(q[p*2]>q[p*2+1])swap(q[p],q[p*2]),p*=2;else swap(q[p],q[p*2+1]),p=p*2+1;}
}

思想：维护一个二叉堆。
总体实现：

int q[N];
int cnt;
void Push(int x){q[++cnt]=x;int p=cnt;while(p>1&&q[p/2]<q[p])swap(q[p/2],q[p]),p/=2;
}
int Top(){return q[1];
}
void Pop(){q[1]=q[cnt--];q[cnt+1]=0;int p=1;while(p<=cnt&&q[p]<max(q[p*2],q[p*2+1])){if(q[p*2]>q[p*2+1])swap(q[p],q[p*2]),p*=2;else swap(q[p],q[p*2+1]),p=p*2+1;}
}

stack

$stack$，栈。
栈的基本操作：
1.t.push(x)，将元素$x$加入栈$t$中。
实现：t[++cnt]=x
2.t.pop()，弹出栈$t$的栈顶。
实现：cnt--
3.t.top()，查询栈$t$的栈顶元素。
实现：t[cnt]
4.t.empty，判断栈$t$是否为空。
实现：(!cnt)
5.t.size()，查询栈$t$的元素个数。
实现：cnt
总体实现：

int t[N];
int cnt;
void Push(int x){t[++cnt]=x;
}
void Pop(){cnt--;
}
int Top(){return t[cnt];
}
bool Empty(){return !cnt;
}
int Size(){return cnt;
}