《C++面向?qū)ο蟪绦蛟O(shè)計(jì)》課件第7章

7.1模板的概念(TemplatesConcept)7.2函數(shù)模板與模板函數(shù)

(FunctionTemplateandTemplateFunction) 7.3類模板與模板類

(ClassTemplateandTemplateClass)7.4標(biāo)準(zhǔn)模板庫(kù)STL(StandardTemplateLibrary)7.5常見編程錯(cuò)誤(CommonProgrammingErrors)本章小結(jié)(ChapterSummary)

習(xí)題7(Exercises7)

模板是C++?語(yǔ)言的一個(gè)重要特性。模板使得程序員能夠快速建立具有類型安全的類庫(kù)集合和函數(shù)集合，是通用程序設(shè)計(jì)的利器。它的實(shí)現(xiàn)，提供了重用程序源代碼的有效方法，方便了更大規(guī)模的軟件開發(fā)。7.1模?板?的?概?念(TemplatesConcept)但宏定義有兩個(gè)問(wèn)題，一是它避開了類型檢查，在某些情況下，會(huì)導(dǎo)致不同類型參數(shù)之間的比較，引起錯(cuò)誤；二是可能在不該替換的地方進(jìn)行了替換，如：

classA

{

intmax(intx,inty);

//…

}同樣，在聲明了一個(gè)類模板之后，可以創(chuàng)建類模板的實(shí)例，它稱為模板類。類模板與模板類的區(qū)別是：類模板是一個(gè)模板，不是一個(gè)實(shí)實(shí)在在的類，其中用到通用類型參數(shù)；而模板類是一個(gè)類，可以由它定義對(duì)象。

模板經(jīng)過(guò)實(shí)例化后就得到模板函數(shù)或模板類，模板函數(shù)或模板類再經(jīng)過(guò)實(shí)例化后就得到對(duì)象。模板、模板類、對(duì)象和模板函數(shù)之間的關(guān)系如圖7-1所示。圖7-1模板、模板類、對(duì)象和模板函數(shù)之間的關(guān)系7.2.1函數(shù)模板的聲明

(DeclarationofFunctionTemplate)

為了定義函數(shù)模板或類模板，首先要進(jìn)行模板說(shuō)明，其作用是說(shuō)明模板中使用的類屬參數(shù)。函數(shù)模板可以用來(lái)創(chuàng)建一個(gè)通用的函數(shù)，以支持多種不同的形參，避免重載函數(shù)的函數(shù)體重復(fù)設(shè)計(jì)。它的最大特點(diǎn)是把函數(shù)使用的數(shù)據(jù)類型作為參數(shù)。7.2函數(shù)模板與模板函數(shù)(FunctionTemplateandTemplateFunction)函數(shù)模板的聲明形式為：

template<typename類型形參表>

<返回類型><函數(shù)名>(參數(shù)表)

{

函數(shù)體

}例如：

template<typenameT>

Tfuc(Tx,inty)

{

Tx;

//…

}如果主調(diào)函數(shù)中有以下語(yǔ)句：

doubled;

inta;

fuc(d,a);

則系統(tǒng)將用實(shí)參d的數(shù)據(jù)類型double去代替函數(shù)模板中的T生成函數(shù)：

doublefuc(doublex,inty)

{

doublex;

//…

}7.2.2函數(shù)模板(FunctionTemplate)

函數(shù)模板定義由模板說(shuō)明和函數(shù)定義組成。所有在模板說(shuō)明的類屬參數(shù)必須在函數(shù)定義中至少出現(xiàn)一次。函數(shù)參數(shù)表中可以使用類屬類型參數(shù)，也可以使用一般類型參數(shù)。

7.2.3模板函數(shù)(TemplateFunction)

函數(shù)模板是對(duì)一組函數(shù)的描述，它以類型作為參數(shù)及函數(shù)返回值類型。它不是一個(gè)實(shí)實(shí)在在的函數(shù)，編譯時(shí)并不產(chǎn)生任何執(zhí)行代碼。當(dāng)編譯系統(tǒng)在程序中發(fā)現(xiàn)有與函數(shù)模板中相匹配的函數(shù)調(diào)用時(shí)，便生成一個(gè)重載函數(shù)。該重載函數(shù)的函數(shù)體與函數(shù)模板的函數(shù)體相同，參數(shù)為具體的數(shù)據(jù)類型。我們稱該重載函數(shù)為模板函數(shù)，它是函數(shù)模板的一個(gè)具體

實(shí)例。【例7-1】

求兩個(gè)數(shù)之中的大值。

程序如下：

//ex7_1.cpp

//Max.h

#include<iostream>

#include<string>

usingnamespacestd;

#ifndefMAX_H

#defineMAX_Htemplate<typenameT>

TMax(Ta,Tb)

{returna>b?a:b;}

#endif

voidmain()

{inta,b;

cout<<"Entertwointeger:\n";

cin>>a>>b;cout<<"Max("<<a<<","<<b<<")="<<Max(a,b)<<endl;

floatx,y;

cout<<"Entertwodouble:\n";

cin>>x>>y;

cout<<"Max("<<x<<","<<y<<")="<<Max(x,y)<<endl;

charc,d;

cout<<"Entertwocharacter:\n";

cin>>c>>d;cout<<"Max("<<c<<","<<d<<")="<<Max(c,d)<<endl;

cout<<"Entertwostrings:\n";

stringg,f;

cin>>g>>f;

cout<<"Max("<<g<<","<<f<<")="<<Max(g,f)<<endl;

}程序的運(yùn)行結(jié)果為：

Entertwointeger:

1245

Max(12,45)=45

Entertwodouble:

3.58.4

Max(3.5,8.4)=8.4Entertwocharacter:

Ab

Max(A,b)=b

Entertwostrings:

goodbetter

Max(good,better)=good

