C++實(shí)用教程16課件

第16章標(biāo)準(zhǔn)模板庫(kù)（STL）

16.1迭代器C++實(shí)用教程1616.1.1迭代器的由來

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

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

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

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

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

C++實(shí)用教程16一旦建立了容器類vector、list或deque實(shí)例化類對(duì)象，就可以通過對(duì)象進(jìn)行下列常用操作（1）元素的插入操作。用于元素插入操作的成員函數(shù)為insert、push_front和push_back（2）元素的刪除和清除操作。用于刪除元素操作的成員函數(shù)有erase、pop_front和pop_back，clear用于清除操作（3）元素訪問操作。容器類vector和deque除了提供下標(biāo)運(yùn)算符“[]”來引用指定位置的對(duì)象元素的內(nèi)存空間外，還提供下列元素訪問操作（4）迭代器和空間大小屬性操作。容器類vector、list和deque都提供下列有關(guān)迭代器和空間大小屬性的常用操作（5）鏈表操作。與容器類vector和deque不同的是，容器類list自身還有不同的常用操作，如反序、排序、合并等C++實(shí)用教程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++實(shí)用教程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++實(shí)用教程16程序運(yùn)行結(jié)果如下：C++實(shí)用教程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++實(shí)用教程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); //輸出所有結(jié)點(diǎn)元素

v.remove(-7); //移除-7結(jié)點(diǎn)

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++實(shí)用教程16程序運(yùn)行結(jié)果如下：

C++實(shí)用教程1616.2.2棧和隊(duì)列

棧（stack）是一種“FILO”（先進(jìn)后出）或“LIFO”（后進(jìn)先出）的線性表，它只允許在表的一端進(jìn)行插入和刪除操作。而隊(duì)列（queue）是一種“FIFO”（先進(jìn)先出）的線性表，與棧剛好相反。在隊(duì)列中，只允許在表的一端插入元素，而在另一端刪除元素。定義對(duì)象時(shí)，它們都可以有下列簡(jiǎn)單的形式：X<int>v; X<int,vector<int>>v; //使用向量容器來構(gòu)造 //注意，vector<int>>的最后面是兩個(gè)大于符號(hào)，它們之間一定要有空格C++實(shí)用教程16說明:（1）ANSI/ISOC++類模板stack和deque中都有一個(gè)protected數(shù)據(jù)成員c，其定義如下：protected:Containerc;但在VisualC++2005中，該數(shù)據(jù)成員是公有的，因此可以在對(duì)象中通過c訪問構(gòu)造時(shí)指定的容器類模板的成員。對(duì)于VisualC++6.0需要通過派生才能使用該數(shù)據(jù)成員c。（2）另外，類模板stack和deque還都重載了運(yùn)算符==、<、!=、>、>=、<=，用于兩個(gè)棧或兩個(gè)隊(duì)列之間的關(guān)系比較。C++實(shí)用教程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++實(shí)用教程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;}程序運(yùn)行結(jié)果如下：C++實(shí)用教程1616.2.3映像

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

（1）元素的插入操作。需要說明的是，這里操作的元素是指“鍵”和“值”的對(duì)子，簡(jiǎn)稱鍵值對(duì)。在容器類map中，用于元素插入操作的成員函數(shù)為insert（2）元素的刪除和清除操作。容器類map用于刪除元素操作的成員函數(shù)是erase，用于清除操作的是clear（3）元素訪問操作。容器類map只提供下標(biāo)運(yùn)算符“[]”來引用指定位置元素的內(nèi)存空間（4）迭代器和空間大小屬性操作。（5）映像操作另外，容器類map還重載了運(yùn)算符==、<、!=、>、>=、<=，用于兩個(gè)映像之間的關(guān)系比較C++實(shí)用教程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; //定義類型名以便后面使用//輸出鍵值對(duì)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);}//顯示某范圍的鍵值對(duì)，演示lower_bound和upper_boundC++實(shí)用教程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);}//顯示某范圍的鍵值對(duì)，演示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++實(shí)用教程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<<"個(gè)元素！"<<endl; //查找操作

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

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++實(shí)用教程16程序運(yùn)行結(jié)果如下：C++實(shí)用教程1616.2.4集合

容器類set具有下列聲明：template<classKey,classCompare=less<Key>, classAllocator=allocator<Key>>classset{};C++實(shí)用教程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;}//顯示某范圍的鍵值對(duì)，演示lower_bound和upper_boundC++實(shí)用教程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;}//顯示某范圍的鍵值對(duì)，演示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++實(shí)用教程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<<"個(gè)元素！"<<endl; //查找操作

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

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++實(shí)用教程16程序運(yùn)行結(jié)果如下：

C++實(shí)用教程1616.3算法

16.3.1概述STL算法部分主要由頭文件<algorithm>、<numeric>和<functional>組成。16.3.2copy和流迭代器1.copy函數(shù)模板copy將序列中某個(gè)范圍的元素復(fù)制到另一個(gè)序列中C++實(shí)用教程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;}程序運(yùn)行結(jié)果如下：C++實(shí)用教程162.流迭代器

輸出流迭代器ostream_iterator是STL預(yù)定義的迭代器類模板，它具有下列定義：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++實(shí)用教程1616.3.3find

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

{ return((i>5)&&(i<8)); }};C++實(shí)用教程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：構(gòu)造

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++實(shí)用教程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++實(shí)用教程16程序運(yùn)行結(jié)果如下：

C++實(shí)用教程1616.3.4sort

函數(shù)模板sort用于為指定序列排序，它的原型如下：//sort,RanIt表示隨機(jī)訪問迭代器template<classRanIt>voidsort(RanItfirst,RanItlast);template<classRanIt,classBPred>voidsort(RanItfirst,RanItlast,BPredpred);其功能是將[first,last]之間的序列按從小到大的升序進(jìn)行排序C++實(shí)用教程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++實(shí)用教程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++實(shí)用教程16程序運(yùn)行結(jié)果如下：C++實(shí)用教程1616.4綜合應(yīng)用實(shí)例

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

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

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

char strID[10]; //學(xué)號(hào)

float fScore[3]; //三門課成績(jī)

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++實(shí)用教程16voidCStudent::print(intn) //n為序號(hào)，<=0時(shí)不顯示序號(hào){ staticboolisHead=false; if(!isHead){ //輸出表頭

if(n>0)cout<<setw(6)<<"序號(hào)"; cout<<setw(20)<<"姓名"<<setw(10)<<"學(xué)號(hào)" <<setw(10)<<"成績(jī)1"<<setw(10)<<"成績(jī)2"<<setw(10)<<"成績(jī)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));