C-程序設計教學課件chapter-6-template-Part2

C++ProgrammingChapter6TemplatesandSTLPartⅡIndex

1.IntroductiontoSTL

2.Containers

2.1SequenceContainers

2.2AssociativeContainers

2.3Containeradapters

3.Iterators

4.Algorithms1.IntroductiontoSTL

TheStandardTemplateLibrary(STL):

AlibraryofstandardtemplatesVerypowerfulVeryfastVeryflexible

Turnsoutyouwon'tactuallyhavetocodeanytemplateclassesyourselfanyway

It'sallbeendoneforyou1.IntroductiontoSTL

Thestandardtemplatelibrary(STL)contains:Containers,Algorithms,andIterators

Acontainerisawaythatstoreddataisorganizedinmemory,forexampleanarrayofelements.

AlgorithmsintheSTLareproceduresthatareappliedtocontainerstoprocesstheirdata,forexamplesearchforanelementinanarray,orsortanarray.

Iteratorsareageneralizationoftheconceptofpointers,theypointtoelementsinacontainer,forexampleyoucanincrementaniteratortopointtothenextelementinanarray1.IntroductiontoSTL

AlgorithmsuseiteratorstointeractwithobjectsstoredincontainersContainerContainerIteratorAlgorithmObjectsIteratorIteratorAlgorithmIteratorAlgorithm2.Containers

Acontainerisawaytostoredata,eitherbuilt-indatatypeslikeintandfloat,orclassobjects.

Threetypesofcontainers:Sequencecontainers,AssociativecontainersandContaineradapters2.1SequenceContainers

Asequencecontainerstoresasetofelementsinsequence,inotherwordseachelement(exceptforthefirstandlastone)isprecededbyonespecificelementandfollowedbyanother,<vector>,<list>and<deque>aresequentialcontainers

InanordinaryC++arraythesizeisfixedandcannotchangeduringrun-time,itisalsotedioustoinsertordeleteelements.Advantage:quickrandomaccess.2.1SequenceContainers

<vector>isanexpandablearraythatcanshrinkorgrowinsize,butstillhasthedisadvantageofinsertingordeletingelementsinthemiddle.

<list>isadoublelinkedlist(eachelementhaspointstoitssuccessorandpredecessor),itisquicktoinsertordeleteelementsbuthasslowrandomaccess.

<deque>isadouble-endedqueue,thatmeansonecaninsertanddeleteelementsfrombothends,itisakindofcombinationbetweenastack(lastinfirstout)andaqueue(firstinfirstout)andconstitutesacompromisebetweena<vector>anda<list>.2.1.1VectorContainerintarray[5]={12,7,9,21,13};vector<int>v(array,array+5);12792113v.pop_back();v.push_back(15);127921127921150123412792115v.begin();v[3]2.1.1VectorContainers#include<vector>#include<iostream>vector<int>v(3);//createavectorofintsofsize3v[0]=23;v[1]=12;v[2]=9;//vectorfullv.push_back(17);//putanewvalueattheendofarrayfor(inti=0;i<v.size();i++)//memberfunctionsize()ofvectorcout<<v[i]<<””;//randomaccesstoi-thelementcout<<endl;2.1.1VectorContainer#include<vector>#include<iostream>intarr[]={12,3,17,8};//standardCarrayvector<int>v(arr,arr+4);//initializevectorwithCarraywhile(!v.empty())//untilvectorisempty{cout<<v.back()<<””;//outputlastelementofvectorv.pop_back();//deletethelastelement}cout<<endl;2.1.2ListContainer

AnSTLlistcontainerisadoublelinkedlist,inwhicheachelementcontainsapointertoitssuccessorandpredecessor.

Itispossibletoaddandremoveelementsfrombothendsofthelist

Listsdonotallowrandomaccessbutareefficienttoinsertnewelementsandtosortandmergelists2.1.2ListContainerintarray[5]={12,7,9,21,13};list<int>li(array,array+5);12792113li.pop_back();li.push_back(15);12792112792115li.pop_front();li.push_front(8);7921812792115li.insert()7121721232.2AssociativeContainers

Anassociativecontainerisnon-sequentialbutusesakeytoaccesselements.Thekeys,typicallyanumberorastring,areusedbythecontainertoarrangethestoredelementsinaspecificorder,forexampleinadictionarytheentriesareorderedalphabetically.2.2AssociativeContainers

A<set>storesanumberofitemswhichcontainkeys.Thekeysaretheattributesusedtoordertheitems,forexampleasetmightstoreobjectsoftheclassPersonwhichareorderedalphabeticallyusingtheirname

A<map>storespairsofobjects:akeyobjectandanassociatedvalueobject.A<map>issomehowsimilartoanarrayexceptinsteadofaccessingitselementswithindexnumbers,youaccessthemwithindicesofanarbitrarytype.