C++語(yǔ)言將根據(jù)“實(shí)參表”中的類型生成一個(gè)重載函數(shù)即模板函數(shù)。該模板函數(shù)的定義體與函數(shù)模板的函數(shù)定義體相同，而“形參表”的類型則以“實(shí)參表”的實(shí)際類型為依據(jù)。

圖7-2給出了函數(shù)模板和模板函數(shù)的關(guān)系示意。其中的重載函數(shù)，通過(guò)函數(shù)模板按實(shí)際類型生成模板函數(shù)，這個(gè)過(guò)程稱為實(shí)例化。編譯程序?qū)嵗蟮哪０搴瘮?shù)自動(dòng)生成目標(biāo)

代碼。圖7-2函數(shù)模板與模板函數(shù)【例7-2】

分析以下程序中的錯(cuò)誤。

#include<iostream>

usingnamespacestd;

template<typenameT>

TMin(Ta,Tb)

{

returna>b?a:b;

}voidmain()

{

intn=3;

chard='a';

doublew=2.4;

cout<<min(n,n)<<endl;

cout<<min(d,d)<<endl;

cout<<min(w,w)<<endl;//error

cout<<min(n,w)<<endl;//error

cout<<min(d,w)<<endl;//error

}【例7-3】

定義冒泡排序法的函數(shù)模板。

程序如下：

#include<iostream>

usingnamespacestd;

#include<stdlib.h>

#include<time.h>template<typenameElementType> //模板說(shuō)明

voidSortBubble(ElementType*a,intsize) //具有類屬類型參數(shù)和整型參數(shù)的參數(shù)表

{inti,work;

ElementTypetemp; //類屬類型變量

for(intpass=1;pass<size;pass++)//對(duì)數(shù)組排序{work=1;

for(i=0;i<size-pass;i++)

if(a[i]>a[i+1])

{temp=a[i];

a[i]=a[i+1];

a[i+1]=temp;

work=0;

}

if(work)break;

}

}voidmain()

{inta[10];

srand(time(0)); //調(diào)用種子函數(shù)

for(inti=0;i<10;i++)a[i]=rand()%100;

//用隨機(jī)函數(shù)初始化數(shù)組

for(i=0;i<10;i++)cout<<a[i]<<“

”;//輸出原始序列

cout<<endl;

SortBubble(a,10);//調(diào)用排序函數(shù)模板

cout<<“AfterOrder:”<<endl;

for(i=0;i<10;i++)cout<<a[i]<<“

”;//輸出排序后序列

cout<<endl;

}程序運(yùn)行結(jié)果為：

83557124961897649277

AfrerOrder:

182455647177839296977.2.4重載函數(shù)模板

(OverloadingFunctionTemplate)

模板函數(shù)與重載是密切相關(guān)的。實(shí)際上，從函數(shù)模板產(chǎn)生的相關(guān)函數(shù)都是同名的，因此C++編譯系統(tǒng)采用重載的方法調(diào)用相應(yīng)函數(shù)。

函數(shù)模板本身可以用多種方式重載，這需要提供其他函數(shù)模板，指定不同參數(shù)的相同函數(shù)名。【例7-4】

使用函數(shù)模板求最大值的程序。

程序如下：

#include<iostream>

usingnamespacestd;

template<typenameT>

Tmax(Tm1,Tm2)

{

return(m1>m2)?m1:m2;

}template<typenameT>

Tmax(Tm1,Tm2,Tm3)

{

Ttemp=max(m1,m2);

returnmax(temp,m3);

}

template<typenameT>

Tmax(Ta[],intn)

{

Tmaxnum=a[0];

for(inti=0;i<n;i++)

if(maxnum<a[i])maxnum=a[i];

returnmaxnum;

}

voidmain()

{

doubled[]={6.6,7.3,5.4,8.8,4.2,7.1,6.9,3.7,1.8,3.5};

inta[]={-7,-6,-4,12,-9,2,-11,-8,-3,18};

charc[]="goodmorning";

cout<<""<<max(12.9,5.4)<<""<<max(12,28)<<""<<max('p','m')<<endl;

cout<<"max(16,34,52)="<<max(16,34,52)<<endl

<<"max(16.2,34.5,52.3)="<<max(16.2,34.5,52.3)<<endl

<<"max('D','B','E')="<<max('D','B','E')<<endl;

cout<<"intarrmax="<<max(a,10)<<"doublemax="<<max(d,10)

<<"charmax="<<max(c,10)<<endl;

}程序運(yùn)行結(jié)果為：

12.928p

max(16,34,52)=52

max(16.2,34.5,52.3)=52.3

max(‘D’,‘B’,‘E’)=E

intarrmax=18doublemax=8.8charmax=r用戶可以用一個(gè)非模板函數(shù)重載一個(gè)同名的函數(shù)模板，例如，可以這樣定義：

template<classT>

Tmax(Ta,Tb)

{

return(a>b)?a：b;

}

intmax(int,int);//顯式地聲明函數(shù)max(int,int)，不是模板函數(shù)

voidf(inti,charc)

{max(i,i); //調(diào)用函數(shù)max(int,int)

max(c,c); //調(diào)用模板max(char,char)

max(i,c); //調(diào)用函數(shù)max(int,int)

max(c,i); //調(diào)用函數(shù)max(int,int)

}這里，非模板函數(shù)max(int,int)重載了上述的函數(shù)模板max(Ta,Tb)，當(dāng)出現(xiàn)調(diào)用語(yǔ)句：max(i,c);和max(c,i);時(shí)，它執(zhí)行的是重載的非模板函數(shù)版本max(int,int)。還可以定義如下函數(shù)：

charmax(char*x,char*y)

{

return(strcmp(x,y)>0)?x:y;

}

7.3.1類模板的定義

(DefinitionofClassTemplate)

