大二6系下課件與第五章

C++與C＃1第五章模板2int

min(

int

a,

int

b

){return

a

<b

?a

:b;}double

min(

double

a,

double

b

){return

a

<b

?a

:b;}需要為每一種數(shù)據(jù)類型定義一個(gè)min函數(shù)例：求兩個(gè)數(shù)的最小值參數(shù)個(gè)數(shù)、處理流程相同3?

min(

?

a,

?

b

){return

a

<

b

?

a

:

b;}函數(shù)參數(shù)類型或返

回類型能否在函數(shù)

定義時(shí)不明確指定，當(dāng)調(diào)用時(shí)根據(jù)實(shí)參再確定？45.1函數(shù)模板template

<

class

Type

>Typemin(

Type

a,

Typeb){return

a

<b

?a

:b;}5.1.1函數(shù)模板定義：將函數(shù)參數(shù)類型或返回類型參數(shù)化關(guān)鍵字template總是放在模板的定義與聲明的最前面；關(guān)鍵字后面是用逗號(hào)分隔的模板參數(shù)表，它用尖括號(hào)<>括起來(lái)；每個(gè)模板類型參數(shù)由關(guān)鍵字

class或typename開頭，參數(shù)名是用戶自定義的標(biāo)識(shí)符。template

<

typename

Parm

>Parm

min(Parma,

Parmb

){return

a

<b

?a

:b;}5template

<

class

Type

>Typemin(

Type

a,

Typeb){return

a

<b

?a

:b;}void

main

(

){int

ri

=

min(

10,

20

);double

rd=

min

(

10.2,20.1

);}//int

min

(

int

,

int

);//

double

min

(

double

,

double

);模板實(shí)例化6template

<

class

T1,

class

T2,

class

T3

>T1

sum(

T2

a,

T3

b){T1

s;s

=

a+b;return

s;}模板類型參數(shù)7在模板定義中的使用方式和一般類型相同注意：函數(shù)參數(shù)類型可以被部分參數(shù)化，但模板參數(shù)表不能為空。例：求一數(shù)組中的最小值。8int

min

(

const

int

array[

10

]

){int

min_val

=

array[0];for

(int

i=1;

i<10;i++)if(array[i]<min_val)min_val

=

array[i];return

min_val;}int

min

(

const

int

array[

],

int

size

){int

min_val

=

array[0];for

(int

i=1;

i<size;

i++)if(array[i]<min_val)min_val

=

array[i];return

min_val;}template

<

class

Type>Type

min

(

const

Type

array[],

int

size

){Type

min_val=array[0];for

(int

i=1;

i<size;

i++)if(array[i]<min_val)min_val

=

array[i];return

min_val;}int

min(

const

int

(

&r_array

)

[10]

){int

min_val

=

r_array[0];for

(int

i=1;i<

10;

++i)if(r_array[i]<min_val)min_val

=

r_array[i];return

min_val;}9template

<class

Type,

int

size>Typemin(const

Type(

&r_array

)[size]

){Type

min_val

=r_array[0];for

(int

i=1;

i<

size;

++i)if(r_array[i]<min_val)min_val

=

r_array[i];return

min_val;}template

<class

Type>Typemin(const

Type

r_array

[],int

size

);用函數(shù)實(shí)參的類型來(lái)決定模板實(shí)參的類型和值的過(guò)程被稱為模板實(shí)參推演。（函數(shù)返回類型并不用于模板實(shí)參推演）void

main

(){int

ai

[]={12,

7,

9,

39,

3

};double

ad[3]

={2.3,

4.5,

1.8

};int

i

=

min

(

ai

,5);;int

a

=min

(ad

,3);}5.1.2函數(shù)模板實(shí)例化//Type為int,size為5double

d=min(ad,3)//Type為double,size為310//Type為double,size為3template

<

class

T1,

class

T2,

class

T3

>T1

sum(

T2

a,

T3

b){T1

s;s

=

a+b;return

s;}char

a=

‘0’;int

i

=1;char

b=

sum(a,i);char

sum(char,

int

);

?char

c

=sum

<char,

char,

int

>(a,

i);顯式模

板實(shí)參，可省略

尾部模

板實(shí)參11char

d=sum

<char>(a,

i);

