-- template 的用法
在程序設計當中經(jīng)常會出現(xiàn)使用同種數(shù)據(jù)結(jié)構(gòu)的不同實例的情況。例如:在一個程序中
可以使用多個隊列、樹、圖等結(jié)構(gòu)來組織數(shù)據(jù)。同種結(jié)構(gòu)的不同實例,也許只在數(shù)據(jù)元素
的類型或數(shù)量上略有差異,如果對每個實例都重新定義,則非常麻煩且容易出錯。那么能
否對同種類型數(shù)據(jù)結(jié)構(gòu)僅定義一次呢?答案是肯定的,C++提供的類模板(Class Template
)就可以實現(xiàn)該功能。
一、類模板
類模板是C++提供的一種特殊機制,通過它我們可以定義一種特殊的類(稱為模板類),在類
的定義中可以包含待定的類型參數(shù),在聲明類的實例時,系統(tǒng)會自動根據(jù)傳遞的類型生成
用戶想要生成的類實例。下面是用C++實現(xiàn)的一個簡單的模板類Clist的定義。
Template <class T, int I> class CList
{
public:
int SetItem(int Index, const T &Item);
int GetItem(int Index, T &Item);
private:
T Buffer;
}
在這里,T是類型參數(shù),I是整型常量參數(shù)。T和I的實際值是在聲明具體類實例時指定的。
模板類的<>號內(nèi)可以包括任意個類型參數(shù)和常量參數(shù)(至少要有一個參數(shù))。類型參數(shù)和
常量參數(shù)可以是任何合法的標準類型和用戶自定義類型,包括簡單類型及各種結(jié)構(gòu)體。同
其他類一樣,類成員函數(shù)SetItem的實現(xiàn)可以在類定義內(nèi)完成,也可以在類CList定義處實
現(xiàn):
template<class T, int I> int CList<T, I>::SetItem(int Index, const T &Item)
{
if ( (Index<0)||(Index>I-1) )
return 0; // 出錯
Buffer[Index]= Item ;
return 1; // 成功
}
值得注意的是,在類定義外完成函數(shù)實現(xiàn)時,必須以關鍵字template和類模板定義中相同
的參數(shù)表(<>號內(nèi)的)開頭(上例為template<class T, int I>),并且范圍分解操作符前的
類名后應跟上模板參數(shù)名清單(上例為CList<T, I>)。另外,與非模板類不同的是,必須將
函數(shù)實現(xiàn)包括在調(diào)用它的每個源文件中,使編譯器能從函數(shù)實現(xiàn)產(chǎn)生代碼。通常的做法是
將模板類的函數(shù)實現(xiàn)也放在定義該類的頭文件中,這樣只需在調(diào)用的源文件中包含該頭文
件即可。
那么,如何使用生成特定的類實例呢?我們可以像使用其他類一樣來使用模板類,不過必須
指定模板參數(shù)的值。例如采用如下聲明:
CList <int, 100> IntList;
則使IntList成為CList類的實例,每次出現(xiàn)的T參數(shù)都換成int, 每次出現(xiàn)的I參數(shù)都換成
100。這樣,IntList類中的Buffer就是一個長度為100的整型數(shù)組,SetItem和GetItem函數(shù)
參數(shù)是int值的引用。例:
IntList.SetItem(0, 5); //給數(shù)組第一個元素賦為整數(shù)5
模板類還可以像其他類一樣可以定義構(gòu)造函數(shù)和析構(gòu)函數(shù)。下面我們以一種簡單的數(shù)據(jù)
結(jié)構(gòu)——堆棧為例,來說明如何用類模板來構(gòu)造通用數(shù)據(jù)結(jié)構(gòu)。
二、 利用類模板實現(xiàn)通用堆棧結(jié)構(gòu)
任何抽象數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn),歸根結(jié)底都只有兩種方式:順序存儲(用數(shù)組實現(xiàn))
,鏈式存儲(用指針實現(xiàn))。堆棧也不例外,按其實現(xiàn)方式可分為順序棧(用數(shù)組實現(xiàn))和鏈
棧(用指針實現(xiàn))。
1. 通用順序棧的實現(xiàn)
因為順序棧中的元素在空間上連續(xù)存儲,棧頂?shù)脑匚恢眯枰⒚?所以構(gòu)造順序棧的模
板類應該有這樣的一些成員變量:一個待定類型和長度的數(shù)組Buffer,一個記錄棧頂元素
的數(shù)組下標的整型變量top。堆棧的基本操作主要有:入棧(Push)、出棧(Pop)、置空(Se
tEmpty)、判斷當前狀態(tài)(IsEmpty)等,它們應用模板類的成員函數(shù)來實現(xiàn)。作為一個標準
的類,它還應該有自己的構(gòu)造函數(shù)和析構(gòu)函數(shù)。具有這些功能的模板類,就可以作為一個
通用的順序棧來使用了。該類的定義如下:
template <class T,int SIZE> class CArrayStackTemp
{
public:
CArrayStackTemp () //缺省構(gòu)造函數(shù),構(gòu)造一個空堆棧
{
top= -1;
};
～ CArrayStackTemp (){};//析構(gòu)函數(shù)
void SetEmpty (); //置空堆棧
bool IsEmpty(); //判斷堆棧是否為空
bool Push(T element); //入棧
bool Pop(T& element);//出棧
private:
T Buffer[SIZE];
int top;
};
與堆棧的基本操作相對應的成員函數(shù)的實現(xiàn)如下:
template <class T, int SIZE> void CArrayStackTemp<T, SIZE>:: SetEmpty ()
{
top= -1; //將棧頂指針賦 -1,并不實際清除數(shù)組元素
}
template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: IsEmpty ()
{
return(top == -1);
}
template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: Push (T element
)
{
top++;
if (top>SIZE-1)
{
top--;
return false; //堆棧已滿,不能執(zhí)行入棧操作
}
Buffer[top]=element;
return true;
}
template <class T, int SIZE> void CArrayStackTemp<T, SIZE>:: Pop (T& element
)
{
if (IsEmpty())
return false;
element =Buffer[top];
top--;
return true;
}
根據(jù)實際需要,還可以擴充堆棧功能。例如:加入取棧頂元素、求堆棧長度等操作,其方法
如上。
2. 通用鏈棧的實現(xiàn)
模板類中允許使用指針和定義自己的結(jié)構(gòu),這就為實現(xiàn)鏈式結(jié)構(gòu)提供了保證。這里采用一
個單鏈表來實現(xiàn)堆棧,棧頂指針指向鏈表的第一個結(jié)點,入棧和出棧均在鏈表的頭進行。
該模板類的定義如下:
template <class T> class CLinkStackTemp
{
public:
//類的缺省構(gòu)造函數(shù),生成一個空堆棧
CLinkStackTemp ()
{
top=NULL;
};
～ClinkStackTemp(){}; //析構(gòu)函數(shù)
//定義結(jié)點結(jié)構(gòu)
struct node
{
T
data; //入棧元素
node* next; //指向下一結(jié)點的指針
};
void SetEmpty(); //置空堆棧
bool IsEmpty(); //判斷堆棧是否為空
bool Push(T element); //壓入堆棧
bool Pop(T& element);//彈出堆棧
private:
node* top;
};
該類的成員函數(shù)實現(xiàn)如下:
template <class T> void CLinkStackTemp <T>::SetEmpty()
{
//釋放堆棧占用的內(nèi)存
node* temp;
while (top!=NULL)
{
temp=top;
top=top->next;
delete temp;
}
}
template <class T> bool CLinkStackTemp <T>::IsEmpty()
{
return (top==NULL);
}
template <class T> bool CLinkStackTemp <T>::Push(T element)
{
node* temp=new node();
if (temp ==NULL)
return false ;
temp->data=element;
temp->next=top;
top=temp;
return true;
}
template <class T> bool CLinkStackTemp <T>::Pop(T& element)
{
if ( IsEmpty())
return false;
node* q = top;
element = top->data;
top=top->next;
delete q;
return true;
}
與順序棧的實現(xiàn)略有不同,鏈棧不必指定棧的容量,其大小可以是近似"無限"的。為了程
序的使用方便,我們同樣可以加入一些增強的功能。
三、 通用堆棧類的使用
通用堆棧類的使用較為簡單,堆棧類的實例就是一個可以方便使用的堆棧。對堆棧的操作
都是通過類的成員函數(shù)來實現(xiàn)的。使用的具體步驟如下:
1. 在要使用堆棧類的程序代碼的文件開頭包括模板類及其成員函數(shù)的定義。
2. 類的實例化,可聲明成變量,也可以聲明它的指針,如:
CArrayStackTemp <int, 100> intStack; //生成一個長度為100的int型堆棧
//生成一個元素為Record型的堆棧,Record為自定義結(jié)構(gòu)
CLinkStackTemp <Record>* RecordStack;
RecordStack=new CLinkStackTemp<Record>;
應注意在定義順序棧時,必須指定棧的大小,而鏈棧則不必。另外在指定指針類型和執(zhí)行
new操作時,必須對模板參數(shù)賦值,并且前后要一致。
3. 對堆棧進行操作,如:
intStack.Push(3); //將整數(shù)3入棧
RecordStack.SetEmpty(); //將堆棧置空
無論我們使用哪種堆棧類,對用戶來講都是透明的,操作起來并無差別。