類模板的成員函數(shù)被認(rèn)為是函數(shù)模板，也稱為類屬函數(shù)。因此，當(dāng)給出一個(gè)類模板的成員函數(shù)的定義時(shí)，必須遵循函數(shù)模板的定義。7.3類模板與模板類(ClassTemplateandTemplateClass)定義類模板的一般格式如下：

template<類型形參表>

class類名

{

類聲明體;

};

template類型形參表

返回類型類名類型名表::成員函數(shù)(形參表)

{

成員函數(shù)定義體;

}

【例7-5】

求一個(gè)數(shù)的平方是算法中經(jīng)常要用到的基本單元。對(duì)于int型和double型分別需要兩個(gè)類來(lái)實(shí)現(xiàn)，類Square1實(shí)現(xiàn)求int型數(shù)據(jù)的平方，類Square2實(shí)現(xiàn)求double型數(shù)據(jù)的平方。如果采用類模板來(lái)實(shí)現(xiàn)，則只需要一次即可以實(shí)現(xiàn)。程序如下：

classSquare1

{

public:

Square1(inty):x(y){}

intfun()

{

returnx*x;

}

private:

intx;

};classSquare2

{

public:

Square(doubley):x(y){}

doublefun()

{

returnx*x;

}

private:

doublex;

};采用類模板的方式實(shí)現(xiàn)：

template<classT> //T為模板參數(shù)

classSquare

{

public:

Square(Ty):x(y){}

//T的具體類型根據(jù)類模板的調(diào)用情況確定

Tfun()

{

returnx*x;

}

private:

Tx;

};模板類的成員函數(shù)必須是函數(shù)模板。類模板中的成員函數(shù)的定義，若放在類模板的定義之中，則與類的成員函數(shù)的定義方法相同；若在類模板之外定義，則成員函數(shù)的定義格式如下：

類名：template<模板形參表>

返回值類型類模板名類型名表：成員函數(shù)名(參數(shù)表)

{

成員函數(shù)體

}7.3.2類模板的使用(UsageofClassTemplate)

類模板也不能直接使用，必須先實(shí)例化為相應(yīng)的模板類，定義該模板類的對(duì)象后才能使用。使用類模板是指用某一數(shù)據(jù)類型替代類模板的類型參數(shù)，聲明類模板之后創(chuàng)建模板類，一般格式如下：

<類模板名><類型實(shí)參表>由類模板經(jīng)實(shí)例化而生成的具體類稱為模板類，格式為：

<類模板名><類型實(shí)參表><對(duì)象名>[(<實(shí)參表>)]

其中，“類型實(shí)參表”應(yīng)與該類模板中的“類型形參表”相匹配?！皩?duì)象名”是定義該模板類的一個(gè)或多個(gè)對(duì)象。【例7-6】

定義一個(gè)數(shù)組類模板，了解類模板的實(shí)際作用。

程序如下：

//通用數(shù)組類

#include<iostream>

#include<cstdlib>

usingnamespacestd;

constintsize=10;

template<typenameAType>classatype //模板類

{

public:

atype()

{

inti;

for(i=0;i<size;i++)array[i]=i;

}

AType&operator[](intn);

private:

ATypearray[size];

};template<typenameAType>AType&atype<AType>::operator[](intn)

{

//下標(biāo)越界檢查

if(n<0||n>=size)

{cout<<"下標(biāo)"<<n<<"超出范圍!"<<endl;

exit(1);

}

returnarray[n];

}

intmain()

{

atype<int>intob;

//integer數(shù)組類，intob為該類的一個(gè)對(duì)象

atype<double>doubleob;

//double數(shù)組類，doubleob為該類的一個(gè)對(duì)象

inti;

cout<<"Integer數(shù)組:";

for(i=0;i<size;i++)intob[i]=i;

for(i=0;i<size;i++)

cout<<intob[i]<<"";

cout<<endl;

cout<<"Double數(shù)組:";

for(i=0;i<size;i++)

doubleob[i]=(double)i/2;

for(i=0;i<size;i++)

cout<<doubleob[i]<<"";

cout<<endl;

intob[12]=100; //下標(biāo)越界

return0;

}程序運(yùn)行結(jié)果：

Integer數(shù)組：0123456789

Dounle數(shù)組：00.511.522.533.544.5

下標(biāo)12超出范圍！程序說(shuō)明：該程序定義了一個(gè)類模板atype(AType)，模板參數(shù)為AType。其中語(yǔ)句“atype<int>intob”是用實(shí)際類型參數(shù)int替換類模板atype的模板參數(shù)AType，將類模板atype(AType)實(shí)例化為下面的模板類：

classatype

{

public:

atype();

int&operator[](intn);

private:

intarray[size];

}然后，表達(dá)式intob調(diào)用構(gòu)造函數(shù)，創(chuàng)建模板類對(duì)象intob。同理，主函數(shù)中的語(yǔ)句“atype<double>doubleob;”將類模板atype(AType)實(shí)例化為下面的模板類，并創(chuàng)建類對(duì)象doubleob：

classatype

{

public:

atype();

double&operator[](intn);

private:

doublearray[size];

};因此說(shuō)，類模板的實(shí)例化創(chuàng)建的結(jié)果是一種類型，而類的實(shí)例化創(chuàng)建的結(jié)果則是一個(gè)對(duì)象。類模板、模板類和對(duì)象三者的邏輯關(guān)系如圖7-3所示。圖7-3類模板、模板類和對(duì)象三者之間的邏輯關(guān)系7.3.3類模板的友元(FriendofClassTemplate)

類模板的友元和類的友元的特點(diǎn)基本相同，但也具有自身的特殊情況。

【例7-7】

包含友元函數(shù)的類模板舉例。

程序如下：

#include<iostream>

#include<iomanip>

#include<cstdlib>

usingnamespacestd;

constintLen=16;template<classT> //模板定義

classSeqLn //順序表類模板

