第16章 標準模板庫（STL）16.1 迭代器16.1.1 迭代器的由來n在STL中，迭代器是一種“特殊”的指針，用來指定或引用容器中元素的位置 n正是因為對不同容器的操作具有相同的實現(xiàn)代碼，所以才會形成STL的算法器及迭代器以優(yōu)化和簡化算法代碼。16.1.2 迭代器的類型nSTL提供了5種不同的迭代器：輸入、輸出、正向、雙向和隨機訪問迭代器 n（1）輸入迭代器。它是一種單向迭代器，只可遞增，不可回退 n（2）輸出迭代器。它是一種單向迭代器，只不過它是向容器中寫入元素。n（3）正向迭代器。它是輸入迭代器和輸出迭代器功能的組合，其操作元素總是向前移動（即支持+操作），與輸入迭代器或輸出迭代器不同的是，它多次遍歷的順序都是相同的。n（4）雙向迭代器。它常用于reserse（逆序）等操作，支持指針的+和操作。n（5）隨機訪問迭代器。它具有雙向迭代器的所有功能，同時增加了直接訪問容器中任何元素的功能，即可向前、向后跳過任意多個元素，以及用于對元素排序的關系運算等 16.2 容器類n容器是一個與數(shù)組類似的單元，可以存取若干元素 n主要容器類有：deque（雙端隊列）、list（鏈表、列表）、queue（隊列）、stack（棧）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重集合）16.2.1 向量、鏈表和雙端隊列n1.模型概述向量、鏈表和雙端隊列都可以看成是順序存儲的線性表，只是鏈表不像向量和雙端隊列那樣具有隨機訪問的能力 n2.deque、list和vectortemplate class T,class Allocator=template class T,class Allocator=allocator allocator class vector class vector;template class T,class Allocator=template class T,class Allocator=allocator allocator class deque class deque;template class T,class Allocator=template class T,class Allocator=allocator allocator class list class list;n一旦建立了容器類vector、list或deque實例化類對象，就可以通過對象進行下列常用操作 n（1）元素的插入操作。用于元素插入操作的成員函數(shù)為insert、push_front和push_back n（2）元素的刪除和清除操作。用于刪除元素操作的成員函數(shù)有erase、pop_front和pop_ back，clear用于清除操作 n（3）元素訪問操作。容器類vector和deque除了提供下標運算符“”來引用指定位置的對象元素的內(nèi)存空間外，還提供下列元素訪問操作 n（4）迭代器和空間大小屬性操作。容器類vector、list和deque都提供下列有關迭代器和空間大小屬性的常用操作 n（5）鏈表操作。與容器類vector和deque不同的是，容器類list自身還有不同的常用操作，如反序、排序、合并等 例Ex_Vector 向量容器類示例#include#include/向量容器類頭文件包含#include/迭代器頭文件包含#include/算法器頭文件包含using namespace std;/演示iterator操作void show(vector&v)if(v.empty()cout該向量容器為空！n;return;vector:iterator ip;/定義指針for(ip=v.begin();ipv.end();ip+)cout*ip,t;coutendl;/演示操作n#include n#include/向量容器類頭文件包含n#include/迭代器頭文件包含n#include/算法器頭文件包含nusing namespace std;n/演示iterator操作nvoid show(vector&v)nnif(v.empty()nncout該向量容器為空！n;return;nnvector:iterator ip;/定義指針nfor(ip=v.begin();ipv.end();ip+)ncout*ip,t;ncoutendl;n程序運行結果如下：4.list示例n例Ex_List 鏈表容器類示例。n#include n#include/鏈表容器類頭文件包含n#include/迭代器頭文件包含nusing namespace std;n/演示iterator操作nvoid show(list&v)nnif(v.empty()cout該鏈表為空！n;return;nlist:iterator ip=v.begin();/定義指針nwhile(ip!=v.end()nncout*ip,t;ip+;nncoutendl;nnint main()nnlist v;nv.push_back(20);v.push_back(40);v.push_back(5);v.push_back(7);nlist:iterator ip=v.begin();nip=v.insert(ip,13);nv.insert(ip,-7);nshow(v);/輸出所有結點元素nv.remove(-7);/移除-7結點nv.reverse();show(v);nv.sort();show(v);nlist l;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);l.push_back(8);l.push_back(16);nv.merge(l);nshow(v);show(l);nreturn 0;n程序運行結果如下：16.2.2 棧和隊列n棧（stack）是一種“FILO”（先進后出）或“LIFO”（后進先出）的線性表，它只允許在表的一端進行插入和刪除操作。而隊列（queue）是一種“FIFO”（先進先出）的線性表，與棧剛好相反。在隊列中，只允許在表的一端插入元素，而在另一端刪除元素。n定義對象時，它們都可以有下列簡單的形式：X v;X int,vector v;/使用向量容器來構造/注意，vector的最后面是兩個大于符號，它們之間一定要有空格說明:n（1）ANSI/ISO C+類模板stack和deque中都有一個protected數(shù)據(jù)成員c，其定義如下：protected:Container c;但在Visual C+2005中，該數(shù)據(jù)成員是公有的，因此可以在對象中通過c訪問構造時指定的容器類模板的成員。對于Visual C+6.0需要通過派生才能使用該數(shù)據(jù)成員c。n（2）另外，類模板stack和deque還都重載了運算符=、=、=，用于兩個棧或兩個隊列之間的關系比較。例Ex_Stack 棧類模板示例。n#include n#include/棧模板頭文件包含n#include/向量容器類頭文件包含n#include/迭代器頭文件包含nusing namespace std;ntypedef stackint,vector STACK;nclass CStack:public STACKnnpublic:nvoid show()/遍歷操作nnif(empty()cout棧為空！n;return;nvector:iterator ip=c.begin();/定義指針nwhile(ip!=c.end()ncout*ip,t;ip+;ncoutendl;n/清棧操作nvoid clear()nwhile(!empty()pop();n;int main()CStack v;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();return 0;程序運行結果如下：16.2.3 映像n1.概述n與map概念相同，關聯(lián)容器類multimapmultimap支持的是多對一關系，即一個鍵對應于多個值。map和multimap都支持雙向迭代器，可以實現(xiàn)多路遍歷操作 n2.map容器類容器類map具有下列聲明：template class Key,class T,class Compare=template class Key,class T,class Compare=less,less,class Allocator=class Allocator=allocatorpair allocatorpair class mapclass map;一旦建立了容器類map的實例化對象，就可以通過實例化類對象進行下列常用操作 n（1）元素的插入操作。需要說明的是，這里操作的元素是指“鍵”和“值”的對子，簡稱鍵值對。在容器類map中，用于元素插入操作的成員函數(shù)為insert n（2）元素的刪除和清除操作。容器類map用于刪除元素操作的成員函數(shù)是erase，用于清除操作的是clear n（3）元素訪問操作。容器類map只提供下標運算符“”來引用指定位置元素的內(nèi)存空間 n（4）迭代器和空間大小屬性操作。n（5）映像操作 n另外，容器類map還重載了運算符=、=、=，用于兩個映像之間的關系比較 例Ex_Map 映像容器類示例#pragma warning(disable:4786)/避免string使用中的警告出現(xiàn)#include#include/映像容器類頭文件包含#include/迭代器頭文件包含#include/字符串類頭文件包含using namespace std;typedefmapstring,int,less STR2INT;/定義類型名以便后面使用typedefSTR2INT:iterator POS;/定義類型名以便后面使用/輸出鍵值對void showpair(POS pos)cout主鍵為：(*pos).first,t值為：(*pos).secondendl;/遍歷輸出void show(STR2INT&v)if(v.empty()cout(*pEnd).first)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)nshowpair(p);nn/顯示某范圍的鍵值對，演示lower_bound和upper_boundnvoid showl(STR2INT&v,string k1,string k2)nnPOS pFirst,pEnd,p;npFirst=v.lower_bound(k1);npEnd=v.upper_bound(k2);nif(*pFirst).first (*pEnd).first)nswap(pFirst,pEnd);nfor(p=pFirst;p!=pEnd;p+)nshowpair(p);nnint main()nnSTR2INT v;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);n/刪除操作ncout-endl;nint n=v.erase(Two);ncout共刪除了 n 個元素！endl;n/查找操作ncout-endl;nPOS pos=v.find(Six);nif(pos!=v.end()showpair(pos);n/顯示某范圍的鍵值對ncout-endl;nshowu(v,Four,Eight);ncout-endl;nshowl(v,Four,Eight);ncout-endl;npair pp=v.equal_range(FIVE);nshowpair(pp.first);nshowpair(pp.second);nreturn 0;n程序運行結果如下：16.2.4 集合n容器類set具有下列聲明：ntemplate class Key,class Compare=template class Key,class Compare=less,less,nclass Allocator=class Allocator=allocator allocator nclass set;class set;25可編輯 例Ex_Set 集合容器類示例。#pragma warning(disable:4786)#include#include/映像容器類頭文件包含#include/迭代器頭文件包含#include/字符串類頭文件包含using namespace std;typedefsetstring,less STRSET;/定義類型以便后面使用typedefSTRSET:iteratorPOS;/定義類型以便后面使用/遍歷輸出void show(STRSET&v)if(v.empty()cout該映像為空！n;return;POS ip;/定義指針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;nnint main()nnSTRSET v;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;nint n=v.erase(Two);ncout共刪除了 n 個元素！endl;n/查找操作ncout-endl;nPOS pos=v.find(Six);nif(pos!=v.end()cout*posendl;n/顯示某范圍的鍵值對ncout-endl;nshowu(v,Two,Five);ncout-endl;nshowl(v,Two,Five);ncout-endl;npair pp=v.equal_range(FIVE);ncout*(pp.first)endl;ncout*(pp.second)endl;nreturn 0;n程序運行結果如下：16.3 算法n16.3.1 概述nSTL算法部分主要由頭文件、和組成。n16.3.2 copy和流迭代器n1.copyn函數(shù)模板copy將序列中某個范圍的元素復制到另一個序列中 例Ex_Copy copy函數(shù)使用示例#include#include#include#include using namespace std;typedef vector IntVector;int main()int arr10=2,3,7,8,4,11,5,9,1,13 ;IntVector v(8);copy(arr,arr+8,v.begin();copy(arr,arr+8,v.begin();ostream_iterator out(cout,);copy(arr,arr+10,out);copy(arr,arr+10,out);cout endl;copy(v.begin(),v.end(),out);copy(v.begin(),v.end(),out);cout endl;return 0;程序運行結果如下：2.流迭代器n輸出流迭代器ostream_iterator是STL預定義的迭代器類模板，它具有下列定義：template class T,class charT=char,class traits=char_traits class ostream_iteratorostream_iterator:public iterator public:ostream_iterator(ostream_type&s);ostream_iterator(ostream_type&s,const charT*delimiter);16.3.3 findn函數(shù)模板find用于查找，它的原型如下：ntemplatetemplatenInIt find(InItInIt find(InIt first,InIt,InIt last,const T&const T&value););ntemplate template nInIt find_if(InItInIt find_if(InIt first,InIt,InIt last,PredicatePredicate pred););例Ex_Find find函數(shù)使用示例。#include#include#include#include using namespace std;typedef vector IntVector;class USERDOpublic:bool operator()(int i)/運算符“()”重載函數(shù)return (i5)&(i8);int main()ostream_iterator out(cout,);int a=1,3,5,6,6,7,7,7,8,8,8,8;/整數(shù)數(shù)組aconst int ANUM=sizeof(a)/sizeof(int);IntVector v(a,a+ANUM);/A：構造copy(v.begin(),v.end(),out);coutendl;IntVector:iterator it=find(v.begin(),v.end(),3);/查找整數(shù)3cout找到*it 的位置在：it-v.begin()endl;cout-endl;IntVector:iterator start=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()endl;start=it+1;while(it!=v.end();cout-endl;start=v.begin();do/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()cout找到*it 的位置在：it-v.begin()endl;start=it+1;while(it!=v.end();return 0;程序運行結果如下：16.3.4 sortn函數(shù)模板sort用于為指定序列排序，它的原型如下：n/sort,RanIt表示隨機訪問迭代器ntemplatetemplaten void sort(RanIt void sort(RanIt first,RanIt,RanIt last););ntemplatetemplaten void sort(RanIt void sort(RanIt first,RanIt,RanIt last,BPred,BPred pred););n其功能是將first,last之間的序列按從小到大的升序進行排序 例Ex_Sort sort函數(shù)使用示例#include#include#include#include using namespace std;class C2Pred public:C2Pred(int a,int b):first(a),second(b)void show()cout(first,second)endl;bool operator (const C2Pred&m)const return first m.first;/按first值從小到大排序friend friend bool less_second(const C2Pred&m1,const C2Pred&m2)return m1.second m2.second;/按second值從小到大排序private:int first;int second;nint main()n nvector vect;nint i;nfor(i=0;i 5;i+)n C2Pred ob(10-i,i*3);vect.push_back(ob);nfor(i=0;i vect.size();i+)vecti.show();ncout按first值從小到大排序:endl;nsort(vect.begin(),vect.end();nfor(i=0;i vect.size();i+)vecti.show();ncout按second值從小到大排序:endl;nsort(vect.begin(),vect.end(),less_second);nfor(i=0;i vect.size();i+)vecti.show();nreturn 0;n程序運行結果如下：16.4 綜合應用實例#include#include#include/鏈表類頭文件包含#include/迭代器頭文件包含#include#include#include using namespace std;class CStudent;ostream&operator(ostream&os,const CStudent&stu);class CStudentpublic:CStudent()CStudent(char*name,char*id,float s1,float s2,float s3);void print(int n=-1);char*GetName()return strName;friend ostream&operator(ostream&os,const CStudent&stu);bool operator (const CStudent&stu)const/重載 stu.total;/按total從高到低排序private:charstrName20;/姓名charstrID10;/學號floatfScore3;/三門課成績floattotal;/總分;CStudent:CStudent(char*name,char*id,float s1,float s2,float s3)strncpy(strName,name,20);strncpy(strID,id,10);fScore0=s1;fScore1=s2;fScore2=s3;total=fScore0+fScore1+fScore2;void CStudent:print(int n)/n為序號，0)coutsetw(6)序號;coutsetw(20)姓名setw(10)學號setw(10)成績1setw(10)成績2setw(10)成績3setw(10)總分0)coutsetw(6)n;coutsetw(20)strNamesetw(10)strIDsetw(10)fScore0setw(10)fScore1setw(10)fScore2setw(10)totalendl;ostream&operator(ostream&os,const CStudent&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);return os;class CStuListpublic:voidAdd(CStudent stu);/添加記錄intSeek(char*name,CStudent&stu);/按姓名查找,返回記錄號，-1表示沒有找到voidShowAll();/遍歷列表顯示voidSortToFile(char*filename);/按學生總成績從高到低排序并寫到文件中private:listtheBuf;/鏈表對象;void CStuList:Add(CStudent stu)theBuf.push_back(stu);int CStuList:Seek(char*name,CStudent&stu)/按姓名查找 int nRec=-1,i=0;list:iterator ip=theBuf.begin();/定義指針while(ip!=theBuf.end()stu=(CStudent)(*ip);if(0=strcmp(stu.GetName(),name)nRec=i;break;ip+;i+;return nRec;void CStuList:ShowAll()/遍歷列表顯示list:iterator ip=theBuf.begin();/定義指針int i=0;while(ip!=theBuf.end()ip-print(+i);ip+;void CStuList:SortToFile(char*filename)theBuf.sort();ShowAll();/將排序后的內(nèi)容保存在文件中ofstream fout(filename);copy(theBuf.begin(),theBuf.end(),ostream_iterator(fout);int main()CStuList theStu;CStudent stu1(MaWenTao,99001,88,90,75.5);CStudent stu2(LiMing,99002,92,80,81.5);CStudent stu3(WangFang,99003,89,70,78);CStudent stu4(YangYang,99004,90,80,90);CStudent stu5(DingNing,99005,80,78,85);theStu.Add(stu1);theStu.Add(stu2);theStu.Add(stu3);theStu.Add(stu4);theStu.Add(stu5);theStu.ShowAll();CStudent stu;int nRec=theStu.Seek(LiMing,stu);if(nRec=0)cout找到的結果為：endl;stu.print(nRec+1);else cout沒有找到！endl;cout執(zhí)行SortToFile后的結果：endl;theStu.SortToFile(student.dat);return 0;程序運行結果如下：49可編輯