|
|
I.背景
C++在很多人的心目中，一直是一種OO語言，而事實上，現(xiàn)在對C++的非OO部分的各種使用被逐漸地挖掘出來，其中最大的部分莫過于是 template。STL、loki、boost， ，很多先行者為我們提供了方案，有的已經(jīng)被列入C++標準的一部分。template的一個重要使用方法就是template meta programming，它利用編譯器對于template的解釋是靜態(tài)的這一特性，讓編譯器在編譯時做計算，可以有效的提高程序的運行速度。有關(guān)于 template meta programming的記載，最早見于Erwin Unruh，他在1994年寫了一個用template計算質(zhì)數(shù)的程序。我希望通過這篇文章介紹一些TMP的基本技巧和應用，并且最終完成一個質(zhì)數(shù)計算程序。
（閱讀本文的過程中，建議你試圖編譯每一個給出的程序。由于所有的類只需要public成員，所以都用struct聲明，但是仍然稱之為類。）
II.技術(shù)
通常我們編寫一個（小）程序，需要的語言支持其實不必很多，只要有順序、選擇和循環(huán)三種控制結(jié)構(gòu)理論上就可以寫出大多數(shù)程序了。我們先用TMP建立一個簡單的語言環(huán)境。
1.打印
程序有了結(jié)果，需要有一個方式反饋給運行者，這里我們利用C++的出錯信息，建立一個打印函數(shù)。要知道我們希望一切都在編譯的時候結(jié)束，那么我們就必須讓C++編譯器在編譯信息里面告訴我們，所以我們利用編譯器的出錯信息。當然這只是一個trick，如果你的TMP只是程序的一部分，你可以使用正常的輸入輸出。
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
這個類，每當別人引用到它的result的時候，編譯器就會打印出錯信息，因為一個unsigned int是不能隱式的轉(zhuǎn)成一個unsigned char*的。譬如下面這段程序
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
unsigned int test1 = print<77>::result;
unsigned int test2 = print<123>::result;
在我的Dev C++里，會輸出
main.cpp: In instantiation of `print<77>':
main.cpp:7: instantiated from here
main.cpp:4: invalid conversion from `unsigned char*' to `unsigned int'
main.cpp: In instantiation of `print<123>':
main.cpp:8: instantiated from here
main.cpp:4: invalid conversion from `unsigned char*' to `unsigned int'
這個輸出雖然不是很好看，但也算是差強人意。
2.選擇
Andrei Alexanderescu在他的大作Modern C++ Design里面使用過一個類，可以根據(jù)bool的值選擇不同的類型。今天我們要寫的一個是根據(jù)bool的值選擇不同的整數(shù)。
template<bool condition, unsigned int value1, unsigned int value2>
struct template_if
{
static const unsigned int result = value1;
};
template<unsigned int value1, unsigned int value2>
struct template_if<false, value1, value2>
{
static const unsigned int result = value2;
};
這里用到了模板的特化，如果你對這個不熟悉，那么大致可以這樣理解：第一個template_if的定義告訴編譯器，“一般的” template_if，會選擇第一個值作為結(jié)果。第二個template_if告訴編譯器，如果第一個參數(shù)是false的話，我們就使用第二個值（第三個參數(shù)）作為結(jié)果。下面這段代碼演示了template_if的用法。
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<bool condition, unsigned int value1, unsigned int value2>
struct template_if
{
static const unsigned int result = value1;
};
template<unsigned int value1, unsigned int value2>
struct template_if<false, value1, value2>
{
static const unsigned int result = value2;
};
template<unsigned int value>
struct print_if_77
{
static const unsigned int result = template_if<value == 77 , print<value>::result , 0>::result;
};
unsigned int test1 = print_if_77<77>::result;
unsigned int test2 = print_if_77<123>::result;
如果你去編譯這段代碼的話，你會發(fā)覺77和123都被打印出來了，雖然錯誤信息不一樣，但是這不是我們想要的結(jié)果。為什么呢？很遺憾，對C++編譯器來說，template_if<true, 1, 100>和template<true, 1, 200>是兩個不同的類，雖然后一個參數(shù)的值我們并不關(guān)心，但是編譯器必須在template初始化的時候，給出所有的參數(shù)，這就導致它會去計算 print<value>::result，當然，計算的結(jié)果就是報錯。也就是說，因為編譯器要計算這個值才導致了我們的print不可用，要解決這個問題，有兩個方法：或者讓編譯器不計算這個值，或者讓編譯器在某些情況下可以計算出正確的值。
方法一可以讓編譯器不計算這個值，通過修改template_if，我們傳入兩個不同的類，而不是unsigned int。
首先修改print，加一個新的類dummy_print：
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct dummy_print
{
static const unsigned int result = value;
};
接著，加入一套對類型進行選擇的模板：
template<bool condition, typename T1, typename T2>
struct template_if_type
{
static const unsigned int result = T1::result;
};
template<typename T1, typename T2>
struct template_if_type<false, T1, T2>
{
static const unsigned int result = T2::result;
};
這樣原先的程序就變成：
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct dummy_print
{
static const unsigned int result = value;
};
template<bool condition, typename T1, typename T2>
struct template_if_type
{
static const unsigned int result = T1::result;
};
template<typename T1, typename T2>
struct template_if_type<false, T1, T2>
{
static const unsigned int result = T2::result;
};
template<unsigned int value>
struct print_if_77
{
static const unsigned int result = template_if_type<value == 77 ,
dummy_print<value> , print<value>>::result;
};
void main()
{
unsigned int test1 = print_if_77<77>::result;
//unsigned int test2 = print_if_77<123>::result;
}
現(xiàn)在的“運行結(jié)果”非常正確。
方法二可以讓編譯器在某些情況下計算出正確的值，我們加一套新的模板：
template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = (unsigned char*)value;
};
原先的程序變?yōu)椋?br>template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print_if_77
{
static const unsigned int result = print_if<value == 77 , value>::result;
};
void main()
{
unsigned int test1 = print_if_77<77>::result;
//unsigned int test2 = print_if_77<123>::result;
}
輸出也是正確的。
這兩種方案，我個人傾向于后者，因為其實我們一定是要做一次判斷的，并且這次判斷一定會添加新的類，那么還是print_if的解決方案比較直觀。
3. 循環(huán)
首先必須明確的是，template不可能實現(xiàn)我們一般意義上的循環(huán)，但是它可以做一件和循環(huán)類似的事情：迭代。
如果有這樣一個循環(huán)：for( unsigned int i = 0 ; i < value ; ++i )
我們可以這樣寫：
template<unsigned int value>
struct loop
{
static const unsigned int result = loop<value - 1>::result + 1;
};
template<>
struct loop<0>
{
static const unsigned int result = 0;
};
這就是告訴編譯器，我們的迭代從0開始，到value結(jié)束，每個值是前者加1。
下面給出一個更廣泛的循環(huán)的實現(xiàn)：for( unsigned int i = begin ; i < end ; i = i + step )，假設(shè)0<=begin<end，并且step>0。（更復雜的情況，總可以通過template specialization分派完成）
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct loop
{
static const unsigned int result = loop< begin + step, end, step>::result - step;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct loop<begin, end, step, false>
{
static const unsigned int result = begin;
};
這里的result的計算過程不重要，關(guān)鍵是為了驅(qū)動編譯器進一步的實例化模板。
下面是一個實例程序，用來打印13到29之間的整數(shù)，步長為5。
template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = value;
};
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct loop
{
static const unsigned int result = loop< begin + step, end, step>::result - step;
static const unsigned int print_result = print_if<true, result>::result;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct loop<begin, end, step, false>
{
static const unsigned int result = begin;
};
static unsigned int result = loop<13,29,5>::result;
III.應用
上面我已經(jīng)介紹了怎樣用TMP實現(xiàn)打印，選擇和循環(huán)了，現(xiàn)在我們來把這些投入運用。下面我會用上面的所提供的機制，寫兩個程序：計算階乘和計算質(zhì)數(shù)。
1.計算階乘
我們先寫一個普通的C++程序來計算階乘：
#include <iostream>
int main()
{
unsigned int limit = 10;
unsigned int factorial = 1;
for( unsigned int i = 1 ; i <= limit ; ++ i )
factorial *= i;
std::cout<<factorial<<std::endl;
}
這個程序是一個一重循環(huán)，我們就用循環(huán)來做：
template<unsigned int value>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct loop
{
static const unsigned int result = loop< begin + step, end, step>::result * begin;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct loop<begin, end, step, false>
{
static const unsigned int result = begin;
};
static unsigned int result = print<loop<1, 10, 1>::result>::result;
因為這里不必要盤算是否輸出，所以就直接用print了。
2.計算質(zhì)數(shù)
同樣，我們先寫一個普通的程序來計算：
#include <iostream>
int main()
{
unsigned int limit = 30;
for( unsigned int i = 2 ; i <= limit ; ++i )
{
unsigned int j;
for( j = 2 ; j < i ; ++j )
if( i % j == 0 )
break;
if( i == j )
std::cout<<i<<std::endl;
}
}
這里用到了兩層循環(huán)，而且還是用了分支和打印。用我們提供的機制轉(zhuǎn)化成TMP形式如下：
template<bool condition, unsigned int value>
struct print_if
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print_if<false, value>
{
static const unsigned int result = value;
};
template<bool condition, unsigned int value1, unsigned int value2>
struct template_if
{
static const unsigned int result = value1;
};
template<unsigned int value1, unsigned int value2>
struct template_if<false, value1, value2>
{
static const unsigned int result = value2;
};
// 這里增加一個i作為參數(shù)，因為在內(nèi)循環(huán)也需要知道外部的i的值
template<unsigned int i, unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct inner_loop
{
static const unsigned int result = template_if<i % begin,
inner_loop< i, begin + step, end, step>::result,
begin>::result;
};
template<unsigned int i, unsigned int begin, unsigned int end, unsigned int step>
struct inner_loop<i, begin, end, step, false>
{
static const unsigned int result = begin;
};
template<unsigned int begin, unsigned int end, unsigned int step, bool loop_continue = begin < end >
struct outer_loop
{
static const unsigned int result = outer_loop< begin + step, end, step>::result;
static const unsigned int is_prime = inner_loop<begin, 2, begin, 1>::result == begin;
static const unsigned int print_result = print_if<is_prime, begin>::result;
};
template<unsigned int begin, unsigned int end, unsigned int step>
struct outer_loop<begin, end, step, false>
{
static const unsigned int result = 0;
};
static unsigned int result = outer_loop<2, 30, 1>::result;
III.細節(jié)
另外有兩點要說一下：
我們的template_if其實有一種更簡單的寫法，就是?:表達式。
而我們的print_if和print其實可以用確省的模板參數(shù)來統(tǒng)一，唯一的區(qū)別是，要把value放在condition前面。
template<unsigned int value, bool condition = true>
struct print
{
static const unsigned int result = (unsigned char*)value;
};
template<unsigned int value>
struct print<value,false>
{
static const unsigned int result = value;
};
這樣你可以用print<value>來打印一個數(shù)值，也可以用print<value, condition>來做判斷打印。
IIII.后記
很久以前看Inside OLE2的時候，記得作者說過一句話：作者因為寫書而明白。我其實幾年前就寫過類似的程序，但是從來沒有對這樣程序的寫法進行過總結(jié)以至于每一次都是在重新開始。而寫完這篇文章后，我覺得自己比過去明白很多。template meta programming還有很多不同的應用，我以后有機會會繼續(xù)介紹給大家。
對于這篇文章有任何問題，請發(fā)信到 polyrandom@hotmail.com 和我聯(lián)系，也請訪問 http://www.allaboutprogram.com/ 以獲得最近的更新。
|