{

public:

SeqLn<T>():size(0){}//類模板的構(gòu)造函數(shù)

~SeqLn<T>(){} //類模板的析構(gòu)函數(shù)

voidInsert(constT&m,constintnst); //數(shù)據(jù)類型為模板形參T

TDelete(constintnst); //返回值類型為模板形參T

intLnSize()const

{

returnsize;

}

private:

//轉(zhuǎn)換函數(shù)模板的聲明

friendvoidIntToDouble(SeqLn<int>&n,SeqLn<double>&da);

friendvoidDisplay(SeqLn<T>&mySeqLn);

//類模板的友元

friendvoidSuccess();

//類模板的友元

private:

Tarr[Len];

//數(shù)據(jù)元素為模板形參T

intsize;

};template<classT> //成員函數(shù)的模板定義

voidSeqLn<T>::Insert(constT&m,constintnst)

{

if(nst<0||nst>size)

{

cerr<<"nstError!"<<endl;

exit(1);

}

if(size==Len)

{

cerr<<"theListisover,can'tinsertanydata!"<<endl;

exit(1);

}

for(inti=size;i>nst;i--)arr[i]=arr[i-1];

arr[nst]=m;

size++;

}template<classT> //成員函數(shù)的模板定義

TSeqLn<T>::Delete(constintnst)

{

if(nst<0||nst>size-1)

{

cerr<<"nstError!"<<endl;

exit(1);

}

if(size==0)

{

cerr<<"theListisnull,nodatacanbedeleted!"<<endl;

exit(1);

}

Ttemp=arr[nst];

for(inti=nst;i<size-1;i++)

arr[i]=arr[i+1];

size--;

returntemp;

}voidSuccess()

{

cout<<"theTransformisover."<<endl;

}

template<classT>

voidDisplay(SeqLn<T>&mySeqLn)

{

for(inti=0;i<mySeqLn.size;i++)

{

cout<<setw(5)<<mySeqLn.arr[i];

if((i+1)%8==0) //每行輸出8個(gè)元素

cout<<endl;

}

}

template<classT1,classT2> //函數(shù)模板的模板定義

voidIntToDouble(SeqLn<T1>&n,SeqLn<T2>&da)

{

da.size=n.size;

for(inti=0;i<n.size;i++)

da.arr[i]=double(n.arr[i]);

}

intmain()

{

SeqLn<int>i_List;//定義int型順序表類對(duì)象

SeqLn<double>d_List;

//定義double型順序表類對(duì)象

for(inti=0;i<Len;i++)

i_List.Insert(i,0);

IntToDouble(i_List,d_List);

Success();

Display(d_List); //輸出轉(zhuǎn)換后的結(jié)果

d_List.Delete(2); //執(zhí)行刪除操作

Display(d_List); //輸出刪除以后的結(jié)果

return0;

}程序運(yùn)行結(jié)果為：

TheTransformisover.

15141312111098

76543310

1514121110987

65433107.3.4類模板與靜態(tài)成員

(ClassTemplateandStaticMember)

在非模板類中，類的所有對(duì)象共享一個(gè)靜態(tài)數(shù)據(jù)成員，靜態(tài)數(shù)據(jù)成員應(yīng)在文件范圍內(nèi)初始化。

【例7-8】

類模板中含有靜態(tài)數(shù)據(jù)成員示例。

程序如下：

#include<iostream>

usingnamespacestd;

template<classT>

classA

{

Tm;

staticTn;

public

:

A(Ta)

:m(a){n+=m}

voiddisp()

{cout<<"m="<<m<<",n="<<n<<endl;}

};

template<classT>

TA<T>

::n=0;

intmain()

{

A<int>a(2),b(3);

a.disp();

b.disp();

A<double>c(1.6),d(5.4);

c.disp();

d.disp();

return0;

}程序運(yùn)行結(jié)果為：

m=2,n=5

m=3,n=5

m=1.6,n=7

m=5.4,n=77.4.1容器(Containers)

容器是數(shù)據(jù)結(jié)構(gòu)，是包含一組元素或元素集合的對(duì)象。容器類中包含一組元素或一個(gè)元素集合，作為通用元素收集器(genericholder)。C++語(yǔ)言的容器類中可以包含混合類型的元素，即容器類可以包含一組不同類型的元素或一組相同類型的元素。7.4標(biāo)準(zhǔn)模板庫(kù)STL(StandardTemplateLibrary)

1．容器的分類

在C++標(biāo)準(zhǔn)庫(kù)中包括7種基本容器：向量(vector)、雙端隊(duì)列(deque)、列表(list)、集合(set)、多重集合(multiset)、映射(map)和多重映射(multimap)等。

(1)?C++提供的順序類型容器有向量(vector)、鏈表(list)、雙端隊(duì)列(deque)。

(2)關(guān)聯(lián)容器主要包括集合(set)、多重集合(multiset)。

(3)容器適配器主要指堆棧(stack)和隊(duì)列(queue)，見表7-1。表7-1STL中的容器及頭文件名

2．容器的接口

STL經(jīng)過(guò)精心設(shè)計(jì)，使容器提供類似的功能。許多一般化的操作所有容器都適用，也有些操作是為某些容器特別設(shè)定。只有了解接口函數(shù)的原型，才能正確地使用標(biāo)準(zhǔn)模板庫(kù)的組件編程。標(biāo)準(zhǔn)容器類定義的公有函數(shù)見表7-2，表7-3是順序和關(guān)聯(lián)容器共同支持的成員函數(shù)。表7-2標(biāo)準(zhǔn)容器類定義的公有函數(shù)表7-3順序和關(guān)聯(lián)容器共同支持的成員函數(shù)

3．順序容器

順序容器將一組具有相同類型的元素以嚴(yán)格的線性形式組織起來(lái)。

1)向量容器(vector)

