實(shí)驗(yàn)平臺(tái)：Win7，VS2013 Community，GCC 4.8.3（在線版）

所謂元編程就是編寫直接生成或操縱程序的程序，C++ 模板給 C++ 語言提供了元編程的能力，模板使 C++ 編程變得異常靈活，能實(shí)現(xiàn)很多高級(jí)動(dòng)態(tài)語言才有的特性（語法上可能比較丑陋，一些歷史原因見下文）。普通用戶對(duì) C++ 模板的使用可能不是很頻繁，大致限于泛型編程，但一些系統(tǒng)級(jí)的代碼，尤其是對(duì)通用性、性能要求極高的基礎(chǔ)庫（如 STL、Boost）幾乎不可避免的都大量地使用 C++ 模板，一個(gè)稍有規(guī)模的大量使用模板的程序，不可避免的要涉及元編程（如類型計(jì)算）。本文就是要剖析 C++ 模板元編程的機(jī)制。

下面所給的所有代碼，想做實(shí)驗(yàn)又懶得打開編譯工具？一個(gè)在線運(yùn)行 C++ 代碼的網(wǎng)站（GCC 4.8）很好~

1. C++模板的語法

函數(shù)模板（function template）和類模板（class template）的簡單示例如下：

#include <iostream>

// 函數(shù)模板
template<typename T>
bool equivalent(const T& a, const T& b){
    return !(a < b) && !(b < a);
}
// 類模板
template<typename T=int> // 默認(rèn)參數(shù)
class bignumber{
    T _v;
public:
    bignumber(T a) : _v(a) { }
    inline bool operator<(const bignumber& b) const; // 等價(jià)于 (const bignumber<T> b)
};
// 在類模板外實(shí)現(xiàn)成員函數(shù)
template<typename T>
bool bignumber<T>::operator<(const bignumber& b) const{
    return _v < b._v;
}

int main()
{
    bignumber<> a(1), b(1); // 使用默認(rèn)參數(shù)，"<>"不能省略
    std::cout << equivalent(a, b) << '\n'; // 函數(shù)模板參數(shù)自動(dòng)推導(dǎo)
    std::cout << equivalent<double>(1, 2) << '\n';
    std::cin.get();    return 0;
}

程序輸出如下：

1
0

關(guān)于模板（函數(shù)模板、類模板）的模板參數(shù)（詳見文獻(xiàn)[1]第3章）：

• 類型參數(shù)（type template parameter），用 typename 或 class 標(biāo)記；
• 非類型參數(shù)（non-type template parameter）可以是：整數(shù)及枚舉類型、對(duì)象或函數(shù)的指針、對(duì)象或函數(shù)的引用、對(duì)象的成員指針，非類型參數(shù)是模板實(shí)例的常量；
• 模板型參數(shù)（template template parameter），如“template<typename T, template<typename> class A> someclass {};”；
• 模板參數(shù)可以有默認(rèn)值（函數(shù)模板參數(shù)默認(rèn)是從 C++11 開始支持）；
• 函數(shù)模板的和函數(shù)參數(shù)類型有關(guān)的模板參數(shù)可以自動(dòng)推導(dǎo)，類模板參數(shù)不存在推導(dǎo)機(jī)制；
• C++11 引入變長模板參數(shù)，請(qǐng)見下文。

模板特例化（template specialization，又稱特例、特化）的簡單示例如下：

// 實(shí)現(xiàn)一個(gè)向量類
template<typename T, int N>
class Vec{
    T _v[N];
    // ... // 模板通例（primary template），具體實(shí)現(xiàn)
};
template<>
class Vec<lt;float, 4>{
    float _v[4];
    // ... // 對(duì) Vec<float, 4> 進(jìn)行專門實(shí)現(xiàn)，如利用向量指令進(jìn)行加速
};
template<int N>
class Vec<bool, N>{
    char _v[(N+sizeof(char)-1)/sizeof(char)];
    // ... // 對(duì) Vec<bool, N> 進(jìn)行專門實(shí)現(xiàn)，如用一個(gè)比特位表示一個(gè)bool
};

所謂模板特例化即對(duì)于通例中的某種或某些情況做單獨(dú)專門實(shí)現(xiàn)，最簡單的情況是對(duì)每個(gè)模板參數(shù)指定一個(gè)具體值，這成為完全特例化（full specialization），另外，可以限制模板參數(shù)在一個(gè)范圍取值或滿足一定關(guān)系等，這稱為部分特例化（partial specialization），用數(shù)學(xué)上集合的概念，通例模板參數(shù)所有可取的值組合構(gòu)成全集U，完全特例化對(duì)U中某個(gè)元素進(jìn)行專門定義，部分特例化對(duì)U的某個(gè)真子集進(jìn)行專門定義。

更多模板特例化的例子如下（參考了文獻(xiàn)[1]第44頁）：

template<typename T, int i> class cp00; // 用于模板型模板參數(shù)
// 通例
template<typename T1, typename T2, int i, template<typename, int> class CP>
class TMP;
// 完全特例化
template<>
class TMP<int, float, 2, cp00>;
// 第一個(gè)參數(shù)有const修飾
template<typename T1, typename T2, int i, template<typename, int> class CP>
class TMP<const T1, T2, i, CP>;
// 第一二個(gè)參數(shù)為cp00的實(shí)例且滿足一定關(guān)系，第四個(gè)參數(shù)為cp00
template<typename T, int i>
class TMP<cp00<T, i>, cp00<T, i+10>, i, cp00>;
// 編譯錯(cuò)誤!，第四個(gè)參數(shù)類型和通例類型不一致
//template<template<int i> CP>
//class TMP<int, float, 10, CP>;

關(guān)于模板特例化（詳見文獻(xiàn)[1]第4章）：

• 在定義模板特例之前必須已經(jīng)有模板通例（primary template）的聲明；
• 模板特例并不要求一定與通例有相同的接口，但為了方便使用（體會(huì)特例的語義）一般都相同；
• 匹配規(guī)則，在模板實(shí)例化時(shí)如果有模板通例、特例加起來多個(gè)模板版本可以匹配，則依據(jù)如下規(guī)則：對(duì)版本AB，如果 A 的模板參數(shù)取值集合是B的真子集，則優(yōu)先匹配 A，如果 AB 的模板參數(shù)取值集合是“交叉”關(guān)系（AB 交集不為空，且不為包含關(guān)系），則發(fā)生編譯錯(cuò)誤，對(duì)于函數(shù)模板，用函數(shù)重載分辨（overload resolution）規(guī)則和上述規(guī)則結(jié)合并優(yōu)先匹配非模板函數(shù)。

對(duì)模板的多個(gè)實(shí)例，類型等價(jià)（type equivalence）判斷規(guī)則（詳見文獻(xiàn)[2] 13.2.4）：同一個(gè)模板（模板名及其參數(shù)類型列表構(gòu)成的模板簽名（template signature）相同，函數(shù)模板可以重載，類模板不存在重載）且指定的模板實(shí)參等價(jià)（類型參數(shù)是等價(jià)類型，非類型參數(shù)值相同）。如下例子：

#include <iostream>
// 識(shí)別兩個(gè)類型是否相同，提前進(jìn)入模板元編程^_^
template<typename T1, typename T2> // 通例，返回 false
class theSameType       { public: enum { ret = false }; };
template<typename T>               // 特例，兩類型相同時(shí)返回 true
class theSameType<T, T> { public: enum { ret = true }; };

template<typename T, int i> class aTMP { };

int main(){
    typedef unsigned int uint; // typedef 定義類型別名而不是引入新類型
    typedef uint uint2;
    std::cout << theSameType<unsigned, uint2>::ret << '\n';
    // 感謝 C++11，連續(xù)角括號(hào)“>>”不會(huì)被當(dāng)做流輸入符號(hào)而編譯錯(cuò)誤
    std::cout << theSameType<aTMP<unsigned, 2>, aTMP<uint2, 2>>::ret << '\n';
    std::cout << theSameType<aTMP<int, 2>, aTMP<int, 3>>::ret << '\n';
    std::cin.get(); return 0;
}

1
1
0

關(guān)于模板實(shí)例化（template instantiation）（詳見文獻(xiàn)[4]模板）：

• 指在編譯或鏈接時(shí)生成函數(shù)模板或類模板的具體實(shí)例源代碼，即用使用模板時(shí)的實(shí)參類型替換模板類型參數(shù)（還有非類型參數(shù)和模板型參數(shù)）；
• 隱式實(shí)例化（implicit instantiation）：當(dāng)使用實(shí)例化的模板時(shí)自動(dòng)地在當(dāng)前代碼單元之前插入模板的實(shí)例化代碼，模板的成員函數(shù)一直到引用時(shí)才被實(shí)例化；
• 顯式實(shí)例化（explicit instantiation）：直接聲明模板實(shí)例化，模板所有成員立即都被實(shí)例化；
• 實(shí)例化也是一種特例化，被稱為實(shí)例化的特例（instantiated (or generated) specialization）。

隱式實(shí)例化時(shí)，成員只有被引用到才會(huì)進(jìn)行實(shí)例化，這被稱為推遲實(shí)例化（lazy instantiation），由此可能帶來的問題如下面的例子（文獻(xiàn)[6]，文獻(xiàn)[7]）：

#include <iostream>

template<typename T>
class aTMP {
public:
    void f1() { std::cout << "f1()\n"; }
    void f2() { std::ccccout << "f2()\n"; } // 敲錯(cuò)鍵盤了，語義錯(cuò)誤：沒有 std::ccccout
};

int main(){
    aTMP<int> a;
    a.f1();
    // a.f2(); // 這句代碼被注釋時(shí)，aTMP<int>::f2() 不被實(shí)例化，從而上面的錯(cuò)誤被掩蓋!
    std::cin.get(); return 0;
}

所以模板代碼寫完后最好寫個(gè)諸如顯示實(shí)例化的測(cè)試代碼，更深入一些，可以插入一些模板調(diào)用代碼使得編譯器及時(shí)發(fā)現(xiàn)錯(cuò)誤，而不至于報(bào)出無限長的錯(cuò)誤信息。另一個(gè)例子如下（GCC 4.8 下編譯的輸出信息，VS2013 編譯輸出了 500 多行錯(cuò)誤信息）：

#include <iostream>

// 計(jì)算 N 的階乘 N!
template<int N>
class aTMP{
public:
    enum { ret = N==0 ? 1 : N * aTMP<N-1>::ret }; // Lazy Instantiation，將產(chǎn)生無限遞歸!
};

