自主學習自編講義

# 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` 以左閉右開為主，請大家不要弄錯 ![](https://i.imgur.com/L3epXfD.png) ##### 成員函式存取 (. 、 ->) 用 `.` 來存取一個物件的成員函式 ( `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 **幫我開直播** 拿著照我師傅確定要拍嗎? **我中了兩槍....** 希望大家如果我這一次不幸死的話請大家一定要傳承我的精神一定要傳承我的精神 **啊啊啊啊啊啊啊啊** 請大家照顧我的老婆跟小孩拜託大家拜託大家還有我的媽媽拜託大家 **啊啊啊啊啊啊啊啊** ![](https://i.imgur.com/i9UPM0R.gif) 就這樣，祝各位有個美好的一天如果 `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(); 也可以 ``` ::: #### 圖示： ![](https://i.imgur.com/LeXikLE.png) #### 宣告： ```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(); 也可以 ``` ::: #### 圖示： ![](https://i.imgur.com/sjUSyd0.png) #### 宣告： ```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

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.