容器類庫(kù)中的向量容器包含有以下4種構(gòu)造函數(shù)：

(1)?vector()；默認(rèn)構(gòu)造函數(shù)，它創(chuàng)建大小為零的向量容器。

(2)?vector(size_typen,constT&value=T())；初始化了大小為n的向量，第二個(gè)參數(shù)是每個(gè)對(duì)象的初始值，默認(rèn)為T()構(gòu)造的對(duì)象。

(3)?vector(constvector&x)；拷貝構(gòu)造函數(shù)，用常數(shù)向量x來(lái)初始化此向量。

(4)?vector(constiteratorfirst,constiteratorlast)；從支持常數(shù)迭代器conat_iterator的容器中選取一部分來(lái)建立一個(gè)新的向量?！纠?-9】

應(yīng)用向量容器求2～n之間的素?cái)?shù)。

程序如下：

#include<iostream>

#include<iomanip>

#include<vector> //包含向量容器頭文件

usingnamespacestd;

voidmain(void)

{

vector<int>A(10);

//用來(lái)存放質(zhì)數(shù)的向量，初始狀態(tài)有10個(gè)元素

intn; //質(zhì)數(shù)范圍的上限，運(yùn)行時(shí)輸入

intprimecount=0,i,j;

cout<<"Enteravalue>=2asupperlimitforprimenumbers:";

cin>>n;

A[primecount++]=2; //2是一個(gè)質(zhì)數(shù)

for(i=3;i<n;i++)

{

if(primecount==A.size())

//如果質(zhì)數(shù)表已滿，則再申請(qǐng)10個(gè)元素的空間

A.resize(primecount+10);

if(i%2==0)

//大于2的偶數(shù)不是質(zhì)數(shù)，因此略過(guò)本次循環(huán)的后繼部分

continue; //檢查3,5,7,...,i/2是否i的因子

j=3;

while(j<=i/2&&i%j!=0)

j+=2;

if(j>i/2) //若上述參數(shù)均不為i的因子，則i為質(zhì)數(shù)

A[primecount++]=i;

}

for(i=0;i<primecount;i++) //輸出質(zhì)數(shù)

{

cout<<setw(5)<<A[i];

if((i+1)%10==0) //每輸出10個(gè)數(shù)換行一次

cout<<endl;

}

cout<<endl;

}程序運(yùn)行結(jié)果：

Enteravalue>=2asupperlimitforprimenumbers:100

2

3

5 8

11

13

17

1923

29

31

37

41 43

47

53 596167 71

737983 8997

2)雙端隊(duì)列容器(deque)

雙端隊(duì)列容器是一種放松了訪問(wèn)權(quán)限的隊(duì)列。

雙端隊(duì)列容器包含以下有4種形式的構(gòu)造函數(shù)：

(1)?deque()；構(gòu)造size()為0的雙端隊(duì)列容器。

(2)?deque(size-typen，constT&v=T())；初始化大小為n的雙端隊(duì)列，第二個(gè)參數(shù)是每個(gè)元素的初始值，默認(rèn)為T()構(gòu)造的對(duì)象。

(3)?deque(constdeque&x)；拷貝構(gòu)造函數(shù)，用雙端隊(duì)列x來(lái)初始化此雙端隊(duì)列容器。

(4)?deque(constiteratorfirst，constiteratorlast)；從另一個(gè)支持constiterator的容器中選取一部分來(lái)建立一個(gè)新的雙端隊(duì)列容器。【例7-10】

使用雙端隊(duì)列容器保存雙精度數(shù)值序列。

程序如下：

#include<iostream>

#include<deque> //包含雙端隊(duì)列容器頭文件

#include<algorithm> //包含算法頭文件

usingnamespacestd;

intmain()

{

deque<double>values;//聲明一個(gè)雙精度型deque序列容器

ostream_iterator<double>output(cout,“

”);

values.push_front(2.2);

//應(yīng)用函數(shù)push_front在deque容器開頭插入元素

values.push_front(3.5);

values.push_back(1.1);

//應(yīng)用函數(shù)push_back在deque容器結(jié)尾插入元素

cout<<"valuescontains:";

for(inti=0;i<values.size();++i)

cout<<values[i]<<'';

values.pop_front();

//應(yīng)用函數(shù)push_front從deque容器中刪除第一個(gè)元素

cout<<“\nAfterpop_frontvaluescontains:”;

copy(values.begin(),values.end(),output);

values[1]=5.4;

//應(yīng)用操作符[]來(lái)重新賦值

cout<<"\nAftervalues[1]=5.4valuescontains:";

copy(values.begin(),values.end(),output);

cout<<endl;

return0;

}程序運(yùn)行結(jié)果為：

Valuescontains:3.52.2 1.1

Afterpop_frontvaluescontains:2.2 1.1

Aftervalues[1]=5.4valuescontains:2.2 5.4

3)列表容器(list)

列表容器由雙向鏈表構(gòu)成，因此可以從鏈表的任意一端開始遍歷。

與向量容器和雙端隊(duì)列容器一樣，列表容器也有4種形式的構(gòu)造函數(shù)：

(1)?list()；構(gòu)造size()為0的列表容器。

(2)?list(size-typen，constT&v=T())；初始化一個(gè)大小為n的列表容器，把列表容器中的每個(gè)對(duì)象初始化為T()構(gòu)造的對(duì)象。

(3)?list(constlist&x)；按另一個(gè)列表容器x初始化列表。

(4)?list(const_iteratorfirst，constiteratorlast)；從另一個(gè)支持constiterator的容器中選取一部分來(lái)建立一個(gè)新的列表容器。

由于列表容器是順序訪問(wèn)的容器，因此與向量容器不同，它沒(méi)有capacity()、operator[]和at()這幾個(gè)成員函數(shù)。除此之外，列表容器的訪問(wèn)函數(shù)與向量容器的訪問(wèn)函數(shù)相同，有begin()、end()、rbegin()rend()size()、max_size()、empty()、front()和back()等?！纠?-11】

