模板與泛型編程

1、6.1 模板的概念 6.2 函數(shù)模板 6.3 類模板 6.4 編程示例:棧模板 6.5 泛型編程,第 6 章 模板,6.1 模板的概念,6.1.1 什么是模板 在編程中程序員經(jīng)常會遇到這樣的情況，對于不同數(shù)據(jù)類型的參數(shù)雖然需要實(shí)現(xiàn)相似的函數(shù)功能，例如編寫求兩個整型數(shù)據(jù)中最大值的函數(shù)與求兩個實(shí)型數(shù)據(jù)最大值的函數(shù)，它們的程序邏輯相同，程序代碼也相同，只是它們的參數(shù)類型與返回值類型不同。對這樣的情況，在C語言中程序員不得不定義兩個函數(shù)，然后將程序代碼重復(fù)書寫一遍。同樣有時也會遇到具有類似功能的類，例如一個整型數(shù)據(jù)集合的類與實(shí)型數(shù)據(jù)集合的類，它們實(shí)現(xiàn)的功能相同，但存儲的數(shù)據(jù)類型不同。,對于上面的情況，

2、C+語言中可以使用模板來避免在程序中多次書寫相同的代碼。模板是一種描述函數(shù)或類的特性的藍(lán)圖?？梢詮囊粋€函數(shù)模板生成多個函數(shù)或從一個類模板生成多個類。建立一個模板后，編譯器將根據(jù)需要從模板生成多份代碼。,6.1.2 模板的基本語法 C+語言中使用關(guān)鍵字template開始一個模板的聲明，模板聲明的一般形式為： template說明體 模板參數(shù)表可以包含一個或多個模板參數(shù)聲明，如果有多個模板參數(shù)，參數(shù)與參數(shù)之間以逗號隔開。例如帶有一個參數(shù)的模板可以以下述形式開頭： template class表示參數(shù)T是一個數(shù)據(jù)類型。在使用該模板時，T可以用用戶定義的數(shù)據(jù)類型，也可以用C+語言固有的數(shù)據(jù)類型，如i

3、nt、float等替換。這里的class與類定義中的class沒有關(guān)系。 參數(shù)標(biāo)識符T也可以用其它的任何標(biāo)識符來表示，例如：,template 通常的習(xí)慣是，表示數(shù)據(jù)類型的參數(shù)用T打頭，后跟表示該參數(shù)的含義的英文單詞，T表示英文Type。 多個參數(shù)的模板聲明的格式為： template 類模板參數(shù)除了可以是數(shù)據(jù)類型外，還可以是其它類型的數(shù)據(jù)，例如整型數(shù)據(jù)： template 參數(shù)的具體使用方法將在下面兩節(jié)中詳細(xì)介紹。,6.2 函 數(shù) 模 板,6.2.1 函數(shù)模板的定義 不管它們的性質(zhì)如何，所有的函數(shù)模板都具有同樣的基本格式：,template 函數(shù)頭 函數(shù)體 例如，下面是一個單參數(shù)的模板的聲明

4、： template void f(T param) /此處為函數(shù)體 ,template關(guān)鍵字和尖括號中的class T一起開始了模板的構(gòu)造。下面的函數(shù)頭函數(shù)體中的T在使用時將被指定的類型標(biāo)識符替代。模板中的每個參數(shù)在函數(shù)參數(shù)表中必須至少使用一次。下面的聲明是不允許的： template void f(T1 param) /.函數(shù)體 這個函數(shù)模板聲明了兩個參數(shù)T1和T2，但是函數(shù)本身卻只使用了T1來定義param。正確的聲明應(yīng)該是在函數(shù)參數(shù)表中至少使用T1和T2各一次：,template void f(T1 param1,T2 param2) /.函數(shù)體 下面是一個模板聲明的程序源文件，讀者可

5、以將它輸入命名為minmax.h，以便在需要時使用。通常的習(xí)慣是，將模板放在頭文件中聲明，以便不同的程序文件可以共享。目前的編譯器一般不支持將函數(shù)模板的聲明與函數(shù)模板的函數(shù)體部分分別存放，生成獨(dú)立的函數(shù)庫文件，然后使用（普通函數(shù)可以在頭文件中聲明原型，函數(shù)實(shí)現(xiàn)放在獨(dú)立的源文件中，編譯生成函數(shù)庫，在使用時只需要頭文件中函數(shù)原型聲明，而不需要函數(shù)實(shí)現(xiàn)的源代碼）。,#ifndef MINMAX_H #define MINMAX_H/避免重復(fù)包含本文件 template T max(T a, T b) return (ab)?a:b; ,template T min(T a,T b) return (

