owned this note
owned this note
Published
Linked with GitHub
# containers
> STL containers == Standard Template Library containers
---
## 前言
這是我怕有些初階班剛上進階班對 `containers` 還不熟，所以才寫了這 $35000$ 多字的講義 (經過一些增修後超過了 `49000` 字)
雖然和學長的講義很像，而且可能也沒有比較詳細，但還是加減看一下 :poop:
---
## NOT STL containers
### 傳統一維陣列
實用程度： :star: :star: :star: :star: :star:
初階班前幾堂就會碰到了，這邊小講一下
使用時不用任何標頭檔，他是你為這一個變量分配一串記憶體
:::success
:::spoiler 沒學過指標、參照、迭代器但想學的點我
可以看 [$pointer$ 初階班講義 $by$ 第 $11$ 屆初階教學 **samsonjaw**](https://hackmd.io/@samson-note/pointer_reference)
#### 指標 (pointer, *)
指標是可以存取一個記憶體位置的變數，但說穿了他和 `int` 之類的一樣是型別
他的宣告方式，在變數名字前加一個 `*`
要取值的話也是在指標變數前加一個 `*`
若沒有初始化或被指派，去存取他的值會出問題 (大概率 `RE`)
因此我們常在宣告時就直接指派一個空指標 `nullptr` 給他
指標更多的用法是用 `new` 來分配新的記憶體給他，讓他不用依賴其他變數的記憶體位置
##### 宣告指標
```cpp
int *a, *b; // a and b are pointers
int* a, b; // b isn't a pointer
```
##### * 在 C++ 中的六種出現情形：
1. 乘法 `(a * b)`
2. 乘法賦值 `(a *= b)`
3. 指標宣告 `(int *a, *b)`
4. `call by address` `( void modify(int *arr, const int len) )`
5. 取值 `get value` (指標，`pointer` ) `(cout << *ptr << endl)`
6. 取值 `get value` (迭代器，`iterator` ) `(cout << *vec.begin() << endl)`
##### 指標使用範例
```cpp=
#include <iostream>
using namespace std;
void addition(int *x, int *y) { // call by address
*x = 1, *y = 1; // 取址，將 x, y 兩者記憶體儲存的值改成 1
cout << *x + *y << endl; // 輸出 2
}
int main() {
int b = 10, c = 100;
int *ptr = &b, *a = &c; // 指標宣告
cout << *ptr << endl; // 輸出 10
*ptr = 30; // 直接將 b 的記憶體儲存的值改成 30
cout << b << endl; // 輸出 30
addition(ptr, a);
cout << *ptr << ' ' << *a << endl; // 輸出 1 1
cout << ptr << endl; // 會輸出一個記憶體位址名稱，如： 0x6ffdfc
return 0;
}
```
#### 參照 (reference, &)
有的人又叫他參考、引用，上次 **APCS** 有考出這個菜鳥殺手
和 `pointer` 一樣，若要宣告一個參照型別 `(reference type)`，在變數名字前加一個 `&`
而且在宣告時就要初始化他所參照的對象
可以將參照想像成是將要替代的東西取一個別名，兩者指向同一個記憶體位址，而且都可以對其進行存取、修改
而 `call by reference` 只有 **C++** 才有，**C** 語言只有 `call by pointer`
`call by reference` 相較之下方便、好寫很多
參照是直接拿取記憶體位置，因此如果在大量需要呼叫 ($e.g.$ 遞迴、快速冪) 等程式碼中，若沒有加參考可能會將時間浪費在拷貝數據上，進而導致 `TLE`
順帶一提，最基本的 `call by value` 就是將你給的變數複製一份到新的記憶體位置上再進行運作
##### 宣告指標
```cpp
int &a = b, &c = d; // a and c are references
int& a = b, c = d; // c is just a normal int value type
```
##### & 在 C++ 中的六種出現情形：
1. 位元運算 `bitand` `(a & b)`
2. 位元 `and` 賦值 `and_eq` `(a &= b)`
3. 邏輯運算 `and` `(a && b)`
4. 參照宣告 `(int &a, &b)`
5. `call by reference` `( void modify(int &x, int &y) )`
6. 取址 `get address` `(*ptr = &val)`
##### 參照使用範例
```cpp=
#include <iostream>
using namespace std;
void sub(int &x, int &y) { // call by reference，對這邊改動也會影響主程式中的變數
x = y;
y = -8;
cout << x - y << endl; // 輸出 10
}
int main() {
int a = 1, b = 2;
int &ref = a; // 宣告參照 ref，此時將 ref 看作是 a 的別名
int *ptr = &b; // 進行取址，將 b 的記憶體位址指派給 *ptr 這個指標
cout << (a & b) << endl; // 輸出兩者的位元運算值：0
if (a && b) // 若 a、b 皆為 true
cout << *ptr * ref << endl; // 輸出指標 ptr 取值乘上參照 ref 的值：2
a &= b; // a = a & b，現在 a 為 0，同樣地，ref 也是 0
sub(ref, b);
cout << a << ' ' << *ptr << endl; // 輸出 2 -8
return 0;
}
```
##### 迭代器 (iterator)
他跟指標 `pointer` 很像，簡單來說容器專用的 `pointer`，在前面有提到，也是一樣用 `*` 來進行取值
許多 `STL` 都有支援 `iterator`
不過注意 `stack`、`queue` 沒有支援！
如果用了會吃 `CE`
範例搭配下面的成員函式存取來講
`begin()` 指的是最開始那格
`end()` 指的是最後面的後面那格
**C++** 的 `iterator` 以左閉右開為主，請大家不要弄錯
##### 成員函式存取 (. 、 ->)
用 `.` 來存取一個物件的成員函式 ( `struct` / `class` )
當你要存取一個指標內的成員函式的話，應該用 `->` 較為方便，而不是 `*` 搭配 `.`
因為 **C++** 有一個名為運算子優先順序的東西
例如 `* /` 在 `+ -` 前面，而 `.` 較 `*` 優先，因此若要用需要加 `()` 提升他的優先程度，就像數學式一樣
- `begin()` 最常用，指向 `[0]` 這格
- `end()` 最常用，指向 `back()` 後面那格
- `rbegin()` 次常用，指向 `back()`
- `rend()` 次常用，指向 `[0]` 前面那格
- `cbegin()` 少見，`const begin()` 就是只能存取不能修改，但用 `begin()` 就好
- `cend()` 少見，`const end()` 就是只能存取不能修改，但用 `end()` 就好
- `crbegin()` 極少見，`const rbegin()` 就是只能存取不能修改，但用 `rbegin()` 就好
- `crend()` 極少見，`const rend()` 就是只能存取不能修改，但用 `rend()` 就好
##### 使用範例
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int len = 100;
vector < pair<int, int> > vec(100);
for (int i = 0; i < len; i++) {
vec[i].first = i;
vec[i].second = i * len;
}
vector<int>::iterator iter;
for (iter = vec.begin(); iter != vec.end(); iter++) {// ++ 有被 overload
// it = next(it);
cout << iter -> first << ' ' << iter -> second << endl;
// iter -> first 寫成 (*iter).first 也可以
}
return 0;
}
```
##### APCS考題範例
以下程式碼輸出為何？ (**APCS** 考題以 **C** 語言命題)
```c=
#include <stdio.h>
void add(int x, int y) {
x = 1;
y = 1;
printf("%d ", x + y);
}
int main() {
int a = 3, b = 5;
add(a, b);
printf("%d\n", a + b);
return 0;
}
```
:::spoiler 答案點我：
```
2 8
```
答對了嗎？因為沒有加 `reference`，這一題是 `call by value`，在上面函數內改動的值不會影響到 `main` 中變數的值
但是很多人會答出 $2\ 2$
不過通常 **APCS** 都是考 **C** 語言，而非 **C++**，因此不會有 `call by reference` 出現
:::
#### 宣告：
```cpp
int arr[n] = {};
// 基本款，n 是陣列大小
// = {} 可不打，若不打不初始化
// 大括號中沒東西是初始化為 0
// 若大括號中元素數量不足 n 個，那會將元素優先初始化給前面項，沒有初始化到的自動初始化為 0
// 因此可以直接打 {0} 來得到全部初始化為 0 的陣列
int arr[] = {a1, a2, a3, ..., an};
// 可以不指定大小，但後面一定要有初始化
// 大括號中的元素數量即為陣列大小，非不定大小
```
:::warning
:::spoiler 陣列傳遞
若要傳遞陣列到函式中，要注意用法：
```cpp
void (int *arr,int len)
void (int arr[], int len)
// 若要傳遞的話不能打出陣列大小，而這裡的 arr[] 相當於 arr*，是傳遞一個位址 address
// 因此需要再傳遞一個變數為 arr 的大小以免溢位
```
試著將一串 $0$ 的陣列變成一串 $1$ 的陣列 (使用 `call by pointer`)
範例 `code`：
```cpp=
#include <iostream>
using namspace std;
void modify(int *a, const int len) {
for (int i = 0; i < len; i++)
a[i] = true;
}
int main() {
const int n = 3;
int arr[n] = {};
for (int i = 0; i < n; i++)
cout << arr[i] << ' ';
cout << endl;
modify(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}
```
:::
#### 使用範例
將一串數字進行 `bubble sort`
```cpp=
#include <iostream>
#include <algorithm> // for swap
using namespace std;
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
swap(arr[i], arr[j]);
for (int i = 0; i < n; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}
```
:::spoiler **毒區退散** 若對指標很熟，可以做動態記憶體配置，這樣常數小又抵得上半個 `vector`：
#### 範例程式碼
```cpp=
#include <iostream>
#include <cstdlib> // malloc
#include <cstring> // memset
//#include <stdlib.h>
//#include <string.h>
int main() {
int *arr;
int len = 10;
arr = new int[len];
// C: arr = (int*) malloc(len * sizeof(int)); 我用這個
memset(arr, 0, len * sizeof(int));
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
// 也可以將 arr[i] 寫成 *(arr + i)
delete [] arr;
// C: free(arr); 我用這個
return 0;
}
```
#### malloc
先宣告一個整數指標、所需長度
用 `malloc` 分配記憶體給他
他是 **C** 語言時期的產物，因此他也位於 `<stdlib.h>` 標頭檔中
但許多在 **C** 語言時期就存在的函式在 **C++** 中被寫入 `iostream`
也就是說，這些函式只要 `#include <iostream>` 即可使用
不用再另外去找原本定義他的標頭檔
這裡的 `calloc`、`malloc`、`realloc`、`free` 四個函式就是例子
但小心 `memset` 沒有被定義
在標頭檔 `<cstdlib>` 中 `malloc` 函數定義如下：
```cpp
void *malloc( size_t size )
```
當我們用完之後，他回傳的是一個 `void*` 的記憶體位置，我們應該要將他指定為 `int*` 以避免後面操作時出問題
而要小心的部份是，若沒有成功分配記憶體位置 (過大)，則函式會 `return` 一個空指標
`nullptr`，而在 **C** 語言中是 `NULL`
因此分配完後在不確定的情形下，應該進行檢查：
```cpp=
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
int main() {
int *arr;
int len = 10;
arr = (int*) malloc(len * sizeof(int));
if (arr == nullptr) {
cout << "failed to allocate the memory\n";
return 1; // 代表程式出錯
}
memset(arr, 0, len * sizeof(int));
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
free(arr);
return 0;
}
```
#### memset
`memset` 在標頭檔 `<cstring>` 中定義如下：
同樣是 **C** 語言時期的產物，因此他也位於 `<string.h>` 標頭檔中
```cpp
void *memset( void* dest, int ch, std::size_t count )
```
第一格放要指派的記憶體位置
第二格放指定的數字
最後放大小，而大小是用「字節」(位元組) 為單位，也就是以 `byte` 為單位
要小心 arr 是一個指標，指標大小為 `8 bytes`，所以在這形況下不能用 `sizeof(arr)`
因此我們用 `len` 去乘上一個位置，也就是 `int` 的 `size` 這樣就可以成功計算所需的記憶體數量
不過 `sizeof(arr*)` 代表著那一個指標所代表的值記憶體大小，因此可以寫成 `sizeof(arr*) * len`
註：資料型態占的位元組 `(bytes)`
- `bool = 1`
- `char = 1`
- `int = 4`
- `float = 4`
- `long long = 8`
- `double = 8`
#### calloc
同時，這兩個也可以用一個 `calloc` 函式合併
`calloc` 和 `malloc` 不同之處在於 `calloc` 在分配記憶體位置時會同時將他初始化為 $0$
參數的傳入也有所不同，他要求兩個參數，前者為數量，後者則是每格記憶體位置大小
同時他也在 `<cstdlib>` 函式庫中定義
定義如下：
```cpp
void *calloc( size_t count, size_t size )
```
他若沒有成功分配記憶體位置也會回傳空指標 `nullptr`、`NULL`
以上面的程式碼為例：
```cpp=
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
int main() {
int *arr;
int len = 10;
arr = (int*) malloc(len * sizeof(int));
if (arr == nullptr) {
cout << "failed to allocate the memory\n";
return 1; // 代表程式出錯
}
memset(arr, 0, len * sizeof(int));
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
free(arr);
return 0;
}
```
相當於是
```cpp=
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
int *arr;
int len = 10;
arr = (int*) calloc(len, sizeof(int));
if (arr == nullptr) {
cout << "failed to allocate the memory\n";
return 1; // 代表程式出錯
}
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
free(arr);
return 0;
}
```
#### realloc
`realloc` 是針對已分配的記憶體來重行分配
與下面會提到的 `resize` 相似
和 `malloc` 不同之處在於他會保留原本已被分配的值
他的處理方式有分為 $3$ 種情形
不過因為和我們的應用較沒關係，因此這邊不多做介紹，有興趣可以自己去上網學習
他需要兩個參數，前者是分配的基礎，後者則是分配的記憶體總量
```cpp
void *realloc( void* dest, std::size_t count )
```
和上面的兩個 `alloc` 一樣，都會在記憶體分配失敗時回傳一個空指標 `nullptr` 或 `NULL`
程式碼舉例：
```cpp=
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
int len = 10;
int *arr = (int*) calloc(len, sizeof(int));
if (arr == nullptr) {
cout << "failed to allocate the memory\n";
return 1; // 代表程式出錯
}
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
len = 20;
arr = (int*) realloc(arr, len * sizeof(int));
for (int i = 0; i < len; i++)
cout << arr[i] << ' '; // 後面十位不會被初始化為 0
cout << endl;
free(arr);
return 0;
}
```
#### 定義於 iostream 中的函式
:::spoiler * 代表我看過的，後面部份我認識的有解釋
數學類函式：
1. `abs(int x)` * 絕對值，但要注意這是 **C** 語言中 `<stdlib.h>` 所定義的 `abs` ， 而不是 `<math.h>` 中定義的，他沒有 `overload` 浮點數
2. `fabs(double x)` 對浮點數取絕對值，有了 `<math.h>` 就不重要了
3. `pow(double x, double a)` * $x^a$
4. `sqrt(double x)` * 開平方根
5. `exp(double x)` * $e^x$
6. `log(double x)` * 小心這裡的 $log$ 是自然對數 $ln$，也就是 $log_e$
7. `log10(double x)` * $log_{10}$ 也就是常用對數 $log$
8. `ceil(double x)` * 取上界，正數進位，負數捨去小數
9. `floor(double x)` * 取下界，正數捨去小數，負數小數變 $-1$
10. `trunc(double x)` * 將小數捨去
11. `round(double x)` * 四捨五入到「整數位」
12. `lround(double x)` 將四捨五入完的數轉成 $long$
13. `llround(double x)` 將四捨五入完的數轉成 $long long$
14. `fmod(double x, double denum)` 小數取模，`return` 值為正
15. `remainder(double x, double denum)` 也是小數取模，`return` 值有可能為負
16. `max(double a, double b)` * 取大值
17. `min(double a, double b`) * 取小值
18. `fmax(double a, double b)` 小數用的，`max` 已經 `overload` 過了，沒用
19. `fmin(double a, double b)` 小數用的，`min` 已經 `overload` 過了，沒用
20. `nextafter`
21. `nexttoward`
字元分類和操作函式：
1. `isalpha(char c)` * 是字母
2. `isalnum(char c)` * 是英數字母
3. `isblank(char c)` * 是 ' '、'\t'
4. `iscntrl(char c)` 是控制字元
5. `isdigit(char c)` * 是數字
6. `isgraph(char c)` 不屬於 `iscntrl && isblank`
7. `islower(char c)` * 是小寫字母
8. `isprint(char c)` * 是可印字元，不屬於 `iscntrl`
9. `ispunct(char c)` 是符號
10. `isspace(char c)` * 是 ' '、'\t'、'\n'、'\v'、'\f'
11. `isupper(char c)` * 是大寫字母
12. `isxdigit(char c)` 屬於十六進位中的表示字元
13. `tolower(char c)` * 若為大寫字母轉小寫
14. `toupper(char c)` * 若為小寫字母轉大寫
簡單而言：
```cpp
islower || isupper => isalpha
isalpha || isdigit => isalnum
isalnum || ispunct => isgraph
isgraph || isblank => isprint
```
字串操作函式：簡單介紹，好複雜
1. `strcpy(char *dest, char *src)` * 將 $src$ 複製到 $dest$
2. `strncpy(char *dest, char *sec, size_t n)` * 和上面一樣但有指定大小
3. `strcat`
4. `strncat`
5. `strcmp(char* a, char* b)` * 比較兩個字元陣列，相同為 $0$，不同若前者字典序較後，`return 1`；後者字典序較後，`reutrn -1`
6. `strncmpstrncpy(char *a, char *b, size_t n)` * 和上面一樣但有指定大小
7. `strcoll`
8. `strxfrm`
9. `strlen(char *str)` * 回傳字元陣列大小，且不含 '\0' 字元
10. `strerror`
11. `strchr(char* str, char c)` * 找到最先出現的字元位置，回傳一個字元指標 `char pointer`，找不到回傳空指標 `nullptr`
12. `strrchr(char* str, char c)` * 找到最後出現的字元位置，回傳一個字元指標 `char pointer`，找不到回傳空指標 `nullptr`
13. `strstr(char* str, char *s)` * 找到最先出現的子字串位置，回傳一個指向找到的第一個字母其字元指標 `char pointer`，找不到回傳空指標 `nullptr`
14. `strtok`
15. `strspn`
16. `strcspn`
動態記憶體分配函式：上面都有介紹
1. `malloc` *
2. `calloc` *
3. `realloc` *
4. `free` *
輸出入函式：不介紹，有興趣可以自己查
1. `fopen` *
2. `freopen` *
3. `fclose` *
4. `fread` *
5. `fwrite` *
6. `fgetc` *
7. `fgets` *
8. `fputc` *
9. `fputs` *
10. `getchar` *
11. `putchar` *
12. `puts` *
13. `getc` *
14. `putc` *
15. `ungetc`
16. `ftell`
17. `fseek`
18. `rewind`
19. `clearerr`
20. `feof`
21. `ferror`
22. `perror`
`time_t` 這個型別 `type` 也有，但是他的函式都全都在 `<ctime> / <time.h>` 中定義，只有這個沒什麼用
:::
---
### 傳統二維陣列
他和傳統一維陣列一樣不用 `include` ，初階班也一定教過和用過，這邊也是小提一下就好
#### 宣告：
```cpp
int arr[row][column] = {};
int arr[2][2] = {{1, 2}, {3, 4}};
// 若要初始化不為 0，要用兩層大括號，中間用逗號隔開
int arr[][2] = {{1,2},{3,4},{5,6}};
// 一樣可以第一個中括號不指定大小讓編譯器自行判斷
```
而若用動態二維陣列就是：
```cpp
int **arr; //用法比較複雜，我個人不推薦使用，除非常數真的壓很緊之類的
```
:::info
:::spoiler **11th 進階助教有話說**
若想學二維動態陣列的請自學 (但對你們知道其實**有了 `vector` 就不會有人用動態記憶體配置了**，而且我也沒有用過)，喔然後**自學也是學程式很重要的一部份**，像這位 `Frankie` 學長也是從高一自學到現在才那麼電的，反正最後我想說，
:::spoiler
**幫我開直播** 拿著 照我 師傅確定要拍嗎? **我中了兩槍....** 希望大家 如果我這一次不幸死的話 請大家一定要傳承我的精神一定要傳承我的精神 **啊啊啊啊啊啊啊啊** 請大家照顧我的老婆跟小孩拜託大家 拜託大家還有我的媽媽 拜託大家 **啊啊啊啊啊啊啊啊**
就這樣，祝各位有個美好的一天
如果 `Frankie` 講到這邊，我應該不是躺在床上耍廢就是去溫泉
:::
---
### 傳統多維陣列
就是傳統二維陣列的延伸
#### 宣告：
```cpp
int arr[height][width][length]; // 三維
int arr[A1][A2]...[AN] // N維
```
:::warning
:::spoiler 有沒有多重指標呢？
有的！
```cpp=
int val = 2;
int *arr1 = &val;
int **arr2 = &arr1;
int ***arr3 = &arr2;
int ***cubicarray; // 三維陣列
```
:::
---
### string
實用程度：:star: :star: :star: :star: :star:
大家在初階班應該都已經學過很多，他只要 `#include <iostream>` 就可以使用
但有部份功能需要 `#include <string>` 才能使用 (應該吧？)
其實他和 `vector` 幾乎一模一樣，只是多了以 `operator +` 來串接字符、字串
可以把他當作 `vector <char>` 的加強版
#### 宣告：
```cpp
string s(N, V);
// N 是大小，不加預設為空
// V 是每一格的值，有大小後一定要加
string s(it1, it2);
// it1、it2 是其它以 string 為的迭代器，左閉右開複製到 s 中
string s(str);
string s{str};
string s = str;
// 將整個 str 複製到 s 中
string s = "";
string s = ""s;
string s("");
string s{""};
string s{"", len}; // len 是前面字符串的長度，可不加
// 雙括號中可以直接放想要的字串
注意：若雙括號中有嵌入 '/0' 字符 (空字符)，那會讀到這個字符為止
string s = "ab\0\0cd"; // s = "ab"
string s{"ab\0\0cd", 6}; // s = "ab\0\0cd"
string s = "ab\0\0cd"s; // s = "ab\0\0cd"
// 可以用 {str, len} 或者 operator ""s 來避免這個問題
// operator ""s 回傳值即為 {str, len}
```
#### 複雜度
- 隨機存取快 $O(1)$
- 從尾端增刪元素快 $O(1)$
- 串接兩字串 $O(N)$
- 中間增刪元素極慢 $O(N)$
- find $O(N)$
- clear $O(N)$
- size $O(1)$
- empty $O(1)$
#### 成員函式 and 操作
:::spoiler * 是常用等級
- ***** `operator[]`
- ***** 雖然沒有 `push_front()` 但可以用 `s = "..." + s` 來進行 (`+` 已被 `overload`)
- ***** `pop_back()`
- **** `begin()`
- **** `end()`
- **** `length()`
- *** `back()` 等同 `[s.size() - 1]`
- *** `size()` 等同 `length()`
- *** `clear()` 等同 `s = ""`
- *** `empty()` 等同 `s.size() == 0`
- *** `find`()
- *** `resize()`
- *** `fill()`
- *** `insert()`
- *** `erase()`
- *** `replace()`
- *** `push_back()` 被 `+=` `overload` 了
- *** `append()` 也是被 `+=` `overload`
- ** `front()` 等同 `[0]`
- ** `string::npos`
- ** `rfind()`
- ** `rbegin()`
- ** `rend()`
- ** `substr()`
- ** `compare()` 等同 `!=` ，但回傳值是一個 `sign` 函數，可判斷大小 (- 是小，+ 是大，0 是相等)
- \* `swap()`
- \* `cbegin()`
- \* `cend()`
- \* `at()` 等同 `[]`
- \* `copy()`
- \* `find_first_of()`
- \* `find_last_of()`
- `find_frist_not_of()`
- `find_last_not_of()`
- `crbegin()`
- `crend()`
- `data()`
- `c_str`
- `shrink_to_fit()`
- `emplace()` 很像 `insert`
:::
#### 使用範例
比對兩個字串相同與否
```cpp=
#include <iostream>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
if (s1 == s2)
cout << "The Same\n";
else
cout << "Not The Same\n";
return 0;
}
```
---
### bitset
==**11th** 進階教學覺得很香，可以看看 :poop:==
實用程度： :star:
在標頭檔 `<bitset>` 中定義，他內部已經有 `#include <string>`
他對空間優化極大，相對於 `bool array` 每一格是 `1 byte` 他每一格只占 `1 bit`，是普通陣列的 $\frac{1}{8}$
不過在一些題目中，他對數字的二進位運算非常強大，有優化常數大約 $32$ 倍左右，不無小補
`bitset` 最右方是第 $0$ 格，和平時的陣列相反，請大家注意
#### 宣告：
```cpp
bitset <N> b(s, pos, n);
// N 需要是 constexpr，就是要在編譯期就知道的常數
// 不加括號預設為0
// s 是由 '0'、'1' 所組成的字串
// 後面的括號是從 s 的 pos 到 n
bitset <N> b(u);
bitset <N> b(ull);
// u / ull 是無號整數，N 開不夠的話只保留最後 N 位
```
#### 成員函式 and 操作
:::spoiler * 是常用等級
##### 成員函式
- ***** `operator[]`
- **** `count()` `return` `true` 的數量
- **** `to_string()`
- **** `to_ulong()`
- **** `to_ullong()` **C++11**
- *** `size()`
- *** `flip()` 將每一位都取反
- *** `set()` 將整個設成 $1$
- *** `reset()` 將整個設成 $0$
- ** `all()` 是不是都是 $1$ **C++11**
- ** `any()` 有沒有 $1$
- ** `set(pos, val)` $val$ 不打預設 `true` 將 $pos$ 位設值，等同 `b[pos] = val`
- ** `reset(pos)` 將 $pos$ 位設成 $0$，等同 `set(pos, false)` 和 `b[pos] = 0`
- ** `flip(pos)` 將 $pos$ 位取反，等同 `b[pos] = !b[pos]`
- \* `none()` 是不是沒有 $1$，等同 `!any()`
- \* `test(pos)` 等同 `b[pos]`
##### 操作 (除了輸出、入，都有大量優化過)
- & bitand `(b2 = b & b1)`
- &= and_eq `(b &= b1)`
- | bitor `(b2 = b | b1)`
- |= or_eq `(b |= b1)`
- ^ xor `(b2 = b ^ b1)`
- ^= xor_eq `(b ^= b1)`
- ~ compl `(b = ~b1)`
- \<< leftshift `(b = b1 << 1)`
- \>> rightshift `(b = b1 >> 1)`
- \<<= leftshift_eq `(b <<= 1)`
- \>>= rightshift_eq `(b >>= 1)`
- \>> istream `(cin >> b)`
- \<< ostream `(cout << b)`
:::
#### 使用範例
經典問題：集合之聯集、差集、交集
```cpp=
#include <iostream>
#include <bitset>
using namespace std;
int main() {
bitset <1000> b1, b2;
cin >> b1 >> b2;
cout << (b1 & b2).count() << endl; // 交集
cout << (b1 | b2).count() << endl; // 聯集
cout << (b1 & ~b2).count() << endl; // 差集
return 0;
}
```
---
## STL containers
他全名是 `Standard Template Library containers`，是利用 `template` 的實作，來使每一個容器可以自定義要放入的元素為何，而重點就在於 `< >` 這兩片角括號能不能放多樣型別
### list
實用程度： :star:
在標頭檔 `<list>` 中定義
這難用又跟 `deque` 很像，不過是用分隔的記憶區塊串接的，不支援隨機存取
他所有的出現幾乎都要和 `hash table` 搭配
也就是說，他都要與 `unordered_map` 搭配使用，非常複雜
若真的要用，建議自己使用 `vector <struct>` 來代替他的性質
他用 `double-linked-list` 實作，所以移動刪除都是 `O(1)`
#### 宣告：
```cpp
list <T> l(N, V);
// T 是資料型態
// N 是大小，不加預設為空
// V 是每一格的值，要有大小後才能加，不加預設為空或 0
list <T> l(it1, it2);
// it1、it2 是其它以 list 為基底的容器迭代器，左閉右開複製到 list 中
list <T> l(l2);
list <T> l{l2};
list <T> l = l2;
// 需要和 l 同樣是 list<T> 型別，將整個複製
list <int> l = {1, 2, 3};
list <int> l{1, 2, 3};
// 也可以用傳統陣列的初始化方式來進行
初始化 list 中所有值：
l.assign(V, N);
設定 list 大小：
l.resize(N);
// V 是值，N 是大小
```
#### 複雜度
- 隨機存取極慢，只能遍歷 $O(N)$
- 增刪元素極快 $O(1)$
- 清除 $O(N)$
- size $O(1)$
- empty $O(1)$
:::spoiler * 是常用等級
#### 成員函式
- ***** `push_back()`
- ***** `pop_back()`
- ***** `push_front()`
- ***** `pop_front()`
- ***** `begin()`
- ***** `end()`
- **** `insert()`
- **** `erase()`
- **** `size()`
- **** `clear()`
- **** `front()`
- **** `back()`
- **** `splice()`
- **** `merge()`
- **** `remove()`
- **** `sort()`
- **** `reverse()`
- *** `empty()` 等同 `l.size() == 0`
- *** `assign()`
- *** `resize()`
- *** `emplace_back()` 像 `push_back()`
- *** `emplace_front()` 像 `push_front()`
- *** `emplace()` 像 `insert()`
- ** `rbegin()`
- ** `rend()`
- \* `unique()`
- \* `swap()`
- \* `cbegin()`
- \* `cend()`
- `crbegin()`
- `crend()`
:::
#### 這很麻煩，我不想寫使用範例
---
### forward_list (C++ 11)
:::spoiler 沒有用收起來
實用程度：$0$
在標頭檔 `<forward_list>` 中定義
這更難用，以 `single-linked-list` 實作而成
只能單向操作，顯然用 `vector` 更好，同樣不支援隨機存取，不要用他
==連 `size()` 都沒有是要玩啥==
#### 宣告：
```cpp
forward_list <T> fl(N, V);
// T 是資料型態
// N 是大小，不加預設為空
// V 是每一格的值，要有大小後才能加，不加預設為空或 0
forward_list <T> fl(it1, it2);
// it1、it2 是其它以 list 為基底的容器迭代器，左閉右開複製到 forward_list 中
forward_list <T> fl(fl2);
forward_list <T> fl{fl2};
forward_list <T> fl = fl2;
// 需要和 fl 同樣是 forward_list<T> 型別，將整個複製
forward_list <int> fl = {1, 2, 3};
forward_list <int> fl{1, 2, 3};
// 也可以用傳統陣列的初始化方式來進行
初始化 list 中所有值：
fl.assign(V, N);
設定 list 大小：
fl.resize(N);
// V 是值，N 是大小
```
#### 複雜度
- 隨機存取極慢，只能遍歷 $O(N)$
- 增刪元素極快 $O(1)$
- 清除 $O(N)$
- size $O(1)$
- empty $O(1)$
:::spoiler * 是常用等級
#### 成員函式
- ***** `push_front()`
- ***** `pop_front()`
- ***** `begin()`
- ***** `end()`
- **** `before_begin()`
- **** `insert_after()`
- **** `erase_after()`
- **** `clear()`
- **** `front()`
- **** `splice_after()`
- **** `merge()`
- **** `remove()`
- **** `sort()`
- **** `reverse()`
- **** `empty()`
- *** `assign()`
- *** `resize()`
- ** `emplace_after()` 像 `insert_after()`
- ** `emplace_front()` 像 `push_front()`
- \* `unique()`
- \* `swap()`
- \* `cbegin()`
- \* `cend()`
- \* `cbefore_begin()`
:::
#### 根本沒有用，不需要使用範例
---
### pair
實用程度： :star: :star: :star: :star:
在標頭檔 `<utility>` 中定義
`<algorithm>` 已經有 `#include <utility>`
因此也可以直接 `#include <algorithm>`
但其實自己寫一個 `struct` 可能有時也比 `pair` 更方便，兩者看個人偏好
#### 宣告：
```cpp
pair <T1, T2> p{a, b};
pair <T1，T2> p = {a, b};
pair <T1, T2> p(a, b);
pair <T1, T2> p = make_pair(a, b);
pair <T1, T2> p = {make_pair(a, b)};
// T1、T2 是資料型態
// 後面不打值預設為空或 0
pair <T1, T2> p1{p};
pair <T1，T2> p1 = {p};
pair <T1，T2> p1 = p;
pair <T1, T2> p1(p);
// 直接複製 p 到 p1，兩者資料型態要相同
```
#### 用法
- 用 `make_pair(a, b)` 來構造出一個 `pair` ，直接用 `{a, b}` 呼叫建構元也可以
- first 存取第一項的值
- second 存取第二項的值
#### 使用範例：sort cmp
他常搭配 `sort` 使用，但自定義比較要有 `cmp` 函式，下一章會提到
[傳送門在這](https://hackmd.io/yzwA-2lsTsepbJYTz2ZZWg#cmp-%E8%87%AA%E5%AE%9A%E7%BE%A9%E5%87%BD%E5%BC%8F)
---
### tuple (C++ 11)
:::spoiler 用 `struct` 啦！
實用程度： :star:
在標頭檔 `<tuple>` 中定義
其實要用 `tuple` (元組) 還不如用更多樣性的 `struct` (結構體) 所以常常被取代
#### 宣告：
```cpp
tuple <T1, T2, ..., TN> tpl(v1, v2, ..., vN);
tuple <T1, T2, ..., TN> tpl{v1, v2, ..., vN};
tuple <T1, T2, ..., TN> tpl = make_tuple(v1, v2, ..., vN);
// T1、T2 是資料型態
// 後面不打值預設為空或 0
tuple <T1, T2, ..., TN> tpl1{tpl};
tuple <T1, T2, ..., TN> tpl1 = {tpl};
tuple <T1, T2, ..., TN> tpl1 = tpl;
tuple <T1, T2, ..., TN> tpl1(tpl);
// 直接複製 tpl 到 tpl1，兩者資料型態要相同
```
#### 用法
- 用 `make_tuple(a, b, ...)` 來構造出一個 `tuple` ，直接用 `{a, b, ...}` 呼叫建構元也可以
- `get <x> (tpl)` 來存取第 x - 1 項的參照
- `tuple_element<x,decltype(tpl)>::type` 可以拿到第 x - 1 項的型別
- `tuple_size<decltype(tpl)>::value` 可以拿到 `tuple` 的大小
- 和 `pair` 一樣可以 `sort`
- 成員函式有 `swap()`
- 用全員函式 `tie(a, b, ...)` 可以將元素一一分配到 `tuple` 中
#### 我會直接用 `struct`，沒有使用範例
往後第兩章會提到
[傳送門在這](https://hackmd.io/@FDfrankie/textbook/%2F39vpPSkdRna66NwjcITQag)
:::success
特別的是：`tuple` 中的型別 `type` 可以是 `reference` 參照 (引用)
```cpp
int ref = 10;
tuple <int&> tpl(ref);
// 此時 int& 代表的是 ref 的別稱，也就是參照，當我更改 tpl 的第 1 格時，ref 同時被改動
get <0> (tpl) = 8;
// ref 也變成 8
```
:::
---
### array (C++ 11)
實用程度： :star: :star:
在標頭檔 `<array>` 中定義
他是將一維傳統陣列，以 `STL` 方式實作而成，一樣大小不可變
好處是可以在 `vector` 等其他容器內
#### 宣告：
```cpp
array <T, N> arr = {...T物件};
array <T, N> arr{...T物件};
// T 是資料型態，N 是大小，= 可打可不打
// 若 T 物件不足 N 個，沒指定的都默認是 0
array <T, N> arr = {};
array <T, N> arr{};
array <T, N> arr;
// 不打值預設為 0
要初始化陣列中所有值：
arr.fill(V);
// V 是值
```
#### 成員函式
:::spoiler * 是常用等級
- ***** `operator[]`
- **** `begin()`
- **** `end()`
- **** `fill()`
- *** `size()`
- *** `back()` 等同 `[arr.size() - 1]`
- *** `empty()` 等同 `arr.size() == 0`
- ** `front()` 等同 `[0]`
- ** `rbegin()`
- ** `rend()`
- \* `at()` 等同 `[]`
- \* `swap()`
- \* `cbegin()`
- \* `cend()`
- `crbegin()`
- `crend()`
- `data()`
:::
#### 跟傳統陣列很像，也是 `vector` 的下位版，就不特別介紹了
---
### vector
實用程度： :star: :star: :star: :star: :star:
在標頭檔 `<vector>` 中定義
`vector` 是傳統陣列的加強版，他可變大小，而且支援隨機存取，非常好用
可以直接用他取代傳統陣列，而且他能抓取的記憶體較傳統陣列來得多
#### 宣告：
```cpp
vector <T> vec(N, V);
// T 是資料型態
// N 是大小，不加預設為空
// V 是每一格的值，要有大小後才能加，不加預設為空或 0
vector <T> vec(it1, it2);
// it1、it2 是其它以 vector 為基底的容器迭代器，左閉右開複製到 vector 中
vector <T> vec(vec2);
vector <T> vec{vec2};
vector <T> vec = vec2;
// 需要和 vec 同樣是 vector<T> 型別，將整個複製
vector <int> vec = {1, 2, 3};
vector <int> vec{1, 2, 3};
// 也可以用傳統陣列的初始化方式來進行
初始化 vector 中所有值：
vec.assign(N, V);
設定 vector 大小：
vec.resize(N);
// V 是值，N 是大小
```
#### 複雜度
- 隨機存取快 $O(1)$
- 從尾端增刪元素快 $O(1)$
- 中間增刪元素極慢 $O(N)$
- 清除 $O(N)$
- size $O(1)$
- empty $O(1)$
:::spoiler * 是常用等級
#### 成員函式
- ***** `operator[]`
- ***** `push_back()`
- ***** `pop_back()`
- **** `begin()`
- **** `end()`
- **** `size()`
- **** `clear()`
- *** `empty()` 等同 `vec.size() == 0`
- *** `assign()`
- *** `resize()`
- *** `fill()`
- *** `back()` 等同 `[vec.size() - 1]`
- *** `emplace_back()` 常數較 `push_back()` 來得小一些
- ** `insert()`
- ** `erase()`
- ** `front()` 等同 `[0]`
- ** `rbegin()`
- ** `rend()`
- \* `swap()`
- \* `cbegin()`
- \* `cend()`
- \* `at()` 等同 `[]`
- `crbegin()`
- `crend()`
- `data()`
- `shrink_to_fit()`
- `emplace()` 很像 `insert`
:::
#### 使用範例
由小至大排序一串數字
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, t;
vector <int> vec;
cin >> n;
vec.clear();
for (int i = 0; i < n; i++) {
cin >> t;
vec.push_back(t);
}
sort(vec.begin(), vec.end());
for (int i = 0; i < vec.size(); i++)
cout << vec[i] << ' ';
cout << endl;
return 0;
}
```
### 2D vector
我要把這個單獨拿出來講，這就是 `STL` 包著另一個 `STL` 的例子，也是我們最常碰到的一個
他和傳統二維陣列一樣，只是每一列都是可變陣列 `vector`，而且也可加欄 `column`
十分好用，我們常拿他來建圖，而且有時他可能比傳統二維陣列還要省空間
矩陣運算時，他也可以在函式之間傳遞，不像傳統二維陣列一樣麻煩
[建圖](https://hackmd.io/@FDfrankie/textbook/%2Fcta0PHmaSq67rbnoDbGDEA)
#### 宣告
```cpp
vector < vector<T> > vec(N, vector<T>(K, V));
// T 是資料型態
// 後面的 vector<T> 若不打也是預設此 2D vector 的每一個 vector 為空
// N、K 是大小，不加預設為空
// V 是每一格的值，要有大小後才能加，不加預設為空或 0
初始化 2Dvector 中所有 vector：
vec.assign(N, vector<T>(K, V));
設定 2Dvector 大小：
vec.resize(N);
// V 是值，N K 是大小
```
---
### deque
實用程度： :star: :star: :star: :star: :star:
全名是： `double ended queue` 雙向佇列
在標頭檔 `<deque>` 中定義
`deque` 又是 `vector` 的加強版，他可雙向增刪，非常好用
但要小心他的常數比 `vector` 略高，不過通常題目不會卡這點小東西
#### 宣告：
```cpp
deque <T> dq(N, V);
// T 是資料型態
// N 是大小，不加預設為空
// V 是每一格的值，要有大小後才能加，不加預設為空或 0
deque <T> dq(it1, it2);
// it1、it2 是其它以 deque 為基底的容器迭代器，左閉右開複製到 deque 中
deque <T> dq(dq2);
deque <T> dq{dq2};
deque <T> dq = dq2;
// 需要和 dq 同樣是 deque<T> 型別，將整個複製
deque <int> dq = {1, 2, 3};
deque <int> dq{1, 2, 3};
// 也可以用傳統陣列的初始化方式來進行
初始化 deque 中所有值：
dq.assign(N, V);
設定 deque 大小：
dq.resize(N);
// V 是值，N 是大小
```
#### 複雜度
- 隨機存取快 $O(1)$
- 頭尾增刪元素快 $O(1)$
- 中間增刪元素極慢 $O(N)$
- 清除 $O(N)$
- size $O(1)$
- empty $O(1)$
#### 成員函式
:::spoiler * 是常用等級
- ***** `operator[]`
- ***** `push_back()`
- ***** `push_front()`
- ***** `pop_front()`
- ***** `pop_back()`
- **** `begin()`
- **** `end()`
- **** `size()`
- **** `clear()`
- *** `empty()` 等同 `dq.size() == 0`
- *** `assign()`
- *** `resize()`
- *** `fill()`
- *** `back()` 等同 `[dq.size() - 1]`
- *** `emplace_front()` 常數較 `push_front()` 來得小一些
- *** `emplace_back()` 常數較 `push_back()` 來得小一些
- ** `insert()`
- ** `erase()`
- ** `front()` 等同 `[0]`
- ** `rbegin()`
- ** `rend()`
- \* `swap()`
- \* `cbegin()`
- \* `cend()`
- \* `at()` 等同 `[]`
- `crbegin()`
- `crend()`
- `data()`
- `shrink_to_fit()`
- `emplace()` 很像 `insert`
:::
#### 使用範例
在原本數列中進行以下操作：
1. 前後插入
2. 前後刪除，並將刪除元素輸出 (若陣列為空視為無效操作)
3. 輸出陣列最前方或最後方元素
4. 隨機存取 (若超過陣列大小視為無效操作)
5. 刪除後方元素直到剩 `n` 位 (`n` `<=` 目前陣列大小)
6. 存取陣列大小
```cpp=
#include <iostream>
#include <deque>
using namespace std;
int main() {
int q, n;
string s;
cin >> n;
deque <int> dq(n);
for (int i = 0; i < dq.size(); i++)
cin >> dq[i];
cin >> q;
while (q--) {
cin >> s;
if (s == "push_back") {
cin >> n;
dq.push_back(n); // 插入後方
}
else if (s == "push_front") {
cin >> n;
dq.push_front(n); // 插入前方
}
else if (s == "pop_front" && !dq.empty()) {
cout << dq.front() << endl;
// cout << dq[0] << endl;
dq.pop_front(); // 前方刪除
}
else if (s == "pop_back" && !dq.empty()) {
cout << dq.back() << endl;
// cout << dq[dq.size() - 1] << endl;
dq.pop_back(); // 後方刪除
}
else if (s == "resize") {
cin >> n;
dq.resize(n);
}
else if (s == "at") {
cin >> n;
if (n < dq.size() && n >= 0)
cout << dq[n] << endl;
}
else if (s == "size")
cout << dq.size() << endl;
else if (s == "front" && !dq.empty())
cout << dq.front() << endl; // 前方元素
// cout << dq[0] << endl;
else if (s == "back" && !dq.empty())
cout << dq.back() << endl; // 後方元素
// cout << dq[dq.size() - 1] << endl;
}
return 0;
}
```
---
### stack
實用程度： :star:
中文名是堆疊、棧、堆棧
他的重點就是 `FILO，first in last out` 或 `LIFO，last in first out`
想像一罐洋芋片，一定得從最上面拿起對吧
`DFS` 爆搜常用到概念，但還是被 `vector` 取代
在標頭檔 `<stack>` 中定義
`stack` 是 `vector` 的弱化版，不支援隨機存取，而且還用 `deque` 實作，常數大，不如用 `vector`
:::danger
注意：沒有 `clear()` 喔
清除方式用遍歷
```cpp=
stack <int> sk;
while (!sk.empty()) sk.pop();
// while (sk.size()) sk.pop(); 也可以
```
:::
#### 圖示：
#### 宣告：
```cpp
stack < T, C<T> > sk;
// T 是資料型態
// C<T> 是指以 C<T> 為基底，預設 deque<T>
// C<T> 要能支援 back(), push_back(), pop_back(), empty(), size()，能放 vector, deque, list
stack < T, C<T> > sk(sk2);
stack < T, C<T> > sk{sk2};
// 需要和 sk 同樣以C <T> 為基底的型別，將整個複製
stack < T, C<T> > sk = sk2;
stack < T, C<T> > sk = {sk2};
// 需要同樣是 stack < T, C<T> > 型別，才能將整個複製
stack <int> sk = {1, 2, 3};
stack <int> sk{1, 2, 3};
// 也可以用傳統陣列的初始化方式來進行
```
#### 複雜度
- 棧頂增刪元素 $O(1)$
- 讀取棧頂元素 $O(1)$
- size $O(1)$
- empty $O(1)$
#### 成員函式
:::spoiler * 是常用等級
- ***** `push()`
- ***** `pop()`
- ***** `top()`
- **** `size()`
- *** `empty()` 等同 `sk.size() == 0`
- \* `emplace()` 等同 `push`
- `swap()`
:::
#### 使用範例
支援下列操作：
1. 將元素推入陣列後方
2. 刪除陣列最後方元素，並將其輸出 (若陣列為空視為無效操作)
3. 輸出陣列最後方的值 (若陣列為空視為無效操作)
4. 輸出陣列大小
```cpp=
#include <iostream>
#include <stack>
using namespace std;
int main() {
int t, n;
string s;
cin >> t;
stack <int> sk;
while (t--) {
cin >> s;
if (s == "push") {
cin >> n;
sk.push(n);
}
else if (s == "pop" && !sk.empty()) {
cout << sk.top() << endl;
sk.pop();
}
else if (s == "back" && !sk.empty())
cout << sk.top() << endl;
else if (s == "size")
cout << sk.size() << endl;
}
return 0;
}
```
---
### queue
實用程度： :star: :star:
中文名是 (單向) 佇列
他的重點就是 `FIFO，first in first out` 或 `LILO，last in last out`
想像排隊的隊伍，先到的一定先買東西對吧，但絕對沒有沒品的人插隊！
`BFS` 爆搜常用
在標頭檔 `<queue>` 中定義
`queue` 是 `deque` 的弱化版，不支援隨機存取
`queue` 是用 `deque` 實作的，和 `stack` 一樣
:::warning
其實因為 `queue` 和 `stack` 一樣是用 `deque` 來實作的
因此操作上比直接用 `deque` 還要多了一步，因此可能會慢 `deque` 大概 $10\%$ 左右
不過因為他們可讀性很高，因此寫程式若沒有追求極致速度時，還是會選擇使用他們
順帶一提，不知為何 `stack` 常被 `vector` 取代，但 `queue` 比較少被 `deque` 取代
(所以我才給 `stack` 一星，`queue` 兩星)
:::
:::danger
注意：沒有 `clear()` 喔
清除方式用遍歷
```cpp=
queue <int> q;
while (!q.empty()) q.pop();
// while (q.size()) q.pop(); 也可以
```
:::
#### 圖示：
#### 宣告：
```cpp
queue < T, C<T> > q;
// T 是資料型態
// C<T> 是指以 C<T> 為基底，預設 deque<T>
// C<T> 要能支援 front(), back(), push_back(), pop_front(), empty(), size()，能放 deque, list
queue < T, C<T> > q(q2);
queue < T, C<T> > q{q2};
// 需要和 q 同樣以 C<T> 為底的型別，將整個複製
queue < T, C<T> > q = q2;
queue < T, C<T> > q = {q2};
// 需要同樣是 queue < T, C<T> > 型別，才能將整個複製
queue <T> q{it1, it2}; // C++23，我也是查了才知道，新用法，compiler不夠新會 CE
// it1、it2 是其它以 C<T> 為基底的容器迭代器，左閉右開複製到 queue 中
```
:::danger
不能用 $\{1,\ 2,\ 3\}$ 這種傳統陣列的大括號來初始化喔
:::
#### 複雜度
- 前出後推 $O(1)$
- 讀取頭尾元素 $O(1)$
- size $O(1)$
- empty $O(1)$
#### 成員函式
:::spoiler * 是常用等級
- ***** `push()`
- ***** `pop()`
- ***** `front()`
- **** `back()`
- **** `size()`
- *** `empty()` 等同 `q.size() == 0`
- \* `emplace()` 等同 `push`
- `swap()`
:::
#### 使用範例
支援下列操作：
1. 將元素推入陣列後方
2. 刪除陣列最前方元素，並將其輸出 (若陣列為空視為無效操作)
3. 輸出陣列最後方的值 (若陣列為空視為無效操作)
4. 輸出陣列大小
```cpp=
#include <iostream>
#include <queue>
using namespace std;
int main() {
int t, n;
string s;
cin >> t;
queue <int> q;
while (t--) {
cin >> s;
if (s == "push") {
cin >> n;
q.push(n);
}
else if (s == "pop" && !q.empty()) {
cout << q.front() << endl;
q.pop();
}
else if (s == "back" && !q.empty())
cout << q.back() << endl;
else if (s == "front" && !q.empty())
cout << q.front() << endl;
else if (s == "size")
cout << q.size() << endl;
}
return 0;
}
```
---
### priority_queue
實用程度： :star: :star: :star:
他叫優先佇列，是由一個很猛的東西： `heap` 所實作而成，如果只要求極值非他莫屬
**在標頭檔 `<queue>` 中定義**
~~沒有 <priority_queue> 啦~~
同樣不支援隨機存取
頂端元素預設最大值
若要改成最小值應該在宣告時將 `cmp` 格從預設的 `less<T>` 改成 `greater<T>`
:::danger
注意：沒有 `clear()` 喔
清除方式用遍歷
```cpp=
priority_queue <int> pq;
while (!pq.empty()) pq.pop();
// while (pq.size()) pq.pop(); 也可以
```
:::
#### 宣告：
```cpp
priority_queue <T, C<T>, cmp> pq;
// T 是資料型態
// C<T>、cmp 可以不寫
// C<T> 是指以 C<T> 為基底，預設 vector<T>
// C<T> 要能支援 front(), push_back(), pop_back(), empty(), size()，能放 deque, list
// cmp 是一個 class 或 struct 也可以，C<T> 一定要先寫才有這格，預設 less<T>，他的排序是反向的
// less<T> 在 <functional> 中定義
priority_queue <T> q{it1, it2};
// it1、it2 是同樣裝 T 的容器迭代器，左閉右開丟入 priority_queue 中
priority_queue <T, C<T>, cmp> pq(pq2);
priority_queue <T, C<T>, cmp> pq{pq2};
priority_queue <T, C<T>, cmp> pq = {pq2};
priority_queue <T, C<T>, cmp> pq = pq2;
// 需要和 pq 同樣以 C<T> 為底的型別，而且同樣以 cmp 為基礎作優先排序，將整個複製
priority_queue <T, C<T>, cmp> pq {cmp(),V};
priority_queue <T, C<T>, cmp> pq (cmp(),V);
// cmp() 必打，而且必和 pq 中使用的 cmp 相同，V 是 C<T> 型別
```
#### cmp寫法
:::spoiler 好毒藏起來
用 `operator overloading` 重載小括號，不用 `cmp` 直接重載小於也可以
```cpp=
struct cmp {
bool operator() (const int a, const int b) {
return a > b; //最小值需反向定義，使用 >
}
};
class cmp {
public:
bool operator() (const int a, const int b) {
return a > b; //最小值需反向定義，使用 >
}
};
priority_queue <int, vector<int>, cmp> pq(cmp, v);
/*-----------------------------------------------------------------------*/
bool cmp(const int a, const int b) {return a > b;}
priority_queue <int, vector<int>, decltype(cmp)*> pq(cmp, v);
priority_queue <int, vector<int>, decltype(&cmp)> pq(&cmp, v);
```
:::
#### 複雜度
- 推入、刪除頂端元素 $O(lgN)$
- 讀取頂端元素 $O(1)$
- size $O(1)$
- empty $O(1)$
#### 成員函式
:::spoiler * 是常用等級
- ***** `push()`
- ***** `pop()`
- ***** `top()`
- **** `size()`
- *** `empty()` 等同 `pq.size() == 0`
- \* `emplace()` 等同 `push`
- `swap()`
:::
#### 使用範例
達成以下操作：
1. 將元素加入陣列中
2. 輸出陣列中最大值 (若陣列為空視為無效操作)
3. 輸出陣列最大值並將其刪除 (若陣列為空視為無效操作)
4. 輸出陣列大小
```cpp=
#include <iostream>
#include <queue>
using namespace std;
int main() {
int t, n;
string s;
priority_queue <int> pq;
cin >> t;
while (t--) {
cin >> s;
if (s == "push") {
cin >> n;
pq.push(n);
}
else if (s == "pop" && !pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
else if (s == "top" && !pq.empty())
cout << pq.top() << endl;
else if (s == "size")
cout << pq.size() << endl;
}
return 0;
}
```
---
### set
實用程度： :star: :star: :star:
因為和 `map` 功能相同，因此很常被 `map` 取代
詳細的留到 `map` 說明
在標頭檔 `<set>` 中定義，不支援隨機存取
==**常數極大！！慎用！**==
#### 宣告：
```cpp
set <T, cmp> st;
// T 是資料型態
// cmp 是一個 class，struct 也可以，預設 less<T>
// less<T> 在 <functional> 中定義
set <T> st{it1, it2};
set <T> st = {it1, it2};
// it1、it2 是同樣裝 T 的容器迭代器，左閉右開丟入 set 中
// 但好像不能有 cmp 要不然會 RE，我不知道為何
set <int> st = {1, 2, 3};
set <int> st{1, 2, 3};
// 也可以用傳統陣列的初始化方式來進行
// 但好像不能有 cmp 要不然會 RE，我不知道為何
set <T, cmp> st(st2);
set <T, cmp> st{st2};
set <T, cmp> st = {st2};
set <T, cmp> st = st2;
// 需要裝 T，而且同樣以 cmp 為基礎作優先排序，將整個複製
```
#### cmp寫法
:::spoiler 好毒藏起來
用 `operator overloading` 重載小括號，不用 `cmp` 直接重載小於也可以
```cpp=
struct cmp {
bool operator() (const int a, const int b) {
return a < b;
}
};
class cmp {
public:
bool operator() (const int a, const int b) {
return a < b;
}
};
set <int, cmp> st(v.begin(), v.end());
/*-----------------------------------------------------------------------*/
bool cmp(const int a, const int b) {return a > b;}
set <int, decltype(cmp)*> st(v.begin(), v.end());
set <int, decltype(&cmp)> st(v.begin(), v.end());
```
:::
#### 複雜度
- 插入、刪除元素 $O(lgN)$
- 二分搜 $O(lgN)$
- size $O(1)$
- empty $O(1)$
#### 成員函式
:::spoiler * 是常用等級
- ***** `insert()`
- **** `erase()`
- **** `begin()`
- **** `end()`
- **** `size()`
- **** `find()`
- **** `lower_bound()`
- **** `upper_bound()`
- *** `count()` 在 `set` 中等同 `find(key) != st.end()`
- *** `empty()` 等同 `st.size() == 0`
- *** `clear()`
- ** `rbegin()`
- ** `rend()`
- \* `equal_range()`
- \* `emplace()` 很像 `insert`
- \* `cbegin()`
- \* `cend()`
- `crbegin()`
- `crend()`
- `swap()`
:::
#### 使用範例
陣列中不能有重複元素，若重複加入則視為無效操作
刪除不存在的元素亦視為無效操作
當查找第一個大於等於或大於目標值時，若目標值大於陣列中最大值，則輸出 `2147483647 (INT_MAX)`
支援下列操作：
1. 輸出最大值、最小值 (若陣列為空視為無效操作)
2. 刪除陣列中元素
3. 在陣列中插入元素
4. 刪除最大、最小值 (若陣列為空視為無效操作)
5. 輸出陣列大小
6. 查尋有無元素，若有，輸出 `true`；否則，輸出 `false`
7. 找到第一個大於等於目標且存在於陣列中的值 (若陣列為空視為無效操作)
8. 找到第一個大於目標且存在於陣列中的值 (若陣列為空視為無效操作)
9. 編歷陣列
```cpp=
#include <iostream>
#include <set>
#include <climits> // INT_MAX
using namespace std;
int main() {
int t, n;
string s;
cin >> t;
set <int> st;
while (t--) {
cin >> s;
if (s == "min" && !st.empty())
cout << *st.begin() << endl; // 最小值
else if (s == "max" && !st.empty()) // 最大值
cout << *st.rbegin() << endl;
else if (s == "erase") {
cin >> n;
st.erase(n);
}
else if (s == "erase_max" && !st.empty()) {
cout << *st.rbegin() << endl;
st.erase(prev(st.end())); // 刪除最大值
// st.erase(st.rbegin().base()) << endl;
}
else if (s == "erase_min" && !st.empty()) {
cout << *st.begin() << endl;
st.erase(st.begin()); // 刪除最小值
}
else if (s == "insert") {
cin >> n;
st.insert(n);
}
else if (s == "size")
cout << st.size() << endl;
else if (s == "find") {
cin >> n;
cout << st.count(n) << endl;
/*if (st.find(n) == st.end())
cout << "false\n";
else
cout << "true\n";*/
}
else if (s == "lower_bound") {
cin >> n;
auto it = st.lower_bound(n);
// set<int>::iterator = st.lower_bound(n);
if (it == st.end())
cout << INT_MAX << endl;
else
cout << *it << endl;
// 第一個大於等於 n 的值
}
else if (s == "upper_bound") {
cin >> n;
auto it = st.upper_bound(n);
// set<int>::iterator = st.upper_bound(n);
if (it == st.end())
cout << INT_MAX << endl;
else
cout << *it << endl;
// 第一個大於 n 的值
}
else if (s == "traversal") {
for (int i:st)
cout << i << endl;
/* for (auto it = st.begin(); it != st.end(); it++)
cout << *it << endl;*/
/* for (set<int>::iterator it = st.begin(); it != st.end(); it++)
cout << *it << endl;*/
// it++ 等價於 it = next(it);
}
}
return 0;
}
```
---
### map
實用程度： :star: :star: :star: :star:
在標頭檔 `<map>` 中定義，不支援隨機存取，只能以遍歷方式來走訪每一個節點
不論 `set` 還是 `map` 都是用紅黑邊樹來實作，紅黑邊樹是一個自平衡二元樹
相較於 `set` 只有 `key` ，`map` 是由一對 `key, value` 所組成
他不像 `vector` 等容器一般是連續記憶體，他的記憶體是跳著的，因此不能隨機存取
==**常數極大！！慎用！！**==
因為紅黑邊樹是自平衡二元樹，大家可以去看，他和 `AVL tree` 一樣都是以自旋 `rotate` 的方式來維護他的規則，因此，旋轉的次數、指標的操作都是增加常數的元凶
>key：鍵值 (在 `set`、`map` 中唯一)
>value: 值 (每一個 `key` 所對應到的值)
#### 宣告：
```cpp
map <T1, T2, cmp> m;
// T1 是 key 的資料型態，T2 是 value 的資料型態
// cmp 是一個 class，struct 也可以，預設 less<T>
// less<T> 在 <functional> 中定義
map <T1, T2> m{it1, it2};
map <T1, T2> m = {it1, it2};
// it1、it2 是同樣裝 pair<T1, T2> 的容器迭代器，左閉右開丟入 map 中
// 但好像不能有 cmp 要不然會 RE ，我不知道為何
map <int, int> m = {{1, 2},{3, 4}};
map <int, int> m{{1, 2},{3, 4}};
// 也可以用傳統二維陣列的初始化方式來進行
// 但好像不能有 cmp 要不然會 RE，我不知道為何
map <T1, T2, cmp> m(m2);
map <T1, T2, cmp> m{m2};
map <T1, T2, cmp> m = {m2};
map <T1, T2, cmp> m = m2;
// 需要裝 T，而且同樣以 cmp 為基礎作優先排序，將整個複製
```
#### cmp寫法
:::spoiler 好毒藏起來
用 `operator overloading` 重載小括號，不用 `cmp` 直接重載小於也可以
```cpp=
struct cmp {
bool operator() (const int a, const int b) {
return a < b;
}
};
class cmp {
public:
bool operator() (const int a, const int b) {
return a < b;
}
};
map <int, string, cmp> m(v.begin(), v.end());
/*-----------------------------------------------------------------------*/
bool cmp(const int a, const int b) {return a > b;}
map <int, string, decltype(cmp)*> m(v.begin(), v.end());
map <int, string, decltype(&cmp)> m(v.begin(), v.end());
```
:::
#### 複雜度
- 插入、刪除元素 $O(lgN)$
- 二分搜 $O(lgN)$
- size $O(1)$
- empty $O(1)$
#### 成員函式
:::spoiler * 是常用等級
- ***** `operator[]`
- **** `erase()`
- **** `begin()`
- **** `end()`
- **** `size()`
- **** `find()`
- **** `lower_bound()`
- **** `upper_bound()`
- *** `insert()` 等同 `m[key] = value`
- *** `count()` 在 `map` 中等同 `mp.find(key) != mp.end()`
- *** `empty()` 等同 `mp.size() == 0`
- *** `clear()`
- ** `equal_range()`
- ** `rbegin()`
- ** `rend()`
- \* `emplace()` 很像 `insert`
- \* `at()` 和 `[]` 相同
- \* `cbegin()`
- \* `cend()`
- `crbegin()`
- `crend()`
- `swap()`
:::
#### 使用範例
將出現的鍵值對加入 `map` 中
若值已存在，則將鍵值所對應的數加上
若目標大於等於或大於陣列之最大值，則輸出 `2147483647 (INT_MAX)`
註：此 `map` 代表一個編隊，編隊大小即為編號之數量
註：`key` 代表編碼、`val` 代表人數
支援以下操作：
1. 輸出編碼最大值、最小值對應之人數 (若無任何人視為無效操作)
2. 刪除陣列中編碼，代表廢止此編碼之使用，同時輸出此編碼廢止前之人數 (若代碼不存在視為無效操作，並輸出 `-2147483648 (INT_MIN)` )
3. 在陣列中插入編碼 (若存在則將人數累加到此編碼中)
4. 刪除最大編碼、最小編碼 (若無人視為無效操作)
5. 輸出編隊大小
6. 查尋有無此編號，若有，輸出 `true`；否則，輸出 `false`
7. 找到第一個大於等於目標且存在於陣列中的編碼，並輸出人數 (若陣列為空視為無效操作)
8. 找到第一個大於目標且存在於陣列中的編碼，並輸出人數 (若陣列為空視為無效操作)
9. 查尋此編號之對應人數，若無人輸出 $0$
10. 遍歷整個編隊 (輸出編號 人數)
```cpp=
#include <iostream>
#include <map>
#include <climits> // INT_MAX INT_MIN
using namespace std;
int main() {
int t, key, val;
string s;
map <int, int> m;
cin >> t;
while (t--) {
cin >> s;
if (s == "insert") {
cin >> key >> val;
m[key] += val;
/*auto it = m.find(key);
// map<int, int>::iterator it = m.find(key);
if (it == m.end())
m.insert(make_pair(key, val));
else
it->second += val;*/
}
else if (s == "erase") {
cin >> key;
if (m.find(key) == m.end())
cout << INT_MIN << endl;
else {
cout << m[key] << endl;
m.erase(key);
}
}
else if (s == "size")
cout << m.size() << endl;
else if (s == "max" && !m.empty())
cout << m.rbegin()->second << endl; // 最大值
else if (s == "min" && !m.empty())
cout << m.begin()->second << endl; // 最小值
else if (s == "erase_max" && !m.empty())
m.erase(prev(m.end())); // 刪除最大值
// m.erase(m.rbegin().base());
else if (s == "erase_min" && !m.empty())
m.erase(m.begin()); // 刪除最小值
else if (s == "find") {
cin >> key;
auto it = m.find(key);
// map<int, int>::iterator it = m.find(key);
if (it == m.end())
cout << "false\n";
else
cout << "true\n";
}
else if (s == "at") {
cin >> key;
auto it = m.find(key);
if (it == m.end())
cout << 0 << endl;
else
cout << it->second << endl;
// cout << m[key] << endl;
}
else if (s == "lower_bound") {
cin >> key;
auto it = m.lower_bound(key);
// map<int, int>::iterator it = m.lower_bound(key);
if (it == m.end())
cout << INT_MAX << endl;
else
cout << it->second << endl;
}
else if (s == "upper_bound") {
cin >> key;
auto it = m.upper_bound(key);
// map<int, int>::iterator it = m.lower_bound(key);
if (it == m.end())
cout << INT_MAX << endl;
else
cout << it->second << endl;
}
else if (s == "traversal") {
for (auto i:m) // for (pair <const int, int> i:m)
cout << i.first << ' ' << i.second << endl;
/* for (auto it = m.begin(); it != m.end(); it++)
cout << it->first << ' ' << it->second << endl;*/
/* for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
cout << it->first << ' ' << it->second << endl;*/
// it++ 等價於 it = next(it);
}
}
return 0;
}
```
---
### multiset
:::spoiler 這些都是 `map`、`set` 的延伸，想看再打開
實用程度： :star: :star:
**在標頭檔 `<set>` 中定義**
~~沒有 `<multiset>`~~
我用過不超過十次，這要在特定題目中才有用
和 `set` 特性完全相同，只是他的 `key` 可以重覆而已
此時，`count` 所代表的再也不是 $0\ /\ 1$ 的 `int` 而是其中的數量
`eqal_range()` 在這裡也總算是有點用處，提升至 ***
`lower_bound()` 按照他的定義會回傳「第一個」大於等於的位置
`upper_bound()`則回傳「第一個」大於的位置
`find`若找到回傳「最前面」的那一個位置
因此若此時再寫 `mst.erase(K)` 那會變成將 `set` 中所有的 $K$ 全部刪除，若只要刪除一個應該寫：
`mst.erase(mst.find(K))`
#### 宣告
```cpp
multiset <T, cmp> mst;
```
#### 使用範例
**APCS** 有出過這個 `STL container` 的應用
[傳送門在這](https://hackmd.io/FNpFIaqeQ8WFg45mCddZAw#P4)
:::
---
### multimap
:::spoiler 這些都是 `map`、`set` 的延伸，想看再打開
實用程度： $*$ *給小星星* (沒啥大用)
**在標頭檔 `<map>` 中定義**
~~沒有 `<multimap>`~~
我只用過一到兩次，這要在很特定題目中才有用
和 `map` 不一樣的地方就和 `multiset` 一樣，不再贅述
#### 宣告
```cpp
multimap <T1, T2, cmp> mm;
```
:::
---
### unordered_set (C++ 11)
:::spoiler 這些都是 `map`、`set` 的延伸，想看再打開
實用程度： :star: :star:
**在標頭檔 `<unordered_set>` 中定義**
~~跟 `multiset` 不一樣，不是在 `<set>` 喔~~
在不需要排序的情形下才能用這個
比較少用，因為 `set` 題目很少壓這個
用哈希表 `hash table` 實作，而不是紅黑邊樹，因此才在不同標頭檔定義
最差插入、刪除複雜度 $O(n)$ 是因為 `hash table` 建得不太好的原因
有時還可能比基本款還慢呢！
函式比 `set` 再多一點，因為他可以操縱 `hash`，成員函式中有一些專門用來處理 `hash` 的東東
==但要注意：有時候內鍵 `hash` 不支援一些複雜的鍵值型別，例如 `vector < pair<int, int> >`==
==如果寫進去的話會吃 `CE`，這時候就乖乖用回原本的 `set` 或 `map` 吧==
#### 宣告
```cpp
unordered_set <T, Hash, KeyEqual> ust;
// hash 預設用 hash<T>
// KeyEqual 預設用 equal_to<T>
// 兩者都在 <functional> 中定義
```
#### 複雜度
- 插入、刪除 「平均」$O(1)$，最佳 $O(1)$，最差 $O(n)$
- 查詢 $O(1)$，`hash table` 的特性
:::
---
### unordered_map (C++ 11)
:::spoiler 這些都是 `map`、`set` 的延伸，想看再打開
實用程度： :star: :star: :star:
**在標頭檔 `<unordered_map>` 中定義**
~~跟 `multimap` 不一樣，不是在 `<map>` 喔~~
有部份機車題目會壓這個 $O(1)$
和 `map` 不一樣的地方就和 `unordered_set` 一樣，不再贅述
#### 宣告
```cpp
unordered_map <T1, T2, Hash, KeyEqual> um;
// hash 預設用 hash<T1>
// KeyEqual 預設用 equal_to<T1>
// 兩者都在 <functional> 中定義
```
#### 複雜度
- 插入、刪除 「平均」$O(1)$，最佳 $O(1)$，最差 $O(n)$
- 查詢 $O(1)$，`hash table` 的特性
:::
---
### unordered_multiset (C++ 11)
:::spoiler 這些都是 `map`、`set` 的延伸，想看再打開
實用程度： $0$
**在標頭檔 `<unordered_set>` 中定義**
~~跟 `unordered_set` 一樣，不是在 `<set>` ~~
他同樣也是用 `hash table` 來實作，因此在 `<unordered_set>` 中定義
我根本沒用過
:::
---
### unordered_multimap (C++ 11)
:::spoiler 這些都是 `map`、`set` 的延伸，想看再打開
實用程度： $0$
**在標頭檔 `<unordered_map>` 中定義**
~~跟 `unordered_map` 一樣，不是在 `<map>` ~~
他同樣也是用 `hash table` 來實作，因此在 `<unordered_map>` 中定義
我根本沒用過
:::
---
## 題目練習
### 初階班
`string + stringstream`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a092
`vector + pair + cmp`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a582
雖然出現了一個很恐怖的名詞：`discretization` 離散化，但其實就是 `vector + pair + cmp`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a090
`vector + pair + cmp`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a391
`vector + pair + cmp`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a589
`vector + pair + cmp`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a895
`queue + stack + priority_queue`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a891
`map`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a890
### 進階班
`map`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a773
`map`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a349
`set`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a466
`priority_queue`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a319
`stack`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a167
`stack`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a804
`priority_queue`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a811
`bitset`
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a581
練習 -- 複合題型
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a750
練習 -- 複合題型
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a787
練習 -- 複合題型
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a704
練習 -- 複合題型
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a865
練習 -- **APCS** 搭配演算法使用
https://zerojudge.tw/ShowProblem?problemid=j608
---
## 製作者 / 協作者：
> 製作者：
> >
> > [color=#000000] [name= frankie 阮豐翗 (代課)] [time=Sat, Dec 10, 2022 10:37 PM]
> >
> 協作者：
> > [color=#FF0000] [name= 第 11 屆進階助教 chrislaiisme 賴宇弘]
> > [color=#FF0000] [name= 第 11 屆進階教學 william 郭勝威 :poop: ]
> >
> 引用講義：
> > [color=#1E1ED2] [name= 第 11 屆初階教學 samsonjaw 趙炫翔]
> >
> 學長們的講義 (9th)：
> > [color=#FFFF00]https://hackmd.io/@konchin/book/%2FuX4pl05vRpKAgiuR0XHi_g
Sign in with Wallet