利用標(biāo)準(zhǔn)C++庫(kù)中的列表容器list對(duì)鏈表進(jìn)行操作。

程序如下：

#include<iterator>

#include<list>

usingnamespacestd;

intmain()

{

inti;

list<int>list1,list2;

list<int>::iteratoriter;

//iter是list用的迭代器，自動(dòng)建為雙向訪問(wèn)迭代器

intarr1[]={5,7,17,19,23,43};

intarr2[]={3,9,13,29,41};

for(i=0;i<6;i++)list1.push_back(arr1[i]);

for(i=0;i<5;i++)list2.push_front(arr2[i]);

for(iter=list1.begin();iter!=list1.end();iter++)cout<<*iter<<'\t';

cout<<endl;

for(iter=list2.begin();iter!=list2.end();iter++)cout<<*iter<<'\t';3

cout<<endl;

list1.splice(list1.begin(),list2);

//list2拼接到list1前

for(iter=list1.begin();iter!=list1.end();iter++)cout<<*iter<<'\t';

cout<<endl;

return0;

}程序運(yùn)行結(jié)果為：

5 7 17 19 23 43

41 29 13 9 3

41 29 13 9 35 7

17

19 23

437.4.2迭代器(Iterators)

理解迭代器對(duì)于理解STL框架并掌握STL的使用至關(guān)重要。簡(jiǎn)單地說(shuō)，迭代器是面向?qū)ο蟀姹镜闹羔?，STL算法利用迭代器對(duì)存儲(chǔ)在容器中的元素序列進(jìn)行遍歷，迭代器提供了訪問(wèn)容器和序列中每個(gè)元素的方法。

1．代器的類型

為了滿足某些特定算法的需要，STL迭代器主要包括5種基本迭代器類別：輸入、輸出、前向、雙向和隨機(jī)訪問(wèn)迭代器，以及兩種迭代器適配器(iteratoradapters)：逆向迭代器適配器和插入迭代器適配器。各類迭代器及功能見表7-4。表7-45種基本迭代器表7-4中定義的各種迭代器可執(zhí)行的操作如表7-5所示，從表中可清楚地看出，從輸入/輸出迭代器到隨機(jī)訪問(wèn)迭代器的功能逐步加強(qiáng)。對(duì)比指針對(duì)數(shù)組的操作，兩者的—致性十分明顯。表7-5各類迭代器可執(zhí)行的操作【例7-12】

應(yīng)用逆向迭代器和后插入迭代器。

程序如下：

#include<iostream>

#include<vector>

#include<algorithm>

usingnamespacestd;

voidmain()

{

intA[]={1,2,3,4,5};

constintN=sizeof(A)/sizeof(int);

vector<int>col1(A,A+N);

ostream_iterator<int>output(cout,"");

vector<int>::iteratoriter;

vector<int>::reverse_iteratorr_iter;//定義vector逆向迭代器

cout<<"Listcol1contains:";

copy(col1.begin(),col1.end(),output);

//輸出初始向量容器col1中的元素

iter=col1.begin(); //定義指向初始元素的迭代器

cout<<"\nThefistelementis:"<<*iter;

//輸出第一個(gè)元素

r_iter=col1.rbegin();//逆向迭代器指向最后一個(gè)元素

cout<<"\nThelastelementis:"<<*r_iter<<endl;

//輸出最后一個(gè)元素

back_insert_iterator<vector<int>>b_iter(col1);

//聲明后插迭代器

*b_iter=23;

back_inserter(col1)=16;

copy(col1.begin(),col1.end(),output);

//輸出后插操作后的向量容器col1中的元素

cout<<endl;

for(r_iter=col1.rbegin();r_iter!=col1.rend();r_iter++)

//逆向輸出向量容器col1中的元素

cout<<*r_iter<<'';

cout<<endl;

}程序運(yùn)行結(jié)果為：

Listcol1contains:12345

Thefirstelementis:1

Thelastelementis:5

123452316

162354321

2．迭代器相關(guān)的輔助函數(shù)

C++標(biāo)準(zhǔn)程序庫(kù)為迭代器提供了三個(gè)輔助函數(shù)：advance()、distance()和iter_swap()。前兩個(gè)函數(shù)提供了所有迭代器一些原本只有隨機(jī)訪問(wèn)迭代器才有的訪問(wèn)能力，即前進(jìn)或后退多個(gè)元素，以及處理迭代器之間的距離。第三個(gè)輔助函數(shù)允許用戶交換兩個(gè)迭代器的值。表7-6列出了三個(gè)輔助函數(shù)的功能及函數(shù)原型。表7-6三個(gè)輔助函數(shù)【例7-13】

用三個(gè)迭代器輔助函數(shù)操作列表容器中的元素。

程序如下：

#include<iostream>

#include<list>

#include<algorithm>

usingnamespacestd;

intmain()

{

intA[]={1,2,3,4,5};

constintN=sizeof(A)/sizeof(int);

list<int>col1(A,A+N);

ostream_iterator<int>output(cout,"");

cout<<"Listcol1contains:";

copy(col1.begin(),col1.end(),output);

//輸出初始列表容器col1中的元素

list<int>::iteratorpos=col1.begin();

//定義指向初始元素的迭代器

cout<<"\nThefistelementis:"<<*pos;

//輸出第一個(gè)元素

advance(pos,3);

//前進(jìn)三個(gè)元素，指向第四個(gè)元素

cout<<"\nThe4thelementis:"<<*pos;

//輸出第四個(gè)元素

cout<<"\nTheadvanceddistanceis:"<<distance(col1.begin(),pos);

//輸出當(dāng)前迭代器位置與初始位置的距離

iter_swap(col1.begin(),--col1.end());

//交換列表容器中第一個(gè)元素和最后一個(gè)元素

cout<<"\nAfterexchangeListcol1contains:";

copy(col1.begin(),col1.end(),output);

//輸出交換元素后列表容器col1中的元素

cout<<endl;

return();

}程序運(yùn)行結(jié)果：

