C--程序设计教学课件：chapter-6-template-Part2.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,C+Programming,Chapter6TemplatesandSTL,Part,Index,1.,IntroductiontoSTL,2.Containers,2.1SequenceContainers,2.2AssociativeContainers,2.3Containeradapters,3.Iterators,4.Algorithms,1.IntroductiontoSTL,TheStandardTemplateLibrary(STL):,Alibraryofstandardtemplates,Verypowerful,Veryfast,Veryflexible,Turnsoutyouwontactuallyhavetocodeany,templateclassesyourselfanyway,Itsallbeendoneforyou,1.IntroductiontoSTL,Thestandardtemplatelibrary(STL)contains:,Containers,Algorithms,andIterators,Acontainerisawaythatstoreddataisorganizedin,memory,forexampleanarrayofelements.,AlgorithmsintheSTLareproceduresthatareapplied,tocontainerstoprocesstheirdata,forexamplesearch,foranelementinanarray,orsortanarray.,Iteratorsareageneralizationoftheconceptofpointers,theypointtoelementsinacontainer,forexampleyou,canincrementaniteratortopointtothenextelementin,anarray,1.IntroductiontoSTL,Algorithmsuseiteratorstointeractwithobjects,storedincontainers,Container,Container,Iterator,Algorithm,Objects,Iterator,Iterator,Algorithm,Iterator,Algorithm,2.Containers,Acontainerisawaytostoredata,eitherbuilt-in,datatypeslikeintandfloat,orclassobjects.,Threetypesofcontainers:Sequencecontainers,AssociativecontainersandContaineradapters,2.1SequenceContainers,Asequencecontainerstoresasetofelementsin,sequence,inotherwordseachelement(exceptfor,thefirstandlastone)isprecededbyonespecific,elementandfollowedbyanother,andaresequentialcontainers,InanordinaryC+arraythesizeisfixedandcan,notchangeduringrun-time,itisalsotediousto,insertordeleteelements.Advantage:quick,randomaccess.,2.1SequenceContainers,isanexpandablearraythatcanshrinkor,growinsize,butstillhasthedisadvantageofinserting,ordeletingelementsinthemiddle.,isadoublelinkedlist(eachelementhaspoints,toitssuccessorandpredecessor),itisquicktoinsert,ordeleteelementsbuthasslowrandomaccess.,isadouble-endedqueue,thatmeansonecan,insertanddeleteelementsfrombothends,itisakind,ofcombinationbetweenastack(lastinfirstout)anda,queue(firstinfirstout)andconstitutesacompromise,betweenaanda.,2.1.1VectorContainer,intarray5=12,7,9,21,13;,vectorv(array,array+5);,12,7,9,21,13,v.pop_back();,v.push_back(15);,12,7,9,21,12,7,9,21,15,01234,12,7,9,21,15,v.begin();,v3,2.1.1VectorContainers,#include,#include,vectorv(3);,/createavectorofintsofsize3,v0=23;,v1=12;,v2=9;,/vectorfull,v.push_back(17);,/putanewvalueattheendofarray,for(inti=0;iv.size();i+),/memberfunctionsize()ofvector,coutvi”;,/randomaccesstoi-thelement,coutendl;,2.1.1VectorContainer,#include,#include,intarr=12,3,17,8;,/standardCarray,vectorv(arr,arr+4);,/initializevectorwithCarray,while(!v.empty(),/untilvectorisempty,coutv.back()”;,/outputlastelementofvector,v.pop_back();,/deletethelastelement,coutendl;,2.1.2ListContainer,AnSTLlistcontainerisadoublelinkedlist,in,whicheachelementcontainsapointertoits,successorandpredecessor.,Itispossibletoaddandremoveelementsfrom,bothendsofthelist,Listsdonotallowrandomaccessbutareefficient,toinsertnewelementsandtosortandmergelists,2.1.2ListContainer,intarray5=12,7,9,21,13;,listli(array,array+5);,12,7,9,21,13,li.pop_back();,li.push_back(15);,12,7,9,21,12,7,9,21,15,li.pop_front();,li.push_front(8);,7,9,21,8,12,7,9,21,15,li.insert(),7,12,17,21,23,2.2AssociativeContainers,Anassociativecontainerisnon-sequentialbutuses,akeytoaccesselements.Thekeys,typicallya,numberorastring,areusedbythecontainerto,arrangethestoredelementsinaspecificorder,for,exampleinadictionarytheentriesareordered,alphabetically.,2.2AssociativeContainers,Astoresanumberofitemswhichcontainkeys.,Thekeysaretheattributesusedtoordertheitems,for,exampleasetmightstoreobjectsoftheclassPerson,whichareorderedalphabeticallyusingtheirname,Astorespairsofobjects:akeyobjectandan,associatedvalueobject.Aissomehowsimilar,toanarrayexceptinsteadofaccessingitselements,withindexnumbers,youaccessthemwithindicesof,anarbitrarytype.,andonlyallowonekeyofeachvalue,whereasandallowmultiple,identicalkeyvalues.,2.3Containeradapters,Thereareafewclassesactingaswrappersaround,othercontainers,adaptingthemtoaspecific,interface,stackordinaryLIFO,queuesingle-endedFIFO,priority_queuethesortingcriterioncanbe,specified,Programmerscanspecifytheunderlyingdatatype,3.Iterators,Iteratorsarepointer-likeentitiesthatareusedtoaccess,individualelementsinacontainer.,Oftentheyareusedtomovesequentiallyfromelementto,element,aprocesscallediteratingthroughacontainer.,vector,array_,17,vector:iterator,4,23,12,Theiteratorcorrespondingto,theclassvectorisof,thetypevector:iterator,size_,4,3.Iterators,Thememberfunctionsbegin()andend()returnan,iteratortothefirstandpastthelastelementofa,container.,vectorv,array_,v.begin(),17,4,23,12,v.end(),size_,4,3.Iterators,Onecanhavemultipleiteratorspointingto,differentoridenticalelementsinthecontainer,vectorv,array_,i1,17,4,i2,23,12,i3,size_,4,3.Iterators,#include,#include,intarr=12,3,17,8;,/standardCarray,vectorv(arr,arr+4);,/initializevectorwithCarray,for(vector:iteratori=v.begin();i!=v.end();i+),/initializeiwithpointertofirstelementofv,/i+incrementiterator,moveiteratortonextelement,cout*i”;,/de-referencingiteratorreturnsthe,/valueoftheelementtheiteratorpointsat,coutm),m=*start;,+start;,returnm;,cout”maxofv=”max(v.begin(),v.end();,3.Iterators,Noteveryiteratorcanbeusedwitheverycontainerfor,examplethelistclassprovidesnorandomaccessiterator,Everyalgorithmrequiresaniteratorwithacertainlevelof,capabilityforexampletousetheoperatoryouneeda,randomaccessiterator,Iteratorsaredividedintofivecategoriesinwhichahigher,(morespecific)categoryalwayssubsumesalower(more,general)category,e.g.Analgorithmthatacceptsaforward,iteratorwillalsoworkwithabidirectionaliteratoranda,randomaccessiterator.,input,forward,bidirectional,random,access,output,3.Iterators,Containersanditeratorscategories,vectorRandomaccessiterator,dequeRandomaccessiterator,listBidirectionaliterator,set,multisetBidirectionaliterator,datais,constant,map,multimapBidirectionaliterator,keyis,constant,Containeradapters(stack,queueand,priority_queue)Donotsupportiterators,4.Algorithms,Implementsimple,ornot-so-simpleloopson,ranges,copy,find,butalsopartition,sort,next-,permutation,Specifytheirneedintermsofiteratorcategories,Theydonotcareabouttheexactclass,Mustpayattentiontotheiteratorsprovidedby,containers,Oftenexistinseveralversions,Oneusesdefaultcomparison,user-definedvalue,Othercallsuser-providedpredicate,function,4.Algorithms,Algorithmsvs.memberfunctions,Algorithmsaresimple,generic.Theyknownothing,aboutthecontainerstheyworkon,templateinline,UnaryFunctionfor_each(InpItorFirst,InpItorLast,UnaryFunc,Func),for(;First!=Last;+First)Func(*First);,return(Func);,Specializedalgorithmsmayhavebetterperformance,thosealgorithmsareimplementedasmember,functions.Usememberfunctionswhentheyexist,eg.list:sort()vs.sort(),4.Algorithms,For_Each()Algorithm,#include,#include,#include,voidshow(intn),coutn”;,intarr=12,3,17,8;,/standardCarray,vectorv(arr,arr+4);,/initializevectorwithCarray,/listisalsookey,for_each(v.begin(),v.end(),show);,/applyfunctionshow,/toeachelementofvectorv,4.Algorithms,Find()Algorithm,#include,#include,#include,intkey;,intarr=12,3,17,8,34,56,9;,/standardCarray,vectorv(arr,arr+7);,/initializevectorwithCarray,vector:iteratoriter;,coutkey;,iter=find(v.begin(),v.end(),key);,/findsintegerkeyinv,if(iter!=v.end(),/foundtheelement,cout”Element”key”found”endl;,else,cout”Element”key”notinvectorv”21),intarr=12,3,17,8,34,56,9;,/standardCarray,vectorv(arr,arr+7);,/initializevectorwithCarray,vector:iteratoriter;,iter=find_if(v.begin(),v.end(),mytest);,/findselementinvforwhichmytestistrue,if(iter!=v.end(),/foundtheelement,cout”found”*iterendl;,else,cout”notfound”14),intarr=12,3,17,8,34,56,9;,/standardCarray,vectorv(arr,arr+7);,/initializevectorwithCarray,intn=count_if(v.begin(),v.end(),mytest);,/countselementinvforwhichmytestistrue,cout”found”n”elements”endl;,Somuchforthepart!,