int main(){
    std::cout << aTMP<10>::ret << '\n';
    std::cin.get(); return 0;
}

sh-4.2# g++ -std=c++11 -o main *.cpp
main.cpp:7:28: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating 'class aTMP<-890>'
  enum { ret = N==0 ? 1 : N * aTMP<N-1>::ret };
                            ^
main.cpp:7:28:   recursively required from 'class aTMP<9>'
main.cpp:7:28:   required from 'class aTMP<10>'
main.cpp:11:23:   required from here

main.cpp:7:28: error: incomplete type 'aTMP<-890>' used in nested name specifier

上面的錯(cuò)誤是因?yàn)椋��?dāng)編譯 aTMP<N> 時(shí)，并不判斷 N==0，而僅僅知道其依賴 aTMP<N-1>（lazy instantiation），從而產(chǎn)生無限遞歸，糾正方法是使用模板特例化，如下：

#include <iostream>

// 計(jì)算 N 的階乘 N!
template<int N>
class aTMP{
public:
    enum { ret = N * aTMP<N-1>::ret };
};
template<>
class aTMP<0>{
public:
    enum { ret = 1 };
};

int main(){
    std::cout << aTMP<10>::ret << '\n';
    std::cin.get(); return 0;
}

3228800

關(guān)于模板的編譯和鏈接（詳見文獻(xiàn)[1] 1.3、文獻(xiàn)[4]模板）：

• 包含模板編譯模式：編譯器生成每個(gè)編譯單元中遇到的所有的模板實(shí)例，并存放在相應(yīng)的目標(biāo)文件中；鏈接器合并等價(jià)的模板實(shí)例，生成可執(zhí)行文件，要求實(shí)例化時(shí)模板定義可見，不能使用系統(tǒng)鏈接器；
• 分離模板編譯模式（使用 export 關(guān)鍵字）：不重復(fù)生成模板實(shí)例，編譯器設(shè)計(jì)要求高，可以使用系統(tǒng)鏈接器；
• 包含編譯模式是主流，C++11 已經(jīng)棄用 export 關(guān)鍵字（對(duì)模板引入 extern 新用法），一般將模板的全部實(shí)現(xiàn)代碼放在同一個(gè)頭文件中并在用到模板的地方用 #include 包含頭文件，以防止出現(xiàn)實(shí)例不一致（如下面緊接著例子）；

實(shí)例化，編譯鏈接的簡單例子如下（參考了文獻(xiàn)[1]第10頁）：

// file: a.cpp
#include <iostream>
template<typename T>
class MyClass { };
template MyClass<double>::MyClass(); // 顯示實(shí)例化構(gòu)造函數(shù) MyClass<double>::MyClass()
template class MyClass<long>;        // 顯示實(shí)例化整個(gè)類 MyClass<long>

template<typename T>
void print(T const& m) { std::cout << "a.cpp: " << m << '\n'; }

void fa() {
    print(1);   // print<int>，隱式實(shí)例化
    print(0.1); // print<double>
}
void fb(); // fb() 在 b.cpp 中定義，此處聲明

int main(){
    fa();
    fb();
    std::cin.get(); return 0;
}

// file: b.cpp
#include <iostream>
template<typename T>
void print(T const& m) { std::cout << "b.cpp: " << m << '\n'; }

void fb() {
    print('2'); // print<char>
    print(0.1); // print<double>
}

a.cpp: 1
a.cpp: 0.1
b.cpp: 2
a.cpp: 0.1

上例中，由于 a.cpp 和 b.cpp 中的 print<double> 實(shí)例等價(jià)（模板實(shí)例的二進(jìn)制代碼在編譯生成的對(duì)象文件 a.obj、b.obj 中），故鏈接時(shí)消除了一個(gè)（消除哪個(gè)沒有規(guī)定，上面消除了 b.cpp 中的）。

關(guān)于 template、typename、this 關(guān)鍵字的使用（文獻(xiàn)[4]模板，文獻(xiàn)[5]）：

• 依賴于模板參數(shù)（template parameter，形式參數(shù)，實(shí)參英文為 argument）的名字被稱為依賴名字（dependent name），C++標(biāo)準(zhǔn)規(guī)定，如果解析器在一個(gè)模板中遇到一個(gè)嵌套依賴名字，它假定那個(gè)名字不是一個(gè)類型，除非顯式用 typename 關(guān)鍵字前置修飾該名字；
• 和上一條 typename 用法類似，template 用于指明嵌套類型或函數(shù)為模板；
• this 用于指定查找基類中的成員（當(dāng)基類是依賴模板參數(shù)的類模板實(shí)例時(shí)，由于實(shí)例化總是推遲，這時(shí)不依賴模板參數(shù)的名字不在基類中查找，文獻(xiàn)[1]第 166 頁）。

一個(gè)例子如下（需要 GCC 編譯，GCC 對(duì) C++11 幾乎全面支持，VS2013 此處總是在基類中查找名字，且函數(shù)模板前不需要 template）：

#include <iostream>

template<typename T>
class aTMP{
public: typedef const T reType;
};

void f() { std::cout << "global f()\n"; }

template<typename T>
class Base {
public:
    template <int N = 99>
    void f() { std::cout << "member f(): " << N << '\n'; }
};

template<typename T>
class Derived : public Base<T> {
public:
    typename T::reType m; // typename 不能省略
    Derived(typename T::reType a) : m(a) { }
    void df1() { f(); }                       // 調(diào)用全局 f()，而非想象中的基類 f()
    void df2() { this->template f(); }        // 基類 f<99>()
    void df3() { Base<T>::template f<22>(); } // 強(qiáng)制基類 f<22>()
    void df4() { ::f(); }                     // 強(qiáng)制全局 f()
};

int main(){
    Derived<aTMP<int>> a(10);
    a.df1(); a.df2(); a.df3(); a.df4();
    std::cin.get(); return 0;
}

global f()
member f(): 99
member f(): 22
global f()

C++11 關(guān)于模板的新特性（詳見文獻(xiàn)[1]第15章，文獻(xiàn)[4]C++11）：

• “>>” 根據(jù)上下文自動(dòng)識(shí)別正確語義；
• 函數(shù)模板參數(shù)默認(rèn)值；
• 變長模板參數(shù)（擴(kuò)展 sizeof…() 獲取參數(shù)個(gè)數(shù)）；
• 模板別名（擴(kuò)展 using 關(guān)鍵字）；
• 外部模板實(shí)例（拓展 extern 關(guān)鍵字），棄用 export template。

在本文中，如無特別聲明將不使用 C++11 的特性（除了 “>>”）。

 

2. 模板元編程概述

如果對(duì) C++ 模板不熟悉（光熟悉語法還不算熟悉），可以先跳過本節(jié)，往下看完例子再回來。

C++ 模板最初是為實(shí)現(xiàn)泛型編程設(shè)計(jì)的，但人們發(fā)現(xiàn)模板的能力遠(yuǎn)遠(yuǎn)不止于那些設(shè)計(jì)的功能。一個(gè)重要的理論結(jié)論就是：C++ 模板是圖靈完備的（Turing-complete），其證明過程請(qǐng)見文獻(xiàn)[8]（就是用 C++ 模板模擬圖靈機(jī)），理論上說 C++ 模板可以執(zhí)行任何計(jì)算任務(wù)，但實(shí)際上因?yàn)槟０迨蔷幾g期計(jì)算，其能力受到具體編譯器實(shí)現(xiàn)的限制（如遞歸嵌套深度，C++11 要求至少 1024，C++98 要求至少 17）。C++ 模板元編程是“意外”功能，而不是設(shè)計(jì)的功能，這也是 C++ 模板元編程語法丑陋的根源。

C++ 模板是圖靈完備的，這使得 C++ 成為兩層次語言（two-level languages，中文暫且這么翻譯，文獻(xiàn)[9]），其中，執(zhí)行編譯計(jì)算的代碼稱為靜態(tài)代碼（static code），執(zhí)行運(yùn)行期計(jì)算的代碼稱為動(dòng)態(tài)代碼（dynamic code），C++ 的靜態(tài)代碼由模板實(shí)現(xiàn)（預(yù)處理的宏也算是能進(jìn)行部分靜態(tài)計(jì)算吧，也就是能進(jìn)行部分元編程，稱為宏元編程，見 Boost 元編程庫即 BCCL，文獻(xiàn)[16]和文獻(xiàn)[1] 10.4）。

具體來說 C++ 模板可以做以下事情：編譯期數(shù)值計(jì)算、類型計(jì)算、代碼計(jì)算（如循環(huán)展開），其中數(shù)值計(jì)算實(shí)際不太有意義，而類型計(jì)算和代碼計(jì)算可以使得代碼更加通用，更加易用，性能更好（也更難閱讀，更難調(diào)試，有時(shí)也會(huì)有代碼膨脹問題）。編譯期計(jì)算在編譯過程中的位置請(qǐng)見下圖（取自文獻(xiàn)[10]），可以看到關(guān)鍵是模板的機(jī)制在編譯具體代碼（模板實(shí)例）前執(zhí)行：

從編程范型（programming paradigm）上來說，C++ 模板是函數(shù)式編程（functional programming），它的主要特點(diǎn)是：函數(shù)調(diào)用不產(chǎn)生任何副作用（沒有可變的存儲(chǔ)），用遞歸形式實(shí)現(xiàn)循環(huán)結(jié)構(gòu)的功能。C++ 模板的特例化提供了條件判斷能力，而模板遞歸嵌套提供了循環(huán)的能力，這兩點(diǎn)使得其具有和普通語言一樣通用的能力（圖靈完備性）。

從編程形式來看，模板的“<>”中的模板參數(shù)相當(dāng)于函數(shù)調(diào)用的輸入?yún)��?shù)，模板中的 typedef 或 static const 或 enum 定義函數(shù)返回值（類型或數(shù)值，數(shù)值僅支持整型，如果需要可以通過編碼計(jì)算浮點(diǎn)數(shù)），代碼計(jì)算是通過類型計(jì)算進(jìn)而選擇類型的函數(shù)實(shí)現(xiàn)的（C++ 屬于靜態(tài)類型語言，編譯器對(duì)類型的操控能力很強(qiáng)）。代碼示意如下：

#include <iostream>

template<typename T, int i=1>
class someComputing {
public:
    typedef volatile T* retType; // 類型計(jì)算
    enum { retValume = i + someComputing<T, i-1>::retValume }; // 數(shù)值計(jì)算，遞歸
    static void f() { std::cout << "someComputing: i=" << i << '\n'; }
};
template<typename T> // 模板特例，遞歸終止條件
class someComputing<T, 0> {
public:
    enum { retValume = 0 };
};

