大連海事大學(xué)C++面向?qū)ο蟮某绦蛟O(shè)計胡英Chapter9

9.1函數(shù)模板9.2類模板

9.3標(biāo)準(zhǔn)模板庫第9

章

模板與標(biāo)準(zhǔn)模板庫模板模板是C++支持參數(shù)化多態(tài)的工具，使用模板可以使用戶為類或者函數(shù)聲明一種一般模式，使得類中的某些數(shù)據(jù)成員或者成員函數(shù)的參數(shù)、返回值取得任意類型。C++的標(biāo)準(zhǔn)模板庫STL(StandardTemplateLibrary)已經(jīng)成為一個標(biāo)準(zhǔn)，它包含容器，算法以及迭代子(或稱迭代器)。本章首先探討函數(shù)模板和類模板，然后介紹C++標(biāo)準(zhǔn)模板庫的使用。函數(shù)模板的語法形式如下：

template<typenameT>

函數(shù)定義利用函數(shù)模板，可以建立一個具有通用功能的函數(shù)，支持不同的函數(shù)參數(shù)和返回值，達(dá)到減少代碼書寫量的目的。T代表在函數(shù)模板中要使用的通用類型，在該函數(shù)的調(diào)用過程中，T被具體化?！?/p>

9.1函數(shù)模板】template<typenameT>Tabs(Tvalue){returnvalue>0?value:-value;}例如重載函數(shù)，求絕對值的函數(shù)只要聲明一個函數(shù)模板：intmain(){

int

nValue=-1,nResult;doubledblValue=-1.2,dblResult;

nResult=abs(nValue);

dblResult=abs(dblValue);

cout<<nValue<<"

"<<nResult<<endl;

cout<<dblValue<<"

"<<dblResult<<endl;return0;}-11-1.21.2第一次使用函數(shù)模板abs（）時，實參為整數(shù)，由此可以推導(dǎo)出函數(shù)模板中的參數(shù)類型T為整數(shù)，函數(shù)的返回值也是整數(shù)。第二次調(diào)用abs()時實參為雙精度型，由此推導(dǎo)出函數(shù)模板中的參數(shù)類型T為雙精度型，函數(shù)的返回值為雙精度型。在主程序中可以這樣使用函數(shù)模板：數(shù)據(jù)成員變成另外一種數(shù)據(jù)類型，或者干脆是一個類的對象，又要重新拷貝，重新進(jìn)行修改。這樣不僅程序的代碼數(shù)量急劇增加，修改過程中也很容易出現(xiàn)各種疏漏。用一種類似函數(shù)模板的機制來結(jié)決問題——類模板。C++語言中的類模板的語法定義如下：

Template<模板參數(shù)表>

類聲明當(dāng)模板參數(shù)表中同時包含上述多項內(nèi)容時，各項內(nèi)容之間以逗號隔開。注與函數(shù)模板相同，類模板只有使用的時候才被具體化為某一種類型。使用模板類來產(chǎn)生對象時，按如下形式聲明：

模板<模板參數(shù)表>對象名1，......對象名n;模板參數(shù)表中的內(nèi)容可以為：

class標(biāo)識符 類型說明符標(biāo)識符【

9.2類模板】類模板舉例//EXAMPLE9_02.H#ifndefEXAMPLE9_02_H#defineEXAMPLE9_02_Htemplate<classT>classMax//聲明類模板Max{private:Titem1,//類型為T,T在該類的對象生成時具體化

item2,item3;public:Max(){}Max(Tthefirst,T

thesecond,Tthethird);TGetMaxItem();//求得3個元素中的最大值并按類型T返回

voidSetItem(T

thefirst,T

thesecond,Tthethird);//設(shè)置類中的3個元素的值};#endif//EXAMPLE9_02B.H

例9-2//類模板的實現(xiàn)#ifndefEXAMPLE9_02B_H#defineEXAMPLE9_02B_Htemplate<classT>Max<T>::Max(Tthefirst,Tthesecond,Tthethird): item1(thefirst),item2(thesecond),item3(thethird){return;}template<classT>voidMax<T>::SetItem(T

thefirst,Tthesecond,Tthethird){item1=thefirst;item2=thesecond;item3=thethird;}template<classT>TMax<T>::GetMaxItem()

（續(xù)）{Tmaxitem;

maxitem=item1>item2?item1:item2;

maxitem=maxitem>item3?maxitem:item3;returnmaxitem;}#endif//EXAMPLE9_2.CPP//主程序#include<iostream.h>#include"EXAMPLE902.H"#include"EXAMPLE902B.H"intmain(){Max<int>nmyMax(1,2,3);Max<double>dblmyMax(1.2,1.3,-1.4);

