第16章標準模板庫（STL）

16.1迭代器C++實用教程1616.1.1迭代器的由來

在STL中，迭代器是一種“特殊”的指針，用來指定或引用容器中元素的位置正是因為對不同容器的操作具有相同的實現(xiàn)代碼，所以才會形成STL的算法器及迭代器以優(yōu)化和簡化算法代碼。C++實用教程1616.1.2迭代器的類型

STL提供了5種不同的迭代器：輸入、輸出、正向、雙向和隨機訪問迭代器C++實用教程16（1）輸入迭代器。它是一種單向迭代器，只可遞增，不可回退（2）輸出迭代器。它是一種單向迭代器，只不過它是向容器中寫入元素。（3）正向迭代器。它是輸入迭代器和輸出迭代器功能的組合，其操作元素總是向前移動（即支持++操作），與輸入迭代器或輸出迭代器不同的是，它多次遍歷的順序都是相同的。（4）雙向迭代器。它常用于reserse（逆序）等操作，支持指針的++和操作。（5）隨機訪問迭代器。它具有雙向迭代器的所有功能，同時增加了直接訪問容器中任何元素的功能，即可向前、向后跳過任意多個元素，以及用于對元素排序的關系運算等C++實用教程1616.2容器類

容器是一個與數(shù)組類似的單元，可以存取若干元素主要容器類有：deque（雙端隊列）、list（鏈表、列表）、queue（隊列）、stack（棧）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重集合）C++實用教程1616.2.1向量、鏈表和雙端隊列

1.模型概述向量、鏈表和雙端隊列都可以看成是順序存儲的線性表，只是鏈表不像向量和雙端隊列那樣具有隨機訪問的能力2.

deque、list和vectortemplate<classT,classAllocator=allocator<T>>classvector{…};template<classT,classAllocator=allocator<T>>classdeque{…};template<classT,classAllocator=allocator<T>>classlist{…};

C++實用教程16一旦建立了容器類vector、list或deque實例化類對象，就可以通過對象進行下列常用操作（1）元素的插入操作。用于元素插入操作的成員函數(shù)為insert、push_front和push_back（2）元素的刪除和清除操作。用于刪除元素操作的成員函數(shù)有erase、pop_front和pop_back，clear用于清除操作（3）元素訪問操作。容器類vector和deque除了提供下標運算符“[]”來引用指定位置的對象元素的內存空間外，還提供下列元素訪問操作（4）迭代器和空間大小屬性操作。容器類vector、list和deque都提供下列有關迭代器和空間大小屬性的常用操作（5）鏈表操作。與容器類vector和deque不同的是，容器類list自身還有不同的常用操作，如反序、排序、合并等C++實用教程16[例Ex_Vector]向量容器類示例#include<iostream>#include<vector> //向量容器類頭文件包含#include<iterator> //迭代器頭文件包含#include<algorithm> //算法器頭文件包含usingnamespacestd;//演示iterator操作voidshow(vector<int>&v){ if(v.empty()){ cout<<"該向量容器為空！\n"; return; } vector<int>::iteratorip; //定義指針

for(ip=v.begin();ip<v.end();ip++) cout<<*ip<<",\t"; cout<<endl;}//演示[]操作C++實用教程16#include<iostream>#include<vector> //向量容器類頭文件包含#include<iterator> //迭代器頭文件包含#include<algorithm> //算法器頭文件包含usingnamespacestd;//演示iterator操作voidshow(vector<int>&v){ if(v.empty()){ cout<<"該向量容器為空！\n"; return; } vector<int>::iteratorip; //定義指針

for(ip=v.begin();ip<v.end();ip++) cout<<*ip<<",\t"; cout<<endl;}C++實用教程16程序運行結果如下：C++實用教程164.list示例

[例Ex_List]鏈表容器類示例。#include<iostream>#include<list> //鏈表容器類頭文件包含#include<iterator> //迭代器頭文件包含usingnamespacestd;//演示iterator操作voidshow(list<int>&v){ if(v.empty()){ cout<<"該鏈表為空！\n"; return; } list<int>::iteratorip=v.begin(); //定義指針

while(ip!=v.end()) { cout<<*ip<<",\t"; ip++; } cout<<endl;}C++實用教程16intmain(){ list<int>v; v.push_back(20); v.push_back(40); v.push_back(5); v.push_back(7); list<int>::iteratorip=v.begin(); ip=v.insert(ip,13); v.insert(ip,-7); show(v); //輸出所有結點元素

v.remove(-7); //移除-7結點

v.reverse(); show(v); v.sort(); show(v); list<int>l; l.push_back(12); l.push_back(8); l.push_back(16); l.push_back(7); v.splice(v.end(),l); show(v); show(l); v.pop_back(); v.pop_back(); v.pop_back(); v.pop_back(); show(v); l.push_back(1); l.push_back(8); l.push_back(16); v.merge(l); show(v); show(l); return0;}C++實用教程16程序運行結果如下：

