C模板元編程技術與應用

1、C+模板元編程技術與應用榮耀動機讓更多的C+程序員了解模板元編程，并在此過程中獲得快樂！目錄* 歷史* 導入范例* 主要思想* 靜態(tài)語言設施* 控制結構* 數據結構* 數值計算* 類型計算* 代碼生成* 斷言和契約* 庫* DSEL設計* 結語* 資源歷史1994年，在圣迭哥舉行的一次C+標準委員會會議期間，Erwin Unruh展示了一段特別的代碼，可以在編譯期以編譯錯誤信息的方式產生從2到某個給定值之間的所有質數。這份代碼的原始版本見注5，修訂版見注6。可以使用GCC編譯器觀察到上述效果。同年夏天，Todd Veldhuizen受Erwin的例子啟發(fā)，發(fā)現可以使用C+模板進行元編程（met

2、aprogramming），并發(fā)表了一份技術報告。次年5月又在C+ Report上發(fā)表了一篇名為“Using C+ template metaprograms”的文章，從而將Erwin Unruh發(fā)現的C+編譯期模板編程（Compile-time Template Programming）進一步精化為C+模板元編程（Template Metaprogramming，TMP）。導入范例/ 主模板templatestruct Fib enum Result = Fib:Result + Fib:Result ;/ 完全特化版template struct Fib enum Result = 1 ;

3、/ 完全特化版template struct Fib enum Result = 0 ;1.計算Fibonacci數列第N項/ 示例int main() int i = Fib:Result; / std:cout i std:endl; 主模板用于處理一般的邏輯處理N=1的情況處理N=0的情況特化必須放在主模板之后導入范例語句int i = Fib:Result;被VC7.1編譯成如下指令（Intel P4 CPU）： 00411A1E mov dword ptr i,37h 字面量37h即為Fibonacci數列的第10項的值?？梢?，Fib:Result的確被評估于編譯期，結果作為處理器指

4、令的一部分而被存儲起來。運作機理：當編譯器實例化Fib時，為了給其enum Result賦值，編譯器需要對Fib和Fib進行實例化，同理，又需要針對Fib和Fib實例化同樣的模板，當實例化到Fib和Fib的時候，完全特化版被實例化，至此遞歸結束。這個處理過程類似于遞歸函數調用，編譯器被用于解釋元程序，生成的結果程序中僅包含一個常量值。導入范例/ 主模板templatestruct IfThenElse typedef T1 ResultType;/ 局部特化templatestruct IfThenElse typedef T2 ResultType;/ 示例IfThenElse:Result

5、Type i; / i的類型為int2.類型選擇基于給定的布爾常量表達式在兩個類型之中二選一。若表達式為true，則T1被typedef為ResultT，否則ResultT代表T2。只針對模板參數的局部進行特化。主要思想利用模板特化機制實現編譯期條件選擇結構，利用遞歸模板實現編譯期循環(huán)結構，模板元程序則由編譯器在編譯期解釋執(zhí)行。靜態(tài)語言設施模板元編程使用靜態(tài)C+語言成分，編程風格類似于函數式編程，其中不可以使用變量、賦值語句和迭代結構等。在模板元編程中，主要操作整型（包括布爾類型、字符類型、整數類型）常量和類型。被操縱的實體也稱為元數據（Metadata）。所有元數據均可作為模板參數。其他元數

6、據類型還包括枚舉、函數指針/引用、全局對象的指針/引用以及指向成員的指針等。另外，已經有一些編譯期浮點數計算探索（參見注7）。由于在模板元編程中不可以使用變量，我們只能使用typedef名字和整型常量。它們分別采用一個類型和整數值進行初始化，之后不能再賦予新的類型或數值。如果需要新的類型或數值，必須引入新的typedef名字或常量。靜態(tài)語言設施編譯期賦值通過整型常量初始化和typedef語句實現。例如：enum Result = Fib:Result + Fib:Result;或static const int Result = Fib:Result + Fib:Result;成員類型則通過t