template<typename T>
class codeComputing {
public:
    static void f() { T::f(); } // 根據(jù)類型調(diào)用函數(shù)，代碼計(jì)算
};

int main(){
    someComputing<int>::retType a=0;
    std::cout << sizeof(a) << '\n'; // 64-bit 程序指針
    // VS2013 默認(rèn)最大遞歸深度500，GCC4.8 默認(rèn)最大遞歸深度900（-ftemplate-depth=n）
    std::cout << someComputing<int, 500>::retValume << '\n'; // 1+2+...+500
    codeComputing<someComputing<int, 99>>::f();
    std::cin.get(); return 0;
}

8
125250
someComputing: i=99

C++ 模板元編程概覽框圖如下（取自文獻(xiàn)[9]）：

下面我們將對(duì)圖中的每個(gè)框進(jìn)行深入討論。

 

3. 編譯期數(shù)值計(jì)算

第一個(gè) C++ 模板元程序是 Erwin Unruh 在 1994 年寫的（文獻(xiàn)[14]），這個(gè)程序計(jì)算小于給定數(shù) N 的全部素?cái)?shù)（又叫質(zhì)數(shù)），程序并不運(yùn)行（都不能通過編譯），而是讓編譯器在錯(cuò)誤信息中顯示結(jié)果（直觀展現(xiàn)了是編譯期計(jì)算結(jié)果，C++ 模板元編程不是設(shè)計(jì)的功能，更像是在戲弄編譯器，當(dāng)然 C++11 有所改變），由于年代久遠(yuǎn)，原來的程序用現(xiàn)在的編譯器已經(jīng)不能編譯了，下面的代碼在原來程序基礎(chǔ)上稍作了修改（GCC 4.8 下使用 -fpermissvie，只顯示警告信息）：

// Prime number computation by Erwin Unruh
template<int i> struct D { D(void*); operator int(); }; // 構(gòu)造函數(shù)參數(shù)為 void* 指針

template<int p, int i> struct is_prime { // 判斷 p 是否為素?cái)?shù)，即 p 不能整除 2...p-1
    enum { prim = (p%i) && is_prime<(i>2?p:0), i-1>::prim };
};
template<> struct is_prime<0, 0> { enum { prim = 1 }; };
template<> struct is_prime<0, 1> { enum { prim = 1 }; };

template<int i> struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    // prim 為真時(shí)， prim?1:0 為 1，int 到 D<i> 轉(zhuǎn)換報(bào)錯(cuò)；假時(shí)， 0 為 NULL 指針不報(bào)錯(cuò)
    void f() { D<i> d = prim?1:0; a.f(); } // 調(diào)用 a.f() 實(shí)例化 Prime_print<i-1>::f()
};
template<> struct Prime_print<2> { // 特例，遞歸終止
    enum { prim = 1 };
    void f() { D<2> d = prim?1:0; }
};

#ifndef LAST
#define LAST 10
#endif

int main() {
    Prime_print<LAST> a; a.f(); // 必須調(diào)用 a.f() 以實(shí)例化 Prime_print<LAST>::f()
}

sh-4.2# g++ -std=c++11 -fpermissive -o main *.cpp
main.cpp: In member function 'void Prime_print<2>::f()':
main.cpp:17:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive]
  void f() { D<2> d = prim ? 1 : 0; }
                                 ^
main.cpp:2:28: warning:   initializing argument 1 of 'D<i>::D(void*) [with int i = 2]' [-fpermissive]
 template<int i> struct D { D(void*); operator int(); };
                            ^
main.cpp: In instantiation of 'void Prime_print<i>::f() [with int i = 7]':
main.cpp:13:36:   recursively required from 'void Prime_print<i>::f() [with int i = 9]'
main.cpp:13:36:   required from 'void Prime_print<i>::f() [with int i = 10]'
main.cpp:25:27:   required from here
main.cpp:13:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive]
  void f() { D<i> d = prim ? 1 : 0; a.f(); }
                                 ^
main.cpp:2:28: warning:   initializing argument 1 of 'D<i>::D(void*) [with int i = 7]' [-fpermissive]
 template<int i> struct D { D(void*); operator int(); };
                            ^
main.cpp: In instantiation of 'void Prime_print<i>::f() [with int i = 5]':
main.cpp:13:36:   recursively required from 'void Prime_print<i>::f() [with int i = 9]'
main.cpp:13:36:   required from 'void Prime_print<i>::f() [with int i = 10]'
main.cpp:25:27:   required from here
main.cpp:13:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive]
  void f() { D<i> d = prim ? 1 : 0; a.f(); }
                                 ^
main.cpp:2:28: warning:   initializing argument 1 of 'D<i>::D(void*) [with int i = 5]' [-fpermissive]
 template<int i> struct D { D(void*); operator int(); };
                            ^
main.cpp: In instantiation of 'void Prime_print<i>::f() [with int i = 3]':
main.cpp:13:36:   recursively required from 'void Prime_print<i>::f() [with int i = 9]'
main.cpp:13:36:   required from 'void Prime_print<i>::f() [with int i = 10]'
main.cpp:25:27:   required from here
main.cpp:13:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive]
  void f() { D<i> d = prim ? 1 : 0; a.f(); }
                                 ^
main.cpp:2:28: warning:   initializing argument 1 of 'D<i>::D(void*) [with int i = 3]' [-fpermissive]
 template<int i> struct D { D(void*); operator int(); };

上面的編譯輸出信息只給出了前一部分，雖然信息很雜，但還是可以看到其中有 10 以內(nèi)全部素?cái)?shù)：2、3、5、7（已經(jīng)加粗顯示關(guān)鍵行）。

到目前為止，雖然已經(jīng)看到了階乘、求和等遞歸數(shù)值計(jì)算，但都沒涉及原理，下面以求和為例講解 C++ 模板編譯期數(shù)值計(jì)算的原理：

#include <iostream>

template<int N>
class sumt{
public: static const int ret = sumt<N-1>::ret + N;
};
template<>
class sumt<0>{
public: static const int ret = 0;
};

int main() {
    std::cout << sumt<5>::ret << '\n';
    std::cin.get(); return 0;
}

15

當(dāng)編譯器遇到 sumt<5> 時(shí)，試圖實(shí)例化之，sumt<5> 引用了 sumt<5-1> 即 sumt<4>，試圖實(shí)例化 sumt<4>，以此類推，直到 sumt<0>，sumt<0> 匹配模板特例，sumt<0>::ret 為 0，sumt<1>::ret 為 sumt<0>::ret+1 為 1，以此類推，sumt<5>::ret 為 15。值得一提的是，雖然對(duì)用戶來說程序只是輸出了一個(gè)編譯期常量 sumt<5>::ret，但在背后，編譯器其實(shí)至少處理了 sumt<0> 到 sumt<5> 共 6 個(gè)類型。

從這個(gè)例子我們也可以窺探 C++ 模板元編程的函數(shù)式編程范型，對(duì)比結(jié)構(gòu)化求和程序：for(i=0,sum=0; i<=N; ++i) sum+=i; 用逐步改變存儲(chǔ)（即變量 sum）的方式來對(duì)計(jì)算過程進(jìn)行編程，模板元程序沒有可變的存儲(chǔ)（都是編譯期常量，是不可變的變量），要表達(dá)求和過程就要用很多個(gè)常量：sumt<0>::ret，sumt<1>::ret，…，sumt<5>::ret 。函數(shù)式編程看上去似乎效率低下（因?yàn)樗�和�?shù)學(xué)接近，而不是和硬件工作方式接近），但有自己的優(yōu)勢(shì)：描述問題更加簡潔清晰（前提是熟悉這種方式），沒有可變的變量就沒有數(shù)據(jù)依賴，方便進(jìn)行并行化。

 

4. 模板下的控制結(jié)構(gòu)

模板實(shí)現(xiàn)的條件 if 和 while 語句如下（文獻(xiàn)[9]）：

// 通例為空，若不匹配特例將報(bào)錯(cuò)，很好的調(diào)試手段（這里是 bool 就無所謂了）
template<bool c, typename Then, typename Else> class IF_ { };
template<typename Then, typename Else>
class IF_<true, Then, Else> { public: typedef Then reType; };
template<typename Then, typename Else>
class IF_<false,Then, Else> { public: typedef Else reType; };

// 隱含要求： Condition 返回值 ret，Statement 有類型 Next
template<template<typename> class Condition, typename Statement>
class WHILE_ {
    template<typename Statement> class STOP { public: typedef Statement reType; };
public:
    typedef typename
        IF_<Condition<Statement>::ret,
        WHILE_<Condition, typename Statement::Next>,
        STOP<Statement>>::reType::reType
    reType;
};

IF_<> 的使用示例見下面：

const int len = 4;
typedef
    IF_<sizeof(short)==len, short,
    IF_<sizeof(int)==len, int,
    IF_<sizeof(long)==len, long,
    IF_<sizeof(long long)==len, long long,
    void>::reType>::reType>::reType>::reType
int_my; // 定義一個(gè)指定字節(jié)數(shù)的類型
std::cout << sizeof(int_my) << '\n';

4

WHILE_<> 的使用示例見下面：

// 計(jì)算 1^e+2^e+...+n^e
template<int n, int e>
class sum_pow {
    template<int i, int e> class pow_e{ public: enum{ ret=i*pow_e<i,e-1>::ret }; };
    template<int i> class pow_e<i,0>{ public: enum{ ret=1 }; };
    // 計(jì)算 i^e，嵌套類使得能夠定義嵌套模板元函數(shù)，private 訪問控制隱藏實(shí)現(xiàn)細(xì)節(jié)
    template<int i> class pow{ public: enum{ ret=pow_e<i,e>::ret }; };
    template<typename stat>
    class cond { public: enum{ ret=(stat::ri<=n) }; };
    template<int i, int sum>
    class stat { public: typedef stat<i+1, sum+pow<i>::ret> Next;
                         enum{ ri=i, ret=sum }; };
public:
    enum{ ret = WHILE_<cond, stat<1,0>>::reType::ret };
};

int main() {
    std::cout << sum_pow<10, 2>::ret << '\n';
    std::cin.get(); return 0;
}

385

為了展現(xiàn)編譯期數(shù)值計(jì)算的強(qiáng)大能力，下面是一個(gè)更復(fù)雜的計(jì)算：最大公約數(shù)（Greatest Common Divisor，GCD）和最小公倍數(shù)（Lowest Common Multiple，LCM），經(jīng)典的輾轉(zhuǎn)相除算法：

