《C++實用教程[鄭阿奇主編]16》由會員分享，可在線閱讀，更多相關(guān)《C++實用教程[鄭阿奇主編]16（48頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第16章 標(biāo)準(zhǔn)模板庫（STL）16.1迭代器2021/7/1116.1.1 迭代器的由來n在STL中，迭代器是一種“特殊”的指針，用來指定或引用容器中元素的位置n正是因為對不同容器的操作具有相同的實現(xiàn)代碼，所以才會形成STL的算法器及迭代器以優(yōu)化和簡化算法代碼。2021/7/1216.1.2 迭代器的類型nSTL提供了5種不同的迭代器：輸入、輸出、正向、雙向和隨機訪問迭代器2021/7/13n（1）輸入迭代器。它是一種單向迭代器，只可遞增，不可回退n（2）輸出迭代器。它是一種單向迭代器，只不過它是向容器中寫入元素。n（3）正向迭代器。它是輸入迭代器和輸出迭代器功能的組合，其操作元素總是向前移動

2、（即支持+操作），與輸入迭代器或輸出迭代器不同的是，它多次遍歷的順序都是相同的。n（4）雙向迭代器。它常用于reserse（逆序）等操作，支持指針的+和操作。n（5）隨機訪問迭代器。它具有雙向迭代器的所有功能，同時增加了直接訪問容器中任何元素的功能，即可向前、向后跳過任意多個元素，以及用于對元素排序的關(guān)系運算等2021/7/1416.2 容器類n容器是一個與數(shù)組類似的單元，可以存取若干元素n主要容器類有：deque（雙端隊列）、list（鏈表、列表）、queue（隊列）、stack（棧）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重

3、集合）2021/7/1516.2.1 向量、鏈表和雙端隊列n1.模型概述向量、鏈表和雙端隊列都可以看成是順序存儲的線性表，只是鏈表不像向量和雙端隊列那樣具有隨機訪問的能力n2.deque、list和vectortemplate class T,class Allocator=allocator class vector;template class T,class Allocator=allocator class deque;template class T,class Allocator=allocator class list;2021/7/16n一旦建立了容器類vector、list或

4、deque實例化類對象，就可以通過對象進行下列常用操作n（1）元素的插入操作。用于元素插入操作的成員函數(shù)為insert、push_front和push_backn（2）元素的刪除和清除操作。用于刪除元素操作的成員函數(shù)有erase、pop_front和pop_back，clear用于清除操作n（3）元素訪問操作。容器類vector和deque除了提供下標(biāo)運算符“”來引用指定位置的對象元素的內(nèi)存空間外，還提供下列元素訪問操作n（4）迭代器和空間大小屬性操作。容器類vector、list和deque都提供下列有關(guān)迭代器和空間大小屬性的常用操作n（5）鏈表操作。與容器類vector和deque不同的是

5、，容器類list自身還有不同的常用操作，如反序、排序、合并等2021/7/17例Ex_Vector 向量容器類示例#include#include/向量容器類頭文件包含#include/迭代器頭文件包含#include/算法器頭文件包含usingnamespacestd;/演示iterator操作voidshow(vector&v)if(v.empty()cout該向量容器為空！n;return;vector:iteratorip;/定義指針for(ip=v.begin();ipv.end();ip+)cout*ip,t;coutendl;/演示操作2021/7/18n#includen#in

6、clude/向量容器類頭文件包含n#include/迭代器頭文件包含n#include/算法器頭文件包含nusingnamespacestd;n/演示iterator操作nvoidshow(vector&v)nnif(v.empty()nncout該向量容器為空！n;return;nnvector:iteratorip;/定義指針nfor(ip=v.begin();ipv.end();ip+)ncout*ip,t;ncoutendl;n2021/7/19程序運行結(jié)果如下：2021/7/1104.list示例n例Ex_List鏈表容器類示例。n#includen#include/鏈表容器類頭文件