Listcol1contains:12345

Thefirstelementis:1

The4thelementis:4

Theadvanceddistanceis:3

AfterexchangeListcol1contains523417.4.3算法(Algorithms)

STL算法是通用的，每個(gè)算法都適合于若干種不同的數(shù)據(jù)結(jié)構(gòu)，而不是僅僅能夠用于一種數(shù)據(jù)結(jié)構(gòu)。

1．不可變序列算法

不可變序列算法(Non-mutatingAlgorithm)是指不直接修改所操作的容器內(nèi)容的算法。表7-7是該類算法的功能列表。表7-7不變序列算法表【例7-14】

不可變序列算法對(duì)數(shù)據(jù)進(jìn)行處理。

程序如下：

#include<iostream>

#include<algorithm>

#include<functional>

#include<vector>

usingnamespacestd;

intmain()

{

intiarray[]={0,1,2,3,3,4,5,6,6,6,7,8};

vector<int>ivector(iarray,iarray+sizeof(iarray)/sizeof(int));

//找出ivector之中相鄰元素值相等的第一個(gè)元素

cout<<*adjacent_find(ivector.begin(),ivector.end())<<endl;

//找出ivector之中元素值為6的元素個(gè)數(shù)

cout<<count(ivector.begin(),ivector.end(),6)<<endl;

//找出ivector之中小于7的元素個(gè)數(shù)

cout<<count_if(ivector.begin(),ivector.end(),bind2nd(less<int>(),7))<<endl;

return0;

}程序運(yùn)行結(jié)果為：

3

3

10

2．可變序列算法

可變序列算法(MutatingAlgorithm)可以修改它們所操作的容器的元素。表7-8給出了這類算法中包含的通用算法的功能列表。表7-8可變序列算法表【例7-15】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é)果為：

237841159113

237841159

3．排序相關(guān)算法

STL中有一系列算法都與排序有關(guān)，其中包括對(duì)序列進(jìn)行排序及合并的算法、搜索算法、有序序列的集合操作以及堆操作相關(guān)算法。表7-9給出這些算法的功能列表。表7-9排序相關(guān)算法表【例7-16】

排序算法的應(yīng)用。

程序如下：

#include<iostream>

#include<algorithm>

#include<functional>

#include<vector>

usingnamespacestd;

intmain()

{

intiarray[]={26,17,15,22,23,33,32,40};

vector<int>ivector(iarray,iarray+sizeof(iarray)/sizeof(int));

copy(ivector.begin(),ivector.end(),ostream_iterator<int>(cout,""));

cout<<endl;

//查找并輸出最大、最小值元素

cout<<*max_element(ivector.begin(),ivector.end())<<endl;

//將ivector.begin()+4-ivector.begin()各元素排序，放進(jìn)[ivector.begin(),ivector.begin()+4]區(qū)間。

//剩余元素不保證維持原來(lái)相對(duì)次序

partial_sort(ivector.begin(),ivector.begin()+3,ivector.end());

copy(ivector.begin(),ivector.end(),ostream_iterator<int>(cout,""));

cout<<endl;

//局部排序并復(fù)制到別處

vector<int>ivector1(5);

partial_sort_copy(ivector.begin(),ivector.end(),ivector1.begin(),ivector1.end());

copy(ivector1.begin(),ivector1.end(),ostream_iterator<int>(cout,""));

cout<<endl;

//將指定元素插入到區(qū)間內(nèi)不影響區(qū)間原來(lái)排序的最低、最高位置

cout<<*lower_bound(ivector.begin(),ivector.end(),24)<<endl;

//合并兩個(gè)序列ivector和ivector1，并將結(jié)果放到ivector2中

vector<int>ivector2(13);

merge(ivector.begin(),ivector.end(),ivector1.begin(),ivector1.end(),ivector2.begin());

copy(ivector2.begin(),ivector2.end(),ostream_iterator<int>(cout,""));

cout<<endl;

return0;

}程序運(yùn)行結(jié)果為：

2617152223333240

40

1517222623333240

1517222326

33

15151717222223262326333240

4．?dāng)?shù)值算法

STL提供了四個(gè)通用數(shù)值算法。這四個(gè)算法在numneric頭文件中定義。表7-10給出了這類算法的功能。表7-10數(shù)?值?算?法?表【例7-17】

應(yīng)用數(shù)值算法對(duì)數(shù)據(jù)序列進(jìn)行操作。

程序如下：

#include<iostream>

#include<numeric>

#include<functional>

#include<vector>

usingnamespacestd;

intmain()

{

intiarray[]={1,2,3,4,5};

vector<int>ivector(iarray,iarray+sizeof(iarray)/sizeof(int));

//元素的累計(jì)

cout<<accumulate(ivector.begin(),ivector.end(),0)<<endl;

//向量的內(nèi)積

cout<<inner_product(ivector.begin(),ivector.end(),ivector.begin(),10)<<endl;

//向量容器中元素局部求和

partial_sum(ivector.begin(),ivector.end(),ostream_iterator<int>(cout,“

”));

cout<<endl;

return0;

}

程序運(yùn)行結(jié)果為：

15

65

13610157.4.4適配器(Adapters)

STL提供了可用于容器、迭代器和函數(shù)對(duì)象的不同的適配器類。

【例7-18】

在向量、雙端隊(duì)列和列表容器中使用的堆棧和隊(duì)列適配器示例。

程序如下：

#include<iostream>

#include<vector>

#include<stack>

#include<list>

#include<queue>usingnamespacestd;

intmain()

