NOIP复赛复习10STL容器与字符串模板

NOIP复赛复习10STL容器与字符串模板STL容器STL容器是一些模板类，提供了多种组织数据的常用方法。常用的STL容器包括pair（组合）、list（列表，类似于链表）、vector（向量，类似于数组）、priority_queue（优先队列）、set（集合）、map（映射）、stack（栈）等，通过模板的参数我们可以指定容器中的元素类型。1、pair相当于一个Struct，访问方式举个例子：pairint,intp;那么第一个成员便是p.first、第二个p.second，pair使用起来很方便，简单快速高效，可以当做一个二元struct使用，而且它定义了比较的方法，先根据第一个成员比较，在根据第二个，所以如果你的比较运算符是这样，那么你就不需要定义比较函数了，而struct是不能直接进行比较的，构造pair的方法：make_pair。例：#includecstdio#includealgorithm#includecstring#includeutility#includefunctionalusingnamespacestd;constintN=1010;typedefpairint,intp;pa[N];intmain(){intk=0;a[k++]=p(3,4);a[k++]=p(3,100);a[k++]=p(1,2);a[k++]=p(4,10);sort(a,a+k,greaterp());for(inti=0;ik;i++)printf(%d%d\n,a[i].first,a[i].second);return0;}2、Listlist是一个循环链表。这个容器的特点：快速插入和删除。作用和vector差不多，但内部是用链表实现。这个容器不支持随机访问，你不能[]或者利用通用算法操作，比如说要排序的话你只能利用成员函数比如list.sort()，而且很重要的一点，list的size()函数是线性的，因为是以遍历函数distance实现的。例：HDU5127#includecstdio#includealgorithm#includecstring#includelist#includeutilityusingnamespacestd;typedeflonglongLL;typedefpairLL,LLp;listpl;intmain(){intn;while(scanf(%d,&n),n){l.clear();for(inti=0;in;i++){LLa,b;intt;scanf(%d%I64d%I64d,&t,&a,&b);if(t==1)l.push_back(p(a,b));elseif(t==-1)l.erase(find(l.begin(),l.end(),p(a,b)));else{listp::iteratori=l.begin();LLans=i-first*a+i-second*b;for(++i;i!=l.end();i++)ans=max(ans,i-first*a+i-second*b);printf(%I64d\n,ans);}}}return0;}3、vector相当于一个不定长数组，利用这个你可以添加任意多的元素，容器以连续数组的方式存储元素序列，可以将vector看作是以顺序结构实现的线性表。当我们在程序中需要使用动态数组时，vector将是一个理想的选择。这个完全相当于把一个数组当成一个元素来进行使用了，可以直接相等，赋值操作等。比较经典的使用包括：a、利用vector防止递归爆栈。b、利用vector来实现邻接表。c、利用vector存储空间占用比较大的矩阵。4、priority_queue优先队列其实就是堆，在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先被删除。优先队列具有最高级先出（firstin,largestout）的行为特征。重载有两种方式：直接在struct或者class内部定义；定义比较结构。//内部定义：structnode{intx,y;node(intx=0,inty=0):x(x),y(y){}booloperator(constnode&a)const{returnxa.x;}};priority_queuenodeq;//定义比较结构structnode{intx,y;node(intx=0,inty=0):x(x),y(y){}};structcmp{booloperator()(constnode&a,constnode&b){returna.xb.x;}};priority_queuenode,vectornode,cmpq;priority_queue的应用：贪心例1：POJ2010#includecstdio#includealgorithm#includecstring#includequeueusingnamespacestd;constintN=100010;intl[N],r[N];structcalf{ints,a;}ca[N];boolcmp(calfx,calfy){returnx.sy.s;}intmain(){intn,c,f;scanf(%d%d%d,&n,&c,&f);for(inti=1;i=c;i++)scanf(%d%d,&ca[i].s,&ca[i].a);sort(ca+1,ca+1+c,cmp);n=1;priority_queueintq;intsum=0;for(inti=1;i=n;i++)q.push(ca[i].a),sum+=ca[i].a;l[n]=sum;for(inti=n+1;i=c-n-1;i++){if(ca[i].a=q.top())l[i]=sum;else{sum-=q.top()-ca[i].a;q.pop();q.push(ca[i].a);l[i]=sum;}}sum=0;while(!q.empty())q.pop();for(inti=c;i=c-n+1;i--)q.push(ca[i].a),sum+=ca[i].a;r[c-n+1]=sum;for(inti=c-n;i=n+2;i--){if(ca[i].a=q.top())r[i]=sum;else{sum-=q.top()-ca[i].a;q.pop();q.push(ca[i].a);r[i]=sum;}}intans=-1;for(inti=c-n;i=n+1;i--){if(r[i+1]+l[i-1]+ca[i].a=f){ans=ca[i].s;break;}}printf(%d\n,ans);return0;}priority_queue的应用：加速搜索例2：CSU1780#includecstdio#includecstring#includealgorithm#includevector#includeutility#includequeue#defineINF0x3f3f3f3f#defineLLlonglongusingnamespacestd;structpo{intx,y,w,di;booloperator(constpo&a)const{returnwa.w;}};intn,m,vis[505][505],v[505][505][4];intmaze[510][510],r1,c1,r2,c2,t;charst[5];intdx[]={1,-1,0,0},dy[]={0,0,1,-1};intbfs(){priority_queuepo,vectorpo,greaterpoq;q.push((po){r1,c1,maze[r1][c1],0});memset(vis,0,sizeof(vis));vis[r1][c1]=1;while(!q.empty()){pot=q.top();q.pop();if(t.x==r2&&t.y==c2)returnt.w;for(inti=0;i4;i++){intnx=t.x+dx[i],ny=t.y+dy[i];if(nx1||nxn||ny1||nym||vis[nx][ny]||maze[nx][ny]==-1)continue;q.push((po){nx,ny,t.w+maze[nx][ny],0});vis[nx][ny]=1;}}return-1;}intbfs1(){memset(v,0,sizeof(v));priority_queuepo,vectorpo,greaterpoq;q.push((po){r1,c1,maze[r1][c1],-1});v[r1][c1][0]=v[r1][c1][1]=v[r1][c1][2]=v[r1][c1][3]=1;while(!q.empty()){pot=q.top();q.pop();if(t.x==r2&&t.y==c2)returnt.w;for(inti=0;i4;i++){if(i==t.di)continue;intnx=t.x+dx[i],ny=t.y+dy[i];if(nx1||nxn||ny1||nym||v[nx][ny][i]||maze[nx][ny]==-1)continue;q.push((po){nx,ny,t.w+maze[nx][ny],i});v[nx][ny][i]=1;}}return-1;}intmain(){while(~scanf(%d%d%d%d%d%d,&n,&m,&r1,&c1,&r2,&c2)){memset(maze,-1,sizeof(maze));for(inti=1;i=n;++i)for(intj=1;j=m;++j){scanf(%s,st);if(st[0]!='*')sscanf(st,%d,&maze[i][j]);}printf(Case%d:%d%d\n,++t,bfs(),bfs1());}return0;}5、setset，顾名思义，集合，无重复元素，插入的元素自动按增序排列。内部实现:红黑树，一种平衡的二叉排序树。容器最主要的功能就是判重，也可以进行二分查找。要允许重复元素，选用multiset即可。容器性能：set与map的查找、删除、插入性能都是对数复杂度。没有定义比较方式的元素需要进行重载，重载方式和优先队列一样。set的应用：判重例：UVA11572#includecstdio#includealgorithm#includecstring#includesetusingnamespacestd;inta[1000001];setints;intmain(){intt,n;scanf(%d,&t);while(t--){scanf(%d,&n);for(inti=0;in;i++)scanf(%d,a+i);s.clear();intst=0,en=0,ma=0;while(enn){while(enn&&!s.count(a[en]))s.insert(a[en++]);ma=max(ma,en-st);s.erase(a[st++]);}printf(%d\n,ma);}return0;}6、map这个容器适用于那些需要进行映射（可以根据Key找到对应的Value，作为hash还是不错的），因此map是关联数组。要允许重复元素，使用multimap。map的应用：映射例：HDU4460#includecstdio#includecstring#includestring#includevector#includealgorithm#includemap#includequeueusin