ETH官方钱包

創作內容

7 GP

傳說中的TMP---Template Metaprogramming,神的領域

作者:willyliu│2010-02-09 03:57:45│巴幣:14│人氣:9116
想想看,有人在程式編譯時塞了一堆運算,榨取程式效能(可能在你差個0.5秒就AC時)。不需要手動展開迴圈,卻獲得相同的效能。
不使用巨集,而且比巨集更高階、更抽象,兼具效能和語言層次的Template Metaprogramming就是此。

先做個簡單的C++ Template 簡單介紹吧。
沒有看過vector<T>?......至少也看過vector<int>吧。
角括號裏面的int不是裝飾用的,是用來宣告vector裏面存的是什麼型態。
裡所當然,你可以存char, double...等任何你想用的資料型態。
聰明的vector就會根據你所引入的類別,進行記憶體配置等操作。

vector所用的這項技術就是C++ Template的功能-泛型程式設計。
泛型就是適用於各種型態,程式碼卻只要寫一次。如下:
template < class T, class Allocator = allocator<T> > class vector;
這是C++標準的vector介面。

在上面的定義中class T所說的就是T是一個"任意"類別,你可以傳入當參數,和函式的"引數"相似。
在標準vector的函式裏面 會有許多T 的出現,當你把int代入T時,這份程式碼裡的T就會是int。

簡單的範例
template<class T, int N>
class A
{
T n[N];
};
這裡A<T, N>就是一個AT力場class template。

我們只要將int代入 、變成A<int, 10>,就會讓裏面的n變成一個int型態,size為10的陣列
要注意template<>後面沒有分號,因為它是用來影響class A的
清楚template在做什麼了?上頭的角括號就是參數列

但是,參數的型態只限定 "內建整數、bool、class" 其餘一蓋不行。
例如:
template<double D>
這樣就不行
還有,傳入int參數時只能傳入static const int,靜態常數
這是編譯器會因為template上頭的參數產生新的類別
如過你這樣寫:A<int, 10>,和這樣的效力是相同的
class A
{
int n[10];
};
編譯器要產生一個類別,是在編譯的時候完成的,不是在程式執行時。
所以int必須是"static const",這代表"編譯時期產生",且"不可更動"的數字。
這樣就不合法:
A<int, abs(-1)>
別以為他會產生A<int, 1>,他只會有error,abs的回傳值是一個執行期"變數"
正因為他限定編譯時期就必須決定的變數,我們可以利用"編譯期操作"來達成許多目標

好,現在開始進入Template Metaprogramming的世界
展示TMP常用的幾招:
template<int N>
struct A
{
static const int value =  A<N - 1>::value * 2;
};
然後,就會遞迴下去,什麼時候會停止?它不會!
所以,有數學基礎的應該都知道,遞迴式應該要有初始值:
template<>
struct A<0>
{
static const int value = 1;
};
這叫作"特化",編譯器不會用A<N>來產生A<0>,因為你已經指明了A<0>是什麼
所以A<n>::value(n >= 0)就會是2 ^ n
 上面template的地方要注意,被特化的參數不能放在裏面

下一個範例:
template<int N, int END>
struct Operation
{
static inline void OP1()
{
//some operations
Operation<N + 1, END>::OP1();
}
};
template<int END>
struct Operation<END, END>
{
static inline void OP1(){}
};

這是一個用template做成的迴圈,由於inline而且沒有使用變數,(編譯器)展開之後效能會很高
限制是迴圈的起、終點必須是靜態常數、我們要事先知道

下一個範例:
template<bool B, class TRUE, class FALSE>
struct IF
{
typedef TRUE result;
};
template<class TRUE, class FALSE>
struct IF<false, TRUE, FALSE>
{
typedef FALSE result;
};
這是一個條件句,相當於 B ? TRUE : FALSE
typedef也是TMP常用的手法

如果我把一些運算的結果,存在一個ARRAY<N>裏面,要怎麼在執行期間取值呢?
很遺憾,我不知道怎麼在常數時間取值,但可以在O(lg n)時間內辦到:
#include<cstdio>

using namespace std;
template<int N>
struct ARRAY
{
static const int a = ARRAY<N - 1>::a * 2;
};
template<>
struct ARRAY<0>
{
static const int a = 1;
};
template<int LOWER, int UPPER>
struct BS
{
static const int MID = UPPER + LOWER >> 1;
typedef BS<MID + 1, UPPER> GREATER;
typedef BS<LOWER, MID> LESS;
static inline int binary_search(int n)
{
if(n > MID)
return GREATER::binary_search(n);
else return LESS::binary_search(n);
}
};
template<int N>
struct BS<N, N>
{
static const int MID = N;
typedef ARRAY<MID> result;
static inline int binary_search(int n)
{
return result::a;
}
};
int main()
{
printf("ARRAY<%d>::a = %d\n", 28, BS<0, 30>::binary_search(28));
return 0;
}

這邊有了幾個簡單的TMP常用手法介紹,Boost已經有了一個偉大的程式庫叫作MPL
他提供了所有STL裡的,靜態的版本,非常強大,創作技巧可以參考他的原始碼,因為是Open Source的
Boost MPL
引用網址:http://www.jamesdambrosio.com/TrackBack.php?sn=249622
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:|program|programming|程式設計|程式|C++|

留言共 1 篇留言

天亮damody
在下的經驗是,沒事就省著用,大絕都是需要的時候才用的,
要用的話就最好寫一個vector等stl容器也可以通用的演算法,
畢竟template會的人太少,會與人溝通困難。

03-31 03:09

willyliu
是沒錯啦...template 的這種用法不是每個人都能接受的

這畢竟也是蠻前衛的東西03-31 23:05
我要留言提醒:您尚未登入,請先登入再留言

7喜歡★a27268139 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:USACO IOI題 p... 後一篇:USACO Ch4 Ov...


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情? 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】