6、a int inrange(T a,T b,T c) return (b=a) #endif,該程序中聲明并實(shí)現(xiàn)了三個函數(shù)模板，每個模板都以下面的聲明開始： template 在這個聲明中，T是對象的類型，該對象由函數(shù)對其進(jìn)行操作。下面的程序使用了上面定義的模板，從中可以看出如何使用函數(shù)模板： #include #include “minmax.h” int main( ) int a=123, b=456; coutmin(123,456)=min(a,b)n;,coutmax(123,456)=max(a,b)n; double c=3.14159, d=9.87654; coutmin(

7、3.14159, 9.87654)=min(c,d)n; coutmax(3.14159, 9.87654)=max(c,d)n; short s1=10, low=5, high=15; couts1=s1n; if(inrange(s1, low, high),coutlow=s1=highn; else couts1 is not within range lowtohighn; return 0; 從程序中可以看出，函數(shù)模板在使用時并沒有顯式地指明其參數(shù)，程序中有兩處用到min模板，編譯器根據(jù)參數(shù)的數(shù)據(jù)類型進(jìn)行匹配。第一次使用min模板，其參數(shù)為整型數(shù)據(jù)，編譯器從模板生成下面形式的函數(shù)

8、：,int min(int, int); 第二次使用參數(shù)為雙精度型數(shù)據(jù)，編譯器從模板生成下面形式的函數(shù)： double min(double,double); 這里編譯器使用了函數(shù)的重載機(jī)制生成兩個同名的函數(shù)，它們的參數(shù)形式不同，因此無須顯式聲明在套用模板時如何給定模板的參數(shù)。,*6.2.2 重設(shè)模板函數(shù) 前面的例子演示了如何定義一個函數(shù)模板以及如何使用，但有時可能需要替換已定義的模板，請看下面的例子：,#include minmax.h #include void main( ) char * first=first; char * second=second; coutmax(first,

9、second); ,根據(jù)已定義的模板，編譯器將從模板生成下面的函數(shù)： char * max(char * a, char * b) return (ab)?a:b; 程序在執(zhí)行的過程中將比較兩個指針參數(shù)的值，而不是比較指針?biāo)赶虻淖址?，對char*類型的參數(shù)不能套用函數(shù)模板。C+語言允許在定義了一個模板后以特定的函數(shù)來替換模板，為修復(fù)上面程序的缺陷，可重新編寫一個字符串求最大值的函數(shù)來代替含模板生成的函數(shù)。下面是修改后的程序代碼：,#include minmax.h #include #include char * max(char * a,char * b) return strcmp(a

10、,b)0?a:b; void main( ) char * first=first; char * second=second; coutmax(first, second); ,現(xiàn)在編譯器在編譯表達(dá)式max(first,second)時，不再從max模板生成函數(shù)，而直接使用程序中定義的求字符串類型數(shù)據(jù)最大值的函數(shù)。 如果模板所產(chǎn)生的函數(shù)版本不能達(dá)到預(yù)期的結(jié)果，那么就可以使用上面的技術(shù)來替換模板。,*6.2.3 顯式和隱式的模板函數(shù) 前面的例子中，編譯器在由函數(shù)模板生成函數(shù)時根據(jù)程序中函數(shù)調(diào)用的參數(shù)類型進(jìn)行匹配，生成的函數(shù)原型完全由編譯器決定，無須在程序中顯式聲明。這種隱式生成的模板函數(shù)編譯器

11、對參數(shù)類型進(jìn)行精確匹配，不進(jìn)行任何隱含的類型轉(zhuǎn)換?？聪旅娴某绦蚱瑪啵?template T max(T a, T b) return (ab)?a:b; void f(int i,char c) ,max(i, i);/調(diào)用max(int, int) max(c, c);/調(diào)用max(char, char) max(i, c);/沒有匹配的max(int, char) max(c, i);/沒有匹配的max(char, int) 這段代碼在編譯時將會產(chǎn)生以下的錯誤信息： Could not find a match for max(int, char) in function f(int, c

12、har) Could not find a match for max(char, int) in function f(int, char),int max(int, int); /顯式聲明max(int, int) void f(int i, char c) max(i, i); /調(diào)用max(int, int) max(c, c); /調(diào)用max(char, char) max(i, c); /調(diào)用max(int, int) max(c, i); /調(diào)用max(int, int) 通過顯式聲明模板函數(shù)，編譯器對不能從模板進(jìn)行精確匹配的調(diào)用試圖以顯式聲明的函數(shù)原型進(jìn)行匹配，這里將函數(shù)調(diào)用表