<set>and<map>onlyallowonekeyofeachvalue,whereas<multiset>and<multimap>allowmultipleidenticalkeyvalues.2.3Containeradapters

Thereareafewclassesactingaswrappersaroundothercontainers,adaptingthemtoaspecificinterface

stack–ordinaryLIFO

queue–single-endedFIFO

priority_queue–thesortingcriterioncanbespecified

Programmerscanspecifytheunderlyingdatatype3.Iterators

Iteratorsarepointer-likeentitiesthatareusedtoaccessindividualelementsinacontainer.

Oftentheyareusedtomovesequentiallyfromelementtoelement,aprocesscallediteratingthroughacontainer.vector<int>array_17vector<int>::iterator42312Theiteratorcorrespondingtotheclassvector<int>isofthetypevector<int>::iteratorsize_43.Iterators

Thememberfunctionsbegin()andend()returnaniteratortothefirstandpastthelastelementofacontainer.vector<int>varray_v.begin()1742312v.end()size_43.Iterators

Onecanhavemultipleiteratorspointingtodifferentoridenticalelementsinthecontainervector<int>varray_i1174i22312i3size_43.Iterators#include<vector>#include<iostream>intarr[]={12,3,17,8};//standardCarrayvector<int>v(arr,arr+4);//initializevectorwithCarrayfor(vector<int>::iteratori=v.begin();i!=v.end();i++)//initializeiwithpointertofirstelementofv//i++incrementiterator,moveiteratortonextelement{cout<<*i<<””;//de-referencingiteratorreturnsthe//valueoftheelementtheiteratorpointsat}cout<<endl;3.Iterators#include<vector>#include<iostream>intmax(vector<int>::iteratorstart,vector<int>::iteratorend){intm=*start;while(start!=stop){if(*start>m)m=*start;++start;}returnm;}cout<<”maxofv=”<<max(v.begin(),v.end());3.Iterators

Noteveryiteratorcanbeusedwitheverycontainerforexamplethelistclassprovidesnorandomaccessiterator

Everyalgorithmrequiresaniteratorwithacertainlevelofcapabilityforexampletousethe[]operatoryouneedarandomaccessiterator

Iteratorsaredividedintofivecategoriesinwhichahigher(morespecific)categoryalwayssubsumesalower(moregeneral)category,e.g.Analgorithmthatacceptsaforwarditeratorwillalsoworkwithabidirectionaliteratorandarandomaccessiterator.inputforwardbidirectionalrandomaccessoutput3.Iterators

Containersanditeratorscategories

vector–Randomaccessiterator

deque–Randomaccessiterator

list–Bidirectionaliterator

set,multiset–Bidirectionaliterator,dataisconstant

map,multimap–Bidirectionaliterator,keyisconstant

Containeradapters(stack,queueandpriority_queue)–Donotsupportiterators4.Algorithms

Implementsimple,ornot-so-simpleloopsonranges

copy,find,butalsopartition,sort,next-permutation

Specifytheirneedintermsofiteratorcategories

TheydonotcareabouttheexactclassMustpayattentiontotheiteratorsprovidedbycontainers

Oftenexistinseveralversions

Oneusesdefaultcomparison,user-definedvalueOthercallsuser-providedpredicate,function4.Algorithms

Algorithmsvs.memberfunctions

Algorithmsaresimple,generic.Theyknownothingaboutthecontainerstheyworkontemplate<classInpItor,classUnaryFunc>inlineUnaryFunctionfor_each(InpItorFirst,InpItorLast,UnaryFuncFunc){for(;First!=Last;++First)Func(*First);return(Func);}

Specializedalgorithmsmayhavebetterperformance,thosealgorithmsareimplementedasmemberfunctions.Usememberfunctionswhentheyexisteg.list::sort()vs.sort()4.Algorithms

For_Each()Algorithm#include<vector>#include<algorithm>#include<iostream>voidshow(intn){cout<<n<<””;}intarr[]={12,3,17,8};//standardCarrayvector<int>v(arr,arr+4);//initializevectorwithCarray//list<int>isalsookeyfor_each(v.begin(),v.end(),show);//applyfunctionshow//toeachelementofvectorv4.Algorithms

Find()Algorithm#include<vector>#include<algorithm>#include<iostream>intkey;intarr[]={12,3,17,8,34,56,9};//standardCarrayvector<int>v(arr,arr+7);//initializevectorwithCarrayvector<int>::iteratoriter;cout<<”entervalue:”;cin>>key;iter=find(v.begin(),v.end(),key);//findsintegerkeyinvif(iter!=v.end())//foundtheelementcout<<”Element”<<key<<