cout<<nmyMax.GetMaxItem()<<endl;

cout<<dblmyMax.GetMaxItem()<<endl;return0;}31.3編程實現(xiàn)棧類模板并測試//EXAMPLE9_03.CPP//源程序開始#include<iostream.h>#include<stdlib.h>template<classT>classCStack

//模板名{public:

CStack(intsize_t=9);//構(gòu)造函數(shù)模板

~CStack();//析構(gòu)函數(shù)模板

boolEmpty()const;//?？张袛?/p>

boolFull()const;//棧滿判斷

voidClear();//清空棧

T&Top()const;//查詢棧頂元素

voidPush(constT&);//入棧

T&Pop();//出棧private:

intsize;

inttop;

例9-3（續(xù)）

T*ptrStack;};template<classT>CStack<T>::CStack(intsize_t)//構(gòu)造函數(shù)模板{ if(size_t>0) size=size_t; elsesize=9; top=-1;

ptrStack=newT[size];}template<classT>CStack<T>::~CStack()//析構(gòu)函數(shù)模板{ delete[]ptrStack;}template<classT>bool

CStack<T>::Empty()const//?？张袛鄘 returntop==-1;}（續(xù)）template<classT>bool

CStack<T>::Full()const//棧滿判斷{

returntop==size-1;}template<classT>T&CStack<T>::Top()const//查詢棧頂元素{

if(!Empty()) returnptrStack[top]; elseexit(1);}template<classT>voidCStack<T>::Clear()//清空棧{

top=-1;}template<classT>voidCStack<T>::Push(constT&value)//入棧{

if(!Full()) {

（續(xù)）

ptrStack[++top]=value; } elseexit(1);}template<classT>T&CStack<T>::Pop()//出棧{

if(!Empty()) { top--; returnptrStack[top+1]; } elseexit(1);}//測試程序intmain(){

CStack<double>dblStack(5);

//定義一個CStack<double>模板類對象dblStack inti; doubletemp;

（續(xù)）

for(i=0;i<5;i++) {

cout<<"Pushelements"<<i<<"instack:";

cin>>temp;

dblStack.Push(temp);//入棧

}

while(!dblStack.Empty()) { temp=dblStack.Pop();//出棧

cout<<"--->"<<temp<<endl; } return0;}Pushelements0instack:11.11Pushelements1instack:22.22Pushelements2instack:33.33Pushelements3instack:44.44Pushelements4instack:55.55--->55.55--->44.44--->33.33--->22.22--->11.11程序運行結(jié)果：實現(xiàn)了數(shù)組、鏈表、線性表、棧和隊列，它們屬于線性容器。另外，這里還將使用到雙端隊列，就是兩端都可以進(jìn)行插入和刪除操作的線性表。除了線性容器，我們還將接觸到兩種非線性容器：集合和映射。【

9.3.1基本數(shù)據(jù)結(jié)構(gòu)知識】C++的標(biāo)準(zhǔn)模板庫STL包含容器、算法和迭代子，其中容器模板包括鏈表、向量、棧、隊列、集合、映象等，算法模板包括諸如排序、查找等各種算法，而迭代子則可以針對不同容器進(jìn)行操作。本章將著重介紹STL的使用?！?/p>

9.3標(biāo)準(zhǔn)模板庫】若干個固定事物的全體叫做一個集合，組成集合的事物叫做這個集合的元素。例如對于一個有四個元素的集合A可以如下表示：A={a1,a2,a3,a4}映射則是把一個集合中的元素和另一個集合中的元素聯(lián)系起來。日常生活中也存在大量映射的例子，如一個身份證號碼可以映射為某個確定的人，圖書館中一本書的編號和這本書也是一個映射。例如兩個集合A和B：A={1,2,3,4}B={a,b,c,d}我們可以構(gòu)造從集合A到集合B的映射(1,a),(2,b),(3,d),(4,c)等等。子集：如果一個集合A的所有元素都是另一個集合B的元素，則集合A是集合B的子集。交集：取集合A和集合B中所有相同元素組成的集合差集：集合A對集合B的差集可以定義為由所有屬于集合A但不屬于集合B的元素組成的集合。1994年7月，STL正式成為標(biāo)準(zhǔn)C++庫的一部分。STL中的容器類是基于模板的，它既包含線性容器，也包含非線性容器，其中主要有： vector(向量模板)

list(鏈表模板)

stack(棧模板)

queue(隊列模板)

deque(雙端隊列模板)

set(集合模板)