C++實用教程1616.2.2棧和隊列

棧（stack）是一種“FILO”（先進后出）或“LIFO”（后進先出）的線性表，它只允許在表的一端進行插入和刪除操作。而隊列（queue）是一種“FIFO”（先進先出）的線性表，與棧剛好相反。在隊列中，只允許在表的一端插入元素，而在另一端刪除元素。定義對象時，它們都可以有下列簡單的形式：X<int>v; X<int,vector<int>>v; //使用向量容器來構造 //注意，vector<int>>的最后面是兩個大于符號，它們之間一定要有空格C++實用教程16說明:（1）ANSI/ISOC++類模板stack和deque中都有一個protected數(shù)據成員c，其定義如下：protected:Containerc;但在VisualC++2005中，該數(shù)據成員是公有的，因此可以在對象中通過c訪問構造時指定的容器類模板的成員。對于VisualC++6.0需要通過派生才能使用該數(shù)據成員c。（2）另外，類模板stack和deque還都重載了運算符==、<、!=、>、>=、<=，用于兩個?；騼蓚€隊列之間的關系比較。C++實用教程16[例Ex_Stack]棧類模板示例。#include<iostream>#include<stack> //棧模板頭文件包含#include<vector> //向量容器類頭文件包含#include<iterator> //迭代器頭文件包含usingnamespacestd;typedefstack<int,vector<int>>STACK;classCStack:publicSTACK{public: voidshow() //遍歷操作

{ if(empty()){ cout<<"棧為空！\n"; return; } vector<int>::iteratorip=c.begin(); //定義指針

while(ip!=c.end()) { cout<<*ip<<",\t"; ip++; } cout<<endl; }//清棧操作

voidclear() { while(!empty())pop(); }};C++實用教程16intmain(){ CStackv; 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;}程序運行結果如下：C++實用教程1616.2.3映像

1.概述與map概念相同，關聯(lián)容器類multimap支持的是多對一關系，即一個鍵對應于多個值。map和multimap都支持雙向迭代器，可以實現(xiàn)多路遍歷操作2.map容器類容器類map具有下列聲明：template<classKey,classT,classCompare=less<Key>, classAllocator=allocator<pair<constKey,T>>>classmap{…};C++實用教程16一旦建立了容器類map的實例化對象，就可以通過實例化類對象進行下列常用操作

（1）元素的插入操作。需要說明的是，這里操作的元素是指“鍵”和“值”的對子，簡稱鍵值對。在容器類map中，用于元素插入操作的成員函數(shù)為insert（2）元素的刪除和清除操作。容器類map用于刪除元素操作的成員函數(shù)是erase，用于清除操作的是clear（3）元素訪問操作。容器類map只提供下標運算符“[]”來引用指定位置元素的內存空間（4）迭代器和空間大小屬性操作。（5）映像操作另外，容器類map還重載了運算符==、<、!=、>、>=、<=，用于兩個映像之間的關系比較C++實用教程16[例Ex_Map]映像容器類示例#pragmawarning(disable:4786) //避免string使用中的警告出現(xiàn)#include<iostream>#include<map> //映像容器類頭文件包含#include<iterator> //迭代器頭文件包含#include<string> //字符串類頭文件包含usingnamespacestd;typedef map<string,int,less<string>>STR2INT; //定義類型名以便后面使用typedef STR2INT::iterator POS; //定義類型名以便后面使用//輸出鍵值對voidshowpair(POSpos){ cout<<"主鍵為："<<(*pos).first<<",\t值為："<<(*pos).second<<endl; }//遍歷輸出voidshow(STR2INT&v){ if(v.empty()) { cout<<"該映像為空！\n"; return; } POSip; for(ip=v.begin();ip!=v.end();ip++) showpair(ip);}//顯示某范圍的鍵值對，演示lower_bound和upper_boundC++實用教程16voidshowu(STR2INT&v,stringk1,stringk2){ POSpFirst,pEnd,p; pFirst=v.upper_bound(k1); pEnd=v.lower_bound(k2); if((*pFirst).first>(*pEnd).first) swap(pFirst,pEnd); for(p=pFirst;p!=pEnd;p++) showpair(p);}//顯示某范圍的鍵值對，演示lower_bound和upper_boundvoidshowl(STR2INT&v,stringk1,stringk2){ POSpFirst,pEnd,p; pFirst=v.lower_bound(k1); pEnd=v.upper_bound(k2); if((*pFirst).first>(*pEnd).first) swap(pFirst,pEnd); for(p=pFirst;p!=pEnd;p++) showpair(p);}C++實用教程16intmain(){ STR2INTv; //添加操作