7、ypedef引入，例如：typedef T1 Result;新、舊編譯器均支持靜態(tài)語言設施條件結構采用模板特化或條件操作符實現。如果需要從兩個或更多種類型中選其一，可以使用模板特化 ，如前述的IfThenElse。可以使用條件操作符返回兩個候選數值之一，例如：templatestruct Max enum Result = (a b) ? a : b ; ;靜態(tài)C+代碼使用遞歸而不是循環(huán)語句。遞歸的終結采用模板特化實現。如果沒有充當終結條件的特化版，編譯器將一直實例化下去，一直到達編譯器的極限。C+標準建議編譯器實現至少要支持17層實例化。大多數編譯器支持的遞歸實例化數目遠不止17。例如，GC

8、C支持多達500層遞歸模板實例化。C+靜態(tài)語言設施是圖靈完備的，理論上可以用于實現任何可實現的算法?？梢允褂媚０逶幊虒崿F與運行期C+所對應的程序流程控制結構?？刂平Y構/ If/ 主模板templatestruct If;/ 完全特化版templatestruct If static void F() / 待執(zhí)行的語句 ;/ 完全特化版templatestruct If static void F() / 待執(zhí)行的語句 ;/ 示例If:F();主模板未必一定要予以定義。此主模板純粹供隨后的特化所用?？刂平Y構/ For/ 主模板templatestruct For static inline v

9、oid f() / 待執(zhí)行的語句 For:f(); ;/ 完全特化版templatestruct For static inline void f() / 空，什么都不做 ;類似地，可以給出While、Do-While實現/ 使用For:f();我們必須給出這個什么也不做的f()，否則會導致N=1時實例化失敗?？刂平Y構/ Switch/ 主模板templatestruct Switch static void f() / 缺省情況下執(zhí)行的語句 ;/ 完全特化版1templatestruct Switch static void f() / 待執(zhí)行的語句1 ;/ 完全特化版2templatest

10、ruct Switch static void f() / 待執(zhí)行的語句2 ;/ 示例Switch:f();該實現不夠直觀，在語法上和運行期switch相去甚遠。一個更自然的實現應該支持類似于運行期switch的語法控制結構struct A static void execute() cout A endl; ;struct B static void execute() cout B endl; ;struct C static void execute() cout Default endl; ;/ 用法示例Switch(1+1-2), Case1, A, Case2, B, Case :

11、Result:execute(); / 打印“Default我們希望支持這樣的用法控制結構/ Switchconst int DEFAULT = -1; struct NilCase;template struct Case enum tag = tag_; typedef Type_ Type; typedef Next_ Next;/ 主模板template struct Switchprivate: typedef typename Case:Next NextCase; enum caseTag = Case:tag, found = (caseTag = tag | caseTag

12、= DEFAULT);public: typedef typename IfThenElsefound, typename Case:Type, typename Switch:Result:ResultType Result;/ 局部特化template struct Switch typedef NilCase Result;利用typename消除歧義 如前述 類似地，可以分別給出更符合直覺的、結構性更好的For、While、Do-While實現。控制結構最早提出編譯期控制思想并給出雛形實現的是Todd Veldhuizen，參見注1。Krysztof Czarnecki, Ulrich

13、 Eisenecker則實現了更一般化的編譯期結構（如剛才展示的第二個版本的Switch）參見注12。可以使用嵌套模板實現復雜的編譯期數據結構（編譯期容器），其中可以容納整數和類型?？疾靸蓚€例子：一個序列，為Loki庫中的Typelist；一個是二叉樹（或樹的二叉樹表示）結構。數據結構Boost MPL庫中定義有vector、deque、list、set以及map等序列，它們都是編譯期數據結構。數據結構/ Typelisttemplate struct Typelist typedef T Head; typedef U Tail; / 計算長度/ 主模板template struct Len

