前言

很多的語言其實都有 template 或者 meta programming, 而 C++ 作為同時具備兩者並結合的語言創造了一種非常可怕的工具。

其可怕之處有二

1. 功能很可怕，可以在編譯期作遞迴等複雜運算
2. debug 起來很可怕，沒有足夠好用的 debugger, compiler 出錯會吐成千上萬行的 error 根本看不懂

熟悉 template 可以讓你在 C++ 這個靜態語言裡面寫出近似於 python 或 javascript 這類動態語言的 code.
也就是創造更好用的 API 同時不需要支付效能代價

然而資訊科學是一個沒有賢者之石的世界
要得到又快又好用的東西，你要嘛向神明祈禱
或者就是付出巨大的努力
這什麼捏他，這個作者好中二阿

經典案例，費氏數列

為了展現模板的基礎特性，我們用最通俗的範例來展示 template 可以做到等價於 if-else 和 recursive 的操作。

#include <iostream>

template<int n>
struct fib {
    static constexpr int result = fib<n - 1>::result + fib<n - 2>::result;
};

template<>
struct fib<0> {
    static constexpr int result = 0;
};

template<>
struct fib<1> {
    static constexpr int result = 1;
};

int main() {
    std::cout << fib<10>::result << std::endl; // 55
}

觀念

所有的 template 都應該視為一種函數一種輸入為任何靜態時期可以決定內容的函數，包括型別、primiary type value 等等，而輸出為一個型別。

這個輸出的型別就是 template type 被呼叫當下的樣子本身。
以上面的範例來說 fib<0> 就是輸入為 0 的輸出型別

換言之 fib<0>, fib<1> ... fib<n> 各自都不是同一種型別，這是非常重要的特性
之後會使用到。

何謂靜態時期可決定？

簡單來說就是在程式真正編譯完跑起來之前就可以通過計算推導得知內容的符號或表達式。
也就是說模板運算其實可以被任何 hard code 取代，
我們之所以使用模板其中一個最根本的目的是為了節省 hard code 的代碼量

在上面的範例中，我們在 main 裡呼叫 fib 模板傳入 10,
其實我們完全可以在紙上手算出第 10 個費氏數列的值然後直接 hard code 上去輸出

但是 compiler 其實是有數學運算能力的，所以我們不要 hard code 55
我們 hard code 10 然後讓 compiler 通過模板運算得到 55

完整解釋範例

首先 template<int n> struct fib 這裡宣告了一個輸入為 int value 的 fib 模板型別。
在這裡我們需要一個東西來表示費氏數列的運算結果。
我們知道模板運算的結果是一個型別，所以這個東西勢必為型別的一部分

我們說：
一個型別的一部分若為型別則為成員型別，這種狀況我們用 using 即可表示。
而一個型別的一部分若為數值則為靜態變數，我們用 static 宣告

這裡要注意，我們說的一部分不包含單純的 member variable, 為什麼呢？

struct S {
    int v;
};

在這個範例中，S 沒有 instance (也就是 S o) 的話，v 是沒有任何情況可以被取用的。
也就是說，v 其實是 S 派生的 object 的一部分而不是 S 本身的一部分。

(這一整段使用的一部分的概念乃是為了理解方便用的非常不精準的字，能 get 到觀念就好，不要執著於字面上的意義)

所以說，fib 的輸出型別中必須要有某種 static member 來表示費氏數列的數值結果，同時他必須保證是編譯時期決定的。
在這個範例中 result 充當了這個角色，而 constexpr 則是一個關鍵字，告訴編譯器請盡可能在編譯期計算這個符號的內容

而 result 的計算方式就遵照費氏數列的公式，
概念上就是 fib<n-1> + fib<n-2>
但是注意，剛剛講過我們是用 result 來表示數值的運算結果，
所以必須改成 result = fib<n-1>::result + fib<n-2>::result

終止條件

遞迴必須要有終止條件，也就是說模板必須要有方法表示 if-else
在這裡就出現另一個模板特性叫做特化
這個概念其實一種 match and replace 的動作，
在這個範例中 template<> struct fib<0> 即告訴 compiler 說當 input 是 0 的時候
請使用下列實作取代本來通用的 template<int n> struct fib 版本
而 fib<0> 的實作很簡單，就是 result = 0, 同理 1 也是。

至此我們就完成了模板運算版本的費氏數列。

可是我用動態時期 loop 算就好了啊？

這就是靜態運算與動態運算最大的差異點
靜態時期的計算結果相當於 hard code 所以以上面的範例來說
執行期是不會進行任何數學運算就可以直接輸出 55 的
對於編譯結果來說，fib<10>::result 相當於 int literal 55

