大連海事大學C++面向對象的程序設計胡英Chapter9

9.1函數模板9.2類模板

9.3標準模板庫第9

章

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

template<typenameT>

函數定義利用函數模板，可以建立一個具有通用功能的函數，支持不同的函數參數和返回值，達到減少代碼書寫量的目的。T代表在函數模板中要使用的通用類型，在該函數的調用過程中，T被具體化。【

9.1函數模板】template<typenameT>Tabs(Tvalue){returnvalue>0?value:-value;}例如重載函數，求絕對值的函數只要聲明一個函數模板：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第一次使用函數模板abs（）時，實參為整數，由此可以推導出函數模板中的參數類型T為整數，函數的返回值也是整數。第二次調用abs()時實參為雙精度型，由此推導出函數模板中的參數類型T為雙精度型，函數的返回值為雙精度型。在主程序中可以這樣使用函數模板：數據成員變成另外一種數據類型，或者干脆是一個類的對象，又要重新拷貝，重新進行修改。這樣不僅程序的代碼數量急劇增加，修改過程中也很容易出現(xiàn)各種疏漏。用一種類似函數模板的機制來結決問題——類模板。C++語言中的類模板的語法定義如下：

Template<模板參數表>

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

模板<模板參數表>對象名1，......對象名n;模板參數表中的內容可以為：

class標識符 類型說明符標識符【

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);//設置類中的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);//構造函數模板

~CStack();//析構函數模板

boolEmpty()const;//棧空判斷

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)//構造函數模板{ if(size_t>0) size=size_t; elsesize=9; top=-1;

ptrStack=newT[size];}template<classT>CStack<T>::~CStack()//析構函數模板{ 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程序運行結果：實現(xiàn)了數組、鏈表、線性表、棧和隊列，它們屬于線性容器。另外，這里還將使用到雙端隊列，就是兩端都可以進行插入和刪除操作的線性表。除了線性容器，我們還將接觸到兩種非線性容器：集合和映射?！?/p>

9.3.1基本數據結構知識】C++的標準模板庫STL包含容器、算法和迭代子，其中容器模板包括鏈表、向量、棧、隊列、集合、映象等，算法模板包括諸如排序、查找等各種算法，而迭代子則可以針對不同容器進行操作。本章將著重介紹STL的使用。【

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

list(鏈表模板)

stack(棧模板)

queue(隊列模板)

deque(雙端隊列模板)

set(集合模板)

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

9.3.2標準模板類庫簡介】STL的算法是用函數模板實現(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容器類之間是通過迭代子來進行溝通的，算法面向迭代子，迭代子則面向容器類,對于迭代子，可以將它理解為一個指針，通過它我們可以獲得容器內部的數據對象，然后算法對這個由迭代子獲得的對象進行操作。STL的主要算法有：C++語言標準類庫提供了向量容器，向量既有象數組一樣可以對容器內部對象進行直接訪問的特點，也有類似于鏈表可以對容器內部對象進行順序訪問的特點，同時向量具有動態(tài)特征，所以C++語言中的向量容器具有數組和鏈表兩者的優(yōu)點。向量模板類中較為重要的成員函數有begin、end、insert、erase、operator［］等。iteratorinsert(iteratorit,constT&x=T());//將x復制到it位置之前voidinsert(iteratorit,sizetypen,constT&x);//將n個x復制到it位置之前voidinsert(iteratorit,constiteratorfirst,constiteratorlast);//將first和last

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

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

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

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

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

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

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

//該向量類型的迭代子

vector<int>::iterator

nItBegin,nItEnd;

//對向量類型對象中的數據進行順序賦值

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

nItBegin=nMyVector1.begin();

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

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的數據

while(nItBegin!=nItEnd) {

cout<<*nItBegin<<"";

nItBegin++; }

cout<<">"<<endl;

//用標準算法得到整型向量對象中所有數據的和

cout<<"ThesumofnMyVector1[i]is:"<<accumulate(nMyVector1.begin(),nMyVector1.end(),0.0f)<<endl; return0;}//源程序結束程序輸出：nMyVetcor2=<12345678910>nMyVetcor1=<12345678910>ThesumofnMyVector1[i]is:55向量應用舉例（二）使用向量數組存儲一個九九乘法表，并打印輸出。//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;}程序運行結果：12436948121651015202561218243036714212835424981624324048566491827364554637281鏈表類中比較重要的成員函數與向量基本相同，但注意鏈表類不包含［］運算符重載，也沒有+=或-=重載，這一點與向量不同。例9-8整型鏈表模板類list<int>應用//EXAMPLE9_8.CPP//源程序開始#include<iostream>#include<list>#include<iterator>usingnamespacestd;//聲明使用std名稱空間intmain(){list<int>nList1,nList2;//整型list

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

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

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

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

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

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

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

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

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

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

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

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

//手機類{public:

例9-10雙端隊列應用舉例【

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

MobileTel(constchar*b,constint&p)

//構造函數

{

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

{

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

{

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

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

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

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

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

boolempty()const;//清空棧【

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

//得到整型棧對象中的數據

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

nMyStack1.push(i);

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

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

cout<<"";

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

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

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

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

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

9.3.7集合與映射】整型集合應用舉例//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; //得到集合類型對象中的數據

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

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

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

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