// 最小公倍數(shù)，普通函數(shù)
int lcm(int a, int b){
    int r, lcm=a*b;
    while(r=a%b) { a = b; b = r; } // 因?yàn)橛每勺兊拇鎯?chǔ)，不能寫成 a=b; b=a%b;
    return lcm/b;
}
// 遞歸函數(shù)版本
int gcd_r(int a, int b) { return b==0 ? a : gcd_r(b, a%b); } // 簡潔
int lcm_r(int a, int b) { return a * b / gcd_r(a,b); }

// 模板版本
template<int a, int b>
class lcm_T{
    template<typename stat>
    class cond { public: enum{ ret=(stat::div!=0) }; };
    template<int a, int b>
    class stat { public: typedef stat<b, a%b> Next; enum{ div=a%b, ret=b }; };
    static const int gcd = WHILE_<cond, stat<a,b>>::reType::ret;
public:
    static const int ret = a * b / gcd;
};
// 遞歸模板版本
template<int a, int b>
class lcm_T_r{
    template<int a, int b> class gcd { public: enum{ ret = gcd<b,a%b>::ret }; };
    template<int a> class gcd<a, 0> { public: enum{ ret = a }; };
public:
    static const int ret = a * b / gcd<a,b>::ret;
};

int main() {
    std::cout << lcm(100, 36) << '\n';
    std::cout << lcm_r(100, 36) << '\n';
    std::cout << lcm_T<100, 36>::ret << '\n';
    std::cout << lcm_T_r<100, 36>::ret << '\n';
    std::cin.get(); return 0;
}

900
900
900
900

上面例子中，定義一個(gè)類的整型常量，可以用 enum，也可以用 static const int，需要注意的是 enum 定義的常量的字節(jié)數(shù)不會(huì)超過 sizeof(int) （文獻(xiàn)[2]）。

 

5. 循環(huán)展開

文獻(xiàn)[11]展示了一個(gè)循環(huán)展開（loop unrolling）的例子 — 冒泡排序：

#include <utility>  // std::swap

// dynamic code, 普通函數(shù)版本
void bubbleSort(int* data, int n)
{
    for(int i=n-1; i>0; --i) {
        for(int j=0; j<i; ++j)
            if (data[j]>data[j+1]) std::swap(data[j], data[j+1]);
    }
}
// 數(shù)據(jù)長度為 4 時(shí)，手動(dòng)循環(huán)展開
inline void bubbleSort4(int* data)
{
#define COMP_SWAP(i, j) if(data[i]>data[j]) std::swap(data[i], data[j])
    COMP_SWAP(0, 1); COMP_SWAP(1, 2); COMP_SWAP(2, 3);
    COMP_SWAP(0, 1); COMP_SWAP(1, 2);
    COMP_SWAP(0, 1);
}

// 遞歸函數(shù)版本，指導(dǎo)模板思路，最后一個(gè)參數(shù)是啞參數(shù)（dummy parameter），僅為分辨重載函數(shù)
class recursion { };
void bubbleSort(int* data, int n, recursion)
{
    if(n<=1) return;
    for(int j=0; j<n-1; ++j) if(data[j]>data[j+1]) std::swap(data[j], data[j+1]);
    bubbleSort(data, n-1, recursion());
}

// static code, 模板元編程版本
template<int i, int j>
inline void IntSwap(int* data) { // 比較和交換兩個(gè)相鄰元素
    if(data[i]>data[j]) std::swap(data[i], data[j]);
}

template<int i, int j>
inline void IntBubbleSortLoop(int* data) { // 一次冒泡，將前 i 個(gè)元素中最大的置換到最后
    IntSwap<j, j+1>(data);
    IntBubbleSortLoop<j<i-1?i:0, j<i-1?(j+1):0>(data);
}
template<>
inline void IntBubbleSortLoop<0, 0>(int*) { }

template<int n>
inline void IntBubbleSort(int* data) { // 模板冒泡排序循環(huán)展開
    IntBubbleSortLoop<n-1, 0>(data);
    IntBubbleSort<n-1>(data);
}
template<>
inline void IntBubbleSort<1>(int* data) { }

對(duì)循環(huán)次數(shù)固定且比較小的循環(huán)語句，對(duì)其進(jìn)行展開并內(nèi)聯(lián)可以避免函數(shù)調(diào)用以及執(zhí)行循環(huán)語句中的分支，從而可以提高性能，對(duì)上述代碼做如下測(cè)試，代碼在 VS2013 的 Release 下編譯運(yùn)行：

#include <iostream>
#include <omp.h>
#include <string.h> // memcpy

int main() {
    double t1, t2, t3; const int num=100000000;
    int data[4]; int inidata[4]={3,4,2,1};
    t1 = omp_get_wtime();
    for(int i=0; i<num; ++i) { memcpy(data, inidata, 4); bubbleSort(data, 4); }
    t1 = omp_get_wtime()-t1;
    t2 = omp_get_wtime();
    for(int i=0; i<num; ++i) { memcpy(data, inidata, 4); bubbleSort4(data); }
    t2 = omp_get_wtime()-t2;
    t3 = omp_get_wtime();
    for(int i=0; i<num; ++i) { memcpy(data, inidata, 4); IntBubbleSort<4>(data); }
    t3 = omp_get_wtime()-t3;
    std::cout << t1/t3 << '\t' << t2/t3 << '\n';
    std::cin.get(); return 0;
}

2.38643 0.926521

上述結(jié)果表明，模板元編程實(shí)現(xiàn)的循環(huán)展開能夠達(dá)到和手動(dòng)循環(huán)展開相近的性能（90% 以上），并且性能是循環(huán)版本的 2 倍多（如果扣除 memcpy 函數(shù)占據(jù)的部分加速比將更高，根據(jù) Amdahl 定律）。這里可能有人會(huì)想，既然循環(huán)次數(shù)固定，為什么不直接手動(dòng)循環(huán)展開呢，難道就為了使用模板嗎？當(dāng)然不是，有時(shí)候循環(huán)次數(shù)確實(shí)是編譯期固定值，但對(duì)用戶并不是固定的，比如要實(shí)現(xiàn)數(shù)學(xué)上向量計(jì)算的類，因?yàn)榭赡苁?2、3、4 維，所以寫成模板，把維度作為 int 型模板參數(shù)，這時(shí)因?yàn)椴恢�道具體是幾維的也就不得不用循環(huán)，不過因?yàn)榫S度信息在模板實(shí)例化時(shí)是編譯期常量且較小，所以編譯器很可能在代碼優(yōu)化時(shí)進(jìn)行循環(huán)展開，但我們想讓這一切發(fā)生的更可控一些。

上面用三個(gè)函數(shù)模板 IntSwap<&ggt;()、 IntBubbleSortLoop<>()、 IntBubbleSort<>() 來實(shí)現(xiàn)一個(gè)排序功能，不但顯得分散（和封裝原理不符），還暴露了實(shí)現(xiàn)細(xì)節(jié)，我們可以仿照上一節(jié)的代碼，將 IntBubbleSortLoop<>()、 IntBubbleSort<>() 嵌入其他模板內(nèi)部，因?yàn)楹瘮?shù)不允許嵌套，我們只能用類模板：

// 整合成一個(gè)類模板實(shí)現(xiàn)，看著好，但引入了 代碼膨脹
template<int n>
class IntBubbleSortC {
    template<int i, int j>
    static inline void IntSwap(int* data) { // 比較和交換兩個(gè)相鄰元素
        if(data[i]>data[j]) std::swap(data[i], data[j]);
    }
    template<int i, int j>
    static inline void IntBubbleSortLoop(int* data) { // 一次冒泡
        IntSwap<j, j+1>(data);
        IntBubbleSortLoop<j<i-1?i:0, j<i-1?(j+1):0>(data);
    }
    template<>
    static inline void IntBubbleSortLoop<0, 0>(int*) { }
public:
    static inline void sort(int* data) {
        IntBubbleSortLoop<n-1, 0>(data);
        IntBubbleSortC<n-1>::sort(data);
    }
};
template<>
class IntBubbleSortC<0> {
public:
    static inline void sort(int* data) { }
};

int main() {
    int data[4] = {3,4,2,1};
    IntBubbleSortC<4>::sort(data); // 如此調(diào)用
    std::cin.get(); return 0;
}

上面代碼看似很好，不僅整合了代碼，借助類成員的訪問控制，還隱藏了實(shí)現(xiàn)細(xì)節(jié)。不過它存在著很大問題，如果實(shí)例化 IntBubbleSortC<4>、 IntBubbleSortC<3>、 IntBubbleSortC<2>，將實(shí)例化成員函數(shù) IntBubbleSortC<4>::IntSwap<0, 1>()、 IntBubbleSortC<4>::IntSwap<1, 2>()、 IntBubbleSortC<4>::IntSwap<2, 3>()、 IntBubbleSortC<3>::IntSwap<0, 1>()、 IntBubbleSortC<3>::IntSwap<1, 2>()、 IntBubbleSortC<2>::IntSwap<0, 1>()，而在原來的看著分散的代碼中 IntSwap<0, 1>() 只有一個(gè)。這將導(dǎo)致代碼膨脹（code bloat），即生成的可執(zhí)行文件體積變大（代碼膨脹另一含義是源代碼增大，見文獻(xiàn)[1]第11章）。不過這里使用了內(nèi)聯(lián)（inline），如果編譯器確實(shí)內(nèi)聯(lián)展開代碼則不會(huì)導(dǎo)致代碼膨脹（除了循環(huán)展開本身會(huì)帶來的代碼膨脹），但因?yàn)橹貜?fù)編譯原本可以復(fù)用的模板實(shí)例，會(huì)增加編譯時(shí)間。在上一節(jié)的例子中，因?yàn)橹簧婕熬幾g期常量計(jì)算，并不涉及函數(shù)（函數(shù)模板，或類模板的成員函數(shù)，函數(shù)被編譯成具體的機(jī)器二進(jìn)制代碼），并不會(huì)出現(xiàn)代碼膨脹。

為了清晰證明上面的論述，我們?nèi)サ羲��?inline 并將函數(shù)實(shí)現(xiàn)放到類外面（類里面實(shí)現(xiàn)的成員函數(shù)都是內(nèi)聯(lián)的，因?yàn)楹瘮?shù)實(shí)現(xiàn)可能被包含多次，見文獻(xiàn)[2] 10.2.9，不過現(xiàn)在的編譯器優(yōu)化能力很強(qiáng)，很多時(shí)候加不加 inline 并不影響編譯器自己對(duì)內(nèi)聯(lián)的選擇…），分別編譯分散版本和類模板封裝版本的冒泡排序代碼編譯生成的目標(biāo)文件（VS2013 下是 .obj 文件）的大小，代碼均在 VS2013 Debug 模式下編譯（防止編譯器優(yōu)化），比較 main.obj （源文件是 main.cpp）大小。