{

typedefvector<char>vchar; //向量容器類型

stack<int>dqStack;

stack<char,vchar>vecStack;

charad[]="CONTAINERADAPTOR";

cout<<"*Usingstackadaptorwithdequeandvectorcontainers*";

cout<<"\nPushingvaluesintocontainers…"<<endl;

for(inti=0;i<10;i++)

{

dqStack.push((i+1)*2);

vecStack.push(ad[i]);

}

cout<<"Removingvaluesfromcontainers…"<<endl;

cout<<"\ndequecontainer=>";

while(!dqStack.empty())

{

cout<<dqStack.top()<<'';

dqStack.pop();

}

cout<<"\nvectorcontainer=>";

while(!vecStack.empty())

{

cout<<vecStack.top()<<'';

vecStack.pop();

}

typedeflist<double>lstf;//listcontainertype

queue<double,lstf>lstQueue;//queueadaptorwithalist

doublevalues[5]={1.1,2.2,3.3,4.4,5.5};

cout<<"\n\n*Usingqueueadaptprwithlistcontainer*"<<endl;

cout<<"Pushingvaluesintocontainer…"<<endl;

for(intj=0;j<5;j++)

{

lstQueue.push(values[j]);

}

cout<<"Removingvaluesfromcontainer…"<<endl;

cout<<"\nlistcontainer=>";

while(!lstQueue.empty())

{

cout<<lstQueue.front()<<'';

lstQueue.pop();

}

cout<<"\n\n";

return0;

}程序運(yùn)行結(jié)果為：

*Usingstackadaptorwithdequeandvectorcontainers*

Pushingvaluesintocontainers…

Removingvaluesfromcontainers…

dequecontainer=>2018161412108642

vectorcontainer=>ARENIATNOC*Usingqueueadaptprwithlistcontainer*

Pushingvaluesintocontainer…

Removingvaluesfromcontainer…1．模板頭使用一對(duì)尖括號(hào)<>，而不是{}或[]，以下寫法是錯(cuò)誤的：

template{classT} //****ERROR:shouldbe<classT>

classA{

//…

};

template[classT]//****ERROR:shouldbe<classT>

classZ{

//…

};7.5常見編程錯(cuò)誤(CommonProgrammingErrors)

2．在模板頭中指定模板參數(shù)時(shí)，不能省略關(guān)鍵字class或typename，以下寫法是錯(cuò)誤的：

template<T>//****ERROR:keywordclassmissing

classC{

//…

};

3．在模板類的聲明之處定義成員函數(shù)時(shí)，不能省略模板頭，以下寫法是錯(cuò)誤的：

template<classT>classArray{

public:

voidm(); //declaration

//…};

//****ERROR:templateheadermissing

voidArray<T>::,m(){…} //definition正確的寫法是：

template<classT>

classArray{

public:

voidm(); //declaration

//…};

template<classT>

voidArray<T>::m(){…}//definition

4．在模板類的聲明之外定義成員函數(shù)時(shí)，類名必須出現(xiàn)在模板名和域解析符之間，以下寫法是錯(cuò)誤的：

template<classT>classArray{

public:

voidm();//declaration

//…};

//****ERRORshouldbeArray<T>::m()

template<classT>

voidArray::,m(){…}

5．模板類至少有一個(gè)類參數(shù)，以下寫法是錯(cuò)誤的：

template<intx>//****ERROR:noclassparameter

classC{

//…

};

6．如果模板類有多個(gè)參數(shù)，必須用逗號(hào)分開，以下寫法是錯(cuò)誤的：

template<classTintx>//****ERROR:nocomma

classC{

//…

};

7．模板類的每個(gè)函數(shù)型參數(shù)，不管是內(nèi)置的還是自定義的，都必須在模板頭中指定其數(shù)據(jù)類型，以下寫法是錯(cuò)誤的：

template<classT,x> //****ERROR:nodatatypeforx

classC{

//…};

8．只能定義一個(gè)模板類實(shí)例對(duì)象，不能定義一個(gè)模板類的對(duì)象，以下寫法是錯(cuò)誤的：

template<classT>

classArray{

//};

Arraya1; //****ERROR:notaninstantiation

Array<T>a2; //****ERROR:notaninstantiation

template<classT>

Array<T>a3; //****ERROR:notaninstantiation

Array<int>a4; //ok

9．要引用某個(gè)STL部件，必須包含新的C++風(fēng)格的合適的#include，而不是舊風(fēng)格的頭文件。模板是C++?類型參數(shù)化的多態(tài)工具。所謂類型參數(shù)化，是指一段程序可以處理在一定范圍內(nèi)的各種類型的數(shù)據(jù)對(duì)象，這些數(shù)據(jù)對(duì)象呈現(xiàn)相同的邏輯結(jié)構(gòu)。函數(shù)模板和類模板可以聲明為非模板類的友元。使用類模板，可以聲明各種各樣的友元關(guān)系。在C++?中，一個(gè)發(fā)展趨勢(shì)是使用標(biāo)準(zhǔn)模板類庫(kù)(STL)，VC和BC都把它作為編譯器的一部分。本章小結(jié)(ChapterSummary)一、選擇題

1．關(guān)于函數(shù)模板，描述錯(cuò)誤的是()。

A.函數(shù)模板必須由程序員實(shí)例化為可執(zhí)行的函數(shù)模板

B.函數(shù)模板的實(shí)例化由編譯器實(shí)現(xiàn)

C.一個(gè)類定義中，只要有一個(gè)函數(shù)模板，則這個(gè)類是類模板

D.類模板的成員函數(shù)都是函數(shù)模板，類模板實(shí)例化后，成員函數(shù)也隨之實(shí)例化習(xí)題7(Exercises7)2．下列的模板說(shuō)明中，正確的是()。

A.

template<typenameT1,T2>

B.

template<classT1,T2>

C.