csie-sprout-template-and-stl-basic

--- title: csie-sprout-template-and-stl-basic --- # C++ Templates slido: 99601 Sprout 2020 --- ### What is Template? Template 定義一類的 Class/Struct、函數、變數、或者型別。 ---- ### Why Template? ```cpp int arr_int[N]; double arr_double[N]; char arr_char[N]; ``` 你想要有函數可以 sort 這些東西。 ---- ### Without Template... ```cpp void sort_int(int arr[], int n) { for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) if (arr[j] < arr[i]) swap(arr[j], arr[i]); } void sort_double(double arr[], int n) { for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) if (arr[j] < arr[i]) swap(arr[j], arr[i]); } ``` ---- ### 差別是...? ```cpp void sort_`T`(`T` arr[], int n) { for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) if (arr[j] < arr[i]) swap(arr[j], arr[i]); } ``` ---- ### With Template ```cpp template<typename T> void sort(T arr[], int n) { for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) if (arr[j] < arr[i]) swap(arr[j], arr[i]); } ``` 以上就是用 Template 定義**一類**函數的例子。我們定義了可以對**一類**型別做排序的函數。 ---- 編譯器會在**編譯時期**進行 template 的代入，產生需要的代碼。 ```cpp int arr_int[N]; sort<int>(arr_int, N); // 可以用 <T> 明示 T 為何 double arr_double[N]; sort(arr_double, N); // 若不明示 <T>，編譯器會自動推斷 ``` ---- 自定義的 struct 也可以： ```cpp struct Int { int i; bool operator < (const Int &rhs) const { return i < rhs.i; } }; Int arr_Int[N]; sort(arr_Int, N); ``` 注意到我們定義的 sort 模板會進行 < 的比較。如果我們傳進去的型態沒有定義 <，編譯器在展開 template 之後就會發現錯誤。 --- ### Template without Template 用 \#define 也能達到類似 template 的效果： ```cpp #define define_sort(T, F)\ // 用反斜線表示延續下行 void F(T *arr, int n){\ for (int i = 0; i < n; ++i)\ for (int j = i; j < n; ++j)\ if (arr[j] < arr[i])\ swap(arr[j], arr[i]);\ } define_sort(int, sort_int) // 編譯器會直接做字串替換 define_sort(double, sort_double) ``` ---- ### define 陷阱 ```cpp #define mul(a, b) (a * b) mul(3, 5); // => (3 * 5) mul(2 + 3, 4 + 5); // => (2 + 3 * 4 + 5) #define fixed_mul(a, b) ((a) * (b)) fixed_mul(2 + 3, 4 + 5); // => ((2 + 3) * (4 + 5)) ``` --- ### class/struct Template ```cpp template<typename T> struct Data { T i; void print() { cout << i << endl; } }; Data<int> integer; // 必須明示 <int>，因為編譯器無法在此推斷型態 integer.i = 1; integer.print(); // 輸出 1 Data<char> character; character.i = 'I'; character.print(); // 輸出 I ``` --- ### Variable Template ```cpp template<int N> struct square { static const int value = N * N; }; int v25 = square<5>::value; // 25 ``` 以上我們定義了**一類**變數，是傳入的常數的平方。 --- ### Alias Template 說到給型態暱稱，有兩種常用的做法： ```cpp typedef long long lint1; lint1 ans = 1LL << 60; using lint2 = long long; lint2 ans = 1LL << 60; ``` ---- ### Alias Template 我們也可以用 Template 定義一些有參數的暱稱： ```cpp template <typename T> struct remove_pointer<T*> { using type = T; }; int a = 5; remove_pointer<int*>::type b = a; // b = 5; ``` --- ### 其他 Template 參數除了概括一種型態（先前的 template\<typename T\>) 以外，還有一些其他參數的給法。 ---- ### 多個參數 ```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); // => -2147483648 ``` 以上我們定義一個可以傳入 T 型態的參數，並會回傳其轉型至 U 型態的函數。 ---- ### 常數參數 ```cpp template<typename T, int N> T multiply(T v) { return v * N; } multiply<int, 3>(10); // => 30 ``` 我們定義了一個可以傳入型態 T 的參數，並回傳其與 N 經過乘法作用的結果。常數的型態必須屬於整數型、指標、或是參照。 ---- ### 預設參數 ```cpp template<typename T = int, int N = 3> T multiply(T v) { return v * N; } multiply(10); // => 30 ``` ---- ### 可變參數 ```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，我們能明示編譯器哪些事情要在編譯時期完成，直接將結果存起來供執行時使用。 ---- ### constexpr 關鍵字 const 與 constexpr 很相似，但後者強迫編譯器在編譯的時候完成此常數的計算（因此你也必須確定編譯器真的能夠在編譯時期確定這個常數）。 ```cpp constexpr int v25 = 5 * 5; // OK int n; constexpr int vnn = n * n; // error: the value of 'n' is not usable in a constant expression ``` ---- ### constexpr + Variable Template ```cpp template <int x, int y> struct compute { constexpr static int add = x + y; }; constexpr int add46 = compute<4, 6>::add; // 10 ``` 由於我們要求 add46 要在編譯時期得到結果，compute<4, 6> 會在編譯時期產生。 --- ### 特殊化有時需要對某些特定的 template 參數做特殊的處理，其中一個方法就是利用 template 特殊化。 ---- 注意特殊化目前只適用於 struct 或 class： ```cpp template <int x, int y> struct divide { constexpr static int result = x / y; }; template <int x> struct divide<x, 0> { constexpr static int result = 42; }; divide<8, 1>::result; // 適用前者: 8 divide<8, 0>::result; // 適用後者: 42 ``` 有類似函數重載的效果，編譯器會嘗試使用最具體而且不會有編譯錯誤的 template 進行展開。 ---- ### 利用特殊化比較型態 ```cpp struct False { const static int value = false; }; struct True { const static int value = true; }; template<typename T, typename U> struct Is_same : False {}; // 若 T != U, 繼承 False 類 template<typename T> struct Is_same<T, T> : True {}; // 繼承 True 類 double d; static_assert(Is_same<decltype(d), double>::value, ""); // OK int i; static_assert(Is_same<decltype(i), int>::value, ""); // error: static assertion failed ``` --- ### Template 元編程大家到這邊就應能理解，Template 簡單來說就是用很奇怪的語法請編譯器產生正常的 C++ 代碼。 ---- ### Template 元編程 Template 意外被發現，即便未必有效率，可以在編譯時期執行任意的運算（圖靈完全）。 ---- ### Template 元編程挑戰編譯時期執行僅能對常數進行操作，因此不允許有變數重複代值；是一種函數式編程。 ---- ### not 函數式編程? 計算 5!: ```cpp int ans = 1; for (int i = 1; i <= 5; ++i) { ans *= i; // i 跟 ans 都在變 } ``` ---- ### is 函數式編程? 計算 5!: ```cpp int fact(int n) { return n == 0 ? 1 : n * fact(n - 1); } int ans = fact(5); // 所有宣告都是常數 ``` ---- ### 編譯時期計算 5! ```cpp template<int n> struct fact { constexpr static int result = n * fact<n - 1>::result; }; template<> struct fact<0> { constexpr static int result = 1; }; fact<5>::result; // 120 ``` template 遞迴深度預設最大只有 900，超過就需要額外加上編譯參數 `-ftemplate-depth=D`。 ---- ### 題外話優化效果有限，請勿走火入魔。 --- # C++ STL --- ### Standard Template Library C++ Template 有很強的泛化描述能力。常用的容器和算法大多已作為標準被泛化。 --- ### STL 容器 ![](https://i.imgur.com/35pdupF.png) ---- ### 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(); // 移除所有元素 ... // 其他等著你探索的 }; ``` ---- ### 例子 ```cpp vector<int> vec(5, 1); // vec = {1, 1, 1, 1, 1} for (int i = 0; i < vec.size(); ++i) { vec[i] *= i; } // vec = { 0, 1, 2, 3, 4} vec.pop_back(); // vec = { 0, 1, 2, 3 } vec.clear(); // vec = { } vec.push_back(-1); // vec = { -1 } ``` --- ### STL 迭代器 STL 的容器都有定義迭代器，供我們遍歷元素。迭代器必然屬於以下五種之一： 1. Input Iterator 2. Output Iterator 3. Forward Iterator 4. Bidirectional Iterator 5. Random-access Iterator ---- 在下節 <STL> 裡會再詳細介紹 iterator。 --- ### STL 算法對容器有很多常用的算法能由標準函數庫呼叫。事實上，大多都只要迭代器相容就能夠使用。以下介紹一些常用的： ---- ### 匿名函數在這之前先介紹匿名函數(std::function)： ```cpp function<int(int, int)> add = [](int a, int b) { return a + b; }; // function<回傳型(參數型)> 函數名 = [](參數) { ... }; add(3, 4); // 7 int ans = [](int a, int b) { return a * b; } (3, 9); // 可以不給名稱就直接呼叫 ``` ---- ```cpp int c = 5; []() { c = 6; } (); // error: 'c' is not captured [=]() { c = 6; } (); // error: assignment of read-only variable 'c' [&]() { c = 6; } (), cout << c; // OK, 輸出: 6 ``` ---- ### Capture by value ```cpp int c = 5; auto f = [=]() { return c; }; c = 6; cout << f(); // 輸出: 5 ``` ---- ### Capture by reference ```cpp int c = 5; auto f = [&]() { return c; }; c = 6; cout << f(); // 輸出: 6 ``` ---- ### Binding 匿名函數會在創建時在其變數空間結合。 ```cpp int c = 6; function<int()> f; if (true) { int c = 5; f = [&]() { return c; }; } c = 7; cout << f(); // 輸出: 5 ``` ---- ### std::any_of ![](https://i.imgur.com/AfHIHH1.png) ```cpp int vec[] = {1, 2, 3, 4, 5}; any_of(vec, vec + 5, [](int v) { return v < 0; }); // false ``` ---- ### std::find ![](https://i.imgur.com/3utaXHH.png) ```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 ![](https://i.imgur.com/Zv02Ut0.png) ```cpp int vec[] = {1, 2, 3, 4, 5}; reverse(vec + 1, vec + 4); // vec = { 1, 4, 3, 2, 5} ``` ---- ### std::random_shuffle ![](https://i.imgur.com/mW4v19o.png) ```cpp int vec[] = {1, 2, 3, 4, 5}; random_shuffle(vec, vec + 5); // vec 會被隨機排列 ``` ---- ### std::lower_bound ![](https://i.imgur.com/3sC9734.png) ```cpp int vec[] = {1, 2, 3, 3, 4, 5}; int i = lower_bound(vec, vec + 5, 3) - vec; // i = 2 ``` ![](https://i.imgur.com/eeexr3m.png) ---- ### 更多全世界的秘寶都放在這裡了： http://www.cplusplus.com/reference/algorithm/ --- ### 練習 NEOJ#369 艾莉燕的生日請大家輸入完之後只用一行 std::sort 搭配匿名函數處理掉。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.