v.insert(STR2INT::value_type("Zero",0)); v.insert(STR2INT::value_type("One",1)); v.insert(STR2INT::value_type("Two",2)); v.insert(STR2INT::value_type("Three",3)); v["Four"]=4; v["Five"]=5; v["Six"]=6; v["Seven"]=7; v["Eight"]=8; show(v); //刪除操作

cout<<"-----------------------------------"<<endl; intn=v.erase("Two"); cout<<"共刪除了"<<n<<"個元素！"<<endl; //查找操作

cout<<"-----------------------------------"<<endl; POSpos=v.find("Six"); if(pos!=v.end()) showpair(pos); //顯示某范圍的鍵值對

cout<<"-----------------------------------"<<endl; showu(v,"Four","Eight"); cout<<"-----------------------------------"<<endl; showl(v,"Four","Eight"); cout<<"-----------------------------------"<<endl; pair<POS,POS>pp=v.equal_range("FIVE"); showpair(pp.first); showpair(pp.second); return0;}C++實用教程16程序運行結果如下：C++實用教程1616.2.4集合

容器類set具有下列聲明：template<classKey,classCompare=less<Key>, classAllocator=allocator<Key>>classset{};C++實用教程16[例Ex_Set]集合容器類示例。#pragmawarning(disable:4786)#include<iostream>#include<set> //映像容器類頭文件包含#include<iterator> //迭代器頭文件包含#include<string> //字符串類頭文件包含usingnamespacestd;typedef set<string,less<string>> STRSET; //定義類型以便后面使用typedef STRSET::iterator POS; //定義類型以便后面使用//遍歷輸出voidshow(STRSET&v){ if(v.empty()){ cout<<"該映像為空！\n"; return; } POSip; //定義指針

for(ip=v.begin();ip!=v.end();ip++) cout<<*ip<<"\t"; cout<<endl;}//顯示某范圍的鍵值對，演示lower_bound和upper_boundC++實用教程16voidshowu(STRSET&v,stringk1,stringk2){ POSpFirst,pEnd,p; pFirst=v.upper_bound(k1); pEnd=v.lower_bound(k2); if((*pFirst)>(*pEnd)) swap(pFirst,pEnd); for(p=pFirst;p!=pEnd;p++) cout<<*p<<"\t"; cout<<endl;}//顯示某范圍的鍵值對，演示lower_bound和upper_boundvoidshowl(STRSET&v,stringk1,stringk2){ POSpFirst,pEnd,p; pFirst=v.lower_bound(k1); pEnd=v.upper_bound(k2); if((*pFirst)>(*pEnd)) swap(pFirst,pEnd); for(p=pFirst;p!=pEnd;p++) cout<<*p<<"\t"; cout<<endl;}C++實用教程16intmain(){ STRSETv; //添加操作

v.insert("Zero"); v.insert("One"); v.insert("Two"); v.insert("Three"); v.insert("Four"); v.insert("Five"); v.insert("Six"); show(v); //刪除操作

cout<<"-----------------------------------"<<endl; intn=v.erase("Two"); cout<<"共刪除了"<<n<<"個元素！"<<endl; //查找操作

cout<<"-----------------------------------"<<endl; POSpos=v.find("Six"); if(pos!=v.end()) cout<<*pos<<endl; //顯示某范圍的鍵值對

cout<<"-----------------------------------"<<endl; showu(v,"Two","Five"); cout<<"-----------------------------------"<<endl; showl(v,"Two","Five"); cout<<"-----------------------------------"<<endl; pair<POS,POS>pp=v.equal_range("FIVE"); cout<<*(pp.first)<<endl; cout<<*(pp.second)<<endl; return0;}C++實用教程16程序運行結果如下：

C++實用教程1616.3算法

16.3.1概述STL算法部分主要由頭文件<algorithm>、<numeric>和<functional>組成。16.3.2copy和流迭代器1.copy函數(shù)模板copy將序列中某個范圍的元素復制到另一個序列中C++實用教程16[例Ex_Copy]copy函數(shù)使用示例

#include<iostream>#include<vector>#include<algorithm>#include<iterator>usingnamespacestd;typedefvector<int>IntVector;intmain(){ intarr[10]={2,3,7,8,4,11,5,9,1,13}; IntVectorv(8); copy(arr,arr+8,v.begin()); ostream_iterator<int,char>out(cout,""); copy(arr,arr+10,out); cout<<endl; copy(v.begin(),v.end(),out); cout<<endl; return0;}程序運行結果如下：C++實用教程162.流迭代器

輸出流迭代器ostream_iterator是STL預定義的迭代器類模板，它具有下列定義：template<classT,classcharT=char,classtraits=char_traits<charT>>classostream_iterator:publiciterator<output_iterator_tag,void,void,void,void>{public: ostream_iterator(ostream_type&s); ostream_iterator(ostream_type&s,constcharT*delimiter); …};C++實用教程1616.3.3find

