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

想想看，有人在程式編譯時塞了一堆運算，榨取程式效能(可能在你差個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
{
};
這裡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必須是"static const"，這代表"編譯時期產生"，且"不可更動"的數字。
這樣就不合法：
A<int, abs(-1)>
別以為他會產生A<int, 1>，他只會有error，abs的回傳值是一個執行期"變數"
正因為他限定編譯時期就必須決定的變數，我們可以利用"編譯期操作"來達成許多目標

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

下一個範例：
template<int N, int END>
struct Operation
{
};
template<int END>
struct Operation<END, END>
{
};

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

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

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

using namespace std;
template<int N>
struct ARRAY
{
};
template<>
struct ARRAY<0>
{
};
template<int LOWER, int UPPER>
struct BS
{
};
template<int N>
struct BS<N, N>
{
};
int main()
{
}

這邊有了幾個簡單的TMP常用手法介紹，Boost已經有了一個偉大的程式庫叫作MPL
他提供了所有STL裡的，靜態的版本，非常強大，創作技巧可以參考他的原始碼，因為是Open Source的
Boost MPL