類模板封裝版本代碼如下，注意將成員函數(shù)在外面定義的寫法：

#include <iostream>
#include <utility>  // std::swap

// 整合成一個(gè)類模板實(shí)現(xiàn)，看著好，但引入了 代碼膨脹
template<int n>
class IntBubbleSortC {
    template<int i, int j> static void IntSwap(int* data);
    template<int i, int j> static void IntBubbleSortLoop(int* data);
    template<> static void IntBubbleSortLoop<0, 0>(int*) { }
public:
    static void sort(int* data);
};
template<>
class IntBubbleSortC<0> {
public:
    static void sort(int* data) { }
};

template<int n> template<int i, int j>
void IntBubbleSortC<n>::IntSwap(int* data) {
    if(data[i]>data[j]) std::swap(data[i], data[j]);
}
template<int n> template<int i, int j>
void IntBubbleSortC<n>::IntBubbleSortLoop(int* data) {
    IntSwap<j, j+1>(data);
    IntBubbleSortLoop<j<i-1?i:0, j<i-1?(j+1):0>(data);
}
template<int n>
void IntBubbleSortC<n>::sort(int* data) {
    IntBubbleSortLoop<n-1, 0>(data);
    IntBubbleSortC<n-1>::sort(data);
}

int main() {
    int data[40] = {3,4,2,1};
    IntBubbleSortC<2>::sort(data);  IntBubbleSortC<3>::sort(data);
    IntBubbleSortC<4>::sort(data);  IntBubbleSortC<5>::sort(data);
    IntBubbleSortC<6>::sort(data);  IntBubbleSortC<7>::sort(data);
    IntBubbleSortC<8>::sort(data);  IntBubbleSortC<9>::sort(data);
    IntBubbleSortC<10>::sort(data); IntBubbleSortC<11>::sort(data);
#if 0
    IntBubbleSortC<12>::sort(data); IntBubbleSortC<13>::sort(data);
    IntBubbleSortC<14>::sort(data); IntBubbleSortC<15>::sort(data);
    IntBubbleSortC<16>::sort(data); IntBubbleSortC<17>::sort(data);
    IntBubbleSortC<18>::sort(data); IntBubbleSortC<19>::sort(data);
    IntBubbleSortC<20>::sort(data); IntBubbleSortC<21>::sort(data);

    IntBubbleSortC<22>::sort(data); IntBubbleSortC<23>::sort(data);
    IntBubbleSortC<24>::sort(data); IntBubbleSortC<25>::sort(data);
    IntBubbleSortC<26>::sort(data); IntBubbleSortC<27>::sort(data);
    IntBubbleSortC<28>::sort(data); IntBubbleSortC<29>::sort(data);
    IntBubbleSortC<30>::sort(data); IntBubbleSortC<31>::sort(data);
#endif
    std::cin.get(); return 0;
}

分散定義函數(shù)模板版本代碼如下，為了更具可比性，也將函數(shù)放在類里面作為成員函數(shù)：

#include <iostream>
#include <utility>  // std::swap

// static code, 模板元編程版本
template<int i, int j>
class IntSwap {
public: static void swap(int* data);
};

template<int i, int j>
class IntBubbleSortLoop {
public: static void loop(int* data);
};
template<>
class IntBubbleSortLoop<0, 0> {
public: static void loop(int* data) { }
};

template<int n>
class IntBubbleSort {
public: static void sort(int* data);
};
template<>
class IntBubbleSort<0> {
public: static void sort(int* data) { }
};

template<int i, int j>
void IntSwap<i, j>::swap(int* data) {
    if(data[i]>data[j]) std::swap(data[i], data[j]);
}
template<int i, int j>
void IntBubbleSortLoop<i, j>::loop(int* data) {
    IntSwap<j, j+1>::swap(data);
    IntBubbleSortLoop<j<i-1?i:0, j<i-1?(j+1):0>::loop(data);
}
template<int n>
void IntBubbleSort<n>::sort(int* data) {
    IntBubbleSortLoop<n-1, 0>::loop(data);
    IntBubbleSort<n-1>::sort(data);
}

int main() {
    int data[40] = {3,4,2,1};
    IntBubbleSort<2>::sort(data);  IntBubbleSort<3>::sort(data);
    IntBubbleSort<4>::sort(data);  IntBubbleSort<5>::sort(data);
    IntBubbleSort<6>::sort(data);  IntBubbleSort<7>::sort(data);
    IntBubbleSort<8>::sort(data);  IntBubbleSort<9>::sort(data);
    IntBubbleSort<10>::sort(data); IntBubbleSort<11>::sort(data);
#if 0
    IntBubbleSort<12>::sort(data); IntBubbleSort<13>::sort(data);
    IntBubbleSort<14>::sort(data); IntBubbleSort<15>::sort(data);
    IntBubbleSort<16>::sort(data); IntBubbleSort<17>::sort(data);
    IntBubbleSort<18>::sort(data); IntBubbleSort<19>::sort(data);
    IntBubbleSort<20>::sort(data); IntBubbleSort<21>::sort(data);

    IntBubbleSort<22>::sort(data); IntBubbleSort<23>::sort(data);
    IntBubbleSort<24>::sort(data); IntBubbleSort<25>::sort(data);
    IntBubbleSort<26>::sort(data); IntBubbleSort<27>::sort(data);
    IntBubbleSort<28>::sort(data); IntBubbleSort<29>::sort(data);
    IntBubbleSort<30>::sort(data); IntBubbleSort<31>::sort(data);
#endif
    std::cin.get(); return 0;
}

程序中條件編譯都未打開時(shí)（#if 0），main.obj 大小分別為 264 KB 和 211 KB，條件編譯打開時(shí)（#if 1），main.obj 大小分別為 1073 KB 和 620 KB�？梢钥吹剑�類模板封裝版的對(duì)象文件不但絕對(duì)大小更大，而且增長更快，這和之前分析是一致的。

 

6. 表達(dá)式模板，向量運(yùn)算

文獻(xiàn)[12]展示了一個(gè)表達(dá)式模板（Expression Templates）的例子：

#include <iostream> // std::cout
#include <cmath>    // std::sqrt()

// 表達(dá)式類型
class DExprLiteral {                    // 文字量
    double a_;
public:
    DExprLiteral(double a) : a_(a) { }
    double operator()(double x) const { return a_; }
};
class DExprIdentity {                   // 自變量
public:
    double operator()(double x) const { return x; }
};
template<class A, class B, class Op>    // 雙目操作
class DBinExprOp {
    A a_; B b_;
public:
    DBinExprOp(const A& a, const B& b) : a_(a), b_(b) { }
    double operator()(double x) const { return Op::apply(a_(x), b_(x)); }
};
template<class A, class Op>             // 單目操作
class DUnaryExprOp {
    A a_;
public:
    DUnaryExprOp(const A& a) : a_(a) { }
    double operator()(double x) const { return Op::apply(a_(x)); }
};
// 表達(dá)式
template<class A>
class DExpr {
    A a_;
public:
    DExpr() { }
    DExpr(const A& a) : a_(a) { }
    double operator()(double x) const { return a_(x); }
};

// 運(yùn)算符，模板參數(shù) A、B 為參與運(yùn)算的表達(dá)式類型
// operator /, division
class DApDiv { public: static double apply(double a, double b) { return a / b; } };
template<class A, class B> DExpr<DBinExprOp<DExpr<A>, DExpr<B>, DApDiv> >
operator/(const DExpr<A>& a, const DExpr<B>& b) {
    typedef DBinExprOp<DExpr<A>, DExpr<B>, DApDiv> ExprT;
    return DExpr<ExprT>(ExprT(a, b));
}
// operator +, addition
class DApAdd { public: static double apply(double a, double b) { return a + b; } };
template<class A, class B> DExpr<DBinExprOp<DExpr<A>, DExpr<B>, DApAdd> >
operator+(const DExpr<A>& a, const DExpr<B>& b) {
    typedef DBinExprOp<DExpr<A>, DExpr<B>, DApAdd> ExprT;
    return DExpr<ExprT>(ExprT(a, b));
}
// sqrt(), square rooting
class DApSqrt { public: static double apply(double a) { return std::sqrt(a); } };
template<class A> DExpr<DUnaryExprOp<DExpr<A>, DApSqrt> >
sqrt(const DExpr<A>& a) {
    typedef DUnaryExprOp<DExpr<A>, DApSqrt> ExprT;
    return DExpr<ExprT>(ExprT(a));
}
// operator-, negative sign
class DApNeg { public: static double apply(double a) { return -a; } };
template<class A> DExpr<DUnaryExprOp<DExpr<A>, DApNeg> >
operator-(const DExpr<A>& a) {
    typedef DUnaryExprOp<DExpr<A>, DApNeg> ExprT;
    return DExpr<ExprT>(ExprT(a));
}

// evaluate()
template<class Expr>
void evaluate(const DExpr<Expr>& expr, double start, double end, double step) {
    for(double i=start; i<end; i+=step) std::cout << expr(i) << ' ';
}

int main() {
    DExpr<DExprIdentity> x;
    evaluate( -x / sqrt( DExpr<DExprLiteral>(1.0) + x ) , 0.0, 10.0, 1.0);
    std::cin.get(); return 0;
}

-0 -0.707107 -1.1547 -1.5 -1.78885 -2.04124 -2.26779 -2.47487 -2.66667 -2.84605

代碼有點(diǎn)長（我已經(jīng)盡量壓縮行數(shù)），請(qǐng)先看最下面的 main() 函數(shù)，表達(dá)式模板允許我們以 “-x / sqrt( 1.0 + x )” 這種類似數(shù)學(xué)表達(dá)式的方式傳參數(shù)，在 evaluate() 內(nèi)部，將 0-10 的數(shù)依次賦給自變量 x 對(duì)表達(dá)式進(jìn)行求值，這是通過在 template<> DExpr 類模板內(nèi)部重載 operator() 實(shí)現(xiàn)的。我們來看看這一切是如何發(fā)生的。

