C++ Templates === 2021 sprout [Reference](https://hackmd.io/@3sM5hwzZQhSdPoJSYpIQGQ/B1frY7OaV) --- ### What is Template? Template 是一種參數化類型的機制 ---- ### Why Template? ```cpp int a = 3, b = 5; Swap(a, b); double c = 3.0, d = 5.0; Swap(c, d); ``` 你想要有函數可以 Swap 這些東西。 ---- ### Without Template... ```cpp void Swap(int& a, int &b) { int tmp = a; a = b; b = tmp; } void Swap(double& a, double &b) { double tmp = a; a = b; b = tmp; } ``` ---- ### 差別是...? ```cpp void Swap(`T`& a, `T` &b) { `T` tmp = a; a = b; b = tmp; } ``` ---- ### Function with Template ```cpp template<typename T> void Swap(T& a, T& b) { T tmp = a; a = b; b = tmp; } ``` ---- 編譯器會在**編譯時期**進行 template 的代入，產生需要的程式碼。 ```cpp int a = 3, b = 6; Swap<int>(a, b); // 可以用 <T> 明示 T 為何 double c = 3, d = 6; sort(c, d); // 若不明示 <T>，編譯器會自動推斷 ``` --- ### class/struct Template ```cpp template<typename T> struct Data { T val; void print() { cout << i << endl; } }; Data<int> integer; // 必須明示 <int>，因為編譯器無法在此推斷型態 integer.val = 1; integer.print(); // 輸出 1 Data<char> character; character.val = 'I'; character.print(); // 輸出 I ``` --- ### 多個參數 ```cpp template<typename T, typename U> U cast_T_to_U(T t) { return U(t); }; cast_T_to_U<double, int>(1.5); // => 1 cast_T_to_U<long long, int>(2147483648LL); // => overflow ``` 以上我們定義一個可以傳入 T 型態的參數，並會回傳其轉型至 U 型態的函數。 ---- ```cpp template<typename T, typename U> struct Pair { T x; U y; }; Pair<int, double> P; P.x = 3; P.y = 4.1; ``` ---- ### 可變參數 (C++11 or later) ```cpp template<typename T> void print(T last) { cout << last << endl; } template<typename T, typename ... Args> void print(T head, Args... tail) { // ... 適用的規則與上面的不同 cout << head << ", "; print(tail...); } print(1, "HI", 0.5); // 輸出: 1, HI, 0.5 ``` 利用省略符號的特性，我們可以實現接受任意多參數、任意混合型態的函數。 --- ### 編譯時期執行 透過 template，我們能明示編譯器哪些事情要在編譯時期完成，直接將結果存起來供執行時使用。 --- ### Template 大家到這邊就應能理解，Template 簡單來說就是用很奇怪的語法請編譯器產生正常的 C++ 代碼。 ---- ### Template 元編程 Template 意外被發現，即便未必有效率，可以在編譯時期執行任意的運算（圖靈完全）。 ---- ### 編譯時期計算費氏數列 ```cpp template<int n> struct Fib { enum { val = Fib<n - 1>::val + Fib<n - 2>::val }; }; template<> struct Fib<0> { enum {val = 0}; }; template<> struct Fib<1> { enum {val = 1}; }; Fib<10>::val // 55 ``` template 遞迴深度預設最大只有 900，超過就需要額外加上編譯參數 `-ftemplate-depth=D`。 ---- ### constexpr (C++11) const 與 constexpr 很相似，但後者強迫編譯器在編譯的時候完成此常數的計算（因此你也必須確定編譯器真的能夠在編譯時期確定這個常數）。 ```cpp constexpr int n = (10 > 1 ? 2 * 3 : 1 + 2); int x = 10; constexpr int n = x; // error ``` ---- ### 編譯時期計算費氏數列 (C++14) 縮綁對於 constexpr 的限制因此以下這份程式碼可以在編譯時期計算費氏數列 ```cpp constexpr int Fib(int n) { if (n == 0 || n == 1) return n; return Fib(n - 1) + Fib(n - 2); } Fib(10) // 10 ``` ---- ### 題外話 優化效果有限，請勿走火入魔。 --- # C++ STL --- ### Standard Template Library C++ Template 有很強的泛化描述能力。 常用的容器和算法大多已作為標準被泛化。 --- ### STL 容器  ---- ### std::vector vector 是動態陣列，可以想成大概長這樣： ```cpp template<typename T> class vector { private: ... // 內部細節 public: vector(); // 創建一個空的 vector vector(int n, T t); // n 個 t void push_back(T t); // 將 t 塞到尾端 void pop_back(); // 將尾端的元素退出並縮小 int size(); // 回傳現在的元素數量 T operator[](int i); // 可以用 [i] 取得第 i 個元素 void clear(); // 移除所有元素 ... // 其他等著你探索的 }; ``` ---- 在下節裡會再詳細介紹 vector --- ### STL 算法 對容器有很多常用的算法能由標準函數庫呼叫。 事實上，大多都只要迭代器相容就能夠使用。 以下介紹一些常用的： `#include <algorithm>` ---- ### std::for_each  ```cpp void print(int x) { cout << x << '\n'; } int main() { int a[] = {1, 2, 3, 4, 5}; for_each(a, a + 5, print); return 0; } ``` ---- ## for_each 可能的實作方式 ```cpp template<typename T, class Func> void for_each(T _begin, T _end, Func _func) { for (; _begin != _end; _begin++) { _func(*_begin); } }; ``` ---- ```cpp void for_each(int* _begin, int* _end, void (*_func)(int)) { for (; _begin != _end; _begin++) { _func(*_begin); } }; ``` ---- ### std::find  ```cpp int vec[] = {1, 2, 3, 4, 5}; int i = find(vec, vec + 5, 3) - vec; // i = 2 i = find(vec, vec + 5, 0) - vec; // i = 5 ``` ---- ### std::reverse  ```cpp int vec[] = {1, 2, 3, 4, 5}; reverse(vec + 1, vec + 4); // vec = { 1, 4, 3, 2, 5} ``` ---- ### std::random_shuffle  ```cpp int vec[] = {1, 2, 3, 4, 5}; random_shuffle(vec, vec + 5); // vec 會被隨機排列 ``` ---- ### std::lower_bound  ```cpp int vec[] = {1, 2, 3, 3, 4, 5}; int i = lower_bound(vec, vec + 5, 3) - vec; // i = 2 ```  ---- ### std::sort  ```cpp int vec[] = {7, 2, 10, 3, 1}; sort(vec, vec + 5); ``` ---- ### 更多 全世界的秘寶都放在這裡了： http://www.cplusplus.com/reference/algorithm/ ----