vector总结

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

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

vector中迭代器的声明：vector<int>::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完全可以替代邻接表：定义vector<int>G[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<bits/stdc++.h>

 2 using namespace std;

 3 vector<int>node;

 4 int n;

 5 int main()

 6 {

 7     int i,j,flag,x;

 8     vector<int>::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<bits/stdc++.h>

  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 vector<dot>node;

 10 stack<int>s;

 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:v<node[x].v?0:1;}

 14 int get_min(int x){while(lc(x)){x=lc(x);}return x;}

 15 int get_max(int x){while(rc(x)){x=rc(x);}return x;}

 16 int search(int x,int v)

 17 {

 18     if(!x){return 0;}

 19     int d=cmp(x,v);

 20     if(d==-1){return x;}

 21     return search(node[x].ch[d],v);

 22 }

 23 void rotate(int x,int d)

 24 {

 25     int k=fa(x);

 26     node[k].ch[d^1]=node[x].ch[d];if(node[x].ch[d]){fa(node[x].ch[d])=k;}

 27     fa(x)=fa(k);if(fa(k)){int d2=cmp(fa(k),node[k].v);node[fa(k)].ch[d2]=x;}

 28     fa(k)=x;node[x].ch[d]=k;maintain(k);

 29 }

 30 void splay(int x)

 31 {

 32     int y,p,d,d2;

 33     while(fa(x))

 34     {

 35         y=fa(x);p=fa(y);d=cmp(y,node[x].v);

 36         if(!p){rotate(x,d^1);break;}

 37         d2=cmp(p,node[y].v);

 38         if(d^d2){rotate(x,d^1);rotate(x,d2^1);}

 39         else{rotate(y,d2^1);rotate(x,d^1);}

 40     }

 41     root=x;maintain(x);

 42 }

 43 int find(int x,int v)

 44 {

 45     int p=search(x,v);if(!p){return 0;}

 46     splay(p);return p;

 47 }

 48 int insert(int x,int v,int f)

 49 {

 50     if(!x)

 51     {

 52         if(!s.empty()){x=s.top();s.pop();node[x]=(dot){0,0,v,1,1,f};}

 53         else{x=new_node(v,f);}

 54         return x;

 55     }

 56     int d=cmp(x,v);

 57     if(d==-1){node[x].w++;return x;}

 58     int p=insert(node[x].ch[d],v,x);maintain(x);

 59     return p;

 60 }

 61 void add(int v){int p=insert(root,v,0);splay(p);}

 62 int merge(int x,int y)

 63 {

 64     if(!x){return y;}if(!y){return x;}

 65     int p=get_max(x);splay(p);

 66     fa(y)=p;rc(p)=y;

 67     maintain(p);return p;

 68 }

 69 void remove(int v)

 70 {

 71     int x=find(root,v);if(!x){return;}

 72     if(node[x].w>1){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(k<s+1){return kth(lc(x),k);}

 86     else{return kth(rc(x),k-s-w);}

 87 }

 88 int pre(int x,int v,int ans)

 89 {

 90     if(!x){return ans;}

 91     if(node[x].v<v){return pre(rc(x),v,node[x].v);}

 92     else{return pre(lc(x),v,ans);}

 93 }

 94 int suc(int x,int v,int ans)

 95 {

 96     if(!x){return ans;}

 97     if(node[x].v>v){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 }

巴特西