模板库使用NEU-APNIA事业部培训模版简介

一、模板简单介绍 二、STL概 三、STL的组件以及关 四、常用容器介 五、写在后 六、附录：如何选择容 一、模板简单介绍函数模要求：此函数可以接受int、char以及double类型的参数。charcharMaxOfChar(charcNum1,charcNum2{return(cNum1>cNum2)?cNum1:}//用于比较intintMaxOfInt(intiNum1,intiNum2{return(iNum1>iNum2)?iNum1:}doubleMaxOfDouble(doubledNum1,doubledNum2{return(dNum1>dNum2)?dNum1:}charcharMax(charcNum1,charcNum2{return(cNum1>cNum2)?cNum1:}//用于比较intintMax(intiNum1,intiNum2{return(iNum1>iNum2)?iNum1:}doubleMax(doubledNum1,doubledNum2{return(dNum1>dNum2)?dNum1:}C++的实现方式，完全没有必要去记住哪个函数对应哪种数据类型，因为不管是针对哪种数据类型的比较，只需要简单的调用Max()就可temte<classTTMax(constT&Input1,constT&Input2{return(Input1>Input2)?Input1:}甚至任何自定义类型(只要你实现了它的比较运算符operator>)。#defineMax(Input1,Input2)((Input1>Input2)?Input1:Input2temte<classT>————〉TMax(constT&Input1,constT&Input2{return(Input1>Input2)?Input1:}1Inputconst&的，这样做的好处是减少函数调用时候的开销，因为我们不知道T类型到底有多大。类模#define#define0#definetemte<classT>classCVector{CVector():{}unsignedint{return}intpush_back(constT&Element{if(m_Size>MAX_NUM-1{return}DataList[m_Size]=Element;return}intpop_back(T&Element{if(0==m_Size{return}}

Element=DataList[m_Size-1];m_Size--;returnunsignedintTDataList[MAX_NUMTypeList.push_back(Element);TypeList.pop_back(Element);

CVector<TypeName>需要考虑到各种性能和空间的因素，行为也很复杂。不过STL设计的思想正是基于模板。二、STL先进技术与深厚理论的产品。说他是产品也可以，说他是规格也可以，说是软件组件技术发展史上一个让工程师/程序员的心血不至于随时间的推移、人事异动而烟消云散。从副程式(subroutines)、程序(procedures、函数(functions)、类别(classes)，到函数库(functionlibraries、类别库(classlibraries)、各种组件(components)，从结构化设计、模组化设计、物件导向设计，到样式(patterns)STL就是在这个背景下诞生的。STL的价值在两方面。低层次而言，STL带给我们一套急具价值的零组件，这种价值就像MFC对于Windows开发过程所带来的价值一样，直接而。除此之外STL还带给我们一个次的以泛型思维为基础的设计理念。在这个里面，我们只会提到如何使用STL，对于次的三、 的组件以及关 STL六大组件的关系如下图所示：Container通过Allocator取得数据空间，Algorithm通过Itor存Container内容，Functor可以协助Algorithm完成不同的策略变化，Adapter可以修饰或者套接Funtor。四、常用容器介序列式容序列式容器包括：Vector、List、Queue、Stack等。Vector基本结Vectr是说你完全可以不必关心你到底向这个数组里面添加了多少个元素，继续添加就对了（当然内存耗尽。实际上，Vector的实现就像文章开头所举的例子一样，在初始化的时候，会申请一定的空间用来数vector<int>iv(1)00110iv.size()==iv.capacity()==012iv.size()==3；iv.capacity()==4;可以观察到，VectorPush操Vector的一个策略，前面提到过，Vector的空间是连续的，而连续空间的申请和释放操作都相当耗Vector的常用成员函构造函数Example：vector<int>vector（SizeTypecountExample:vector<int>iv(3);vector（SizeTypecount，ConstType&ValExample:vector<int>iv(3,2);vector（const_vector&SourceVectorExample：vector<int>vector<int>iv2(iv1其他成员函referenceat（size_typePosExample：vector<int>iv.push_back(1iv.push_back(2iv.push_back(3referenceExample：vector<int>iv;iv.push_back(1iv.push_back(2iv.push_back(3 tor说明：返回Vector初始位置的迭代器(i Example：vector<int>iv;iv.push_back(1iv.push_back(2iv.push_back(3 torItiv.begin();inti=*It;//i的值应该是1，2Vector来讲，它的迭代器在使用的时候完全可以等同于一般的指针。Example：vector<int>iv.push_back(1iv.push_back(2iv.push_back(3voidExample：vector<int>iv.push_back(iv.push_back(1iv.push_back(2intiSizeiv.size()iSizeboolExample：vector<int>iv.push_back(1); torExample：vector<int>iv;iv.push_back(1iv.push_back(2//循环整个for( torit=iv.begin();it!=iv.end();++it{Do} torerase（ torWhere torerase（ torFirst， torLast-”Example：vector<int>iv.push_back(1iv.push_back(2iv.push_back(3iv.eraseiv.begin1删除元素iv.eraseiv.beginiv.begin2删除元素“1”和erase的参数Where和First、Last必须在[begin(),end()]范围之内，否则会发生的错Example：vector<int>iv;iv.push_back(1iv.push_back(2iv.push_back(iv.push_back(3inti=iv.fronti torinsert（i torWhereconstType&Val）Example：vector<int>iv.push_back(1insert的位置必须在[begin(),end()]范围之内，否则会发生的错误voidpush_back(constType&ValvoidExample：vector<int>iv.push_back(1iv.push_back(2iv.pop_back();//此时元素为1，2size_typesize()referenceoperator[](size_typePos)Example：vector<int>iv;iv.push_back(1iv.push_back(2iv.push_back(3//iv[0]=1，iv[1]=2,iv[2]=1、operator[]只能用来取得已经存在的元素，而不能向vector中添加元素，例如下面的代码是错误vector<int>iv01;//错误，vector的空间还没有被分2、operator[]和正常数组的使用方法一样，也同样没有越界检查，比如你通过iv[10]的方式一个只有1个元素的vector，不会被提示出错，但这样做可能会有不可预计的事情发生。Vector综合示例#include<stdlib.h>#include<time.h>#include<vector>classCDataSet{staticenum{ALLDATA= t:随机数的个数iMaxData:CDataSet(unsigned t,unsignedintiMaxData t{srand((unsigned)time(NULL)for(intiLoop=0;iLoop t;++iLoop{m_DataList.push_back((unsignedint)rand()%iMaxData}}int{ t=vector<int torfor(it=m_DataList.begin();it!=m_DataList.end();++it{if(m_bIsPrimeData(*it){}} }voidPrint(ePrintRangeiPrintRange){switch(iPrintRange{case{}case{}{}}}//boolIsPrimeData(unsignedintiDataIndex{if(iDataIndex t{return}returnm_bIsPrimeData(m_DataList[iDataIndex]}//boolm_bIsPrimeData(intiInputData){for(intiLoop=2;iLoop<iInputData;++iLoop{if(0==iInputData%iLoop{}}return((iLoop==iInputData)&&(iLoop!=1)}voidm_PrintAllData(){cout<<"AllDataList:"<<for(intiLoop=0;iLoop t;++iLoop{cout<<m_DataList[iLoop]<<}cout<<}voidm_PrintPrimeData(){cout<<"PrimeDataList:"<<for(intiLoop=0;iLoop t;++iLoop{if(m_bIsPrimeData(m_DataList[iLoop]){cout<<m_DataList[iLoop]<<}}cout<<}vector<int>m_DataList; void{CDataSetDataList(10,100);}们预想的并不一致，甚至可能造成程序的！这是为什么呢？问题处在DeletePrimeData（）这个函数，看for(it=m_DataList.begin();it!=m_DataList.end();++it{if(m_bIsPrimeData(*it){}} 777 tor为7果这种问题发生在Vector的尾部的话，就可能造成内存的而引起程序的。那这个问题该怎么解void{vector<int>TempList;vector<int>::i for(it=m_DataList.begin();it!=m_DataList.end();++it{if(!m_bIsPrimeData(*it){}}t=}Vector中的元素清空并用新Vector的元素进行重新填充(m_DataList.assign(TempList.begin(),TempList.end());)。这样做既可以避免在循环中删除元素带来的Itor，有可以在一定程度上提高效率List的基本相对于Vector的线性空间，List就复杂的多，它每次添加或者删除一个元素，就会申请或者释放一于元素的插入和删除，List都是常数时间。temte<classT>struct_list_node{ } list<int>il;for(intiLoop=0;iLoop<5;++iLoop{il.push_back(iLoop}List之后list<intilListil.begin()==List常用构造函Example:list<int>list(size_typeCountExample:list<int>il(3);list(size_typecount,constType&_ValExample:list<int>il(3,5)list(constlist&SourceListExample:list<int>SourceList(3,5)list<int>il(SourceList);其它常用成begin（clear（empty（绍一些不同于Vector的方法：voidmerge（list<Type,Allocator>&List2递增的方式排序，Copy之后，将List2中的所有元素清空。list<int>List1;list<int>List2;List1.push_back(1List1.push_back(3List1.push_back(5List2.push_back(2List2.push_back(4List1.merge(List2);调用Merge之前，List1:1,3, List2:2,4,调用Merge之后，List1:1,2,3,4,5, List2:请注意，调用Merge之前，必须保证两个List都是完全排序的，不然会产生一个比较的结果，而一般情况下，这种情况并不是用户的本意（产生这种结果的原因可参考Merge的实现方法。如果是针对用户自定义类型的List，在使用这个函数之前，还要保证实现了operator<。voidlist<int>il; //List中元素为:2voidpush_front(constType&_Val说明：向List的首位插入一个元素。list<int>il;voidlist<int>il;il.push_back(3il.push_back(1il.push_back(2List3，1，2il.sort();//List中的元素：1，2，3List的综合示例到此类的末尾位置。分析：每种都有自己的种类，并且每类按照次序存放，说明原有的顺序不应该被打乱，并且这ListList#include<iostream>#include<list>usingnamespace#defineNOINDEX enumeBookKind{ = =COMPUTER =ENGLISH+1, =CHEMISTRY+1,ALLBOOKKIND=PHYSICS+1,struct{booloperator==(constBook_t&_Right){return(iBookKind==_Right.iBookKind} iBookKind;//Book iBookIndex;//Book在一类中的位static t[ALLBOOKKIND];//静态成员，表示每种的数 t[ALLBOOKKIND]={2,1,2,1voidPrint(list<Book_t>StudentList{list<Book_t torfor(it=StudentList.begin();it!=StudentList.end();++it{cout<<it->iBookKind<<"\t"<<it->iBookIndex<<}}list<Book_t torSeek(list<Book_t torit, t{for(intiLoop=0;iLoop t;++iLoop{}return}void{//现有constBook_tBookList[]{ CHEMISTRY, //将现有插入书list<Book_t BookCase(BookList,BookList+sizeof(BookList)/sizeof(Book_t)//constBook_tNewBookList[]{COMPUTER,NOINDEX,CHEMISTRY,NOINDEX,ENGLISH,NOINDEX,PHYSICS,NOINDEX,COMPUTER,NOINDEX,PHYSICS,NOINDEX t=sizeof(NewBookList)/sizeof(Book_tlist<Book_t>::i for(intiLoop=0;iLoop t;++iLoop{stTempBook=NewBookList[iLoop//找到相同种类的第一个位置，在这里默认为每种都存在至少一本it=find(BookCase.begin(),BookCase.end(),stTempBook//更新新插入的书在此类位 //指针偏移到下一类书的开头并将新书插入(因为插入操作是前插入)it=Seek(it, t[it->iBookKind]++);BookCase.insert(it,stTempBook);}}关联式容（alue黑树(RB-Tree)，因为树提供了很好的搜索效率。（Key，Set元素中的实值就是键值，键值就是实值；Set不允许两个元素拥有相同的键值。常用构造函set<int>set(const_set&_Rightset<int>is1;is1.insert(0);is1.insert(1set<int>is2(is1其他成员函Size_typecount(constkey&_Key)所以此返回值只有1和0两种情况。set<int>is.insert(1is.insert(1intiCnt=is.count(1) t=1iCnt=is.count(2); t=0pair< tor, tor equal_range(constKey&_Key于_Key的迭代子，second为Key值大于_Key的迭代子。set<int>pair<set<int tor,set<int tor>is.insert(0is.insert(1is.insert(2Ret=is.equal_range(1Ret=is.equal_range(2);//*Ret.first=2;Ret.second= torfind(constKey&_Keyfind（）find（）方法的容器最好使用自带的方法，因为通用的find（）没有针对容器做过优化，在效率方面劣于自带的方法。set<int>is;is.insert(0is.insert(1is.insert(2if(is.find(1)!=is.end(){Do}pair< tor,bool>insert( value_type&Value变量指向原元素存在的位置；如果插入元素的key不存在，则bool值为true,返回新插入元素的迭代子。set<int>pair<set<int tor,bool>Ret=is.insert(1);//ret.second=trueRet=is.insert(2);//ret.second=trueRet=is.insert(1);//ret.second=false p()set<int,lessintis1;//set<int,less<int>> parekcl1= boolb=kcl1(1,2);//b=trueset<int,greater<intis2set<int,greater<int>> parekcl2= b=kcl2(1,2); //b=false p() itorlower_bound(constKey&_Key)说明：返回大于或者等于_Key的第一个元素的迭代子set<int>is;is.insert(0is.insert(1is.insert(3inti=*(is.lower_bound(1));//i=1i=*(is.lower_bound(2));//i=3 torupper_boundconstKey&_Key说明：返回大于_Key的第一个元素的迭代子set<int>is;is.insert(0is.insert(1is.insert(3inti=*(is.up_bound(1));//i*isup_bound3i=3存在Key值相同的元素。下面介绍几个multiset常用的方法size_typecount(constKey&_Key)数multiset<int>is;is.insert(0);is.insert(1is.insert(1is.insert(2intiCnt=is.count(1); t=2iCnt=is.count(2); t=1SetMultiSet的综合示例户选择的号码不存在的时候返回相应的信息。用户可以随时按照号码从小到大的顺序查看所有的情set#include<iostream>#include<set>#include<stdlib.h>#include<time.h>usingnamespace#defineRANDOM enumeReturnCode{SUCCESS=WRONG_NUMBER=SUCCESS+1,NUMBER_EXIST=WRONG_NUMBER+1,ALLNUMBER_EXIST=NUMBER_EXIST+1struct{friendbooloperator<(constLottery_t&_Left,constLottery_t&_Right{return(_Left.iLotteryNum<_Right.iLotteryNum}//号int// class{CLotteryProduction():m_MaxNum(10{srand((unsigned)time(NULL)}eReturnCodeBuyLottery(Lottery_tintiLotteryNum=RANDOM, t=1){//if(m_LotteryList.size()==m_MaxNum+1{return}//if((iLotteryNum>m_MaxNum)||(iLotteryNum<0){return}Lottery_tstLotteryForEntry;if(RANDOM==iLotteryNum){//产生一个随机号码,for(;;{ t= pair<set<Lottery_t tor,bool>Retm_LotteryList.insert(stLotteryForEntryif(Ret.second{}}{

}//按照用户选择的号码生成 t= pair<set<Lottery_t>::i tor,bool>Ret=m_LotteryList.insert(stLotteryForEntryif(Ret.second{return}}*pLottery=return}voidDisy(){set<Lottery_t torcout<<"LotteryNo\t"<< t"<<for(it=m_LotteryList.begin();it!=m_LotteryList.end();++it{cout<<it->iLotteryNum<<"\t"<<it- t<<}}intGetRandomNum(){return(rand()%(m_MaxNum+1)}set<Lottery_t>m_LotteryList;constint void{eReturnCodeRet;for(;;{Lottery_t//一if(ALLNUMBER_EXIST==Ret){}}//显示的信}Map的特性是，所有元素都会根据元素的键值自动被排序。Mappair（Keymap<int,constchar*>map(constmap&_Rightmap<int,constchar*>MemberList1;MemberList1.insert(make_pair(0,“Mike”));map<int,constchar*>MemberList2(MemberList1其它常用成 torfind(constKey&_Keymap<int,constchar*>MemberList1;MemberList1.insert(make_pair(0,“Mike”));MemberList1.insert(make_pair(1,“Tom”));pair< tor,bool>insert(constvalue_type&_Val说明：插入一个元素，如果此元素不存在，返回值pair中的booltrue,false，pair中的first表map<int,string>typedefmap<int,string>::i torMapIt;pair<MapIt,bool>Ret;Ret=MemberList1.insert(make_pair(0,string(“Mike”))//此时*Ret.first0,“MikeRet.secondRet=MemberList1.insert(make_pair(1,string(“Tom”))//此时*Ret.first1,“TomRet.secondRet=MemberList1.insert(make_pair(1,string(“Mary”))//此时*Ret.first1,“Tom”Ret.second p()map<int,string>MemberList;map<int,string> parekcl;kcl= boolb=kcl(1,2);//b=trueb=kcl(2,1);//b=false; p()此函数实际上还是通过比较两个元素的Key值来确定它们的位置关系。map<int,string>typedefmap<int,string> Pvcl=MemberList. boolb=vcl(make_pair(0,string(“Mike”)),make_pair(1,string(“Tom”))//bb=vcl(make_pair(1,string(“Tom”)make_pair(0,string(“Mike”))//bType&operator[]（constKey&_Key说明：在map<int,string>MemberList.insert(make_pair(0,string(“Mike”)));MemberList.insert(make_pair(1,string(“Tom”))map<int,string>::i torit;it=MemberList.find(1);MemberList[it->first]=multimapmap的示例分析：这个题目中要求进行排序，并且能够随时改变排序的方式，所以应该选择map或者multimap，这样改变排序方式应该更容易一些。同时，考虑到学生的属性（身高、体重和）有可能一致，所以我们multimap。#include<iostream>#include<map>usingnamespacestd;enum{ =0,QUEUE_BY_WEIGHT=QUEUE_BY_HIGH+1,QUEUE_BY_AGE=QUEUE_BY_WEIGHT+1,struct{friendbooloperator>(constStudent_t&_Left,constStudent_t&_Right{return(_Left.iHigh>_Right.iHigh}intiHigh;intiAge;class{构造函数, m_QueueKind(QueueKind){}//voidInsertStudent(constStudent_t*pInputList, t{switch(m_QueueKind{caseInsertByHigh(pInputList, caseInsertByWeight(pInputList, caseInsertByAge(pInputList, }}voidDisy(){cout<<"High\t"<<"Weight\t"<<"Age"<<endl;multimap<int,Student_t,greater<int>>::const_i torit;for(it=m_StudentList.begin();it!=m_Stude