1994年，C++標准委員會在聖迭哥舉行的一次會議期間Erwin Unruh展示了一段可以產生質數的代碼。這段代碼的特別之處在於質數產生於編譯期而非運行期，在編譯器產生的一系列錯誤信息中間夾雜著從2到某個設定值之間的所有質數：
1 // Prime number computation by Erwin Unruh
2 template <int i> struct D { D(void*); operator int(); };
3
4 template <int p, int i> struct is_prime {
5 enum { prim = (p%i) && is_prime<(i > 2 ? p : 0), i -1> :: prim };
6 };
7
8 template < int i > struct Prime_print {
9 Prime_print<i-1> a;
10 enum { prim = is_prime<i, i-1>::prim };
11 void f() { D<i> d = prim; }
12 };
13
14 struct is_prime<0,0> { enum {prim=1}; };
15 struct is_prime<0,1> { enum {prim=1}; };
16 struct Prime_print<2> { enum {prim = 1}; void f() { D<2> d = prim; } };
17 #ifndef LAST
18 #define LAST 10
19 #endif
20 main () {
21 Prime_print<LAST> a;
22 }
類模板D只有一個參數為void*的構造器，而只有0才能被合法轉換為void*。1994年，Erwin Unruh采用Metaware 編譯器編譯出錯信息如下（以及其它一些信息，簡短起見，它們被刪除了）：
23 | Type `enum{}´ can´t be converted to txpe `D<2>´ ("primes.cpp",L2/C25).
24 | Type `enum{}´ can´t be converted to txpe `D<3>´ ("primes.cpp",L2/C25).
25 | Type `enum{}´ can´t be converted to txpe `D<5>´ ("primes.cpp",L2/C25).
26 | Type `enum{}´ can´t be converted to txpe `D<7>´ ("primes.cpp",L2/C25).
如今，上面的代碼已經不再是合法的C++程序了。以下是Erwin Unruh親手給出的修訂版，可以在今天符合標准的C++編譯器上進行編譯：
27 // Prime number computation by Erwin Unruh
28
29 template <int i> struct D { D(void*); operator int(); };
30
31 template <int p, int i> struct is_prime {
32 enum { prim = (p==2) || (p%i) && is_prime<(i>2?p:0), i-1> :: prim };
33 };
34
35 template <int i> struct Prime_print {
36 Prime_print<i-1> a;
37 enum { prim = is_prime<i, i-1>::prim };
38 void f() { D<i> d = prim ? 1 : 0; a.f();}
39 };
40
41 template<> struct is_prime<0,0> { enum {prim=1}; };
42 template<> struct is_prime<0,1> { enum {prim=1}; };
43
44 template<> struct Prime_print<1> {
45 enum {prim=0};
46 void f() { D<1> d = prim ? 1 : 0; };
47 };
48
49 #ifndef LAST
50 #define LAST 18
51 #endif
52
53 main() {
54 Prime_print<LAST> a;
55 a.f();
56 }
在GNU C++ (MinGW Special) 3.2中編譯這段程序時，編譯器將會給出如下出錯信息（以及其它一些信息，簡短起見，它們被刪除了）：
57 Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 17]'
58 Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 13]'
59 Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 11]'
60 Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 7]'
61 Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 5]'
62 Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 3]'
63 Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 2]'
這個例子展示了可以利用模板實例化機制於編譯期執行一些計算。這種通過模板實例化而執行的特別的編譯期計算技術即被稱為模板元編程。
順便說一句，因為編譯器的出錯信息並未被標准化，所以，如果你在Visual C++、Borland C++等編譯器上看不到這麼詳細的出錯信息，請不必訝異。
一個可以運行的模板元編程例子
模板元編程（Template Metaprogramming）更准確的含義應該是“編‘可以編程序的’程序”，而模板元程序（Template Metaprogram）則是“‘可以編程序的’程序”。也就是說，我們給出代碼的產生規則，編譯器在編譯期解釋這些規則並生成新代碼來實現我們預期的功能。
Erwin Unruh的那段經典代碼並沒有執行，它只是以編譯出錯信息的方式輸出中間計算結果。讓我們來看一個可以運行的模板元編程例子 — 計算給定整數的指定次方：
64 // xy.h
65
66 //原始摸板
67 template<int Base, int Exponent>
68 class XY
69 {
70 public:
71 enum { result_ = Base * XY<Base, Exponent-1>::result_ };
72 };
73
74 //用於終結遞歸的局部特化版
75 template<int Base>
76 class XY<Base, 0>
77 {
78 public:
79 enum { result_ = 1 };
80 };
模板元編程技術之根本在於遞歸模板實例化。第一個模板實現了一般情況下的遞歸規則。當用一對整數<X, Y>來實例化模板時，模板XY<X, Y>需要計算其result_的值，將同一模板中針對<X, Y-1>實例化所得結果乘以X即可。第二個模板是一個局部特化版本，用於終結遞歸。
讓我們看看使用此模板來計算5^4 （通過實例化XY<5, 4>）時發生了什麼：
81 // xytest.cpp
82
83 #include <iostream>
84 #include "xy.h"
85
86 int main()
87 {
88 std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
89 }
首先，編譯器實例化XY<5, 4>，它的result_為5 * XY<5, 3>::result_，如此一來，又需要針對<5, 3>實例化同樣的模板，後者又實例化XY<5, 2>…… 當實例化到XY<5, 0>的時候，result_的值被計算為1，至此遞歸結束。
遞歸模板實例化的深度和終結條件
可以想象，如果我們以非常大的Y值來實例化類模板XY，那肯定會占用大量的編譯器資源甚至會迅速耗盡可用資源（在計算結果溢出之前），因此，在實踐中我們應該有節制地使用模板元編程技術。
雖然 C++標准建議的最小實例化深度只有17層，然而大多數編譯器都能夠處理至少幾十層，有些編譯器允許實例化至數百層，更有一些可達數千層，直至資源耗盡。
假如我們拿掉XY模板局部特化版本，情況會如何？
90 // xy2.h
91
92 //原始摸板
93 template<int Base, int Exponent>
94 class XY
95 {
96 public:
97 enum { result_ = Base * XY<Base, Exponent-1>::result_ };
98 };
測試程序不變：
99 // xytest2.cpp
100
101 #include <iostream>
102 #include "xy2.h"
103
104 int main()
105 {
106 std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
107 }
執行如下編譯命令：
C:\>g++ -c xytest2.cpp
你將會看到遞歸實例化將一直進行下去，直到達到編譯器的極限。
GNU C++ (MinGW Special) 3.2的默認實例化極限深度為500層，你也可以手工調整實例化深度：
C:\>g++ -ftemplate-depth-3400 -c xytest2.cpp
事實上，就本例而言，g++ 3.2允許的實例化極限深度還可以再大一些（我的測試結果是不超過3450層）。
因此，在使用模板元編程技術時，我們總是要給出原始模板的特化版（局部特化版或完全特化版或兼而有之），以作為遞歸模板實例化的終結准則。
利用模板元編程技術解開循環
模板元編程技術最早的實際應用之一是用於數值計算中的解循環。舉個例子，對一個數組進行求和的常見方法是：
108 // sumarray.h
109
110 template <typename T>
111 inline T sum_array(int Dim, T* a)
112 {
113 T result = T();
114 for (int i = 0; i < Dim; ++i)
115 {
116 result += a[i];
117 }
118 return result;
119 }
這當然可行，但我們也可以利用模板元編程技術來解開循環：
120 // sumarray2.h
121
122 // 原始模板
123 template <int Dim, typename T>
124 class Sumarray
125 {
126 public:
127 static T result(T* a)
128 {
129 return a[0] + Sumarray<Dim-1, T>::result(a+1);
130 }
131 };
132
133 // 作為終結准則的局部特化版
134 template <typename T>
135 class Sumarray<1, T>
136 {
137 public:
138 static T result(T* a)
139 {
140 return a[0];
141 }
142 };
用法如下：
143 // sumarraytest2.cpp
144
145 #include <iostream>
146 #include "sumarray2.h"
147
148 int main()
149 {
150 int a[6] = {1, 2, 3, 4, 5, 6};
151 std::cout << " Sumarray<6>(a) = " << Sumarray<6, int>::result(a);
152 }
當我們計算Sumarray<6, int>::result(a)時，實例化過程如下：
153 Sumarray<6, int>::result(a)
154 = a[0] + Sumvector<5, int>::result(a+1)
155 = a[0] + a[1] + Sumvector<4, int>::result(a+2)
156 = a[0] + a[1] + a[2] + Sumvector<3, int>::result(a+3)
157 = a[0] + a[1] + a[2] + a[3] + Sumvector<2, int>::result(a+4)
158 = a[0] + a[1] + a[2] + a[3] + a[4] + Sumvector<1, int>::result(a+5)
159 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
可見，循環被展開為a[0] + a[1] + a[2] + a[3] + a[4] + a[5]。這種直截了當的展開運算幾乎總是比循環來得更有效率。
也許拿一個有著600萬個元素的數組來例證循環開解的優勢可能更有說服力。生成這樣的數組很容易，有興趣，你不妨測試、對比一下。
（感謝一位朋友的測試。他說 ，“據在Visual C++ 2003上實測編譯器應當進行了尾遞歸優化，可以不受上面說的遞歸層次的限制，然而連加的結果在數組個數達到4796之後就不再正確了，程序輸出了空行，已經出錯” — 2003年12月30日補充）
模板元編程在數值計算程序庫中的應用 www.2cto.com
Blitz++之所以“快如閃電”（這正是blitz的字面含義），離不開模板元程序的功勞。Blitz++淋漓盡致地使用了元編程技術，你可以到這些文件源代碼中窺探究竟：
• dot.h
• matassign.h
• matmat.h
• matvec.h
• metaprog.h
• product.h
• sum.h
• vecassign.h
讓我們看看Blitz++程序庫dot.h文件中的模板元程序：
160 template<int N, int I>
161 class _bz_meta_vectorDot {
162 public:
163 enum { loopFlag = (I < N-1) ? 1 : 0 };
164
165 template<class T_expr1, class T_expr2>
166 static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
167 f(const T_expr1& a, const T_expr2& b)
168 {
169 return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
170 }
171
172 template<class T_expr1, class T_expr2>
173 static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
174 f_value_ref(T_expr1 a, const T_expr2& b)
175 {
176 return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
177 }
178
179 template<class T_expr1, class T_expr2>
180 static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
181 f_ref_value(const T_expr1& a, T_expr2 b)
182 {
183 return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
184 }
185
186 template<class T_expr1, class P_numtype2>
187 static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, P_numtype2)
188 dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
189 P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
190 P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
191 {
192 return a[I] * i1 + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::dotWithArgs
193 (a, i2, i3, i4, i5, i6, i7, i8, i9);
194 }
195 };
196
197 template<>
198 class _bz_meta_vectorDot<0,0> {
199 public:
200 template<class T_expr1, class T_expr2>
201 static inline _bz_meta_nullOperand f(const T_expr1&, const T_expr2&)
202 { return _bz_meta_nullOperand(); }
203
204 template<class T_expr1, class P_numtype2>
205 static inline _bz_meta_nullOperand
206 dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
207 P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
208 P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
209 {
210 return _bz_meta_nullOperand();
211 }
212 };
這段代碼遠比它乍看上去的簡單。_bz_meta_vectorDot類模板使用了一個臨時變量loopFlag來存放每一步循環條件的評估結果，並使用了一個完全特化版作為遞歸終結的條件。需要說明的是，和幾乎所有元程序一樣，這個臨時變量作用發揮於編譯期，並將從運行代碼中優化掉。
Todd是在Blitz++數值數組庫的主要作者。這個程序庫（以及MTL和POOMA等程序庫）例證了模板元程序可以為我們帶來更加高效的數值計算性能。Todd宣稱Blitz++的性能可以和對應的Fortran程序庫媲美。
Loki程序庫：活用模板元編程技術的典范
模板元編程的價值僅僅在於高性能數值計算嗎？不僅如此。Loki程序庫以對泛型模式的開創性工作聞名於C++社群。它很巧妙地利用了模板元編程技術實現了Typelist組件。Typelist是實現Abstract Factory、Visitor等泛型模式不可或缺的基礎設施。
就像C++標准庫組件std::list提供對一組數值的操作一樣，Typelist可以用來操縱一組類型，其定義非常簡單（摘自Loki程序庫Typelist.h單元）：
213 template <class T, class U>
214 struct Typelist
215 {
216 typedef T Head;
217 typedef U Tail;
218 };
顯然，Typelist沒有任何狀態，也未定義任何操作，其作用只在於攜帶類型信息，它並未打算被實例化，因此，對於Typelist的任何處理都必然發生於編譯期而非運行期。
Typelist可以被無限擴展，因為模板參數可以是任何類型（包括該模板的其他具現體）。例如：
219 Typelist<char, Typelist<int, Typelist<float, NullType> > >
就是一個包含有char、int、float三種類型的Typelist。
按照Loki的約定，每一個Typelist都必須以NullType結尾。NullType的作用類似於傳統C字符串的“\0”，它被聲明於Loki程序庫的NullType.h文件中：
220 class NullType;
NullType只有聲明，沒有定義，因為Loki程序庫永遠都不需要創建一個NullType對象。
讓我們看看IndexOf模板元程序，它可以在一個Typelist中查找給定類型的位置（摘自Loki程序庫的Typelist.h單元）：
221 template <class TList, class T>
222 struct IndexOf;
223
224 template <class T>
225 struct IndexOf<NullType, T>
226 {
227 enum { value = -1 };
228 };
229
230 template <class T, class Tail>
231 struct IndexOf<Typelist<T, Tail>, T>
232 {
233 enum { value = 0 };
234 };
235
236 template <class Head, class Tail, class T>
237 struct IndexOf<Typelist<Head, Tail>, T>
238 {
239 private:
240 enum { temp = IndexOf<Tail, T>::value };
241 public:
242 enum { value = (temp == -1 ? -1 : 1 + temp) };
243 };
IndexOf 提供了一個原始模板和三個局部特化版。算法非常簡單：如果TList（就是一個Typelist）是一個NullType，則value為-1。如果 TList的頭部就是T，則value為0。否則將IndexOf施行於TList的尾部和T，並將評估結果置於一個臨時變量temp中。如果temp為 -1，則value為-1，否則value為1 + temp。
為了加深你對Typelist采用的模板元編程技術的認識，我從Loki程序庫剝離出如下代碼，放入一個typelistlite.h文件中：
244 // typelistlite.h
245
246 // 聲明Nulltype
247 class NullType;
248
249 // Typelist的定義
250 template <class T, class U>
251 struct Typelist
252 {
253 typedef T Head;
254 typedef U Tail;
255 };
256
257 // IndexOf的定義
258
259 // IndexOf原始模板
260 template <class TList, class T> struct IndexOf;
261
262 // 針對NullType的局部特化版
263 template <class T>
264 struct IndexOf<NullType, T>
265 {
266 enum { value = -1 };
267 };
268
269 // 針對“TList頭部就是我們要查找的T”的局部特化版
270 template <class T, class Tail>
271 struct IndexOf<Typelist<T, Tail>, T>
272 {
273 enum { value = 0 };
274 };
275
276 // 處理TList尾部的局部特化版
277 template <class Head, class Tail, class T>
278 struct IndexOf<Typelist<Head, Tail>, T>
279 {
280 private:
281 enum { temp = IndexOf<Tail, T>::value };
282 public:
283 enum { value = (temp == -1 ? -1 : 1 + temp) };
284 };
測試程序如下：
285 // typelistlite_test.cpp
286
287 #include <iostream>
288 #include "typelistlite.h"
289
290 // 自定義類型Royal
291 class Royal {};
292
293 // 定義一個包含有char、int、Royal和float的Typelist
294 typedef Typelist<char, Typelist<int, Typelist<Royal, Typelist<float, NullType> > > > CIRF;
295
296 int main()
297 {
298 std::cout << "IndexOf<CIRF, int>::value = " << IndexOf<CIRF, int>::value << "\n";
299 std::cout << "IndexOf<CIRF, Royal>::value = " << IndexOf<CIRF, Royal>::value << "\n";
300 std::cout << "IndexOf<CIRF, double>::value = " << IndexOf<CIRF, double>::value << "\n";
301 }
程序輸出如下：
302 IndexOf<CIRF, int>::value = 1
303 IndexOf<CIRF, Royal>::value = 2
304 IndexOf<CIRF, double>::value = -1
結語
模板元編程技術並非都是優點，比方說，模板元程序編譯耗時，帶有模板元程序的程序生成的代碼尺寸要比普通程序的大，而且通常這種程序調試起來也比常規程序困難得多。另外，對於一些程序員來說，以類模板的方式描述算法也許有點抽象。
編譯耗時的代價換來的是卓越的運行期性能。通常來說，一個有意義的程序的運行次數（或服役時間）總是遠遠超過編譯次數（或編譯時間）。為程序的用戶帶來更好的體驗，或者為性能要求嚴格的數值計算換取更高的性能，值得程序員付出這樣的代價。
很難想象模板元編程技術會成為每一個普通程序員的日常工具，相反，就像Blitz++和Loki那樣，模板元程序幾乎總是應該被封裝在一個程序庫的內部。對於庫的用戶來說，它應該是透明的。模板元程序可以（也應該）用作常規模板代碼的內核，為關鍵的算法實現更好的性能，或者為特別的目的實現特別的效果。
模板元編程技術首次正式亮相於Todd Veldhuizen的《Using C++ Template Metaprograms》論文之中。這篇文章首先發表於1995年5月的C++ Report期刊上，後來Stanley Lippman編輯《C++ Gems》一書時又收錄了它。參考文獻中給出了這篇文章的鏈接，它還描述了許多本文沒有描述到的內容。
David Vandevoorde和Nicolai M. Josuttis合著的《C++ Templates: The Complete Guide》一書花了一整章的篇幅介紹模板元編程技術，它同樣是本文的參考資料並且也應該作為你的補充閱讀材料。
Andrei Alexandrescu的天才著作《Modern C++ Design: Generic Programming and Design Patterns Applied》的第3章Typelists對Typelist有著更為詳盡的描述。
摘自 zssureqh