在 main() 中調(diào)用 evaluate() 時(shí)，編譯器根據(jù)全局重載的加號(hào)、sqrt、除號(hào)、負(fù)號(hào)推斷“-x / sqrt( 1.0 + x )” 的類型是 Dexpr<DBinExprOp<Dexpr<DUnaryExprOp<Dexpr<DExprIdentity>, DApNeg>>, Dexpr<DUnaryExprOp<Dexpr<DBinExprOp<Dexpr<DExprLiteral>, Dexpr<DExprIdentity>, DApAdd>>, DApSqrt>>, DApDiv>>（即將每個(gè)表達(dá)式編碼到一種類型，設(shè)這個(gè)類型為 ultimateExprType），并用此類型實(shí)例化函數(shù)模板 evaluate()，類型的推導(dǎo)見下圖。在 evaluate() 中，對(duì)表達(dá)式進(jìn)行求值 expr(i)，調(diào)用 ultimateExprType 的 operator()，這引起一系列的 operator() 和 Op::apply() 的調(diào)用，最終遇到基礎(chǔ)類型 “表達(dá)式類型” DExprLiteral 和 DExprIdentity，這個(gè)過程見下圖�？偨Y(jié)就是，請(qǐng)看下圖，從下到上類型推斷，從上到下 operator() 表達(dá)式求值。

上面代碼函數(shù)實(shí)現(xiàn)寫在類的內(nèi)部，即內(nèi)聯(lián)，如果編譯器對(duì)內(nèi)聯(lián)支持的好的話，上面代碼幾乎等價(jià)于如下代碼：

#include <iostream> // std::cout
#include <cmath>    // std::sqrt()

void evaluate(double start, double end, double step) {
    double _temp = 1.0;
    for(double i=start; i<end; i+=step)
        std::cout << -i / std::sqrt(_temp + i) << ' ';
}

int main() {
    evaluate(0.0, 10.0, 1.0);
    std::cin.get(); return 0;
}

-0 -0.707107 -1.1547 -1.5 -1.78885 -2.04124 -2.26779 -2.47487 -2.66667 -2.84605

和表達(dá)式模板類似的技術(shù)還可以用到向量計(jì)算中，以避免產(chǎn)生臨時(shí)向量變量，見文獻(xiàn)[4] Expression templates 和文獻(xiàn)[12]的后面。傳統(tǒng)向量計(jì)算如下：

class DoubleVec; // DoubleVec 重載了 + - * / 等向量元素之間的計(jì)算
DoubleVec y(1000), a(1000), b(1000), c(1000), d(1000); // 向量長度 1000
// 向量計(jì)算
y = (a + b) / (c - d);
// 等價(jià)于
DoubleVec __t1 = a + b;
DoubleVec __t2 = c - d;
DoubleVec __t3 = __t1 / __t2;
y = __t3;

模板代碼實(shí)現(xiàn)向量計(jì)算如下：

template<class A> DVExpr;
class DVec{
    // ...
    template<class A>
    DVec& operator=(const DVExpr<A>&); // 由 = 引起向量逐個(gè)元素的表達(dá)式值計(jì)算并賦值
};
DVec y(1000), a(1000), b(1000), c(1000), d(1000); // 向量長度 1000
// 向量計(jì)算
y = (a + b) / (c - d);
// 等價(jià)于
for(int i=0; i<1000; ++i) {
    y[i] = (a[i] + b[i]) / (c[i] + d[i]);
}

不過值得一提的是，傳統(tǒng)代碼可以用 C++11 的右值引用提升性能，C++11 新特性我們以后再詳細(xì)討論。

我們這里看下文獻(xiàn)[4] Expression templates 實(shí)現(xiàn)的版本，它用到了編譯期多態(tài)，編譯期多態(tài)示意代碼如下（關(guān)于這種代碼形式有個(gè)名字叫 curiously recurring template pattern， CRTP，見文獻(xiàn)[4]）：

// 模板基類，定義接口，具體實(shí)現(xiàn)由模板參數(shù)，即子類實(shí)現(xiàn)
template <typename D>
class base {
public:
    void f1() { static_cast<E&>(*this).f1(); } // 直接調(diào)用子類實(shí)現(xiàn)
    int f2() const { static_cast<const E&>(*this).f1(); }
};
// 子類
class dirived1 : public base<dirived1> {
public:
    void f1() { /* ... */ }
    int f2() const { /* ... */ }
};
template<typename T>
class dirived2 : public base<dirived2<T>> {
public:
    void f1() { /* ... */ }
    int f2() const { /* ... */ }
};

簡化后（向量長度固定為1000，元素類型為 double）的向量計(jì)算代碼如下：

#include <iostream> // std::cout

// A CRTP base class for Vecs with a size and indexing:
template <typename E>
class VecExpr {
public:
    double operator[](int i) const { return static_cast<E const&>(*this)[i]; }
    operator E const&() const { return static_cast<const E&>(*this); } // 向下類型轉(zhuǎn)換
};
// The actual Vec class:
class Vec : public VecExpr<Vec> {
    double _data[1000];
public:
    double&  operator[](int i) { return _data[i]; }
    double operator[](int i) const { return _data[i]; }
    template <typename E>
    Vec const& operator=(VecExpr<E> const& vec) {
        E const& v = vec;
        for (int i = 0; i<1000; ++i) _data[i] = v[i];
        return *this;
    }
    // Constructors
    Vec() { }
    Vec(double v) { for(int i=0; i<1000; ++i) _data[i] = v; }
};

template <typename E1, typename E2>
class VecDifference : public VecExpr<VecDifference<E1, E2> > {
    E1 const& _u; E2 const& _v;
public:
    VecDifference(VecExpr<E1> const& u, VecExpr<E2> const& v) : _u(u), _v(v) { }
    double operator[](int i) const { return _u[i] - _v[i]; }
};
template <typename E>
class VecScaled : public VecExpr<VecScaled<E> > {
    double _alpha; E const& _v;
public:
    VecScaled(double alpha, VecExpr<E> const& v) : _alpha(alpha), _v(v) { }
    double operator[](int i) const { return _alpha * _v[i]; }
};

// Now we can overload operators:
template <typename E1, typename E2> VecDifference<E1, E2> const
operator-(VecExpr<E1> const& u, VecExpr<E2> const& v) {
    return VecDifference<E1, E2>(u, v);
}
template <typename E> VecScaled<E> const
operator*(double alpha, VecExpr<E> const& v) {
    return VecScaled<E>(alpha, v);
}

int main() {
    Vec u(3), v(1); double alpha=9; Vec y;
    y = alpha*(u - v);
    std::cout << y[999] << '\n';
    std::cin.get(); return 0;
}

18

“alpha*(u – v)” 的類型推斷過程如下圖所示，其中有子類到基類的隱式類型轉(zhuǎn)換：

這里可以看到基類的作用：提供統(tǒng)一的接口，讓 operator- 和 operator* 可以寫成統(tǒng)一的模板形式。

 

7. 特性，策略，標(biāo)簽

利用迭代器，我們可以實(shí)現(xiàn)很多通用算法，迭代器在容器與算法之間搭建了一座橋梁。求和函數(shù)模板如下：

#include <iostream> // std::cout
#include <vector>

template<typename iter>
typename iter::value_type mysum(iter begin, iter end) {
    typename iter::value_type sum(0);
    for(iter i=begin; i!=end; ++i) sum += *i;
    return sum;
}

int main() {
    std::vector<int> v;
    for(int i = 0; i<100; ++i) v.push_back(i);
    std::cout << mysum(v.begin(), v.end()) << '\n';
    std::cin.get(); return 0;
}

4950

我們想讓 mysum() 對(duì)指針參數(shù)也能工作，畢竟迭代器就是模擬指針，但指針沒有嵌套類型 value_type，可以定義 mysum() 對(duì)指針類型的特例，但更好的辦法是在函數(shù)參數(shù)和 value_type 之間多加一層 — 特性（traits）（參考了文獻(xiàn)[1]第72頁，特性詳見文獻(xiàn)[1] 12.1）：

// 特性，traits
template<typename iter>
class mytraits{
public: typedef typename iter::value_type value_type;
};
template<typename T>
class mytraits<T*>{
public: typedef T value_type;
};

template<typename iter>
typename mytraits<iter>::value_type mysum(iter begin, iter end) {
    typename mytraits<iter>::value_type sum(0);
    for(iter i=begin; i!=end; ++i) sum += *i;
    return sum;
}

int main() {
    int v[4] = {1,2,3,4};
    std::cout << mysum(v, v+4) << '\n';
    std::cin.get(); return 0;
}

10

其實(shí)，C++ 標(biāo)準(zhǔn)定義了類似的 traits：std::iterator_trait（另一個(gè)經(jīng)典例子是 std::numeric_limits） 。特性對(duì)類型的信息（如 value_type、 reference）進(jìn)行包裝，使得上層代碼可以以統(tǒng)一的接口訪問這些信息。C++ 模板元編程會(huì)涉及大量的類型計(jì)算，很多時(shí)候要提取類型的信息（typedef、 常量值等），如果這些類型的信息的訪問方式不一致（如上面的迭代器和指針），我們將不得不定義特例，這會(huì)導(dǎo)致大量重復(fù)代碼的出現(xiàn)（另一種代碼膨脹），而通過加一層特性可以很好的解決這一問題。另外，特性不僅可以對(duì)類型的信息進(jìn)行包裝，還可以提供更多信息，當(dāng)然，因?yàn)榧恿艘粚�，也帶來�?fù)雜性。特性是一種提供元信息的手段。

策略（policy）一般是一個(gè)類模板，典型的策略是 STL 容器（如 std::vector<>，完整聲明是template<class T, class Alloc=allocator<T>> class vector;）的分配器（這個(gè)參數(shù)有默認(rèn)參數(shù)，即默認(rèn)存儲(chǔ)策略），策略類將模板的經(jīng)常變化的那一部分子功能塊集中起來作為模板參數(shù)，這樣模板便可以更為通用，這和特性的思想是類似的（詳見文獻(xiàn)[1] 12.3）。

標(biāo)簽（tag）一般是一個(gè)空類，其作用是作為一個(gè)獨(dú)一無二的類型名字用于標(biāo)記一些東西，典型的例子是 STL 迭代器的五種類型的名字（input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag），std::vector<int>::iterator::iterator_category 就是 random_access_iterator_tag，可以用第1節(jié)判斷類型是否等價(jià)的模板檢測(cè)這一點(diǎn)：

#include <iostream>
#include <vector>

template<typename T1, typename T2> // 通例，返回 false
class theSameType       { public: enum { ret = false }; };
template<typename T>               // 特例，兩類型相同時(shí)返回 true
class theSameType<T, T> { public: enum { ret = true }; };