14、gth;/ 局部特化template struct LengthTypelist enum value = 1 + Length:value ; / 完全特化template struct Length enum value = 0 ;/ 示例typedef Typelistchar, Typelist T;cout Length:value endl; / 2/ 哨衛(wèi)類型class NullType ;一個typelist的 長 度 等 于tail的長度加1數據結構/ BTreeconst int LEAFVALUE = -1; / 葉子節(jié)點值/ 葉子節(jié)點struct BTLeaf enum

15、 Value = LEAFVALUE ; typedef BTLeaf Left; typedef BTLeaf Right;template struct BTree / BTNode enum Value = N ; typedef Left_ Left; typedef Right_ Right;數據結構/ 判樹是否為空/ 主模板template struct IsEmpty;/ 局部特化template struct IsEmptyBTree enum Result = false ;/ 完全特化templatestruct IsEmptyBTree enum Result = tru

16、e ;數據結構/ 示例typedef BTree tree1;typedef BTree tree2;typedef BTree1, BTree, BTree tree3;int main() cout IsEmpty:Result endl; / 1 cout IsEmpty:Result endl; / 0 cout IsEmpty:Result endl; / 0等價于：typedef BTree aTree2;由于模板元編程最先是因為數值計算而被發(fā)現的，因此早期的研究工作主要集中于數值計算方面，先鋒是Todd Veldhuizen和Blitz+庫。元編程在該領域最早的應用是實現“循環(huán)開

17、解（Unroll Loop）”。其他庫（例如MTL、POOMA等）也采用了這種技術。數值計算數值計算領域還有很多重要的模板元編程（相關）技術，例如“表達式模板（Expression Templates）”（見注2）、“部分求值（ Partial Evaluation）”（見注3）等。數值計算/ 主模板template struct DotProduct static T Result(T* a, T* b) return *a * *b + DotProduct:Result(a+1, b+1); ;/ 局部特化template struct DotProduct static T Resul

18、t(T* a, T* b) return *a * *b; ;一個經典的循環(huán)開解例子：計算向量點積算法思想：向量a和b的點積=向量a和b首元素的乘積+剩余維度向量之點積一維向量的情形數值計算/ 示例int main() int a5 = 1, 2, 3, 4, 5 ; int b5 = 6, 7, 8, 9, 10; cout DotProduct:Result(a, b) endl; / 130/ 循環(huán)開解過程DotProduct:result(a,b)= *a * *b + DotProduct:result(a+1,b+1)= *a * *b + *(a+1) * *(b+1) + Do

19、tProduct:result(a+2,b+2)= *a * *b + *(a+1) * *(b+1) + *(a+2) * *(b+2) + DotProduct:result(a+3,b+3)= *a * *b + *(a+1) * *(b+1) + *(a+2) * *(b+2) + *(a+3) * *(b+3) + DotProduct:result(a+4,b+4)= *a * *b + *(a+1) * *(b+1) + *(a+2) * *(b+2) + *(a+3) * *(b+3) + *(a+4) * *(b+4)值得一提的一個模板元編程陷阱長期以來，科學計算領域一直是F

20、ortran的天下，采用運行期C+實現的算法太慢而無法適應數值計算的要求，利用元編程、表達式模板以及更好的編譯器、優(yōu)化器，現代C+也可以很好地滿足數值計算的要求。數值計算Todd Veldhuizen對C+和Fortran在科學計算領域的性能表現作了比較 （參見注4） 。實踐證明，對于現代C+編程而言，元編程最大的用場本并不在于編譯期數值計算，而是用于類型計算（type computation）（及相關領域）。通過類型參數、模板參數、typedef、枚舉（或靜態(tài)整型常量）以及內嵌類（模板）成員等，借助于靈活的類模板特化能力，模板元編程在類型計算方面可以釋放出極大的能量。類型計算類型計算/ 僅聲