map(映射模板)STL的迭代子可以看成是指針的推廣，迭代子也可以是普通的指針。類型分類順序訪問：直接訪問：順序迭代子使用++、--等進(jìn)行移動，但只能順序訪問容器中的對象。直接訪問迭代子則可以直接訪問容器中的某個特定對象。【

9.3.2標(biāo)準(zhǔn)模板類庫簡介】STL的算法是用函數(shù)模板實現(xiàn)的，可以實現(xiàn)對不同類型對象的通用操作。排序（sort、merge）查找（find、search）比較（equal）集合（includes、setunion、setdifference）計算（accumulate、partialsum）統(tǒng)計（max、min）管理（swap、fill、replace、copy、unique、rotate、reverse）堆操作（makeheap、pushheap、popheap、sortheap）算法與STL容器類之間是通過迭代子來進(jìn)行溝通的，算法面向迭代子，迭代子則面向容器類,對于迭代子，可以將它理解為一個指針，通過它我們可以獲得容器內(nèi)部的數(shù)據(jù)對象，然后算法對這個由迭代子獲得的對象進(jìn)行操作。STL的主要算法有：C++語言標(biāo)準(zhǔn)類庫提供了向量容器，向量既有象數(shù)組一樣可以對容器內(nèi)部對象進(jìn)行直接訪問的特點，也有類似于鏈表可以對容器內(nèi)部對象進(jìn)行順序訪問的特點，同時向量具有動態(tài)特征，所以C++語言中的向量容器具有數(shù)組和鏈表兩者的優(yōu)點。向量模板類中較為重要的成員函數(shù)有begin、end、insert、erase、operator［］等。iteratorinsert(iteratorit,constT&x=T());//將x復(fù)制到it位置之前voidinsert(iteratorit,sizetypen,constT&x);//將n個x復(fù)制到it位置之前voidinsert(iteratorit,constiteratorfirst,constiteratorlast);//將first和last

//之間的對象復(fù)制到it位置之前iteratorerase(iteratorit);//移走it位置的對象iteratorerase(iteratorfirst,iteratorlast);//移走first到last之間的對象用法如下：begin返回指向該向量的第一個對象的迭代子。end返回一個指向向量末尾值的迭代子。insert和erase是向量類的插入和刪除方法?！?/p>

9.3.3向量】向量應(yīng)用舉例(一)//EXAMPLE9_5.CPP#include<iostream>#include<numeric>#include<vector>#include<iterator>usingnamespacestd;intmain(){ 說明一下copy和accumulate函數(shù)的用法：template<classInIt,classOutIt>OutItcopy(InItfirst,InItlast,OutItx);//該函

//數(shù)將從first到last之間的對象依次賦給位置x的對象，

//同時x++。在本例中是賦給標(biāo)準(zhǔn)輸出流。template<classInIt,classT>Taccumulate(InItfirst,InItlast,Tval);//在first

//和last之間依次取得對象值，每次該值與val的和替代原val值，返回val。template<classInIt,classT,classPred>Taccumulate(InItfirst,InItlast,Tval,Predpr);//在first和last之間依次取得對象值，每次該值與val進(jìn)行pr運算后得到的

//新值(在例中用到multiplies,進(jìn)行乘法運算)替代原val值,返回val。例9-5

vector<int>nMyVector1,nMyVector2;//整型向量

//該向量類型的迭代子

vector<int>::iterator

nItBegin,nItEnd;

//對向量類型對象中的數(shù)據(jù)進(jìn)行順序賦值

for(inti=1;i<=10;i++) { nMyVector1.push_back(i); } //該向量類型的迭代子被賦值

nItBegin=nMyVector1.begin();

nItEnd=nMyVector1.end(); //用insert函數(shù)實現(xiàn)兩個向量類型對象成員數(shù)據(jù)的復(fù)制

nMyVector2.insert(nMyVector2.begin(),nMyVector1.begin(),nMyVector1.end());

cout<<"nMyVetcor2=<"; for(i=0;i<nMyVector2.size();i++) {

cout<<nMyVector2[i]<<""; }

cout<<">"<<endl;

nItBegin=nMyVector1.begin();（續(xù)）

nItEnd=nMyVector1.end();

cout<<"nMyVetcor1=<"; //用迭代子輸出向量對象nMyVector1的數(shù)據(jù)

while(nItBegin!=nItEnd) {

cout<<*nItBegin<<"";

nItBegin++; }

cout<<">"<<endl;

//用標(biāo)準(zhǔn)算法得到整型向量對象中所有數(shù)據(jù)的和