int main(){
    std::cout << theSameType< std::vector<int>::iterator::iterator_category,
                              std::random_access_iterator_tag >::ret << '\n';
    std::cin.get(); return 0;
}

1

有了這樣的判斷，還可以根據(jù)判斷結(jié)果做更復(fù)雜的元編程邏輯（如一個(gè)算法以迭代器為參數(shù)，根據(jù)迭代器標(biāo)簽進(jìn)行特例化以對(duì)某種迭代器特殊處理）。標(biāo)簽還可以用來分辨函數(shù)重載，第5節(jié)中就用到了這樣的標(biāo)簽（recursion）（標(biāo)簽詳見文獻(xiàn)[1] 12.1）。

 

8. 更多類型計(jì)算

在第1節(jié)我們講類型等價(jià)的時(shí)候，已經(jīng)見到了一個(gè)可以判斷兩個(gè)類型是否等價(jià)的模板，這一節(jié)我們給出更多例子，下面是判斷一個(gè)類型是否可以隱式轉(zhuǎn)換到另一個(gè)類型的模板（參考了文獻(xiàn)[6] Static interface checking）：

#include <iostream> // std::cout

// whether T could be converted to U
template<class T, class U>
class ConversionTo {
    typedef char Type1[1]; // 兩種 sizeof 不同的類型
    typedef char Type2[2];
    static Type1& Test( U ); // 較下面的函數(shù)，因?yàn)閰��?shù)取值范圍小，優(yōu)先匹配
    static Type2& Test(...); // 變長參數(shù)函數(shù)，可以匹配任何數(shù)量任何類型參數(shù)
    static T MakeT(); // 返回類型 T，用這個(gè)函數(shù)而不用 T() 因?yàn)?T 可能沒有默認(rèn)構(gòu)造函數(shù)
public:
    enum { ret = sizeof(Test(MakeT()))==sizeof(Type1) }; // 可以轉(zhuǎn)換時(shí)調(diào)用返回 Type1 的 Test()
};

int main() {
    std::cout << ConversionTo<int, double>::ret << '\n';
    std::cout << ConversionTo<float, int*>::ret << '\n';
    std::cout << ConversionTo<const int&, int&>::ret << '\n';
    std::cin.get(); return 0;
}

1
0
0

下面這個(gè)例子檢查某個(gè)類型是否含有某個(gè)嵌套類型定義（參考了文獻(xiàn)[4] Substitution failure is not an erro (SFINAE)），這個(gè)例子是個(gè)內(nèi)�。ǚ瓷涞囊环N）：

#include <iostream>
#include <vector>

// thanks to Substitution failure is not an erro (SFINAE)
template<typename T>
struct has_typedef_value_type {
    typedef char Type1[1];
    typedef char Type2[2];
    template<typename C> static Type1& test(typename C::value_type*);
    template<typename> static Type2& test(...);
public:
    static const bool ret = sizeof(test<T>(0)) == sizeof(Type1); // 0 == NULL
};

struct foo { typedef float lalala; };

int main() {
    std::cout << has_typedef_value_type<std::vector<int>>::ret << '\n';
    std::cout << has_typedef_value_type<foo>::ret << '\n';
    std::cin.get(); return 0;
}

1
0

這個(gè)例子是有缺陷的，因?yàn)椴淮嬖谝�用的指針，所以不用用來檢測(cè)引用類型定義�？梢钥吹剑�因?yàn)橹簧婕邦愋屯茢�，都是編譯期的計(jì)算，不涉及任何可執(zhí)行代碼，所以類的成員函數(shù)根本不需要具體實(shí)現(xiàn)。

9. 元容器

文獻(xiàn)[1]第 13 章講了元容器，所謂元容器，就是類似于 std::vector<> 那樣的容器，不過它存儲(chǔ)的是元數(shù)據(jù) — 類型，有了元容器，我們就可以判斷某個(gè)類型是否屬于某個(gè)元容器之類的操作。

在講元容器之前，我們先來看看偽變長參數(shù)模板（文獻(xiàn)[1] 12.4），一個(gè)可以存儲(chǔ)小于某個(gè)數(shù)（例子中為 4 個(gè)）的任意個(gè)數(shù)，任意類型數(shù)據(jù)的元組（tuple）的例子如下（參考了文獻(xiàn)[1] 第 225~227 頁）：

#include <iostream>

class null_type {}; // 標(biāo)簽類，標(biāo)記參數(shù)列表末尾
template<typename T0, typename T1, typename T2, typename T3>
class type_shift_node {
public:
    typedef T0 data_type;
    typedef type_shift_node<T1, T2, T3, null_type> next_type; // 參數(shù)移位了
    static const int num = next_type::num + 1; // 非 null_type 模板參數(shù)個(gè)數(shù)
    data_type data; // 本節(jié)點(diǎn)數(shù)據(jù)
    next_type next; // 后續(xù)所有節(jié)點(diǎn)數(shù)據(jù)
    type_shift_node() :data(), next() { } // 構(gòu)造函數(shù)
    type_shift_node(T0 const& d0, T1 const& d1, T2 const& d2, T3 const& D3)
        :data(d0), next(d1, d2, d3, null_type()) { } // next 參數(shù)也移位了
};
template<typename T0> // 特例，遞歸終止
class type_shift_node<T0, null_type, null_type, null_type> {
public:
    typedef T0 data_type;
    static const int num = 1;
    data_type data; // 本節(jié)點(diǎn)數(shù)據(jù)
    type_shift_node() :data(), next() { } // 構(gòu)造函數(shù)
    type_shift_node(T0 const& d0, null_type, null_type, null_type) : data(d0) { }
};
// 元組類模板，默認(rèn)參數(shù) + 嵌套遞歸
template<typename T0, typename T1=null_type, typename T2=null_type,
         typename T3=null_type>
class my_tuple {
public:
    typedef type_shift_node<T0, T1, T2, T3> tuple_type;
    static const int num = tuple_type::num;
    tuple_type t;
    my_tuple(T0 const& d0=T0(),T1 const& d1=T1(),T2 const& d2=T2(),T3 const& d3=T3())
        : t(d0, d1, d2, d3) { } // 構(gòu)造函數(shù)，默認(rèn)參數(shù)
};

// 為方便訪問元組數(shù)據(jù)，定義 get<unsigned>(tuple) 函數(shù)模板
template<unsigned i, typename T0, typename T1, typename T2, typename T3>
class type_shift_node_traits {
public:
    typedef typename
        type_shift_node_traits<i-1,T0,T1,T2,T3>::node_type::next_type node_type;
    typedef typename node_type::data_type data_type;
    static node_type& get_node(type_shift_node<T0,T1,T2,T3>& node)
    { return type_shift_node_traits<i-1,T0,T1,T2,T3>::get_node(node).next; }
};
template<typename T0, typename T1, typename T2, typename T3>
class type_shift_node_traits<0, T0, T1, T2, T3> {
public:
    typedef typename type_shift_node<T0,T1,T2,T3> node_type;
    typedef typename node_type::data_type data_type;
    static node_type& get_node(type_shift_node<T0,T1,T2,T3>& node)
    { return node; }
};
template<unsigned i, typename T0, typename T1, typename T2, typename T3>
typename type_shift_node_traits<i,T0,T1,T2,T3>::data_type
get(my_tuple<T0,T1,T2,T3>& tup) {
    return type_shift_node_traits<i,T0,T1,T2,T3>::get_node(tup.t).data;
}

int main(){
    typedef my_tuple<int, char, float> tuple3;
    tuple3 t3(10, 'm', 1.2f);
    std::cout << t3.t.data << ' '
              << t3.t.next.data << ' '
              << t3.t.next.next.data << '\n';
    std::cout << tuple3::num << '\n';
    std::cout << get<2>(t3) << '\n'; // 從 0 開始，不要出現(xiàn) 3，否則將出現(xiàn)不可理解的編譯錯(cuò)誤
    std::cin.get(); return 0;
}

10 m 1.2
3
1.2

C++11 引入了變長模板參數(shù)，其背后的原理也是模板遞歸（文獻(xiàn)[1]第 230 頁）。

利用和上面例子類似的模板參數(shù)移位遞歸的原理，我們可以構(gòu)造一個(gè)存儲(chǔ)“類型”的元組，即元容器，其代碼如下（和文獻(xiàn)[1]第 237 頁的例子不同）：

#include <iostream>

// 元容器
template<typename T0=void, typename T1=void, typename T2=void, typename T3=void>
class meta_container {
public:
    typedef T0 type;
    typedef meta_container<T1, T2, T3, void> next_node; // 參數(shù)移位了
    static const int size = next_node::size + 1; // 非 null_type 模板參數(shù)個(gè)數(shù)
};
template<> // 特例，遞歸終止
class meta_container<void, void, void, void> {
public:
    typedef void type;
    static const int size = 0;
};

// 訪問元容器中的數(shù)據(jù)
template<typename C, unsigned i>
class get {
public:
    static_assert(i<C::size, "get<C,i>: index exceed num"); // C++11 引入靜態(tài)斷言
    typedef typename get<C,i-1>::c_type::next_node c_type;
    typedef typename c_type::type ret_type;
};
template<typename C>
class get<C, 0> {
public:
    static_assert(0<C::size, "get<C,i>: index exceed num"); // C++11 引入靜態(tài)斷言
    typedef C c_type;
    typedef typename c_type::type ret_type;
};

// 在元容器中查找某個(gè)類型，找到返回索引，找不到返回 -1
template<typename T1, typename T2> class same_type { public: enum { ret = false }; };
template<typename T> class same_type<T, T> { public: enum { ret = true }; };

template<bool c, typename Then, typename Else> class IF_ { };
template<typename Then, typename Else>
class IF_<true, Then, Else> { public: typedef Then reType; };
template<typename Then, typename Else>
class IF_<false, Then, Else> { public: typedef Else reType; };

template<typename C, typename T>
class find {
    template<int i> class number { public: static const int ret = i; };
    template<typename C, typename T, int i>
    class find_i {
    public:
        static const int ret = IF_< same_type<get<C,i>::ret_type, T>::ret,
            number<i>, find_i<C,T,i-1> >::reType::ret;
    };
    template<typename C, typename T>
    class find_i<C, T, -1> {
    public:
        static const int ret = -1;
    };
public:
    static const int ret = find_i<C, T, C::size-1>::ret;
};

int main(){
    typedef meta_container<int, int&, const int> mc;
    int a = 9999;
    get<mc, 1>::ret_type aref = a;
    std::cout << mc::size << '\n';
    std::cout << aref << '\n';
    std::cout << find<mc, const int>::ret << '\n';
    std::cout << find<mc, float>::ret << '\n';
    std::cin.get(); return 0;
}

