請問一下你們都怎麼寫Template的程式的?
milochen (陳文輝 Chen,Wen-Hui)
自己看了一些書，很讓人純純欲動的就衝下去寫，
寫的時候才會真的發現自己還有很多問題跟很多觀念都不行。
之前在看STL的書時，因為太歡樂的關係，等發現實際要寫Template時卻一直compiler不過。原因是因為
像typename少加或加錯，或者是對於什麼時候要加角括號，有時候不用加角括號分不清楚。小弟的經驗目
前尚沒有任何idea來分辨。所以會有個example放在旁邊，等compiler不過時可以對照一下
XD
以前我分享這個Code是我try了好久才compile過的Code。如果有人對寫Template很有經驗的，也歡迎教一
下。因為我覺得它也許是很trivial，只是可能是我很多觀念還沒打通，所以才變成需要放一個example
code在旁邊參照。
我後來發現在C++ Templates : The Complete
Guide此書中的Page131頁上有提到一個精簡
例子，我後來想想這個可以拿來作一個寫template
的example，不過不知這樣夠不夠
。關於typename用的地方，它課本是這樣子寫的
template<typename T>
struct S: typename X<T>::Base {
S(): typename X<T>:: Base(typename X<T>::Base(0)){}
typename X<T> f(){
typename X<T>::C * p; //declaration of pointer p
X<T>:: D * q; //multiplication!
}
typename X<int>::C * s;
};
struct U{
typename X<int>::C * pc;
};
然後我自己的code的規劃是 標頭檔定義那些member的東東
然後實際寫code的的是在另一個miloDS.cpp 檔裡面，
而Instantiation有那些，則是決定在
另一個叫Templates.cpp的檔案裡
這是等要Link的時候就把 miloDS.o 跟 Templates.o
一起連結起來。
(我是在G++ 3.3.5下面編譯與連結的)
我的miloDS.o 其實是因為一時想要好用的Data
Structure而寫的
(我也不知道這算不算是把 Template當Macro在用的寫法)
底下的 ptrlist<T> 其實就是一個很簡單的 double
linklist的結構
然後它提供一些功能，而這LinkList的node
class寫在裡面，主要是說
每個 LinkList上的node 所存放的 data 之 data type 為 T*
template <typename T>
class ptrlist{
public:
typedef T* value_ptr;
typedef T value_type;
class node;
ptrlist();
node* begin();
node* end();
bool isEmpty();
void insert(value_ptr theDataPtr );
void cancel(node* cancelPtr);
unsigned long getLength();
class node{
public:
node* prev;
node* next;
value_ptr data;
};
node* head;
node* tail;
node* dummy;
private:
unsigned long length;
};
後來我們可能需要一個double LinkList是要可以有key
的搜尋
所以我就轉換一個方式去利用原本的 ptrlist<T>來作。
因為如果當 T 是一個 pair的時候，那麼 (key value, data
value) 這樣子的pair
就可以直接套用在ptrlist裡面了，只是說我們僅需多加一些member
function而以
所以我加入了用來描述 pair 概念的 template東東
template <typename K, typename T>
struct KTpair{
K key;
T data;
};
然後另外定一個叫 keylist<K,T>的東東，K是searching
key的型態
而T是代表所要找尋出來的data，其type為 T*
其宣告如下
template <typename K, typename T, typename _LIST=ptrlist< KTpair<K,T> >
>
class keylist{
public:
keylist();
bool isExist(K searchKey);
bool insert(K Key, T Data);
T search(K searchKey);
void cancel(K searchKey);
unsigned long total();
private:
_LIST *_list;
};
到目前為止，上述的三個東西 ptrlist<T>, keylist<K,T> and
KTpair<K,T> 都是寫在miloDS.h裡
因為我想要利用 keylist 來作我想作的東西
而我想作的東西是下面這樣子的東西...
template<typename T, typename _IMPL=keylist<unsigned long, T*> >
class UniqueIdCollection{
public:
typedef T value_type;
typedef T* value_ptr ;
UniqueIdCollection();
~UniqueIdCollection();
//Check that whether theString is repeatly in UniqueIdCollection
bool isExist(unsigned long theId);
//insert the ID into UniqueIDcollection
void insert(unsigned long theId, T* theData);
//delete the data of theId from UniqueIdCollection
T* cancel(unsigned long theId);
//return the number of unique ID in the Collection
unsigned long size();
//Query the ID for the pointer to data that is corresponding to theId
T* query(unsigned long theId);
private:
_IMPL *_impl;
};
接著實際的Code
就寫在miloDS.cpp裡，而在miloDS.cpp裡面，我覺得有些
typename放的位置跟
角括弧何時要放，裡面就滿多可以看到的，不過
我不知道這樣子足不足夠，因為我當初幾個月前也是每個點都交差的在try，就終於
try出來了。
(在還沒辦法很了解Template機制使用時的語法規則，或許
下面這個已經實踐的例子可以幫助各位在遇到compiler不過的時候可以來參考一下)
因為實際的實踐沒啥太大技巧，就資料結構學的那樣，主要可看的就是
它一些語法的用法，所以我直接把miloDS.cpp它都列在下面來
//*-----START struct KTpair< K, T > MemberFunction--------------------
//No MemberFunction
//------END struct KTpair< K, T > MemberFunction------------------*/
//*-----START ptrlist< T > MemberFunction-------------------
template< typename T >
ptrlist< T >::ptrlist(){
dummy=new node();
tail=dummy;
head=dummy;
dummy->prev=tail;
dummy->next=head;
dummy->data=NULL;
length=0;
}
template< typename T >
typename ptrlist< T >::node* ptrlist< T >::begin(){
return head;
}
template< typename T >
typename ptrlist< T >::node* ptrlist< T >::end(){
return dummy;
}
template< typename T >
bool ptrlist< T >::isEmpty(){
return length==0?true:false;
}
template< typename T >
void ptrlist< T >::insert(typename ptrlist< T >::value_ptr theDataPtr
){
node* insertNode =new node();
insertNode->data=theDataPtr;
if(isEmpty()){
head=tail=insertNode;
insertNode->next=dummy;
insertNode->prev=dummy;
}
else{
head->prev=insertNode;
insertNode->next=head;
insertNode->prev=dummy;
head=insertNode;
}
length++;
}
template< typename T >
void ptrlist< T >::cancel(ptrlist::node* cancelPtr){
if(cancelPtr!=dummy){
length--;
if(length==0){
delete cancelPtr;
tail=dummy;
head=dummy;
}
else{
cancelPtr->prev->next=cancelPtr->next;
cancelPtr->next->prev=cancelPtr->prev;
}
}
}
template< typename T >
unsigned long ptrlist< T >::getLength(){
return length;
}
//------END ptrlist< T > MemberFunction--------------------*/
//*-----START keylist< T > MemberFunction-------------------
template< typename K, typename T, typename _LIST >
keylist< K, T, _LIST >::keylist(){
_list=new _LIST();
cout<<typeid(_list).name()<<endl;
}
template< typename K, typename T, typename _LIST >
bool keylist< K, T, _LIST >::isExist(K searchKey){
bool returnBoolean =false;
typename _LIST::node* q=_list->begin();
while(q!=_list->end() && returnBoolean==false){
if(q->data->key==searchKey)returnBoolean=true;
q=q->next;
}
return returnBoolean;
}
template< typename K, typename T, typename _LIST >
bool keylist< K, T, _LIST >::insert(K Key, T Data){
if(isExist(Key))return false;
KTpair<K,T>* insertPair=new KTpair<K,T>();
insertPair->key=Key;
insertPair->data=Data;
_list->insert(insertPair);
return true;
}
template< typename K, typename T, typename _LIST >
T keylist< K, T, _LIST >::search(K searchKey){
typename _LIST::node* q=_list->begin();
while(q!=_list->end()){
if(q->data->key==searchKey)return (q->data->data);
q=q->next;
}
return NULL;
}
template< typename K, typename T, typename _LIST >
void keylist< K, T, _LIST >::cancel(K searchKey){
typename _LIST::node* q=_list->begin();
bool haveDelete=false;
while(q!=_list->end()&& haveDelete==false){
if(q->data->key==searchKey){
_list->cancel(q);
delete q;
haveDelete=true;
}
q=q->next;
}
}
template< typename K, typename T, typename _LIST >
unsigned long keylist< K, T, _LIST >::total(){
return _list->getLength();
}
//------END keylist< T > MemberFunction--------------------*/
Ok!! miloDS.cpp大概就是這樣子。
然後提一個提外話，當初小弟沒辦法實踐出UniqueStringCollection
(也是一樣用keylist<K,T>去作延伸)
其實至今也還不是很明白是那邊出了問題。
其實我當初本來是還要寫
UniqueIdCollection的，不過我發現寫不起來
可能錯誤是發生那時候對於 const char* 跟 char*
搞不清楚狀況 XD
而我的code沒有對 keylist 裡面 加一個判別 equal 的
FunctionObject。
不知道是不是一定要有 判別 equal 的 FunctionObject 呢??
但我幾個月前好幾次想要寫 UniqueStringCollection都失敗
等之後有空要就要來試寫一下，如果有前輩發現到我那邊有問題的，也歡迎指教
為了要作 UniqueStringCollection 而又不想使用 標準庫的
String
因為當初的目標本來是設立說能夠用自己所學過的演算法與資料結構的概念，
配合Template機制的寫法，自己也要能夠寫出類似像STL這樣子有用的東西。
所以我在miloDS.h多寫了
class equal_string{
public:
char* str;
equal_string(char* theStr);
~equal_string();
bool operator==(const char* theStrB);
bool operator==(equal_string& theStrB);
};
而也在miloDS.cpp裡寫了實踐的碼如下
/*-----START class equal_string MemberFunction----------------
equal_string::equal_string(char* theStr){
int i=0;
while(theStr[i++]!=0);
str=new char[i];
memcpy(str,theStr,i);
}
equal_string::~equal_string(){
delete str;
}
bool equal_string::operator==(const char* theStrB){
int i=0;
char* theStrA=str;
if(theStrA==theStrB)return true;
bool returnBoolean=true;
while(theStrA[i]!=0 && theStrB[i]!=0 && returnBoolean==true){
if(theStrA[i]!=theStrB[i])returnBoolean=false;
i++;
}
if(returnBoolean==false || theStrA[i]!=0 || theStrB[i]!=0)return
false;
return true;
}
bool equal_string::operator==(equal_string& theStrB){
return theStrB==str;
}
//------END equal_string MemberFunction--------------------------*/
所以我的UniqueStringCollection可以這麼如下面的宣告在miloDS.h檔裡
可以寫成如下
template<typename T, typename _IMPL=keylist<equal_string, T*> >
class UniqueStringCollection{
public:
typedef T value_type;
typedef T* value_ptr ;
StrictUniqueIdCollection();
~StrictUniqueIdCollection();
//Check that whether theString is repeatly in UniqueStringCollection
bool isExist(unsigned long theId);
//insert the string into UniqueStringcollection
void insert(unsigned long theId, T* theData);
//delete the theString from UniqueStringCollection
T* cancel(unsigned long theId);
//return the number of unique string in the Collection
unsigned long size();
//Query theId for the pointer to data that is corresponding to
theString
T* query(unsigned long theId);
private:
_IMPL *_impl;
};
然後實踐就寫一點點就有了。不過很顯然的，我發生了一些自己抓不到的錯誤
所以一直沒辦法順利成功。
一開始我想說若是 unsigned long
或者其它東西在keylist都能順利用==來判斷東西是否相同。
但是char* 沒辦法，所以我想說多寫一個 equal_string
來包著，使得用的人用起來
不會發現equal_string的存在，而實際上是由equal_string來完成的
所以我才為 equal_string 寫 operator== 與 operator= 的東東
結果發現還是不行。
我在想是不是我的keylist必須要改寫
也就是說我不能夠寫如下這樣
template <typename K, typename T, typename _LIST=ptrlist< KTpair<K,T> >
>
class keylist{ /*...*/ }
而是要寫像下面這樣子
template <typename K, typename T, typename EQU,typename _LIST=ptrlist<
KTpair<K,T> > >
class keylist{ /*...*/}
是有一定要用到像EQU 這個Function Object來作才行
作出"相等" 的概念嗎?
還是說其實只要物件有支援
operator==的之實現，便可以直接套用上去呢?
當初本來想說以為template好像很好寫，發現寫了以後自己連compile過都有問題。
結果一個好像很作的程式，概念也很好理解，結果一作卻作這麼久。
希望可能也在寫template也跟我還搞不清楚 這細節的
部份要怎麼寫的，
這個example希望可以給您帶來些幫助。如果有先進願意出面糾正我這些錯誤的話，
那許多也還在學如何用template寫程式的晚輩們，會很感激的^__^y
Post
太長了，希望不要造成大家困撓，但我覺得這很重要。
因為如果學Modern C++
Design只是看的懂，而沒辦法把自己所想的idea也實現出來，
那我覺得沒什麼太大的幫助。因為自己用template實現出來中，發現語法錯誤太多。
所以特別把這自己過去花好久時間
"死try"出來可以過的code分享一下。
它這code沒什麼效能，就是 Template 會compile過而己。
小弟的功力實在是太差了，很多東西都只知表皮而無法整個掌握到要領。
還望各位先進們的熱情糾正，小弟感激不盡呀。
PS:
還是說要寫Template程式，有沒有什麼循序漸近的練習題或訓練教材呢?
可以讓我們一邊熟練一邊學一點觀念，然後進行到尾聲後也可以掌握好好的。
因為這些東西課堂上是不會講的，就是這麼東看西看自己寫寫看。
我想如果有個循序漸近的訓練教材，也許會達到比較有效率的學習。
av
不能太長，就像 function
不能太長一樣，一定可以切成很多個小 function
來做的，這樣維護性會好很多。
我對其中一部分回應一下我的看法：
1. typename 的使用時機? typename 這個 keyword 是要告訴
compiler 說接下來的這一串是個 type,
不要把它誤解為別的東西。通常是怕被誤解為要指定某個
namespace 或 class 裡的 member. 例如 typename T::x，如果不寫
typename，compiler 可能以為你是要取用 T 中的 x 這個
member，但通常實際上並沒有這東西，因此會 compile
不過. 至於實際上沒這東西為何 compiler
不能判讀出來呢? 因為它在 parse 這個 template
時跟本不知道啊! 這邊的 T 是個 template
參數，因此在具現化前，compiler 跟本不知道 T
為何物。
2. 我建議還是把 template 的實做放在 .h
檔裡，或是更進一步的，把實作拆開放到 .cpp 檔，但
.h 檔會去 include .cpp
檔，否則你在引用時很容易出錯。或是再更進一步，用
#if 來控制，若 compiler 支援 export
模形，就可以讓實作與介面完全分離，否則 .h
檔還是要 include .cpp 檔。這部分請參考 C++ template 全覽
6.3.3 ( 為分離式模型預做準備).
3. 我也來個題外話，如果想要在 list 中放 pointer,
又要能夠讓這個 list 做好資源管理，免得產生
leak，建議用 boost. boost 裡有個 pointer_container,
裡面有各種 container，但存放的內容都是 pointer 的，在
destructor 中會自動 delete，在刪掉某個元素時也會幫你
delete，很好用的。
OOD Tsen
主要是手邊的Debug工具無法配合Template除錯
而一般常用演算法資料結構都在STL中就有提供了
OOD Tsen@Taiwan
av
你是用哪個 debug 工具? 我現在是用 VC8,
還算蠻不錯的，不過 VC6 就很難用了.
godfat 真常
> 3. 我也來個題外話，如果想要在 list 中放 pointer,
> 又要能夠讓這個 list 做好資源管理，免得產生
> leak，建議用 boost. boost 裡有個 pointer_container,
> 裡面有各種 container，但存放的內容都是 pointer 的，在
> destructor 中會自動 delete，在刪掉某個元素時也會幫你
> delete，很好用的。
推 pointer_container
之前使用 std container 發生重大錯誤而不自知 :(
但如果不想使用 std::vector<boost::shared_ptr<T> >
時怎麼辦？
boost::ptr_vector<T> 是個絕佳的選擇