C-程序设计教学课件chapter-6-template-Part2_第1页
C-程序设计教学课件chapter-6-template-Part2_第2页
C-程序设计教学课件chapter-6-template-Part2_第3页
C-程序设计教学课件chapter-6-template-Part2_第4页
C-程序设计教学课件chapter-6-template-Part2_第5页
已阅读5页,还剩25页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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<<

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论