函數(shù)模板find用于查找，它的原型如下：template<classInIt,classT> InItfind(InItfirst,InItlast,constT&value);template<classInIt,classPredicate> InItfind_if(InItfirst,InItlast,Predicatepred);C++實用教程16[例Ex_Find]find函數(shù)使用示例。#include<iostream>#include<vector>#include<algorithm>#include<functional>usingnamespacestd;typedefvector<int>IntVector;classUSERDO{public: booloperator()(inti) //運算符“()”重載函數(shù)

{ return((i>5)&&(i<8)); }};C++實用教程16intmain(){ ostream_iterator<int,char>out(cout,""); inta[]={1,3,5,6,6,7,7,7,8,8,8,8}; //整數(shù)數(shù)組a constintANUM=sizeof(a)/sizeof(int); IntVectorv(a,a+ANUM); //A：構造

copy(v.begin(),v.end(),out); cout<<endl; IntVector::iteratorit=find(v.begin(),v.end(),3); //查找整數(shù)3 cout<<"找到"<<*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<int>(),7)); if(it!=v.end()) cout<<"找到"<<*it<<"的位置在："<<it-v.begin()<<endl; start=it+1; }while(it!=v.end()); cout<<"---------------------------------------------------------------"<<endl; start=v.begin();C++實用教程16do { //C：循環(huán)找出所有大于7的數(shù)

it=find_if(start,v.end(),bind2nd(greater<int>(),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()); //E if(it!=v.end()) cout<<"找到"<<*it<<"的位置在："<<it-v.begin()<<endl; start=it+1; }while(it!=v.end()); return0;}

C++實用教程16程序運行結果如下：

C++實用教程1616.3.4sort

函數(shù)模板sort用于為指定序列排序，它的原型如下：//sort,RanIt表示隨機訪問迭代器template<classRanIt>voidsort(RanItfirst,RanItlast);template<classRanIt,classBPred>voidsort(RanItfirst,RanItlast,BPredpred);其功能是將[first,last]之間的序列按從小到大的升序進行排序C++實用教程16[例Ex_Sort]sort函數(shù)使用示例#include<iostream>#include<vector>#include<algorithm>#include<functional>usingnamespacestd;classC2Pred{public: C2Pred(inta,intb) :first(a),second(b) {} voidshow() { cout<<"("<<first<<","<<second<<")"<<endl; } booloperator<(constC2Pred&m)const { returnfirst<m.first; } //按first值從小到大排序

friendboolless_second(constC2Pred&m1,constC2Pred&m2) { returnm1.second<m2.second; } //按second值從小到大排序private: intfirst; intsecond;};C++實用教程16intmain(){ vector<C2Pred>vect; inti; for(i=0;i<5;i++) { C2Predob(10-i,i*3); vect.push_back(ob);} for(i=0;i<vect.size();i++) vect[i].show(); cout<<"按first值從小到大排序:"<<endl; sort(vect.begin(),vect.end()); for(i=0;i<vect.size();i++) vect[i].show(); cout<<"按second值從小到大排序:"<<endl; sort(vect.begin(),vect.end(),less_second); for(i=0;i<vect.size();i++)vect[i].show(); return0;}C++實用教程16程序運行結果如下：C++實用教程1616.4綜合應用實例

#include<iostream>#include<iomanip>#include<list> //鏈表類頭文件包含#include<iterator> //迭代器頭文件包含#include<fstream>#include<algorithm>#include<cstring>usingnamespacestd;classCStudent;ostream&operator<<(ostream&os,constCStudent&stu);C++實用教程16classCStudent{public: 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 //重載<運算符

{ returntotal>stu.total; //按total從高到低排序

}private: char strName[20]; //姓名

char strID[10]; //學號

float fScore[3]; //三門課成績

float total; //總分};CStudent::CStudent(char*name,char*id,floats1,floats2,floats3){ strncpy(strName,name,20); strncpy(strID,id,10); fScore[0]=s1; fScore[1]=s2; fScore[2]=s3; total=fScore[0]+fScore[1]+fScore[2];}C++實用教程16voidCStudent::print(intn) //n為序號，<=0時不顯示序號{ staticboolisHead=false; if(!isHead){ //輸出表頭

if(n>0)cout<<setw(6)<<"序號"; cout<<setw(20)<<"姓名"<<setw(10)<<"學號" <<setw(10)<<"成績1"<<setw(10)<<"成績2"<<setw(10)<<"成績3" <<setw(10)<<"總分"<<endl; isHead=true; } if(n>0)cout<<setw(6)<<n; cout<<setw(20)<<strName<<setw(10)<<strID <<setw(10)<<fScore[0]<<setw(10)<<fScore[1]<<setw(10)<<fScore[2] <<setw(10)<<total<<endl;}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));