終止條件還是怪怪的

很多人在寫費氏數列的時候，會採用這種邏輯

int fib(int n) {
    if(n < 2) return n;
    else return fib(n - 1) + fib(n - 2);
}

這種邏輯，終止條件用 n < 2 構成的，這裡也引伸出一個問題
就是如果終止條件涵蓋好幾十個整數，難道我要一個一個寫特化嗎？
想像一下如果有一種遞迴終止條件是 if(n < 100) return ...;
那我豈不是寫到死？

模板還有一種功能叫做 偏特化 (parital specialization)
利用這種通能就能解決這個問題，這裡我們要重寫一種 fib 的靜態運算

#include <iostream>

template<int n, bool is_end>
struct fib_impl {};

template<int n>
struct fib {
    static constexpr int result = fib_impl<n, (n < 2)>::result;
};

template<int n>
struct fib_impl<n, false> {
    static constexpr int result = fib<n - 1>::result + fib<n - 2>::result;
};

template<int n>
struct fib_impl<n, true> {
    static constexpr int result = n;
};

int main() {
    std::cout << fib<10>::result;
    return 0;
}

這個做法乍看複雜其實思路很簡單的，
我們知道 n < 2 回傳的是一個 bool, 那麼我們就把一個 bool 放上可以用於特化的模板參數
我們故且稱之為 is_end
當 is_end 為 true 的時候，執行終止條件，否則執行遞迴
所以在這裡 struct fib_impl<n, false> 和 struct fib_impl<n, true> 充當了這兩種條件的執行路徑。
其中你可以發現，fib_impl 是兩個參數的模板，
在這兩個路徑中我們只對第二個參數 is_end 進行特化，而第一個參數 n 則直接 by pass 過去。

我們姑且先忽略兩條路徑的實作，來看 template<int n> struct fib

fib 可以想像為 fib_impl 的 wrapper, 重點只是為了抹除 is_end 的存在，
所以 n 很直觀的就傳入 fib_impl 的 n
而 is_end 根據最一開始的定義我們用 n < 2 帶入就完成了。

回頭看 fib_impl 兩條路徑的實作

對於 is_end = true 的情況，很直觀的我們使 result = n 即可。
對於 is_end = false 的形況，我們讓他呼叫了 fib, 這看起來會讓一些人腦袋打結
因為 fib 好像一種最外層的 wrapper, 為什麼可以在 implement 中呼叫 wrapper 呢？

這其實是可以的，這就是所謂的 mutual recursion,

然而知道這個名詞沒什麼意義，腦袋還是打結的

所以我們稍微拆解一下，不去呼叫 fib 的話如果使用 fib_impl 會怎麼寫
is_end 該怎麼處理？

根據定義其實 is_end 就是 n < 2 ，而在 n - 1, n - 2 兩條路徑中， n 被替換為 n - 1, n - 2
所以很直觀的， is_end = (n - 1) < 2 和 (n - 2) < 2

寫出來即是

result = fib_impl<n - 1, (n - 1) < 2>::result + fib_impl<n - 2, (n - 2) < 2)>::result;

然後你就會發現你重寫了兩次 ... < 2

煩

所以就呼叫 fib 就好了

一個思考陷阱

剛剛的費氏數列範例，在如何用特化做出 if-else 的部分，應該有人當場想到了三元運算子(?:)

對阿，為什麼不用三元運算子呢？

這樣寫不是簡單多了嗎？

#include <iostream>

template<int n>
struct fib {
    static constexpr int result = (n < 2) ? n : (fib<n - 1>::result + fib<n - 2>::result);
};

int main() {
    std::cout << fib<10>::result << std::endl; // 55
}

然後你就發現編譯器 fail 了
為什麼呢？

這個問題留給讀者思考，本人會在後續篇章解釋

Summary

有些人可能有注意到，寫 template 好像在寫某種 functional programming language
不能直接 loop 但是可以用遞迴做很多事，而且 input output 保證 pure

然後不去宣告變數，把所有東西往參數丟然後在包一層 wrapper
是的，如果你學過 LISP, scheme 之類的語言，你會發現 template 就是那麼回事
後面解釋 variadic template parameter 的時候你就會發現完全可以用 car cdr 的概念去處理任何不定數量參數的問題
然後就會發現 std::tuple 的各種操作的實作都是 car cdr 的組合
所以 head tail 的概念很重要，有學過的可以拿出來複習一下。

其次還有型別封裝、推導然後再拿出來
基本上跟一些語言的 monad 就是同一回事
拆解過後其實都沒什麼神奇的，基本都是常用 template 就會被動學會的東西