21、明struct Nil;/ 主模板template struct IsPointer enum Result = false ; typedef Nil ValueType;/ 局部特化template struct IsPointer enum Result = true ; typedef T ValueType;/ 示例int main() cout IsPointer:Result endl; cout IsPointer:Result endl; IsPointer:ValueType i = 1; /IsPointer:ValueType j = 1; / 錯誤：使用未定義的類型N

22、il可以依樣實現出IsReference、IsClass、IsFloat、IsMemberPointer等元函數，事實上，Boost Type Traits庫提供了數十個類似的元函數以及像add_reference這樣的低級類型操縱元函數，用于偵測、處理類型的基本屬性。該庫已經被納入C+標準委員會技術報告（Technical Report），這預示著它將會進入C+0 x標準。前述的“循環(huán)開解”實際上就是一種代碼生成機制，但模板元編程代碼生成機制的作用并不局限于數值計算領域。代碼生成struct A static void execute() cout A endl; ;struct B sta

23、tic void execute() cout B endl; ;int main() IfThenElse:ResultType:execute();模板元程序充任“高級的預處理指令”等價template struct ScatterHierarchyTag;template class TList, template class Unit struct GenScatterHierarchy;/見下頁前述的“循環(huán)開解”實際上就是一種代碼生成機制，但模板元編程代碼生成機制的作用并不局限于數值計算領域。代碼生成此例摘自Loki&MCDstruct Nil; / 僅聲明struct Em

24、pty;/ Typelisttemplate struct TypeList typedef H Head; typedef T Tail;模板也是一種元數據代碼生成/ 接上template class T1, class T2, template class Unitstruct GenScatterHierarchyTypeList, Unit : public GenScatterHierarchyScatterHierarchyTag, Unit , public GenScatterHierarchy;template class T1, class T2, template cla

25、ss Unitstruct GenScatterHierarchyScatterHierarchyTag, Unit : public GenScatterHierarchy;template class AtomicType, template class Unitstruct GenScatterHierarchy : public Unit;template template class Unitstruct GenScatterHierarchy;處理Nil類型的情況什么都不做將一個非Typelist的原子類型傳給Unit代碼生成/ 自定義類型Teststruct Test enum

26、Value = 100;template struct Holder T Value; static void f() cout sizeof(T) endl; / .;/ 定義一個包含有char、int、Test和float的Typelisttypedef TypeListchar, TypeListint, TypeListTest, TypeList CIRF;typedef GenScatterHierarchy SH;這個Holder模板決定了生成的各個類的能力代碼生成int main() SH sh; cout (dynamic_castHolder&(sh).Value

27、= a) endl; cout (dynamic_castHolder&(sh).Value = 1) endl; cout (dynamic_castHolder&(sh).Value = 3.14f) endl; cout (dynamic_castHolder&(sh).Value.Value) endl; / cout (dynamic_castHolder&(sh).Value = 3.14) endl;GenScatterHierarchy將給定的TypeList中的每一個類型施加于一個由用戶提供的基本模板Holder上，從而產生一個類層次結構。換句

28、話說，生成的各類的能力，取決于客戶提供的Holder模板的能力。示例中生成了一個多重繼承類層次結構，Holder, Holder, Holder, Holder之間沒有任何關系，但它們都是SH的基類，即所產生的SH層次結構其實相當于：class SH: public Holder, public Holder, public Holder, public Holder;代碼生成利用元編程生成類層次結構最大的好處在于其靈活性：TypeList是可擴展的，其長度不但可以任意定制，而且對其更改后SH可以自適應地產生新的代碼。Loki庫中的Abstract Factory泛型模式即借助于這種機制實現在

29、不損失類型安全性的前提下降低對類型的靜態(tài)依賴性。進一步了解typelist和相關的代碼生成技術，以及Abstract Factory泛型模式，參見注11和注15?？梢岳迷幊碳夹g實現編譯期斷言和編譯期約束 。斷言和契約斷言用于指定程序中某些特定點的條件應為“真”。如果該條件不為真，則斷言失敗，程序執(zhí)行中斷。大量使用斷言可以在開發(fā)期捕捉許多錯誤。當然，若有可能，在編譯期抓住錯誤更好。觸發(fā)編譯期斷言的結果是導致程序無法通過編譯。編譯期斷言的實現方式并非僅限于模板元編程一種。斷言和契約/主模板templatestruct StaticAssert;/ 完全特化template struct Sta