cout<<"ThesumofnMyVector1[i]is:"<<accumulate(nMyVector1.begin(),nMyVector1.end(),0.0f)<<endl; return0;}//源程序結(jié)束程序輸出：nMyVetcor2=<12345678910>nMyVetcor1=<12345678910>ThesumofnMyVector1[i]is:55向量應(yīng)用舉例（二）使用向量數(shù)組存儲一個九九乘法表，并打印輸出。//EXAMPLE9_6.CPP//程序開始#include<iostream>#include<vector>usingnamespacestd;intmain(){ vector<int>matrix[9];

inti,j; for(i=1;i<10;i++) for(j=1;j<10;j++) { matrix[i-1].push_back(i*j); }

for(i=1;i<10;i++) for(j=1;j<10;j++) {例9-6

cout<<matrix[i-1][j-1]<<""; if(j==i) {

cout<<endl; break; } } return0;}程序運行結(jié)果：12436948121651015202561218243036714212835424981624324048566491827364554637281鏈表類中比較重要的成員函數(shù)與向量基本相同，但注意鏈表類不包含［］運算符重載，也沒有+=或-=重載，這一點與向量不同。例9-8整型鏈表模板類list<int>應(yīng)用//EXAMPLE9_8.CPP//源程序開始#include<iostream>#include<list>#include<iterator>usingnamespacestd;//聲明使用std名稱空間intmain(){list<int>nList1,nList2;//整型list

//針對整型list的迭代子 list<int>::iteratorbegin,end;

//對整型list對象中的數(shù)據(jù)賦值 for(inti=1;i<=10;i++) nList1.push_back(i);【

9.3.4鏈表類的使用】（續(xù)） //將整型list對象nList1中的數(shù)據(jù)輸出

begin=nList1.begin(); end=nList1.end(); do { cout<<*begin; begin++; if(begin!=end)

cout<<"->"; }while(begin!=end);

cout<<endl; //用insert函數(shù)實現(xiàn)兩個整型list對象成員數(shù)據(jù)的復(fù)制

nList2.insert(nList2.begin(),nList1.begin(),nList1.end()); //將整型list對象nList1中的數(shù)據(jù)輸出

begin=nList2.begin(); end=nList2.end(); //用迭代子輸出整型list對象的數(shù)據(jù),對于list類型不能對迭代子使用+=/-=等運算符

//也不能使用[]進(jìn)行直接存?。ɡm(xù)）

do//輸出nList2 { cout<<*begin; begin++; if(begin!=end)

cout<<"->"; }while(begin!=end);

cout<<endl; return0;}程序運行結(jié)果：1->2->3->4->5->6->7->8->9->101->2->3->4->5->6->7->8->9->10雙端隊列，支持對數(shù)據(jù)的直接訪問和順序訪問。雙端隊列的基本操作一般用在對象序列的開頭或結(jié)尾頻繁插入或者刪除的情況。//EXAMPLE9_10.CPP//源程序開始#include<iostream>#include<deque>#include<iterator>usingnamespacestd;classMobileTel

//手機類{public:

例9-10雙端隊列應(yīng)用舉例【

9.3.5雙端隊列】假設(shè)有一個手機專賣店，手機信息包括品牌和價格，每銷售一部手機，都將該手機信息保存到雙端隊列，列出已銷售手機情況并統(tǒng)計銷售額。

MobileTel(constchar*b,constint&p)

//構(gòu)造函數(shù)

{

strcpy(brand,b); price=p; } voidSetBrand(constchar*b)//設(shè)置品牌

{

strcpy(brand,b); } voidSetPrice(constintp)//設(shè)置價格

{

price=p; } char*GetBrand()//獲得品牌

{

char*pb=newchar[strlen(brand)+1];

strcpy(pb,brand); returnpb; }

int

GetPrice()//獲得價格

{

returnprice; }（續(xù)）private: charbrand[30];//品牌

intprice;//價格};//測試程序intmain(){

deque<MobileTel>mshop;//定義一個雙端隊列

deque<MobileTel>::iteratorbegin,end;//迭代子

charbrand[30];

intprice,total=0; charquit='y'; while((quit!='n')&&(quit!='N')) {

cout<<"顧客買了什么牌子的手機？";

cin>>brand;

cout<<"價格是多少？";

cin>>price;

mshop.push_back(MobileTel(brand,price));

cout<<"還有顧客要買手機嗎？(y|n)";

cin>>quit; }（續(xù)）

begin=mshop.begin(); end=mshop.end();

