应用：
特别是要开二维数组，要节省空间的时候而且长度不定的时候特别好用，图中的邻接表就是很好的例子。
邻接表中一维数组存储顶点，一维vector存储该顶点的所有邻接点，避免开二维数组（邻接矩阵）带来的空间浪费，稀疏图尤其好用。
有时题目要输出路径，可以建立个vector
uva101，木块问题，类似的。
写法：
vector<int>vex[maxn];
应用：输出不重复的、查找(logn因为内部是红黑树，即平衡二叉树）
uva11572
输入一个长度为n的序列A，找到一个尽量长的连续子序列,使得该序列中没有相同的元素。
#include<bits/stdc++.h> using namespace std; //插入count,,insert erase int a[100000005]; int main() { int T; cin>>T; int n; while(T--) { cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } set<int>temp; int l,r,ans; l=r=ans=0; while(r<n)//本来写l<n，多此一举 { while(r<n&&!temp.count(a[r])) { temp.insert(a[r]); r++; } ans=max(ans,r-l); temp.erase(a[l]); l++; } cout<<ans<<endl; } }
[],insert,count和find函数,clear
应用：
以前统计字符出现次数，用的count[a[i]-'0']，其实就是用到map“关联数组”的思想。
#include<bits/stdc++.h> #include<map> using namespace std;map<char,int>a;//常用string，int int main() { char m[100]; cin>>m; int max1=0; for(int i=0;i<strlen(m);i++) { a[m[i]]++;//若不定义map用char数组，则要m[i]-'0' max1=max(max1,a[m[i]]);//字符最多出现次数 } cout<<max1<<endl;
}
还是上面的uva 11572
#include<bits/stdc++.h> using namespace std; //处理重复？→i,j 集合/出现次数 ==0→count[]++→ans→ --到!=temp map<int,int>a; int count1[10000005]; int main() { int T; cin>>T; int n; while(T--) { cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } int temp=-1; int i,j,ans; i=j=ans=0; while(i<n)//尺取法 { while(j<n&&count1[a[j]]==0) { count1[a[j]]++; j++; temp=a[j]; } ans=max(ans,j-i); while(a[i]!=temp) { count1[a[i]]--; i++; } if(a[i]==temp)//刚好到重复数字的位置 { count1[a[i]]--; i++; } } cout<<ans<<endl; a.clear(); } }
也是邻接表的例子，有时题目输入的是顶点名字而不是序号，《数据结构》课本给的方法是，另外用个string vex[]静态数组，但是每次都是顺序查找，要用O（n）时间，而map查找运用红黑树的原理，查找、插入、删除等操作仅用O（logn）时间。
pta QQ密码与账号的注册和登录
输入首先给出一个正整数N（≤），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。
针对每条指令，给出相应的信息：
1）若新申请帐户成功，则输出“New: OK”； 2）若新申请的号码已经存在，则输出“ERROR: Exist”； 3）若老帐户登陆成功，则输出“Login: OK”； 4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”； 5）若老帐户密码错误，则输出“ERROR: Wrong PW”。
#include <bits/stdc++.h> using namespace std; map<string,int>p;//号码与0/1（是否存在）的联系 map<string,string>q;//号码与密码的联系 int main() { int n; cin>>n; char a; string HM; string MM; while(n--) { cin>>a>>HM>>MM; if(a=='N') { if(p[HM]==0) { cout<<"New: OK"<<endl; p[HM]=1; q[HM]=MM; } else { cout<<"ERROR: Exist"<<endl; } } else { if(p[HM]==1) { if(q[HM]==MM) { cout<<"Login: OK"<<endl; } else { cout<<"ERROR: Wrong PW"<<endl; } } else { cout<<"ERROR: Not Exist"<<endl; } } } }
4.queue,deque,stack
size(),front(top),pop(),push(),empty()定义 queue<double> q; deque<double> q; 访问队列中的元素个数 q.size() q.size() 判断队列空 q.empty() q.empty() 尾部压入新元素 q.push(x) q.push_back(x) 头部压入新元素 EOF q.push_front(x) 弹出队列的第一个元素 q.pop() q.pop_front() 弹出队列的最后一个元素 EOF q.pop_back() 访问队首元素 q.front() （访问迭代器）q.begin() 访问队尾元素 q.back() （同上）q.end() 删除所有元素 EOF q.clear() 删除任意位置x EOF q .erase(q.begin() + x) (某大佬总结)应用：前者用的较多，如宽搜以及宽搜引出的各种算法。
deque有些滑动窗口类型题会用到
后者模拟题会用到，如括号匹配，但一般尽量用递归实现。
拓扑排序队列实现：
#include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std; const int maxn=1e6+10; int n,m,t; int G[1000][1000],id[1000],topo[1000]; void toposort() { queue<int> q; int t=0; for(int i=1;i<=n;i++) if(id[i]==0) q.push(i);//入度为零的放进队列 while(!q.empty()) { int u=q.front(); q.pop(); topo[t++]=u;//入度为零的就是排好的，拿出来 for(int i=1;i<=n;i++)//这个循环用来删除拿出来的点和相连接的点的边 if(G[u][i]!=0) if(--id[i]==0) q.push(i); } printf("%d",topo[0]); for(int i=1;i<t;i++) printf(" %d",topo[i]); printf("\n"); } int main() { while(scanf("%d%d",&n,&m) && (m!=0 || n!=0)) { memset(G,0,sizeof(G)); memset(id,0,sizeof(id)); int a,b; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); G[a][b]=1; id[b]++;//记录每个点的入度 } toposort(); } return 0; }
5.priority_queue
注意取队首写法是top()，还有重载运算符写法。
应用：
之前说贪心前一般有排序操作，如果是静态取一般是直接sort，但有时变化是动态的，取出或修改一个元素可能会对整体顺序造成影响，需要时刻排序，这时用priority_queue。
poj 2431 3614 2010 pku 3253
家庭作业代码
#include <bits/stdc++.h> using namespace std; struct aaa { int time,credit; bool operator < (const aaa &x) const {//方便优先队列排序 return credit>x.credit; } }a[1000010]; bool cmp1(aaa x,aaa y) { return x.time < y.time; }; priority_queue<aaa>que; //结构体写法比较好 ，priority_queue <int, vector <int>, greater <int> > q只能用于int; int main() { int n; cin>>n; for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].time,&a[i].credit); //que.push(a[i]); } sort(a+1,a+1+n,cmp1); int now=1; int sum=0; for(int i=1;i<=n;i++) { if(a[i].time>=now)que.push(a[i]),now++; else if(a[i].credit>que.top().credit)que.pop(),que.push(a[i]); //比如t=1两个1,2学分 ，t=2有7学分，不可能只按t小的在前面 } while(!que.empty()){ aaa tmp=que.top();que.pop(); sum+=tmp.credit; } cout<<sum<<endl; }宽搜一般用queue，但在有些问题中搜索权值不同，导致搜索顺序有影响，用优先队列。
2018湘潭程序设计竞赛一道题，我的题解：
点击打开链接
6.list
splice应用：线性结构（包括栈和队列）超时的时候，特别是合并操作，用链式结构往往有出其不意的效果。
洛谷 队列模拟（多删除中间元素操作）
题意：对n个栈，有q次操作。每个操作可能为三种情况中的一种：1.将v插入到s栈的顶端；2.输出s栈的栈顶（若栈为空则输出empty）；3.将栈t插入到栈s的栈顶。（合并）
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<list> #include<algorithm> using namespace std; const int maxn=300005; list<int> l[maxn]; int main() { int n,q,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&q); for(int i=1; i<n+1; i++)l[i].clear(); while(q--) { int op; scanf("%d",&op); if(op==1) { int s,v; scanf("%d%d",&s,&v); l[s].push_back(v); } if(op==2) { int s; scanf("%d",&s); if(l[s].empty())puts("EMPTY"); else { printf("%d\n",l[s].back()); l[s].pop_back(); } } if(op==3) { int s,t; scanf("%d%d",&s,&t); l[s].splice(l[s].end(),l[t]); } } } return 0; }