30、ticAssert;/ 輔助宏#define STATIC_ASSERT(exp) StaticAssert StaticAssertFailed; int main() STATIC_ASSERT(01);聲明STATIC_ASSERT宏是為了方便使用，否則用戶如果寫StaticAssert;在有些編譯器（例如GCC和Borlad C+）中編譯報錯，在另外一些編譯器（例如VC+和Digital Mars）中則可以編譯通過。也就是說，單單“提及”一下StaticAssert是不保險的，要強迫它完全實例化才能保證觸發(fā)斷言，例如StaticAssert S;這看上去有些臆怪，因此我們把它封裝到宏里

31、：StaticAssert StaticAssertFailed;斷言和契約命名為StaticAssertFailed是為了便于在生成的編譯錯誤信息中看出觸發(fā)了一個靜態(tài)斷言，例如在GCC中生成如下錯誤信息：sa.cpp:13: error: aggregate StaticAssert StaticAssertFailed has incomplete type and cannot be defined注意：表達式必須能夠在編譯期進行求值，無法對運行期表達式進行求值。這個錯誤信息還有改善的余地，你可以考察Boost和Loki中的靜態(tài)斷言庫/組件，它們的實現更到位。一個新的關鍵字static_

32、assert極有可能被加入C+0 x，其作用正如StaticAssert模板。斷言和契約契約式設計（Design by Contract）要求為組件指定“契約”，這些契約會在程序運行過程中的某些特定點被強制執(zhí)行。編譯期契約也被稱為約束（constraints）。C+雖然不直接支持約束，但是我們可以手工實現這項技術。例如，結合運用上述StaticAssert和前面編寫的IsPointer，可以實現一個約束：#define CONSTRAINT_MUST_BE_POINTER(T) STATIC_ASSERT(IsPointer:Result != 0)斷言和契約在以下類模板中，通過將該約束放在析

33、構函數中，通?？梢员ＷC模板參數T必須是一個指針類型：template class Testpublic: Test() / 只要該類的實例被創(chuàng)建，約束就會發(fā)揮作用 CONSTRAINT_MUST_BE_POINTER(T); ;我們沒有將它放置于構造函數中，因為構造函數可能不止一個int main() Test r; / OK Test d; / 違反約束，編譯報錯庫C+模板的語法較復雜，一些慣用法應該采用庫的方式提供。將這些復雜性封裝于庫中，并暴露給用戶友好的接口，是每一個模板庫開發(fā)者的責任，因為再復雜的庫都應該是“面向用戶”的。庫中出現大量的繁雜的代碼是可以接受的，因為這樣的工作只需做一次

34、，而所有庫的用戶均可從中受益。高質量的庫可以為開發(fā)可移植、高性能的應用提供良好的基礎，一個經過縝密設計和測試的庫具有良好的復用性，可以屏蔽平臺之間的差異，可以使程序員專注于自己的業(yè)務開發(fā)。知名的模板元編程庫有Loki 注14 、Boost （元編程庫）注13 、Blitz+ 注15以及MTL 注16等。庫Blitz+ 核心庫的開發(fā)者是模板元編程技術的創(chuàng)始人Todd Veldhuizen，可以說是最早利用模板將運行期計算轉移至編譯期的庫，主要提供了對向量、矩陣等進行處理的線性代數計算。長期以來，科學計算一直是Fortran77/90的地盤，而Blitz+利用元編程（以及表達式模板等）技術可以獲得