7、包含n#include/迭代器頭文件包含nusingnamespacestd;n/演示iterator操作nvoidshow(list&v)nnif(v.empty()cout該鏈表為空！n;return;nlist:iteratorip=v.begin();/定義指針nwhile(ip!=v.end()nncout*ip,t;ip+;nncoutendl;n2021/7/111nintmain()nnlistv;nv.push_back(20);v.push_back(40);v.push_back(5);v.push_back(7);nlist:iteratorip=v.begin();n

8、ip=v.insert(ip,13);nv.insert(ip,-7);nshow(v);/輸出所有結(jié)點元素nv.remove(-7);/移除-7結(jié)點nv.reverse();show(v);nv.sort();show(v);nlistl;nl.push_back(12);l.push_back(8);l.push_back(16);l.push_back(7);nv.splice(v.end(),l);nshow(v);show(l);nv.pop_back();v.pop_back();v.pop_back();v.pop_back();nshow(v);nl.push_back(1);

9、l.push_back(8);l.push_back(16);nv.merge(l);nshow(v);show(l);nreturn0;n2021/7/112程序運行結(jié)果如下：2021/7/11316.2.2 棧和隊列n棧（stack）是一種“FILO”（先進后出）或“LIFO”（后進先出）的線性表，它只允許在表的一端進行插入和刪除操作。而隊列（queue）是一種“FIFO”（先進先出）的線性表，與棧剛好相反。在隊列中，只允許在表的一端插入元素，而在另一端刪除元素。n定義對象時，它們都可以有下列簡單的形式：Xv;Xint,vectorv;/使用向量容器來構(gòu)造/注意，vector的最后面是兩個

10、大于符號，它們之間一定要有空格2021/7/114說明:n（1）ANSI/ISOC+類模板stack和deque中都有一個protected數(shù)據(jù)成員c，其定義如下：protected:Containerc;但在VisualC+2005中，該數(shù)據(jù)成員是公有的，因此可以在對象中通過c訪問構(gòu)造時指定的容器類模板的成員。對于VisualC+6.0需要通過派生才能使用該數(shù)據(jù)成員c。n（2）另外，類模板stack和deque還都重載了運算符=、=、=，用于兩個棧或兩個隊列之間的關(guān)系比較。2021/7/115 例Ex_Stack 棧類模板示例。n#includen#include/棧模板頭文件包含n#inc

11、lude/向量容器類頭文件包含n#include/迭代器頭文件包含nusingnamespacestd;ntypedefstackint,vectorSTACK;nclassCStack:publicSTACKnnpublic:nvoidshow()/遍歷操作nnif(empty()cout棧為空！n;return;nvector:iteratorip=c.begin();/定義指針nwhile(ip!=c.end()ncout*ip,t;ip+;ncoutendl;n/清棧操作nvoidclear()nwhile(!empty()pop();n;2021/7/116intmain()CSta

12、ckv;v.push(20);v.push(40);v.push(5);v.push(7);v.show();v.top()=8;v.show();v.pop();v.show();v.clear();v.show();return0;程序運行結(jié)果如下：2021/7/11716.2.3 映像n1.概述n與map概念相同，關(guān)聯(lián)容器類multimap支持的是多對一關(guān)系，即一個鍵對應(yīng)于多個值。map和multimap都支持雙向迭代器，可以實現(xiàn)多路遍歷操作n2.map容器類容器類map具有下列聲明：template class Key,class T,class Compare=less,class

13、Allocator=allocatorpair class map;2021/7/118一旦建立了容器類map的實例化對象，就可以通過實例化類對象進行下列常用操作 n（1）元素的插入操作。需要說明的是，這里操作的元素是指“鍵”和“值”的對子，簡稱鍵值對。在容器類map中，用于元素插入操作的成員函數(shù)為insertn（2）元素的刪除和清除操作。容器類map用于刪除元素操作的成員函數(shù)是erase，用于清除操作的是clearn（3）元素訪問操作。容器類map只提供下標(biāo)運算符“”來引用指定位置元素的內(nèi)存空間n（4）迭代器和空間大小屬性操作。n（5）映像操作n另外，容器類map還重載了運算符=、=、=，用