//省略T2,T35.1.3模板編譯模式12我們把函數(shù)模板定義放在哪里？放在頭文件中，就好像對(duì)內(nèi)聯(lián)函數(shù)定義的做法一樣，在使用函數(shù)模板實(shí)例的地方包含它們；或者我們只在頭文件中給出函數(shù)模板聲明，而把模板定義放在*.c中，就好像對(duì)非內(nèi)聯(lián)函數(shù)的做法一樣。C++支持兩種模板編譯模式：包含模式和分離模式。包含編譯模式：將整個(gè)模板定義放在頭文件中。//model1.htemplate

<class

Type>

Type

min(Type

t1,Type

t2){return

t1<t2?t1:t2;}//在使用模板實(shí)例之前包含模板定義#include

"model1.h"int

i,

j;double

dobj

=

min(

i,

j

);缺點(diǎn)：向用戶暴露了模板實(shí)現(xiàn)細(xì)節(jié)13分離編譯模式：函數(shù)模板的聲明被放在頭文件中，實(shí)現(xiàn)放在*.c文件中。//model2.htemplate

<class

Type>

Type

min(

Type

t1,

Type

t2

);//model2.Cexport

template

<class

Type>Type

min(Type

t1,Type

t2){……}//user.C#include

"model2.h"int

i,

j;double

d

=

min(

i,

j);template之前加上關(guān)鍵字export來(lái)聲明一個(gè)可導(dǎo)出的函數(shù)模板，export不需要出現(xiàn)在頭文件的模板聲明中1415例：定義一個(gè)隊(duì)列類class

Queue

{public:Queue()

:front(

0

),

back(0){}~Queue();int

&

remove();void

add(

const

int

&);bool

is_empty()

const

{return

front

==

0;}private:QueueItem*front;QueueItem*back;};class

QueueItem

{public:QueueItem(

const

int

&

);private:int

item;QueueItem

*next;};能否定義通用

隊(duì)列類：不限制結(jié)點(diǎn)保存的數(shù)據(jù)類型？5.2類模板16template

<class

Type>class

QueueItem

{public:QueueItem(

const

Type

&

);private:Type

item;QueueItem

*next;};將類定義中用到的數(shù)據(jù)類型或常量值參數(shù)化template

<class

Type>class

Queue

{public:Queue()

:front(

0

),

back

(0){}~Queue();Type&

remove();void

add(

const

Type&

);bool

is_empty()

const

{return

front

==

0;}private:QueueItem<Type>

*front;QueueItem<Type>

*back;};類模板實(shí)例17化注意：函數(shù)模板實(shí)例化時(shí)，既可以提供顯式模板實(shí)參，也可根據(jù)函數(shù)實(shí)參進(jìn)行實(shí)例化；類模板無(wú)法根據(jù)上下文環(huán)境確定模板參數(shù)，所以必須提供顯式模板實(shí)參進(jìn)行實(shí)例化。Queue<int>

qi;Queue<string>

qs[100];Queue<double> *qp=newQueue<double>;實(shí)例化后的類模板稱為模板類，其使用方法與一般類相同18類模板成員函數(shù)定義：在類模板定義之外template

<class

Type>voidQueue

<Type>::add(

const

Type&val){QueueItem<Type>

*pt

=new

QueueItem<Type>(

val

);if(is_empty()

)front

=back

=

pt;else{back->next

=

pt;back

=pt;}}當(dāng)類模板被實(shí)例化時(shí)，類模板的19成員函數(shù)并不自動(dòng)被實(shí)例化，只有當(dāng)一個(gè)成員函數(shù)被程序用到函數(shù)調(diào)用或取地址時(shí)，它才被實(shí)例化。Queue

<int>

qi;int

a;…………qi.add(a);類模板編譯模式：包含編譯模式：類模板定義和成員函數(shù)定義等都放在頭文件中。分離編譯模式：類模板定義放在頭文件中，成員函數(shù)等定義放在程序文本文件*.c中。//

-----

Queue.h-----export

template

<class

Type>class

Queue

{...public:Type&

remove();voidadd(const

Type&

);....};//

-----

Queue.C

-----#include

"Queue.h"template

<class

Type>void

Queue<Type>::add(const

Type&val

){

...

}template

<class

Type>Type&

Queue<Type>::remove(){

...

}export關(guān)鍵字用作類模板定義中205.3

STL（標(biāo)準(zhǔn)模板庫(kù)：Standard

Template

Library）各種各樣的數(shù)據(jù)結(jié)構(gòu)：鏈表、堆棧、隊(duì)列、向量……各種各樣的操作：遍歷、插入、刪除、替換……面向?qū)ο蟮淖畲蠛锰帲簭?fù)用、復(fù)用、再?gòu)?fù)用C++標(biāo)準(zhǔn)庫(kù)