35、和Fortran77/90媲美的效率（參見注4）。Loki 將模板元編程在類型計算方面的威力應用于設計模式領域，利用元編程（以及其他一些重要的設計技術）實現了一些常見的設計模式之泛型版本。庫Boost 元編程庫目前主要包含MPL、Type Traits和Static Assert等庫。 Static Assert和Type Traits用作MPL的基礎。MPL是一個通用的模板元編程框架，它仿照STL提供了編譯期算法、序列、迭代器等元編程組件。它為普通程序員進行元編程提供了高級抽象，使得元編程變得容易、高效、富有樂趣。Boost Type Traits庫包含一系列traits類，用于萃取C+類型

36、特征。另外還包含了一些轉換traits（例如移除一個類型的const修飾符等）。Boost Static Assert庫用于編譯期斷言，如果評估的表達式編譯時計算結果為true，則代碼可以通過編譯，否則編譯報錯。DSEL對于領域特定的嵌入式語言（domain-specific embedded language, DSEL）的設計者而言， 模板元編程技術是一件利器。這里的DSEL就是庫，例如一些圖形或矩陣計算庫都可被認為是一種小型語言：其接口定義語法，其實現定義語義。它們均提供了領域特定的符號、構造和抽象。利用模板元編程技術構建的DSEL，高效且語法接近于從頭構建的語言。由于這種DSEL采用純

37、粹的C+編寫，與使用獨立的DSL相比，無需再使用專門的編譯器、編輯器等工具，從而可以消除跨語言邊界所需付出的代價。如欲進一步了解采用C+模板元編程實現DSEL，參見注9。DSELint a510;int i;for_each(a, a+5, for_loop(var(i)=0, var(i)10, +var(i), _1var(i) += 1) ); std:for_each(v.begin(), v.end(), (switch_statement(_1, case_statement(std:cout constant(zero), case_statement(std:cout cons

38、tant(one), default_statement(cout constant(other: ) _1) ), cout constant(n) ) );摘自Boost Lambda庫的幾個例子：DSELfor_each( a.begin(), a.end(), try_catch( bind(foo, _1), / foo may throw catch_exception ( cout constant(Caught foo_exception: ) foo was called with argument = _1 ), catch_exception ( cout constan

39、t(Caught std:exception: ) bind(&std:exception:what, _e), throw_exception(bind(constructor(), _1) ), catch_all(cout constant(Unknown), rethrow() ) ) );結語模板元程序與常規(guī)代碼結合使用時，此時源代碼包含兩種程序：常規(guī)C+運行期程序和編譯期運行的模板元程序。當被編譯器解釋時，模板元程序可以生成高效的代碼，從而可以大幅提高最終應用程序的運行效率。通過將計算從運行期轉移至編譯期，在結果程序啟動之前做盡可能多的工作，最終獲得速度更快的程序。模板元編

40、程也有一些局限性，使用模板元編程時（尤其使用模板元編程進行數值計算時）存在一些注意事項調試困難：元程序執(zhí)行于編譯期，沒有用于單步跟蹤元程序執(zhí)行的調試器（用于設置斷點、察看數據等）。程序員可做的只能是等待編譯過程失敗，然后人工破譯編譯器傾瀉到屏幕上的錯誤信息。 代碼的可讀性較差。結語結果程序性能未必一定最優(yōu)化：“循環(huán)開解”技術要有選擇地使用，具體獲得的效果必須進行評測。倘若代碼展開導致程序尺寸過大，可能會降低cache的命中率，未必會帶來性能上的提高。編譯器局限性：模板的實例化通常要占用不少編譯器資源，大量的遞歸實例化會迅速拖慢編譯器甚至耗盡可用資源。編譯時間延長：元程序被編譯器解釋執(zhí)行的，C+編譯器并不是一個好的解釋器。可移植性較差：對于模板元編程使用的高級模板特性，不同的編譯器的支持度不同。資源以下是一些C+模板元編程資源，它們或者為本幻燈片的制作提供了參考素材，或者提供了延伸知識。2 Todd Veldhuizen, Expression Templates, /tveldhui/papers/Expression-Templates/exprtmpl.html1 Todd Veldhuize