cout<<"現(xiàn)在共賣手機"<<mshop.size()<<"部"<<endl; while(begin!=end) {

cout<<"牌子："<<begin->GetBrand()<<":";

cout<<"價格"<<begin->GetPrice()<<endl; total+=begin->GetPrice(); begin++; }

cout<<"總價："<<total<<endl; return0;}程序運行結(jié)果：顧客買了什么牌子的手機？TCL價格是多少？1000還有顧客要買手機嗎？(y|n)y顧客買了什么牌子的手機？波導(dǎo)價格是多少？1110還有顧客要買手機嗎？(y|n)y顧客買了什么牌子的手機？海爾價格是多少？1200還有顧客要買手機嗎？(y|n)n現(xiàn)在共賣手機3部牌子：TCL:價格1000牌子：波導(dǎo):價格1110牌子：海爾:價格1200總價：3310通過容器適配子得到棧與隊列。適配子是一個提供與容器接口的模板類，不提供新的服務(wù)，只是在原有基本容器語法的基礎(chǔ)上進(jìn)行重新定義。例9-11整型棧應(yīng)用舉例//EXAMPLE9_11.CPP//源程序開始#include<iostream>#include<stack>usingnamespacestd;//聲明使用std名稱空間

標(biāo)準(zhǔn)棧是以LIFO方式進(jìn)行訪問的，其基本接口函數(shù)為push、pop、size、top、empty。 voidpush(constT&x);//將對象x壓入棧中

voidpop();//將棧頂元素出棧

intsize()const;//獲得棧中的元素個數(shù)

constvaluetype&top()const;//查詢棧頂元素

boolempty()const;//清空?！?/p>

9.3.6棧與隊列】intmain(){ stack<int>nMyStack1;//整型棧

//得到整型棧對象中的數(shù)據(jù)

for(inti=0;i<=9;i++) { //用push()入棧

nMyStack1.push(i);

//用top()顯示當(dāng)前棧頂元素

cout<<nMyStack1.top()<<"";

cout<<"";

cout<<"i="<<i<<endl; } //求棧中元素數(shù)目

cout<<"thesizeofnMyStack1="<<nMyStack1.size()<<endl; //用top()顯示棧頂元素，用pop()出棧

for(;!nMyStack1.empty();) {

cout<<nMyStack1.top()<<""; nMyStack1.pop(); }（續(xù)）

cout<<endl; return0;}//源程序結(jié)束程序運行結(jié)果：0i=01i=12i=23i=34i=45i=56i=67i=78i=89i=9thesizeofnMyStack1=109876543210集合與映射是兩種主要的非線性容器，對集合與映射的概念的理解與數(shù)學(xué)上的概念相類比。主要通過集合來學(xué)習(xí)STL中非線性容器的用法。例如:自集、交集、差集，通過includes、setintersection、setdifference等函數(shù)實現(xiàn)的。template<classInIt1,classInIt2,classOutIt>OutItsetdifference(InIt1first1,InIt1last1,InIt2first2,InIt2last2,OutItx);該函數(shù)模板將集合InIt1中從first1到last1中的元素與集合InIt2中從first2到last2中的元素進(jìn)行比較，將屬于InIt1但不屬于InIt2的元素形成一個序列，由x指示(本例中將符合條件的元素用inserter函數(shù)插入到新的集合中)。template<classInIt1,classInIt2,classOutIt>OutItsetintersection(InIt1first1,InIt1last1,InIt2first2,InIt2last2,OutItx);該函數(shù)模板用法與setdifference相同，求兩個集合的交集。template<classInIt1,classInIt2>boolincludes(InIt1first1,InIt1last1,InIt2first2,InIt2last2);該函數(shù)模板求InIt2所指示的集合范圍(first2,last2)是否是InIt1所指示的集合范圍(first1,last1)的子集。【

9.3.7集合與映射】整型集合應(yīng)用舉例//EXAMPLE9_14.CPP//源程序開始#pragmawarning(disable:4786)//防止一個編譯警告的出現(xiàn)#include<iostream>#include<set>#include<iterator>#include<algorithm>usingnamespacestd;//聲明使用std名稱空間intmain(){

set<int>set1,setDiff,setInter;//整型集合

//針對集合類型的迭代子 set<int>::iteratorbegin,end; //得到集合類型對象中的數(shù)據(jù)

for(inti=1;i<=10;i++) set1.insert(i);

//用一個集合對象初始化另一個集合對象

set<int>set2(set1),set3(set2);例9-14

//對set2的集合類型對象增加數(shù)據(jù) for(i=1;i<=5;i++) { set2.insert(i+10); } //求兩個集合的差和交 set_difference(set2.begi