3
9999
2
-1

上面例子已經(jīng)實(shí)現(xiàn)了存儲(chǔ)類型的元容器，和元容器上的查找算法，但還有一個(gè)小問題，就是它不能處理模板，編譯器對(duì)模板的操縱能力遠(yuǎn)不如對(duì)類型的操縱能力強(qiáng)（提示：類模板實(shí)例是類型），我們可以一種間接方式實(shí)現(xiàn)存儲(chǔ)“模板元素”，即用模板的一個(gè)代表實(shí)例（如全用 int 為參數(shù)的實(shí)例）來代表這個(gè)模板，這樣對(duì)任意模板實(shí)例，只需判斷其模板的代表實(shí)例是否在容器中即可，這需要進(jìn)行類型過濾：對(duì)任意模板的實(shí)例將其替換為指定模板參數(shù)的代表實(shí)例，類型過濾實(shí)例代碼如下（參考了文獻(xiàn)[1]第 241 頁）：

// 類型過濾，meta_filter 使用時(shí)只用一個(gè)參數(shù)，設(shè)置四個(gè)模板參數(shù)是因?yàn)�，模板通例的參�?shù)列表
// 必須能夠包含特例參數(shù)列表，后面三個(gè)參數(shù)設(shè)置默認(rèn)值為 void 或標(biāo)簽?zāi)０?template<typename T> class dummy_template_1 {};
template<typename T0, typename T1> class dummy_template_2 {};
template<typename T0, typename T1 = void,
    template<typename> class tmp_1 = dummy_template_1,
    template<typename, typename> class tmp_2 = dummy_template_2>
class meta_filter { // 通例，不改變類型
public:
    typedef T0 ret_type;
};
                    // 匹配任何帶有一個(gè)類型參數(shù)模板的實(shí)例，將模板實(shí)例替換為代表實(shí)例
template<template<typename> class tmp_1, typename T>
class meta_filter<tmp_1<T>, void, dummy_template_1, dummy_template_2> {
public:
    typedef tmp_1<int> ret_type;
};
                    // 匹配任何帶有兩個(gè)類型參數(shù)模板的實(shí)例，將模板實(shí)例替換為代表實(shí)例
template<template<typename, typename> class tmp_2, typename T0, typename T1>
class meta_filter<tmp_2<T0, T1>, void, dummy_template_1, dummy_template_2> {
public:
    typedef tmp_2<int, int> ret_type;
};

現(xiàn)在，只需將上面元容器和元容器查找函數(shù)修改為：對(duì)模板實(shí)例將其換為代表實(shí)例，即修改 meta_container<> 通例中“typedef T0 type;”語句為“typedef typename meta_filter<T0>::ret_type type;”，修改 find<> 的最后一行中“T”為“typename meta_filter<T>::ret_type”。修改后，下面代碼的執(zhí)行結(jié)果是：

template<typename, typename> class my_tmp_2;

// 自動(dòng)將 my_tmp_2<float, int> 過濾為 my_tmp_2<int, int>
typedef meta_container<int, float, my_tmp_2<float, int>> mc2;
// 自動(dòng)將 my_tmp_2<char, double> 過濾為 my_tmp_2<int, int>
std::cout << find<mc2, my_tmp_2<char, double>>::ret << '\n'; // 輸出 2

2

10. 總結(jié)

博文比較長，總結(jié)一下所涉及的東西：

• C++ 模板包括函數(shù)模板和類模板，模板參數(shù)形式有：類型、模板型、非類型（整型、指針）；
• 模板的特例化分完全特例化和部分特例化，實(shí)例將匹配參數(shù)集合最小的特例；
• 用實(shí)例參數(shù)替換模板形式參數(shù)稱為實(shí)例化，實(shí)例化的結(jié)果是產(chǎn)生具體類型（類模板）或函數(shù)（函數(shù)模板），同一模板實(shí)參完全等價(jià)將產(chǎn)生等價(jià)的實(shí)例類型或函數(shù)；
• 模板一般在頭文件中定義，可能被包含多次，編譯和鏈接時(shí)會(huì)消除等價(jià)模板實(shí)例；
• template、typename、this 關(guān)鍵字用來消除歧義，避免編譯錯(cuò)誤或產(chǎn)生不符預(yù)期的結(jié)果；
• C++11 對(duì)模板引入了新特性：“>>”、函數(shù)模板也可以有默認(rèn)參數(shù)、變長模板參數(shù)、外部模板實(shí)例（extern），并棄用 export template；
• C++ 模板是圖靈完備的，模板編程是函數(shù)編程風(fēng)格，特點(diǎn)是：沒有可變的存儲(chǔ)、遞歸，以“<>”為輸入，typedef 或靜態(tài)常量為輸出；
• 編譯期數(shù)值計(jì)算雖然實(shí)際意義不大，但可以很好證明 C++ 模板的能力，可以用模板實(shí)現(xiàn)類似普通程序中的 if 和 while 語句；
• 一個(gè)實(shí)際應(yīng)用是循環(huán)展開，雖然編譯器可以自動(dòng)循環(huán)展開，但我們可以讓這一切更可控；
• C++ 模板編程的兩個(gè)問題是：難調(diào)試，會(huì)產(chǎn)生冗長且難以閱讀的編譯錯(cuò)誤信息、代碼膨脹（源代碼膨脹、二進(jìn)制對(duì)象文件膨脹），改進(jìn)的方法是：增加一些檢查代碼，讓編譯器及時(shí)報(bào)錯(cuò)，使用特性、策略等讓模板更通用，可能的話合并一些模板實(shí)例（如將代碼提出去做成單獨(dú)模板）；
• 表達(dá)式模板和向量計(jì)算是另一個(gè)可加速程序的例子，它們將計(jì)算表達(dá)式編碼到類型，這是通過模板嵌套參數(shù)實(shí)現(xiàn)的；
• 特性，策略，標(biāo)簽是模板編程常用技巧，它們可以是模板變得更加通用；
• 模板甚至可以獲得類型的內(nèi)部信息（是否有某個(gè) typedef），這是反射中的內(nèi)省，C++ 在語言層面對(duì)反射支持很少（typeid），這不利于模板元編程；
• 可以用遞歸實(shí)現(xiàn)偽變長參數(shù)模板，C++11 變長參數(shù)模板背后的原理也是模板遞歸；
• 元容器存儲(chǔ)元信息（如類型）、類型過濾過濾某些類型，它們是元編程的高級(jí)特性。

 

進(jìn)一步學(xué)習(xí)

C++ 確實(shí)比較復(fù)雜，這可能是因?yàn)�，雖然 C++ 語言層次比較低，但它卻同時(shí)可以實(shí)現(xiàn)很多高級(jí)特性。進(jìn)一步學(xué)習(xí) C++ 模板元編程的途徑很多：

• C++ 標(biāo)準(zhǔn)庫的 STL 可能是最好的學(xué)習(xí)案例，尤其是其容器、迭代器、通用算法、函數(shù)類模板等部件，實(shí)現(xiàn)機(jī)制很巧妙；
• 另外一個(gè) C++ 庫也值得一看，那就是 Boost 庫，Boost 的元編程庫參考文獻(xiàn)[16]；
• 很推薦《深入實(shí)踐C++模板編程》這本書，這篇博文大量參考了這本書；
• wikibooks.org 上有個(gè)介紹 C++ 各種編程技巧書：More C++ Idioms，文獻(xiàn)[15]；
• 文獻(xiàn)[17]列了 C++ 模板的參考書，共四本；
• 好多東西，書上講的比較淺顯，而且不全面，有時(shí)候直接看 C++ 標(biāo)準(zhǔn)（最新 C++11）可能更為高效，C++ 標(biāo)準(zhǔn)并不是想象中那樣難讀，C++ 標(biāo)準(zhǔn)委員會(huì)網(wǎng)站的 Papers 也很值得看，文獻(xiàn)[3]。

 

參考文獻(xiàn)：

1. 深入實(shí)踐C++模板編程，溫宇杰著，2013（到當(dāng)當(dāng)網(wǎng)）；
2. C++程序設(shè)計(jì)語言，Bjarne Stroustrup著，裘宗燕譯，2002（到當(dāng)當(dāng)網(wǎng)）；
3. C++標(biāo)準(zhǔn)，ISO/IEC 14882:2003，ISO/IEC 14882:2011（到ISO網(wǎng)站，C++標(biāo)準(zhǔn)委員會(huì)）；
4. wikipedia.org（C++， 模板， Template metaprogramming， Curiously recurring template pattern， Substitution failure is not an erro (SFINAE)， Expression templates， C++11， C++14）；
5. What does a call to ‘this->template [somename]‘ do? （stackoverflow問答）；
6. Advanced C++ Lessons，chapter 6，在線教程，2005（到網(wǎng)站）；
7. C++ TUTORIAL – TEMPLATES – 2015，bogotobogo.com 網(wǎng)上教程（到網(wǎng)站）；
8. C++ Templates are Turing Complete，Todd L. Veldhuizen，2003（作者網(wǎng)站已經(jīng)停了，archive.org 保存的版本，archive.org 可能被限制瀏覽）；
9. Metaprogramming in C++，Johannes Koskinen，2004（中科大老師保存的版本）；
10. C++ Template Metaprogramming in 15ish Minutes（Stanford 課程 PPT，到網(wǎng)站）；
11. Template Metaprograms，Todd Veldhuizen，1995（archive.org 保存 Todd Veldhuizen 主頁，可能限制訪問，在線 PS 文件轉(zhuǎn) PDF 文件網(wǎng)站）；
12. Expression Templates，Todd Veldhuizen，1995；
13. C++ Templates as Partial Evaluation，Todd Veldhuizen，1999；
14. Erwin Unruh 寫的第一個(gè)模板元編程程序；
15. wikibooks.org（C++ Programming/Templates/Template Meta-Programming，More C++ Idioms）；
16. THE BOOST MPL LIBRARY online docs（到網(wǎng)站）；
17. Best introduction to C++ template metaprogramming?（stackoverflow問答）。

注：參考文獻(xiàn)中所給的鏈接，打開不了的，可以參見我的另一篇博客配置瀏覽器

Johannes Koskinen 論文，Stanford 課程 PPT，Todd Veldhuizen 論文我網(wǎng)盤保存的副本 -

鏈接: http://pan.baidu.com/s/1ntJstvF 密碼: hogb

標(biāo)簽： swap 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。