14、于兩個映像之間的關(guān)系比較2021/7/119 例Ex_Map 映像容器類示例#pragmawarning(disable:4786)/避免string使用中的警告出現(xiàn)#include#include/映像容器類頭文件包含#include/迭代器頭文件包含#include/字符串類頭文件包含usingnamespacestd;typedefmapstring,int,lessSTR2INT;/定義類型名以便后面使用typedefSTR2INT:iteratorPOS;/定義類型名以便后面使用/輸出鍵值對voidshowpair(POSpos)cout主鍵為：(*pos).first,t值為：(*

15、pos).secondendl;/遍歷輸出voidshow(STR2INT&v)if(v.empty()cout(*pEnd).first)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)nshowpair(p);nn/顯示某范圍的鍵值對，演示lower_bound和upper_boundnvoidshowl(STR2INT&v,stringk1,stringk2)nnPOSpFirst,pEnd,p;npFirst=v.lower_bound(k1);npEnd=v.upper_bound(k2);nif(*pFirst).first(*pEnd).f

16、irst)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)nshowpair(p);n2021/7/121nintmain()nnSTR2INTv;n/添加操作nv.insert(STR2INT:value_type(Zero,0);nv.insert(STR2INT:value_type(One,1);nv.insert(STR2INT:value_type(Two,2);nv.insert(STR2INT:value_type(Three,3);nvFour=4;vFive=5;nvSix=6;vSeven=7;nvEight=8;nshow(v);

17、n/刪除操作ncout-endl;nintn=v.erase(Two);ncout共刪除了n個元素！endl;n/查找操作ncout-endl;nPOSpos=v.find(Six);nif(pos!=v.end()showpair(pos);n/顯示某范圍的鍵值對ncout-endl;nshowu(v,Four,Eight);ncout-endl;nshowl(v,Four,Eight);ncout-endl;npairpp=v.equal_range(FIVE);nshowpair(pp.first);nshowpair(pp.second);nreturn0;n2021/7/122程序運

18、行結(jié)果如下：2021/7/12316.2.4 集合n容器類set具有下列聲明：ntemplate class Key,class Compare=less,nclass Allocator=allocator nclass set;2021/7/124 例Ex_Set 集合容器類示例。#pragmawarning(disable:4786)#include#include/映像容器類頭文件包含#include/迭代器頭文件包含#include/字符串類頭文件包含usingnamespacestd;typedefsetstring,lessSTRSET;/定義類型以便后面使用typedefSTR

19、SET:iteratorPOS;/定義類型以便后面使用/遍歷輸出voidshow(STRSET&v)if(v.empty()cout該映像為空！n;return;POSip;/定義指針for(ip=v.begin();ip!=v.end();ip+)cout*ipt;cout(*pEnd)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)ncout*pt;ncout(*pEnd)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)ncout*pt;ncoutendl;n2021/7/126nintmain()nnSTRS

20、ETv;n/添加操作nv.insert(Zero);v.insert(One);v.insert(Two);nv.insert(Three);v.insert(Four);v.insert(Five);nv.insert(Six);nshow(v);n/刪除操作ncout-endl;nintn=v.erase(Two);ncout共刪除了n個元素！endl;n/查找操作ncout-endl;nPOSpos=v.find(Six);nif(pos!=v.end()cout*posendl;n/顯示某范圍的鍵值對ncout-endl;nshowu(v,Two,Five);ncout-endl;ns

21、howl(v,Two,Five);ncout-endl;npairpp=v.equal_range(FIVE);ncout*(pp.first)endl;ncout*(pp.second)endl;nreturn0;n2021/7/127程序運行結(jié)果如下：2021/7/12816.3 算法n16.3.1概述nSTL算法部分主要由頭文件、和組成。n16.3.2copy和流迭代器n1.copyn函數(shù)模板copy將序列中某個范圍的元素復(fù)制到另一個序列中2021/7/129 例Ex_Copy copy函數(shù)使用示例#include#include#include#includeusingnamespac

22、estd;typedefvectorIntVector;intmain()intarr10=2,3,7,8,4,11,5,9,1,13;IntVectorv(8);copy(arr,arr+8,v.begin();ostream_iteratorout(cout,);copy(arr,arr+10,out);coutendl;copy(v.begin(),v.end(),out);coutendl;return0;程序運行結(jié)果如下：2021/7/1302.流迭代器n輸出流迭代器ostream_iterator是STL預(yù)定義的迭代器類模板，它具有下列定義：templateclassT,class

23、charT=char,classtraits=char_traitsclassostream_iterator:publiciteratorpublic:ostream_iterator(ostream_type&s);ostream_iterator(ostream_type&s,constcharT*delimiter);2021/7/13116.3.3 findn函數(shù)模板find用于查找，它的原型如下：ntemplatenInIt find(InIt first,InIt last,const T&value);ntemplate nInIt find_if(InIt first,InI

24、t last,Predicate pred);2021/7/132例Ex_Find find函數(shù)使用示例。#include#include#include#includeusingnamespacestd;typedefvectorIntVector;classUSERDOpublic:booloperator()(inti)/運算符“()”重載函數(shù)return(i5)&(i8);2021/7/133intmain()ostream_iteratorout(cout,);inta=1,3,5,6,6,7,7,7,8,8,8,8;/整數(shù)數(shù)組aconstintANUM=sizeof(a)/size

25、of(int);IntVectorv(a,a+ANUM);/A：構(gòu)造copy(v.begin(),v.end(),out);coutendl;IntVector:iteratorit=find(v.begin(),v.end(),3);/查找整數(shù)3cout找到*it的位置在：it-v.begin()endl;cout-endl;IntVector:iteratorstart=v.begin();do/B：循環(huán)找出所有小于7的數(shù)it=find_if(start,v.end(),bind2nd(less(),7);if(it!=v.end()cout找到*it的位置在：it-v.begin()en

26、dl;start=it+1;while(it!=v.end();cout-endl;start=v.begin();2021/7/134do/C：循環(huán)找出所有大于7的數(shù)it=find_if(start,v.end(),bind2nd(greater(),7);if(it!=v.end()cout找到*it的位置在：it-v.begin()endl;start=it+1;while(it!=v.end();cout-endl;start=v.begin();do/D：循環(huán)找出所有(5,8)的數(shù)it=find_if(start,v.end(),USERDO();/Eif(it!=v.end()co

27、ut找到*it的位置在：it-v.begin()endl;start=it+1;while(it!=v.end();return0;2021/7/135程序運行結(jié)果如下：2021/7/13616.3.4 sortn函數(shù)模板sort用于為指定序列排序，它的原型如下：n/sort,RanIt表示隨機訪問迭代器ntemplaten void sort(RanIt first,RanIt last);ntemplaten void sort(RanIt first,RanIt last,BPred pred);n其功能是將first,last之間的序列按從小到大的升序進行排序2021/7/137 例E

28、x_Sort sort函數(shù)使用示例#include#include#include#includeusingnamespacestd;classC2Predpublic:C2Pred(inta,intb):first(a),second(b)voidshow()cout(first,second)endl;booloperator(constC2Pred&m)constreturnfirstm.first;/按first值從小到大排序friend boolless_second(constC2Pred&m1,constC2Pred&m2)returnm1.secondm2.second;/按s

29、econd值從小到大排序private:intfirst;intsecond;2021/7/138nintmain()nnvectorvect;ninti;nfor(i=0;i5;i+)nC2Predob(10-i,i*3);vect.push_back(ob);nfor(i=0;ivect.size();i+)vecti.show();ncout按first值從小到大排序:endl;nsort(vect.begin(),vect.end();nfor(i=0;ivect.size();i+)vecti.show();ncout按second值從小到大排序:endl;nsort(vect.be

30、gin(),vect.end(),less_second);nfor(i=0;ivect.size();i+)vecti.show();nreturn0;n2021/7/139程序運行結(jié)果如下：2021/7/14016.4 綜合應(yīng)用實例#include#include#include/鏈表類頭文件包含#include/迭代器頭文件包含#include#include#includeusingnamespacestd;classCStudent;ostream&operator(ostream&os,constCStudent&stu);2021/7/141classCStudentpublic

31、:CStudent()CStudent(char*name,char*id,floats1,floats2,floats3);voidprint(intn=-1);char*GetName()returnstrName;friendostream&operator(ostream&os,constCStudent&stu);booloperator(constCStudent&stu)const/重載stu.total;/按total從高到低排序private:charstrName20;/姓名charstrID10;/學(xué)號floatfScore3;/三門課成績floattotal;/總分;C

32、Student:CStudent(char*name,char*id,floats1,floats2,floats3)strncpy(strName,name,20);strncpy(strID,id,10);fScore0=s1;fScore1=s2;fScore2=s3;total=fScore0+fScore1+fScore2;2021/7/142voidCStudent:print(intn)/n為序號，0)coutsetw(6)序號;coutsetw(20)姓名setw(10)學(xué)號setw(10)成績1setw(10)成績2setw(10)成績3setw(10)總分0)coutset

33、w(6)n;coutsetw(20)strNamesetw(10)strIDsetw(10)fScore0setw(10)fScore1setw(10)fScore2setw(10)totalendl;ostream&operator(ostream&os,constCStudent&stu)os.write(stu.strName,20);os.write(stu.strID,10);os.write(char*)stu.fScore,sizeof(stu.fScore);os.write(char*)&stu.total,sizeof(float);returnos;2021/7/143c

34、lassCStuListpublic:voidAdd(CStudentstu);/添加記錄intSeek(char*name,CStudent&stu);/按姓名查找,返回記錄號，-1表示沒有找到voidShowAll();/遍歷列表顯示voidSortToFile(char*filename);/按學(xué)生總成績從高到低排序并寫到文件中private:listtheBuf;/鏈表對象;voidCStuList:Add(CStudentstu)theBuf.push_back(stu);intCStuList:Seek(char*name,CStudent&stu)/按姓名查找intnRec=-1

35、,i=0;list:iteratorip=theBuf.begin();/定義指針while(ip!=theBuf.end()stu=(CStudent)(*ip);if(0=strcmp(stu.GetName(),name)nRec=i;break;ip+;i+;returnnRec;2021/7/144voidCStuList:ShowAll()/遍歷列表顯示list:iteratorip=theBuf.begin();/定義指針inti=0;while(ip!=theBuf.end()ip-print(+i);ip+;voidCStuList:SortToFile(char*filen

36、ame)theBuf.sort();ShowAll();/將排序后的內(nèi)容保存在文件中ofstreamfout(filename);copy(theBuf.begin(),theBuf.end(),ostream_iterator(fout);2021/7/145intmain()CStuListtheStu;CStudentstu1(MaWenTao,99001,88,90,75.5);CStudentstu2(LiMing,99002,92,80,81.5);CStudentstu3(WangFang,99003,89,70,78);CStudentstu4(YangYang,99004,9

37、0,80,90);CStudentstu5(DingNing,99005,80,78,85);theStu.Add(stu1);theStu.Add(stu2);theStu.Add(stu3);theStu.Add(stu4);theStu.Add(stu5);theStu.ShowAll();CStudentstu;intnRec=theStu.Seek(LiMing,stu);if(nRec=0)cout找到的結(jié)果為：endl;stu.print(nRec+1);elsecout沒有找到！endl;cout執(zhí)行SortToFile后的結(jié)果：endl;theStu.SortToFile(student.dat);return0;2021/7/146程序運行結(jié)果如下：2021/7/147 結(jié)束語結(jié)束語若有不當(dāng)之處，請指正，謝謝！若有不當(dāng)之處，請指正，謝謝！