vector是不定长数组，具有静态数组的稳定性和动态分配内存的灵活性，在赛场上不失为指针之外牺牲部分时间的保险之举。

本文先介绍一些vector常用的函数（部分借鉴一篇博客中的内容 链接），并以此为铺垫，介绍本人在解题过程中对vector用途的一些总结。

vector中迭代器的声明：vector::iterator it;

迭代器的使用方法与指针几乎完全一样，vector中绝大多数带参数的函数参数都有迭代器，很多函数的返回值也是迭代器。

---

（1）begin,end：

a.begin()返回指向a中第一个元素的迭代器，a.end()返回指向a中最后一个元素的位置的下一个位置的迭代器。

begin和end可以用来遍历，当然for(int i=0;i<a.size();i++)也可以实现，效率完全相同，但在运行一些输入参数为迭代器的函数时，vector的下标就无法解决了。

（2）size,capacity：

a.size()返回a中非空元素个数，a.capacity()返回a所占内存可容纳元素的个数。

（3）clear,resize：

a.clear()是void类型，表示将a中所有元素置空，但不改变a所占内存，即size变为0，capacity不变。

a.resize(x)也是void类型，表示将a的size变为x，capacity变为max(capacity,x)。（好奇怪的操作……）

（4）push_back：

a.pushback(x)是void类型，表示将x插入到a的尾部，size+1。

值得注意的是，a的capacity并不是push_back一次就+1，而是当capacity不够用的时候增大为原来的两倍。即capacity的值只可能是0或2的幂次。在某些极限情况下vector所占内存可以达到预计内存的近似两倍，在做题时要额外注意MLE的风险。

（5）insert：

insert共有三种用法：

1.a.insert(it,val)：函数表示在迭代器it指向位置之前插入值为val的元素，返回指向插入元素的迭代器。

2.a.insert(it,num,val)：该函数是void类型，表示在迭代器it指向位置之前插入num个值为val的元素。

3.a.insert(it,l,r)：该函数是void类型，表示在迭代器it指向位置之前插入从迭代器l指向位置到迭代器r指向位置的前一个位置的元素（即插入某个容器中[l,r)的元素）。

（6）erase：

erase共有两种用法，与insert的第一种和第三种类似。

1.a.erase(it)：函数表示删除迭代器it指向的元素，返回指向被删元素的前一个元素的迭代器。

2.a.erase(l,r)：函数表示删除从迭代器l指向位置到迭代器r指向位置的前一个位置的元素（即删除a中[l,r)的元素）。

insert的操作3和erase的操作2结合起来使用，可以实现区间的插入，删除，交换。

（7）lower_bound,upper_bound：

lower_bound(l,r,x)中l,r为迭代器，函数返回指向容器[l,r)中第一个大于等于x的元素的迭代器。

upper_bound(l,r,x)中l,r为迭代器，函数返回指向容器[l,r)中第一个大于x的元素的迭代器。

---

（1）邻接表的替代品

存储一张图的传统做法是邻接矩阵和邻接表。其中邻接矩阵好写，但内存消耗太大，同时找邻接点较慢，且重边问题较难解决；邻接表稍微复杂一些，但找邻接点快，也能解决重边情况。

而vector完全可以替代邻接表：定义vectorG[maxn];G[i][j]表示以点i为起点连出的第j条边在边目录中的编号。

若向图中加入一条边(u,v)则只需G[u].push_back(v);即可。遍历点u的邻接点只需遍历u的vector，然后根据u连出的边在边目录中的编号找到终点即可。

代码略。

（2）平衡树（除splay以外）的劣质替代品

平衡树一般用于维护一个序列，支持动态插入，删除一个数，同时查询某数的排名和排名为k的数是多少。

而splay由于其灵活性，还可以实现区间的插入，删除和翻转，它甚至还能实现普通线段树具备的功能。

vector可以以较好的复杂度暴力实现除了splay之外的平衡树能实现的一切操作。

具体操作：将序列中的数插入一个vector，并始终保持其有序，对于被操作的数x，可以用upper_bound或lower_bound在O(logn)内实现定位，随后的排名，前驱后继问题可以O(1)实现，插入删除需要用insert和erase。这两个操作复杂度似乎是O(n)，但由于平衡树的题目中各种操作随机进行，且插入和删除的位置也是随机的，vector暴力的速度不会太慢，在数据较小的时候性能可以与平衡树相媲美。

