資料課件講義Savitch_ch_18

Overview,18.1Iterators18.2Containers18.3GenericAlgorithms,Slide18-2,18.1,Iterators,Iterators,STLhascontainers,algorithmsandIteratorsContainersholdobjects,allofaspecifiedtypeGenericalgorithmsactonobjectsincontainersIteratorsprovideaccesstoobjectsinthecontainersyethidetheinternalstructureofthecontainer,Slide18-4,UsingDeclarations,Usingdeclarationsallowuseofafunctionornamedefinedinanamespace:usingns:fun();usingns:iterator;usingstd:vector;usingstd:vector:iterator;,Slide18-5,IteratorBasics,AniteratorisageneralizationofpointerNotapointerbutusuallyimplementedusingpointersThepointeroperationsmaybeoverloadedforbehaviorappropriateforthecontainerinternalsTreatingiteratorsaspointerstypicallyisOK.Eachcontainerdefinesanappropriateiteratortype.Operationsareconsistentacrossalliteratortypes.,Slide18-6,BasicIteratorOperations,Basicoperationssharedbyalliteratortypes+(pre-andpostfix)toadvancetothenextdataitem=and!=operatorstotestwhethertwoiteratorspointtothesamedataitem*dereferencingoperatorprovidesdataitemaccessc.begin()returnsaniteratorpointingtothefirstelementofcontainercc.end()returnsaniteratorpointingpastthelastelementofcontainerc.Analogoustothenullpointer.Unlikethenullpointer,youcanapply-totheiteratorreturnedbyc.end()togetaniteratorpointingtolastelementinthecontainer.,Slide18-7,MoreIteratorOperations,-(pre-andpostfix)movestopreviousdataitemAvailabletosomekindsofiterators.*paccessmayberead-onlyorread-writedependingonthecontainerandthedefinitionoftheiteratorp.STLcontainersdefineiteratortypesappropriatetothecontainerinternals.Somecontainersprovideread-onlyiterators,Slide18-8,Display18.1,KindsofIterators,ForwarditeratorsprovidethebasicoperationsBidirectionaliteratorsprovidethebasicoperationsandthe-operators(pre-andpostfix)tomovetothepreviousdataitem.RandomaccessiteratorsprovideThebasicoperationsandIndexingp2returnsthethirdelementinthecontainerIteratorarithmeticp+2returnsaniteratortothethirdelementinthecontainer,Slide18-9,Display18.2(1-2),ConstantandMutableIterators,Categoriesofiteratordivideintoconstantandmutableiterator.ConstantIteratorcpdoesnotallowassigningelementatpusingstd:vector:const_iterator;const_iteratorcp=v.begin();*cp=something;/illegalMutableiteratorpdoesallowchangingtheelementatp.usingstd:vector:iterator;iteratorp=v.begin();*p=something;/OK,Slide18-10,ReverseIterators,Areverseiteratorenablescyclingthroughacontainerfromtheendtothebeginning.Reverseiteratorsreversethemoreusualbehaviorof+andrp-movesthereverseiteratorrptowardsthebeginningofthecontainer.rp+movesthereverseiteratorrptowardstheendofthecontainer.reverse_iteratorrp;for(rp=c.rbegin();rp!=c.rend();rp+)process_item_at(rp);Objectcisacontainerwithbidirectionaliterators,Slide18-11,Display18.3(1-2),OtherKindsofIterators,Twootherkindsof(weaker)iteratorAninputiteratorisaforwarditeratorthatcanbeusedwithinputstreams.Anoutputiteratorisaforwarditeratorthatcanbeusedwithoutputstreams.,Slide18-12,18.2,Containers,Containers,TheSTLprovidesthreekindscontainers:SequentialContainersarecontainerswheretheultimatepositionoftheelementdependsonwhereitwasinserted,notonitsvalue.ContainerAdaptersusethesequentialcontainersforstorage,butmodifytheuserinterfacetostack,queueorotherstructure.AssociativeContainersmaintainthedatainsortedordertoimplementthecontainerspurpose.Thepositiondependsonthevalueoftheelement.,Slide18-14,SequentialContainers,TheSTLsequentialcontainersarethelist,vectoranddeque.(TheslistisnotintheSTL.)Sequentialmeansthecontainerhasafirst,element,asecondelementandsoon.AnSTLlistisadoublylinkedlist.AnSTLvectorisessentiallyanarraywhoseallocatedspacecangrowwhiletheprogramruns.AnSTLdeque(“d-que”or“deck”)isa“doubleendedqueue”.Datacanbeaddedorremovedateitherendandthesizecanchangewhiletheprogramruns.,Slide18-15,Display18.4,Display18.5,CommonContainerMembers,TheSTLsequentialcontainerseachhavedifferentcharacteristics,buttheyallsupportthesemembers:container();/createsemptycontainercontainer();/destroyscontainer,erasesallmembersc.empty()/trueiftherearenoentriesincc.size()const;/numberofentriesincontainercc=v;/replacecontentsofcwithcontentsofv,Slide18-16,MoreCommonContainerMembers,c.swap(other_container);/swapscontentsof/candother_container.c.push_back(item);/appendsitemtocontainercc.begin();/returnsaniteratortothefirst/elementincontainercc.end();/returnsaniteratortoaposition/beyondtheendofthecontainerc.c.rbegin();/returnsaniteratortothelastelement/inthecontainer.Servestoasstartof/reversetraversal.,Slide18-17,MoreCommonContainerMembers,c.rend();/returnsaniteratortoaposition/beyondtheofthecontainer.c.front();/returnsthefirstelementinthe/container(sameas*c.begin();)c.back();/returnsthelastelementinthecontainer/sameas*(-c.end();c.insert(iter,elem);/insertcopyofelementelem/beforeiteIrc.erase(iter);/removeselementiterpointsto,/returnsaniteratortoelement/followingerasure.returnsc.end()if/lastelementisremoved.,Slide18-18,MoreCommonContainerMembers,c.clear();/makescontainercemptyc1=c2/returnstrueifthesizesequaland/correspondingelementsinc1andc2are/equalc1!=c2/returns!(c1=c2)c.push_front(elem)/insertelementelematthe/frontofcontainerc./NOTimplementedforvectorduetolarge/run-timethatresults,Slide18-19,PITFALL:IteratorsandRemovingElements,Removingelementswillinvalidatessomeiterators.erasememberreturnsaniteratorpointingtothenextelementpasttheerasedelement.Withlistweareguaranteedthatonlyiteratorspointingtotheerasedelementareinvalidated.Withvectoranddeque,treatalloperationsthateraseorinsertasinvalidatingpreviousiterators.,Slide18-20,OperationSupport,Slide18-21,(X)Indicatesthisoperationissignificantlyslower.,Display18.6,TheContainerAdaptersstackandqueue,ContainerAdaptersusesequencecontainersforstoragebutsupplyadifferentuserinterface.AstackusesaLast-In-First-Outdiscipline.AqueueusesaFirst-In-First-Outdiscipline.Apriorityqueuekeepsitsitemssortedonapropertyoftheitemscalledthepriority,sothatthehighestpriorityitemisremovedfirst.Thedequeisthedefaultcontainerforbothstackandqueue.Avectorcannotbeusedforaqueueasthequeuerequiresoperationsatthefrontofthecontainer.,Slide18-22,ContainerAdapterstack,Declarations:stacks;/usesdequeasunderlyingstorestackt;/usesthespecified/containerasunderlyingcontainerforstackStacks(sequence_container);/initializesstackto/toelementsinsequence_container.Header:#includeDefinedtypes:value_type,size_typeNoiteratorsaredefined.,Slide18-23,stackMemberFunctions,Slide18-24,Display18.10(1-2),ContainerAdapterqueue,Declarations:queueq;/usesdequeasunderlyingstorequeueq;/usesthespecified/containerasunderlyingcontainerforqueueStacks(sequence_container);/initializesqueueto/toelementsinsequence_container.Header:#includeDefinedtypes:value_type,size_typeNoiteratorsaredefined.,Slide18-25,queueMemberFunctions,Slide18-26,AssociativeContainerssetandmap,Associativecontainerskeepelementssortedonasomepropertyoftheelementcalledthekey.Onlythefirstinsertionofavalueintoasethaseffect.Theorderrelationtobeusedmaybespecified:sets;Thedefaultorderistherelationaloperatorforbothsetandmap.,Slide18-27,ThesetAssociativeContainer,Declarations:sets;/usesdequeasunderlyingstoresets;/usesthespecified/orderrelationtosortelementsintheset/usesDefinedtypes:value_type,size_typeIterators:iterator,const_iterator,reverse_iterator,const_reverse_iterator,Slide18-28,setMemberFunctions,Slide18-29,Display18.12,Themapassociativecontainer,AmapisafunctiongivenasasetoforderedpairsForeachfirstinanorderedpairthereisatmostonevalue,second,thatappearsinanorderedpairinthemap.Firstandsecondcanbedifferentdatatypes,soforexampleyoucouldmapanintegertoastringTheSTLprovidesatemplateclasspairdefinedintheutilityheaderfile.Youmaywishtoreadaboutthemultisetandmultimap.SeeJosuttis,TheC+StandardLibraryAddisonWesley.,Slide18-30,Mapsasassociativearrays,Analternativeinterpretationisthatamapisanassociativearray.Forexample,numbermapc+=5associatestheinteger5withthestringc+TheeasiestwaytoaddandretrievedatafromamapistousetheoperatorHowever,ifyouattempttoaccessmapkeyandkeyisnotalreadyinthemap,thenanewentrywiththedefaultvaluewillbeadded!,Slide18-31,Display18.14(1-2),mapMemberFunctions,Slide18-32,Efficiency,TheSTLwasdesignedwithefficiencyasanimportantconsideration.STLrequirescompliantimplementationstoguaranteeamaximumrunningtime.STLimplementationsstrivetobeoptimallyefficient.SortingisusuallyspecifiedtobeO(N*log(N)whereNisthenumberofitemsbeingsortedSearchisusuallyspecifiedtobeO(log(N)whereNisthenumberofitemsbeingsearched.,Slide18-33,18.3,GenericAlgorithms,GenericAlgorithms,“GenericAlgorithm”areatemplatefunctionsthatuseiteratorsastemplateparameters.ThischapterwilluseGenericAlgorithm,Genericfunction,andSTLfunctiontemplatetomeanthesamething.Functioninterfacespecifiestask,minimumstrengthofiteratorarguments,andprovidesrun-timespecification.,Slide18-35,RunningTimesandBig-ONotation,Tobeuseful,runningtimesforanalgorithmmustspecifytimeasafunctionoftheproblemsize.Wecantimeaprogramwithastopwatchorinstrumentthecodewithcallstothesystemclocktoempiricallydeterminerunningtime.Whatproblemsdoyouseethere?Thereisabetterway.,Slide18-36,Worstcaserunningtime,Intherestofthechapterwewillalwaysmean“worstcaserunningtime”whenwespecifyarunningtime.Howdoweproceed?Dowecount“steps”or“operations”?Whatisastep?Whatisanoperation?Disagreementabounds,butmostlyweagreetocount=,boolfound=false;while(iN)Assumetargetisnotinarray.LooprunsNtimes,6operation