提供許多復(fù)用組件21STL包括三個(gè)主要組件：容器（container）：模板化的復(fù)雜數(shù)據(jù)類型；迭代器（iterator）：用于迭代訪問(wèn)容器中的數(shù)據(jù)；泛型算法（gernericalgorithm）：可應(yīng)用在多種數(shù)據(jù)類型（包括容器類型或內(nèi)置數(shù)據(jù)類型）上的公共操作。22下面以vector容器為例介紹容器、迭代器、泛型算法的使用5.3.1順序容器：vector類模板：模板參數(shù)表示所存儲(chǔ)每個(gè)元素的數(shù)據(jù)類型快速隨機(jī)訪問(wèn)任何元素在尾部快速插入、刪除元素，在其它位置插入、刪除元素效率很低動(dòng)態(tài)增長(zhǎng)：存儲(chǔ)空間的申請(qǐng)和釋放由vector類負(fù)責(zé)vector類表示具有連續(xù)內(nèi)存單元的數(shù)據(jù)結(jié)構(gòu):順序容器：由單一類型元素組成、順序存放的一個(gè)集合：vector、list、queue23為了定義vector對(duì)象，必須包含庫(kù)頭文件：#include

<vector>using

namespace

std;容器對(duì)象的定義以容器類型的名字開始，后面是所包含的元素的實(shí)際類型，例如：vector

<

int

>vector

<

string

>ivec;svec;可以是各種內(nèi)置數(shù)據(jù)類型或用戶自定義類24初始為空：長(zhǎng)度為0用戶自定義類必須支持以下操作：元素類型必須支持等于操作符元素類型必須支持小于操作符元素類型必須支持復(fù)制構(gòu)造函數(shù)插入元素最簡(jiǎn)單的方法是push_back()，將元素插入在容器的尾部：vector<string

>

svec;stringtext_word;while

(cin

>>text_word

){svec.push_back(

text_word

);cout

<<

svec.size()

<<endl;}長(zhǎng)度動(dòng)態(tài)增長(zhǎng)25vector支持其它一些操作：比較操作指定位置或范圍的插入、刪除操作……迭代器：指向容器中的元素，用于對(duì)順序或關(guān)聯(lián)容器類型中的每個(gè)元素進(jìn)行連續(xù)訪問(wèn)。5.3.2迭代器（iterator）預(yù)定義迭代器iteratorconst_iteratorreverse_iteratorconst_reverse_iterator26++方向向前向前向后向后功能讀/寫讀讀/寫讀vector中定義的迭代器：vector<string>::iteratorvector<int>::iterator//

vector<string>

vec;vector<string>::iterator

iter

=vec.begin();vector<string>::iterator

iter_end

=

vec.end();for(

;

iter

!=

iter_end;

++iter

)cout

<<

*iter

<<endl;begin()返回一個(gè)iterator：它指向容器的第一個(gè)元素end()返回一個(gè)iterator：它指向容器的末元素的下一個(gè)位置迭代器可進(jìn)行比較、自增/自減、解尋址等操作27const_iterator

允許以只讀方式訪問(wèn)容器的底層元素例如#include

<vector

>void

even_odd(

const

vector<int>

*pvec,

vector<int>

*pvec_even,vector<int>

*pvec_odd

){vector<int>::const_iterator

c_iter

=

pvec->begin();vector<int>::const_iterator

c_iter_end

=

pvec->end();for

(

;

c_iter

!=

c_iter_end;

++c_iter

)if

(*c_iter

%

2

)pvec_odd->push_back(

*c_iter

);elsepvec_even->push_back(*c_iter

);}28可以用標(biāo)量算術(shù)運(yùn)算使iterator

從當(dāng)前位置偏移到某個(gè)位置上:vector<int>::iterator

iter=vec.begin()+vec.size()/2;將iter

指向vec

的中間元素，而iter

+=

2;將iter

向前移動(dòng)兩個(gè)元素容器對(duì)象也可以用“由一對(duì)iterator標(biāo)記的起始元素和末元素下一位置之間的拷貝”來(lái)初始化：vector<string>

svec;//

...//用svec

的全部元素初始化svec2vector<string>

svec2(

svec.begin(),

svec.end()

);//用svec

的前半部分初始化svec3vector<string>::iterator it

=svec.begin()

+

svec.size()/2;vector<string>

svec3(

svec.begin(),it

);29在迭代器的支持下，vector等容器類提供檢索、插入、刪除元素等獨(dú)有