C++ 的另一個新世界
C++ 的 MetaProgramming
廢話就不說了, 按照C的傳統慣例,介紹programming的最好方式就是show代碼, 第一個例子就是Hello,world, 這篇文章也不例外
在任何一個cpp文件中,輸入
struct hello_world; //forward declaration
struct A : hello_world
{
};
然后編譯..,注意我沒有說"編譯運行",而僅僅說的是"編譯", 如果不意外的話,在你編譯器的輸出窗口會出現
base class hello_world undefined
或者
base class `hello_world' has incomplete type
等類似的語句, 至少在你的屏幕上打印出了 "hello_world" 字樣,對吧? 對了,這就是這個例子的目的, 我不也打印出來的嗎?
上面這個簡陋的例子闡述了一個重要的現象, "編譯時"而不是運行時, 這就是meta programming的世界, 一個處于編譯期間, 而不是運行期間的世界.
運行時我們能作的事情很多在編譯時我們不能作, 例如我們不能調用函數, 我們不能創建對象, 我們也不能設置斷點, 一切都交給你的C++編譯器.
接下來, 首先回顧一下一些C++的基本模板知識.
由于C++的編譯器符合ISO 標準的程度不一, 我使用的是VC++ 6 和 gcc version 3.2.3 (mingw special 20030504-1)
下面的例子我在這兩個編譯器中都測試過.
C++模板的最經常的認識就是STL中的容器, 例如
vector<int> 就是一個可以裝int的動態數組, vector<sharp*> 就是一個可以裝sharp對象指針的數組.
然后我們還需要一點點模板特化的知識.
例如
template<class T> struct Foo {};
這是一個通用模板, 必配任何類型, 如果我們需要對int進行特別處理, 那么
template<> struct Foo<int> {};
這樣就實現了對 int 類型的完全特化 . VC6 只支持完全特化, 不支持偏特化, 或者部分特化.
不過還是稍微介紹一下:
什么是遍特化了? 還就上面這個例子而言, 如果我們想對所有的指針進行特化, 那么應該是
template<class T> struct Foo<T*> {}
那么什么又是部分特化了, 看看這個:
template<class T, class U> struct bar {};
template<class T> struct bar<T, int> {};
后面這個就是對U模板參數的部分特化,使得 U為 int的時候 使用這個版本.
這篇文章由于針對VC6, 因此你不會遇到偏特化和部分特化的情況.
hello,world的例子以后, 我們準備干點有意思的事情. 例如求兩數之和. 首先看看在運行時的函數我們應該如何實現:
定義:
int sum(int x, int y) { return x+y; }
調用:
int j = sum(3, 4)
那么如何用meta programming的方式實現了?
meta programming 由于處于編譯器, 因此給它的參數必須是編譯時就可以確定的, 在當前C++中允許的為,integer 和 type.
就上面這個例子, 對于模板的調用應該是:
int j = sum_<3,4>::value;
3,4 都為整形常量, 編譯時確定, 然后返回值如何取得? 記住在編譯時是無法進行真正的函數調用的,因此我們只有通過定義在模板類中的一個常量
來獲得返回結果. 最簡單的方法就是在一個 struct定義一個匿名的enum .
sum的定義如下:
template<int x, int y>
struct sum_
{
enum { value = x + y };
};
然后你可以編譯后"運行"檢查檢查看看運行結果
#include <iostream>
using namespace std;
template<int x, int y>
struct sum_
{
enum { value = x + y };
};
int main()
{
cout << sum_<3, 4>::value << endl;
return 0;
}
上面之所以使用struct sum_而不是class sum_是因為struct的默認作用范圍上public, 可以省略幾個鍵擊.
這個例子通用展示了一個重要的觀點, 對應通常可以在運行時調用的函數
int foo(int a, int b)
其對應的meta 實現為:
foo<a, b>::value
也就是我們的foo現在為一個struct name, 參數通過< > 中的模板投遞, 結果通過 ::value 獲得其中定義的一個匿名enum值.
那么如何計算 3,4,5的和?
你可能會想如下:
sum_<3,4,5>::value
但是c++不支持一個模板類使用不同的參數參數存在, 換一個方式,
你如何在 int sum(int a, int b) 存在的情況下獲得3個數的和?
我們可以這樣：
sum( 3, sum(4, 5))
有lisp 背景的可能發現這很符合他們的思考方式, 至少以我浮淺的emacs lisp知識, 不使用中間變量. 同樣,meta中你也可以這樣使用:
sum_< //開始參數
sum_< 3 //第一個參數為3
sum_< 3, sum_< //第二個參數是另外一個表達式的結果
sum_< 3, sum_<4, //這個表達式的第一個參數為４
sum_< 3, sum_<4, 5> //這個表達式的第二個參數為５
sum_< 3, sum_<4, 5>::value //通過::value獲得這個表達式的結果
sum_< 3, sum_<4, 5>::value >::value //然后獲得整個表達式的結果
ok, 就這么多, 看出來沒有, 再解釋一次, 將上面我們的
cout << sum_<3, 4>::value << endl;
中４的位置用一個sum_ 替換就得到了我們需要的三個數之和.
cout << sum_<3, ?? >::value << endl;
===>
?? = sum_<4, 5>::value
===> then
cout << sum_<3, sum_<4, 5>::value >::value << endl;
如果我需要算 2, 3, 4, 5之和呢?
同樣簡單, 你將上面的3, 4 ,5 中的任何一個常量替換成對sum_ 進行一個調用就可以了.
例如:
out << sum_< ?? , sum_<4, 5>::value >::value << endl;
?? = sum_< 2, 3 >::value
合并后為
cout << sum_< sum_<2, 3>::value , sum_<4, 5>::value >::value << endl;
運行的結果為 14.
這就是meta中最簡單的一個例子, 順序調用, 如果你看明白了同時覺得有點意思的話, 下來我們講講
循環語句, 通常我們寫程序都避免遞歸, 因為容易造成堆棧和大腦溢出,但是在 meta 中必須使用遞歸的方式.
下面看看一個計算"階乘"的例子, 其實這個才真正是meta 中的hello,world.
先看后面, 我們調用的方式:
cout << fac<5>::value ; // 結果應該是 5 * 4 * 3 * 2 * 1 = 120;
通過前面的知識, 你知道fac是一個template struct的名字, 有一個模板參數int, value是其中的一個匿名枚舉變量
于是你可以毫不猶豫的寫下:
template<int i>
struct fac
{
enum { value = ??? };
};
但是在value的地方你卡住了, 如果根據 i 得到 value?
讓我們將大腦從"編譯時世界"切換到"運行時的世界", 你如何寫一個通常的遞歸函數來計算階乘?
int fac(int n)
{
if( n == 1)
return 1;
return n * fac(n-1);
}
注意 n == 1是一個遞歸退出條件,先不考慮n為1時的遞歸退出,
其他情況下是將n 乘以 fac (n - 1). 有了前面的sum_ 知識, 你應該可以推出 value = ???
中的??? 應該是
n * //n*
fac //調用下一個fac
fac<n-1> //參數為n-1
fac<n-1>::value //獲得結果
因此fac "函數"的模板實現就是
template<int i>
struct fac
{
enum { value = i * fac<i - 1>::value };
};
然后我們再考慮遞歸退出條件, 為1時value應該為1, 拿起C++中的特化模板武器來
template<>
struct fac<1> //參數為1時的特化
{
enum { value = 1 };
};
這樣就將參數為 1 時的返回值設置為1, 結束遞歸.
這樣,當你輸入
cout << fac<5>::value << endl;
時,編譯器會實例化
template<>
struct fac<5>
{
enum { value = 5 * fac<4>::value };
};
由于fac<5> 需要 fac<4> , 因此然后實例化 fac<4>, 同樣的原因, fac<3> , fac<2>, fac<1>
到fac<1> , 編譯器發現了一個特化版本fac<1> 匹配, 在fac<1>中的value已經是一個常量, 不依賴其他的fac實例, 遞歸退出, 最后
我們得到最終結果120 .
easy, 對不?
然后再介紹 if語句.
還是上面的這個fac例子, 負數的階乘是沒有意義的,先不考慮數學問題,假設我們希望在這個情況下返回-1,如何實現?
如果我們輸入fac<-2>::value , 那么編譯器會嘗試實例化fac<-3>, fac<-4>, ......
你發現這是一個無限遞歸條件, 在運行時會造成你堆棧溢出, 由于我們在"編譯時世界", 取決于你編譯器, 最終總有結束的時候.
例如VC6 報錯: fatal error C1202: recursive type or function dependency context too complex
G++報錯 : template instantiation depth exceeds maximum of 500
因此我們需要一個if判斷語句, 發現當模板參數 < 1的時候返回 -1.
按照測試先行的原則, 我們可以預計
fac<-1>::value == -1 是成立的.
現在的問題是如何實現? 下次再說吧! 也給個機會折磨折磨你的大腦. 記住, 模板不僅僅可以通過enum返回整數, 還可以通過嵌套 typedef返回一個類型.
上回說到一個fac的版本, 希望在負數的情況下返回-1, 而不是無限遞歸下去.
還是按照我們的思維, 先寫個對應"運行時世界"的版本.
int safe_fac(int n)
{
if( n < 1)
return -1;
return fac(n);
}
這個if邏輯很簡單, 如果模板參數<1, 那么直接返回 -1, 否則 還是使用前面的fac那個版本.
好, 轉換成我們的meta 版本.
你想,用個 ?: 運算符不就解決了嗎?
template<int n>
struct safe_fac
{
enum { value = (n < 1 ? -1 : fac<n>::value ) };
};
可惜不對, ?= 只有在"運行時世界"才能使用. 那么 value 后面的???寫什么好呢?
先輕松輕松, 寫一個if的meta 版本, 我敢保證你能看得懂.
template< bool b , class T, class U>
struct if_
{
typedef T type;
};
注意了, 如果以前我們提到的例如sum_, fac等meta functions(其實就是c++中的模板類, 稱之為meta function是因為它們就像是function)
是通過一個 在enum中的value 返回整形的話, 上面剛剛的if_這個例子就展示了 meta中的另外一個武器, 通過typedef 一個type 返回一個類型.
如果我們這樣調用
if_<true, int, double>::type 的結果就是 int 類型, 注意是"類型", 不是對象.
我們想在b為false的時候返回第二個類型U, 即:
if_<false, int, double>::type 的返回結果是double
那么還是很簡單, 部分特化 b 參數就可以了.即:
template<class T, class U>
struct if_<false, T, U>
{
typedef U type;
};
我最前面說了, VC6不支持部分特化, 但是別忘了計算機時間的一條公理:
任何計算機問題都可以通過增加一層來解決. 大部分VC6中的模板的問題還是可以解決的. 如果你不使用VC6, 這部分就不用看了.
VC6是支持全部特化的, 因此我們可以將true, false特化出來
template<bool>
struct if_help
{
...
};
template<>
struct if_help<false>
{
...
};
這個在vc6中是支持的. 然后我們還需要兩個額外的類型參數T,U, 這可以通過嵌套類來實現. 即
template<bool>
struct if_help
{
template<class T, class U>
struct In
{
typedef T type;
};
};
template<>
struct if_help<false>
{
template<class T, class U>
struct In
{
typedef U type;
};
};
然后我們真正的if_ "meta 函數"如下定義:
template<bool b, class T, class U>
struct if_
{
typedef if_help<b>::In<T, U>::type type;
};
先根據b的內容實例化一個對應的if_help, : if_help<b>
然后給其中的In模板投遞T,U參數, ::In<T, U>
然后通過type獲得其中的返回類型 ::type
最后typedef type一下作為自己的返回類型, 這樣外部就可以通過
if_<true, int, double>::type 獲得返回的類型了.
上面if_ 的實現實際上要用幾個C++關鍵字修飾一下:
typedef if_help<b>::In<T, U>::type type;
===>
typedef typename if_help<b>::template In<T, U>::type type;
為什么要加上typename 和 template, 這個解釋起來到是很費勁. 有空再說.
好了, 從模板的語法世界中清醒過來, 現在你知道的是, 我們有了一個if_ 的meta函數, 接受3個參數bool b, class T, class U,
如果b為true, 那么它的返回值 (通過 if_::type 返回) 就是T,
如果b為false, 那么它的返回值 (通過 if_::type 返回) 就是U.
前面我提過了, 參數是通過<>來傳遞的, 因此一個例子就是
if_
//函數名
if_<true,
//第一個參數, bool 型
if_<true, int //第二個參數, 類型
if_<true, int, double //第3個參數, 類型
if_<true, int, doubble> //右括號表示參數結束
if_<true, int, double>::type //通過::type獲得返回結果, 不是value了, 當然這僅僅是一個命名慣例.
因此上面的那個 if_<true, int, double>::type 返回的就是 int,
在"運行時世界", 你可以如下使用:
for( if_<true, int, double>::type i = 0; i < 10; i++) {
cout << "line " << i << "\n";
}
等同于
for( int i = 0; i < 10; i++) {
cout << "line " << i << "\n";
}
當然對于這個例子這樣使用是"有病". 我們等會會用到if_來實現前面的 safe_fac 實現了.
注意我說的返回值并不是前面sum_例子中的整形了, 這個時候返回一個類型. 類型不是實例對象, 這點我想你應該清楚.
編譯時不可能返回對象, 因為要調用構造函數, 要確定對象地址, 我們還沒有進入到" 運行時世界" , 對吧?
實際上meta programming 最重要的使用并不是前面我們提到過的sum_, fac這些, 因為畢竟拿個計算器算一下也花不了幾個時間.
但是返回type就不同了.
那么type可以是什么呢? 可以是int, double這樣的基本類型, 也可以我們前面的 sum_ 模板類等等.
然后再看safe_fac的實現:
先不考慮 <1 的情況, 那么value就應該是直接調用以前的 fac 函數
template<int n>
struct safe_fac
{
enum { value = fac<n>::value };
};
然后再使得 >= 1時才使用fac函數, 那么利用我們前面的if_, 先忽略語法錯誤, 那么可以如下
enum
{
value = if_< n < 1,???, fac<n> >::type::value
};
首先, n < 1 為真時返回一個類型???, 暫時我們還沒有實現, 為false時返回
fac<n>類型, 然后通過::type獲得返回的類型,或者為???, 或者為fac<n>,
然后通過::value得到這個類型的整數結果.
那么 ??? 應該是什么呢? 當然不能直接是-1, 否則 -1::value 就是語法錯誤.
因此我們可以定義一個簡單的"函數", 返回-1:
struct return_neg1
{
enum { value = -1 };
};
如果我們需要返回-2怎么辦? 又定義一個return_neg2 "函數"? 干脆我們一勞永逸, 定義如下:
template<int n>
struct int_
{
enum { value = n };
};
這樣int_ 這個"函數"就是你給我什么, 我就返回什么. 不過int_是一個類型, 例如:
通過如下調用 int_<3>::value 返回它的結果3.
有了這個, 我們的代碼就如下:
value = if_< n < 1, int_<-1>, fac<n> >::type::value
原理清楚了, 最終的版本就是:
template<int n>
struct safe_fac
{
enum { value = if_< n < 1, int_<-1>, fac<n> >::type::value };
};
試試:
cout << safe_fac<-1>::value 輸出 -1.
循環(遞歸表示), 條件判斷, 順序執行都有了, 剩下的就看你自己了.
--------------------------------------------------------------------------------
Boost中的mpl (meta programming library) 提供了一個專門用于metaprogramming的library, 同時前面提到的if_, int_等等就
是從mpl中拷貝來的, 當然我簡化了很多.
Modern C++ Design 其中的Typelist將meta progamming的循環(就是遞歸)發揮得淋漓盡致, 在侯捷的網站上www.jjhou.com有免費的前4章可讀. Typelist在第三章.
書中序言部分, Effective C++的作者Meyers說到, 如果第3章的typelists沒有讓你感到振奮, 那你一定是很沉悶.
就我親身體驗, 我覺得Meyers可能是說到委婉了些:
如果第3章的typelists沒有讓你感到振奮, 那1%的可能是你是很沉悶, 99%的可能是你沒有看懂. I did.
GoF之一的 John Vlissides同樣提到了typelists這一章就值得本書的價格. I believe.
另外, 我發現即使在這本讓人抓狂的天才之作中, 作者仍然使用了n個TYPELIST_n 這樣的預處理宏來處理多個type的情況, 但是在sourceforge
下的Loki庫中我發現已經有了一個MakeTypelist"函數", 看來 meta programming 確實是, 啊...
是不是作者當時都沒有預見到還能夠以C++編譯器內建的模板能力, 而不是依賴預處理宏來處理typelist.?
又, mpl中有專門裝type的容器....