13、達(dá)式max(i,c)和max(c,i)中的c隱含轉(zhuǎn)換為整型數(shù)據(jù)后傳遞給max。,如果用通常的方法定義一個原型為int max(int, int)的函數(shù)，語句max(i, c)和max(c, i)將可以正常編譯，變量c被隱含地轉(zhuǎn)換為整型數(shù)據(jù)后傳遞給max函數(shù)。 對于上面的這種情況，可以通過顯式地聲明從模板生成的函數(shù)原型來解決： template T max(T a, T b) return (ab)?a:b; ,*6.3 類 模 板,6.3.1 類模板的定義與使用 類模板定義了類的模式。例如前面提到的整型數(shù)據(jù)元素集合和實(shí)型數(shù)據(jù)元素集合的例子，它們實(shí)現(xiàn)的功能相同，不同的只是其存儲的數(shù)據(jù)類型不同。將

14、其定義為類模板，模板的參數(shù)為該數(shù)據(jù)類型，可以由它來生成整型集合類和實(shí)型集合類。下面通過一個簡單的例子來介紹如何定義和使用類模板。 #include template class Vector,T *data; int size; public: Vector(int); Vector( )delete data; T ,int main( ) Vector x(5); for(int i=0;i5;i+) xi=i; for(int i=0;i5;i+) coutxi ; coutn; return 0; ,這個例子中定義了一個類模板Vector，它有一個類型參數(shù)T，類定義的模板聲明由temp

15、late開始，下面的類聲明部分與普通類聲明的方法相同，只是在部分地方用參數(shù)T表示數(shù)據(jù)類型。 模板類的每一個非內(nèi)置函數(shù)的定義是一個獨(dú)立的模板，同樣以template開始，函數(shù)頭中的類名由模板類名加模板參數(shù)構(gòu)成，如例子中的Vector。 模板類在使用時與函數(shù)模板不同，函數(shù)模板無須顯式指明使用模板時的參數(shù)（使用了函數(shù)重載機(jī)制），模板類在使用時必須指明參數(shù)，形式為：模板類名。例子中的Vector即是如此，編譯器根據(jù)參數(shù)int生成一個int的Vector類，理解程序時可以將Vector看成是一個完整的類名。在使用時Vector不能單獨(dú)出現(xiàn)，它總是和尖括號中的參數(shù)表一起出現(xiàn)。,6.3.2 類模板參數(shù) 上面

16、的例子中模板只有一個表示數(shù)據(jù)類型的參數(shù)，多個參數(shù)以及其它類型的參數(shù)也是允許的。請看下面的例子： template class Set T elemssize; /存儲元素的數(shù)組 int card;/集合中元素的個數(shù) public:,void EmptySet( )card=0; Bool Member(T); ErrCode AddElem(T); void RmvElem(T); void Copy(Set *); Bool Equal(Set *); void Print( ); void Intersect(Set *,Set *); ErrCode Union(Set *,Set *)

17、; ;,這個模板聲明了一個集合類模板，實(shí)現(xiàn)了整型集合的功能，它有兩個參數(shù)，一個表示集合存儲的數(shù)據(jù)元素的類型，另一個為集合所能存儲的數(shù)據(jù)元素的最大個數(shù)。如果需要一個大集合，則在使用時傳遞一個較大的常數(shù)給size；如果集合較小，則可以從模板生成一個元素個數(shù)較小的集合類，而無須擔(dān)心浪費(fèi)存儲空間。像函數(shù)的參數(shù)可以有缺省值一樣，這里也使用了缺省值，如果在使用時不指明size的大小，則使用缺省的常數(shù)值maxCard。 下面是該模板類非內(nèi)置函數(shù)AddElem和Copy的實(shí)現(xiàn)，其它的函數(shù)請讀者自行補(bǔ)充完整。,template ErrCode Set:AddElem(T elem) if(Member(elem

18、) return noErr; if(cardsize) elemscard+=elem; return noErr; return overflow; ,template void Set:Copy(Set *set) for(int i=0;ielemsi=elemsi; set-card=card; 可以通過下面的語句來使用Set類模板： Set set;,定義一個整型集合對象，參數(shù)T由int類型替換，而參數(shù)size使用缺省值maxCard，也可以像下面這樣指明size的大?。?Set s; 定義一個浮點(diǎn)型的數(shù)據(jù)集合對象，集合的最大元素個數(shù)為10。要注意的是，傳遞給size的值只能用常量

19、表達(dá)式，而不能含有變量，因?yàn)槟０宓膮?shù)是在編譯時處理的，而在編譯階段不可能計算變量表達(dá)式的值。,6.4 編程示例: 棧模板,#include enum Bool False, True; /抽象堆棧類模板定義 template class AbsStack protected: unsigned height;,public: bool IsEmpty( )return (height=0)?True:False; virtual void push(T ,/使用數(shù)組存儲數(shù)據(jù)元素的堆棧類模板 template class ArrayStack:AbsStack Bool Error; T ve