例题：Luogu P3369 【模板】普通平衡树（Treap/SBT）题目链接

题意：写一种数据结构，要求维护一个序列，支持动态插入，删除一个数，同时查询某数的排名和排名为k的数是多少，同时支持查询某数的前驱和后继。

题解：正解是平衡树，当然块状链表也可以A，也可以用vector暴力实现，具体操作见上文。

代码：

1 #include
2 using namespace std;
3 vectornode;
4 int n;
5 int main()
6 {
7 int i,j,flag,x;
8 vector::iterator pos,l,r;
9 cin>>n;
10 for(i=1;i<=n;i++)
11 {
12 scanf("%d%d",&flag,&x);
13 l=node.begin();r=node.end();
14 if(flag==1){pos=lower_bound(l,r,x);node.insert(pos,x);}
15 else if(flag==2){pos=lower_bound(l,r,x);node.erase(pos);}
16 else if(flag==3){pos=lower_bound(l,r,x);printf("%d\n",pos-l+1);}
17 else if(flag==4){printf("%d\n",*(l+x-1));}
18 else if(flag==5){pos=lower_bound(l,r,x);printf("%d\n",*(pos-1));}
19 else{pos=upper_bound(l,r,x);printf("%d\n",*(pos));}
20 }
21 return 0;
22 }

（3）内存池的另类实现

一些高级数据结构，其本质是两种数据结构的嵌套，最经典的是树套树。在写这类数据结构时经常会MLE，因此在建树时需要动态申请内存，并在删除时动态回收，这时候就需要以指针为基础的内存池。然而指针操作存在极大的不稳定性，经常会调试很长时间。这时候vector就以其静态数组的稳定性和动态分配内存的灵活性占有较大优势。

仍然以普通平衡树为例（树套树太难了不会写QAQ），我们分析平衡树代码会发现，使用静态数组时被删除的节点所在编号并不能复用，如果删除操作多一点时会造成很大的内存浪费。我们可以考虑开一个栈，将被删除的节点编号入栈，在插入节点时首先查看栈顶是否为空，如果不为空就将栈顶编号作为新节点编号，初步解决了问题。

然而，我们不知道在n次操作中平衡树节点最多时有多少个，数组大小仍然没有变化，此时我们需要一个大小随时可增加的数组，将原数组换成vector就可以完美解决问题。栈顶为空时进行push_back，或在长度不够时进行resize都可以解决问题。

代码：

1 #include
2 #define lc(x) node[x].ch[0]
3 #define rc(x) node[x].ch[1]
4 #define fa(x) node[x].f
5 using namespace std;
6 const int maxn=1e5+10;
7 struct dot{int ch[2],v,s,w,f;};
8 int n,tot=0,root=0,cap=0;
9 vectornode;
10 stacks;
11 void maintain(int x){node[x].s=node[x].w+node[lc(x)].s+node[rc(x)].s;}
12 int new_node(int v,int f){if(tot==cap-1){node.resize(cap+1000);cap+=1000;}node[++tot]=(dot){0,0,v,1,1,f};return tot;}
13 int cmp(int x,int v){return v==node[x].v?-1:v1){node[x].w--;maintain(x);return;}
73 root=merge(lc(x),rc(x));fa(root)=0;
74 s.push(x);
75 }
76 int rnk(int x,int v)
77 {
78 int p=find(x,v);if(!p){return 0;}
79 return node[lc(p)].s+1;
80 }
81 int kth(int x,int k)
82 {
83 int s=node[lc(x)].s;int w=node[x].w;
84 if(s+1<=k&&k<=s+w){return node[x].v;} 85 else if(kv){return suc(lc(x),v,node[x].v);}
98 else{return suc(rc(x),v,ans);}
99 }
100 int main()
101 {
102 int i,j,flag,x;
103 cin>>n;node.resize(cap+1000);cap+=1000;
104 for(i=1;i<=n;i++)
105 {
106 scanf("%d%d",&flag,&x);
107 if(flag==1){add(x);}
108 else if(flag==2){remove(x);}
109 else if(flag==3){printf("%d\n",rnk(root,x));}
110 else if(flag==4){printf("%d\n",kth(root,x));}
111 else if(flag==5){printf("%d\n",pre(root,x,0));}
112 else{printf("%d\n",suc(root,x,0));}
113 }
114 return 0;
115 }