20、cSize; public: ArrayStack()Empty(); virtual void push(T ,/壓棧操作 template void ArrayStack:push(T ,/出棧操作 template void ArrayStack:pop(T ,/讀取棧頂元素 template void ArrayStack:ReadTop(T ,/置堆棧為空 template void ArrayStack: Empty( ) height = 0; void main() ArrayStack s; int i=30;,s.push(i); int j; s.pop(j); s.po

21、p(j); coutjn; if(s.IsError() couterrorn; else coutno errorn; ,上面的程序首先定義了一個抽象的堆棧模板類AbsStack，該類模板只定義了堆棧類的接口，沒有定義存儲堆棧數(shù)據(jù)元素的內(nèi)部數(shù)據(jù)結(jié)構(gòu)，可以從其派生出使用不同數(shù)據(jù)結(jié)構(gòu)存儲堆棧數(shù)據(jù)元素的堆棧類。本例中使用了常見的存儲方法數(shù)組存儲數(shù)據(jù)元素，然后實(shí)現(xiàn)了堆棧的常見運(yùn)算。,42,6.5 泛型程序設(shè)計C+標(biāo)準(zhǔn)模板庫,泛型程序設(shè)計 與標(biāo)準(zhǔn)模板庫有關(guān)的概念和術(shù)語 C+標(biāo)準(zhǔn)模板庫中的容器 迭代器 標(biāo)準(zhǔn)C+庫中的算法 函數(shù)對象,43,泛型程序設(shè)計,將程序?qū)懙帽M可能通用 將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出

22、來，成為通用的 C+的模板為泛型程序設(shè)計奠定了關(guān)鍵的基礎(chǔ) STL是泛型程序設(shè)計的一個范例 容器(container) 迭代器(iterator) 算法（algorithms） 函數(shù)對象（function object）,44,命名空間（Namespace）,一個命名空間將不同的標(biāo)識符集合在一個命名作用域（named scope）內(nèi) 為了解決命名沖突 例如，聲明一個命名空間NS： namspace NS class File; void Fun (); 則引用標(biāo)識符的方式如下， NS: File obj; NS: Fun (); 沒有聲明命名空間的標(biāo)識符都處于無名的命名空間中,概念和術(shù)語,45,

23、命名空間（Namespace）,可以用using來指定命名空間 例如，經(jīng)過以下聲明：using NS:File;在當(dāng)前作用域中就可以直接引用File using namespace std;命名空間std中所有標(biāo)識符都可直接引用 在新的C+標(biāo)準(zhǔn)程序庫中，所有標(biāo)識符都聲明在命名空間std中，頭文件都不使用擴(kuò)展名。,概念和術(shù)語,46,容器,容器類是容納、包含一組元素或元素集合的對象。 異類容器類與同類容器類 順序容器與關(guān)聯(lián)容器 七種基本容器： 向量（vector）、雙端隊(duì)列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）,

24、概念和術(shù)語,47,容器的接口,通用容器運(yùn)算符 =，!=，=，=，= 方法（函數(shù)）：能夠修改容器的狀態(tài) 迭代方法 begin()，end()，rbegin()，rend() 訪問方法 size()，max_size()，swap()，empty(),48,適配器,適配器是一種接口類 為已有的類提供新的接口。 目的是簡化、約束、使之安全、隱藏或者改變被修改類提供的服務(wù)集合。 三種類型的適配器： 容器適配器 用來擴(kuò)展7種基本容器，它們和順序容器相結(jié)合構(gòu)成棧、隊(duì)列和優(yōu)先隊(duì)列容器 迭代器適配器 函數(shù)對象適配器。,概念和術(shù)語,49,迭代器,迭代器是面向?qū)ο蟀姹镜闹羔?，它們提供了訪問容器、序列中每個元素的方

25、法。,概念和術(shù)語,50,算法,C+標(biāo)準(zhǔn)模板庫中包括70多個算法 其中包括查找算法，排序算法，消除算法，記數(shù)算法，比較算法，變換算法，置換算法和容器管理等等。 這些算法的一個最重要的特性就是它們的統(tǒng)一性，并且可以廣泛用于不同的對象和內(nèi)置的數(shù)據(jù)類型。,概念和術(shù)語,51,順序容器,順序容器的接口 插入方法 push_front()，push_back()，insert()，運(yùn)算符“=” 刪除方法 pop() ，erase()，clear() 迭代訪問方法 使用迭代器 其它順序容器訪問方法（不修改訪問方法） front()，back()，下標(biāo)運(yùn)算符,容 器,52,順序容器向量,向量屬于順序容器，用于容

26、納不定長線性序列（即線性群體），提供對序列的快速隨機(jī)訪問（也稱直接訪問） 向量是動態(tài)結(jié)構(gòu)，它的大小不固定，可以在程序運(yùn)行時增加或減少。 例10-1 求范圍2N中的質(zhì)數(shù)，N在程序運(yùn)行時由鍵盤輸入。,容 器,/10_1.cpp #include #include #include /包含向量容器頭文件 using namespace std ; void main(void) vector A(10); int n; int primecount = 0, i, j; cout=2 as upper limit: ; cin n; Aprimecount+ = 2;,53,for(i = 3; i

27、 i/2) Aprimecount+ = i; for (i = 0; iprimecount; i+)/輸出質(zhì)數(shù) coutsetw(5)Ai; if (i+1) % 10 = 0) /每輸出10個數(shù)換行一次 cout endl; coutendl; ,54,55,順序容器雙端隊(duì)列,雙端隊(duì)列是一種放松了訪問權(quán)限的隊(duì)列。元素可以從隊(duì)列的兩端入隊(duì)和出隊(duì)，也支持通過下標(biāo)操作符“”進(jìn)行直接訪問。 例10-2 使用雙端隊(duì)列容器保存雙精度數(shù)值序列,容 器,56,順序容器列表,列表主要用于存放雙向鏈表，可以從任意一端開始遍歷。列表還提供了拼接（splicing）操作，將一個序列中的元素從插入到另一個序列中。

28、 例10-3 改寫例9-7 從鍵盤輸入10個整數(shù)，用這些整數(shù)值作為結(jié)點(diǎn)數(shù)據(jù)，生成一個鏈表，按順序輸出鏈表中結(jié)點(diǎn)的數(shù)值。然后從鍵盤輸入一個待查找整數(shù)，在鏈表中查找該整數(shù)，若找到則刪除該整數(shù)所在的結(jié)點(diǎn)（如果出現(xiàn)多次，全部刪除），然后輸出刪除結(jié)點(diǎn)以后的鏈表。在程序結(jié)束之前清空鏈表。,容 器,/10_3.cpp #include #include using namespace std ; void main(void) list Link;/構(gòu)造一個列表用于存放整數(shù)鏈表 int i, key, item; for(i=0;i item; Link.push_front(item); coutList

29、: ; / 輸出鏈表,57,list:iterator p=Link.begin(); while(p!=Link.end()/輸出各節(jié)點(diǎn)數(shù)據(jù)，直到鏈表尾 cout key; Link.remove(key); cout List: ; / 輸出鏈表 p=Link.begin();/ 使P重新指向表頭 while(p!=Link.end() cout *p ; p+; / 使P指向下一個節(jié)點(diǎn) cout endl; ,58,59,容器適配器,容器適配器是用來擴(kuò)展7種基本容器的 棧容器 使用適配器與一種基礎(chǔ)容器相結(jié)合來實(shí)現(xiàn) 例10-4：應(yīng)用標(biāo)準(zhǔn)庫中的deque順序容器生成一個整數(shù)棧stack。 隊(duì)列容器 使用適配器與一種基礎(chǔ)容器相結(jié)合來實(shí)現(xiàn)的先進(jìn)先出數(shù)據(jù)結(jié)構(gòu)。 例10-5：應(yīng)用標(biāo)準(zhǔn)庫中的deque順序容器生成一個整數(shù)標(biāo)準(zhǔn)隊(duì)列Queue。,容 器,60,什么是迭代器,迭代器是面向?qū)ο蟀姹镜闹羔?指針可以指向內(nèi)存中的一個地址 迭代器可以指向容器中的一個位置 S