Try   HackMD

containers

STL containers == Standard Template Library containers


前言

這是我怕有些初階班剛上進階班對 containers 還不熟,所以才寫了這 \(35000\) 多字的講義 (經過一些增修後超過了 49000 字)
雖然和學長的講義很像,而且可能也沒有比較詳細,但還是加減看一下 :poop:


NOT STL containers

傳統一維陣列

實用程度: :star: :star: :star: :star: :star:

初階班前幾堂就會碰到了,這邊小講一下
使用時不用任何標頭檔,他是你為這一個變量分配一串記憶體

沒學過指標、參照、迭代器但想學的點我


可以看 \(pointer\) 初階班講義 \(by\)\(11\) 屆初階教學 samsonjaw

指標 (pointer, *)

指標是可以存取一個記憶體位置的變數,但說穿了他和 int 之類的一樣是型別
他的宣告方式,在變數名字前加一個 *
要取值的話也是在指標變數前加一個 *
若沒有初始化或被指派,去存取他的值會出問題 (大概率 RE)
因此我們常在宣告時就直接指派一個空指標 nullptr 給他
指標更多的用法是用 new 來分配新的記憶體給他,讓他不用依賴其他變數的記憶體位置

宣告指標
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)
指標使用範例
#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 就是將你給的變數複製一份到新的記憶體位置上再進行運作

宣告指標
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)
參照使用範例
#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
不過注意 stackqueue 沒有支援!
如果用了會吃 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() 就好
使用範例
#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 語言命題)

#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; }
答案點我:
2 8

答對了嗎?因為沒有加 reference,這一題是 call by value,在上面函數內改動的值不會影響到 main 中變數的值
但是很多人會答出 \(2\ 2\)
不過通常 APCS 都是考 C 語言,而非 C++,因此不會有 call by reference 出現

宣告:

int arr[n] = {};
// 基本款,n 是陣列大小
// = {} 可不打,若不打不初始化
// 大括號中沒東西是初始化為 0
// 若大括號中元素數量不足 n 個,那會將元素優先初始化給前面項,沒有初始化到的自動初始化為 0
// 因此可以直接打 {0} 來得到全部初始化為 0 的陣列
int arr[] = {a1, a2, a3, ..., an};
// 可以不指定大小,但後面一定要有初始化
// 大括號中的元素數量即為陣列大小,非不定大小
陣列傳遞

若要傳遞陣列到函式中,要注意用法:

void (int *arr,int len)
void (int arr[], int len)
// 若要傳遞的話不能打出陣列大小,而這裡的 arr[] 相當於 arr*,是傳遞一個位址 address
// 因此需要再傳遞一個變數為 arr 的大小以免溢位

試著將一串 \(0\) 的陣列變成一串 \(1\) 的陣列 (使用 call by pointer)
範例 code

#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

#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; }
毒區退散 若對指標很熟,可以做動態記憶體配置,這樣常數小又抵得上半個 vector

範例程式碼

#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> 即可使用
不用再另外去找原本定義他的標頭檔
這裡的 callocmallocreallocfree 四個函式就是例子
但小心 memset 沒有被定義

在標頭檔 <cstdlib>malloc 函數定義如下:

void *malloc( size_t size )

當我們用完之後,他回傳的是一個 void* 的記憶體位置,我們應該要將他指定為 int* 以避免後面操作時出問題
而要小心的部份是,若沒有成功分配記憶體位置 (過大),則函式會 return 一個空指標
nullptr,而在 C 語言中是 NULL
因此分配完後在不確定的情形下,應該進行檢查:

#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> 標頭檔中

void *memset( void* dest, int ch, std::size_t count )

第一格放要指派的記憶體位置
第二格放指定的數字
最後放大小,而大小是用「字節」(位元組) 為單位,也就是以 byte 為單位
要小心 arr 是一個指標,指標大小為 8 bytes,所以在這形況下不能用 sizeof(arr)
因此我們用 len 去乘上一個位置,也就是 intsize 這樣就可以成功計算所需的記憶體數量
不過 sizeof(arr*) 代表著那一個指標所代表的值記憶體大小,因此可以寫成 sizeof(arr*) * len

註:資料型態占的位元組 (bytes)

  • bool = 1
  • char = 1
  • int = 4
  • float = 4
  • long long = 8
  • double = 8

calloc

同時,這兩個也可以用一個 calloc 函式合併
callocmalloc 不同之處在於 calloc 在分配記憶體位置時會同時將他初始化為 \(0\)
參數的傳入也有所不同,他要求兩個參數,前者為數量,後者則是每格記憶體位置大小
同時他也在 <cstdlib> 函式庫中定義
定義如下:

void *calloc( size_t count, size_t size )

他若沒有成功分配記憶體位置也會回傳空指標 nullptrNULL
以上面的程式碼為例:

#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; }

相當於是

#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\) 種情形
不過因為和我們的應用較沒關係,因此這邊不多做介紹,有興趣可以自己去上網學習

他需要兩個參數,前者是分配的基礎,後者則是分配的記憶體總量

void *realloc( void* dest, std::size_t count )

和上面的兩個 alloc 一樣,都會在記憶體分配失敗時回傳一個空指標 nullptrNULL

程式碼舉例:

#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 中的函式

* 代表我看過的,後面部份我認識的有解釋

數學類函式:

  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) * 若為小寫字母轉大寫

簡單而言:

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 ,初階班也一定教過和用過,這邊也是小提一下就好

宣告:

int arr[row][column] = {};
int arr[2][2] = {{1, 2}, {3, 4}};
// 若要初始化不為 0,要用兩層大括號,中間用逗號隔開
int arr[][2] = {{1,2},{3,4},{5,6}};
// 一樣可以第一個中括號不指定大小讓編譯器自行判斷

而若用動態二維陣列就是:

int **arr; //用法比較複雜,我個人不推薦使用,除非常數真的壓很緊之類的
11th 進階助教有話說

若想學二維動態陣列的請自學 (但對你們知道其實有了 vector 就不會有人用動態記憶體配置了,而且我也沒有用過),喔然後自學也是學程式很重要的一部份,像這位 Frankie 學長也是從高一自學到現在才那麼電的,反正最後我想說,

幫我開直播 拿著 照我 師傅確定要拍嗎? 我中了兩槍 希望大家 如果我這一次不幸死的話 請大家一定要傳承我的精神一定要傳承我的精神 啊啊啊啊啊啊啊啊 請大家照顧我的老婆跟小孩拜託大家 拜託大家還有我的媽媽 拜託大家 啊啊啊啊啊啊啊啊

就這樣,祝各位有個美好的一天
如果 Frankie 講到這邊,我應該不是躺在床上耍廢就是去溫泉


傳統多維陣列

就是傳統二維陣列的延伸

宣告:

int arr[height][width][length]; // 三維
int arr[A1][A2]...[AN] // N維
有沒有多重指標呢?

有的!

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> 的加強版

宣告:

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 操作

* 是常用等級
  • ***** 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

使用範例

比對兩個字串相同與否

#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\) 格,和平時的陣列相反,請大家注意

宣告:

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 操作

* 是常用等級
成員函式
  • ***** 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)

使用範例

經典問題:集合之聯集、差集、交集

#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)

宣告:

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)\)
* 是常用等級

成員函式

  • ***** 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)

沒有用收起來

實用程度:\(0\)

在標頭檔 <forward_list> 中定義
這更難用,以 single-linked-list 實作而成
只能單向操作,顯然用 vector 更好,同樣不支援隨機存取,不要用他

size() 都沒有是要玩啥

宣告:

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)\)
* 是常用等級

成員函式

  • ***** 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 更方便,兩者看個人偏好

宣告:

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 函式,下一章會提到

傳送門在這


tuple (C++ 11)

struct 啦!

實用程度: :star:

在標頭檔 <tuple> 中定義
其實要用 tuple (元組) 還不如用更多樣性的 struct (結構體) 所以常常被取代

宣告:

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,沒有使用範例

往後第兩章會提到

傳送門在這

特別的是:tuple 中的型別 type 可以是 reference 參照 (引用)

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 等其他容器內

宣告:

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 是值

成員函式

* 是常用等級
  • ***** 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 是傳統陣列的加強版,他可變大小,而且支援隨機存取,非常好用
可以直接用他取代傳統陣列,而且他能抓取的記憶體較傳統陣列來得多

宣告:

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)\)
* 是常用等級

成員函式

  • ***** 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

使用範例

由小至大排序一串數字

#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
十分好用,我們常拿他來建圖,而且有時他可能比傳統二維陣列還要省空間
矩陣運算時,他也可以在函式之間傳遞,不像傳統二維陣列一樣麻煩

建圖

宣告

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 略高,不過通常題目不會卡這點小東西

宣告:

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)\)

成員函式

* 是常用等級
  • ***** 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. 存取陣列大小
#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 outLIFO,last in first out
想像一罐洋芋片,一定得從最上面拿起對吧
DFS 爆搜常用到概念,但還是被 vector 取代

在標頭檔 <stack> 中定義
stackvector 的弱化版,不支援隨機存取,而且還用 deque 實作,常數大,不如用 vector

注意:沒有 clear()
清除方式用遍歷

stack <int> sk; while (!sk.empty()) sk.pop(); // while (sk.size()) sk.pop(); 也可以

圖示:

宣告:

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)\)

成員函式

* 是常用等級
  • ***** push()
  • ***** pop()
  • ***** top()
  • **** size()
  • *** empty() 等同 sk.size() == 0
  • * emplace() 等同 push
  • swap()

使用範例

支援下列操作:

  1. 將元素推入陣列後方
  2. 刪除陣列最後方元素,並將其輸出 (若陣列為空視為無效操作)
  3. 輸出陣列最後方的值 (若陣列為空視為無效操作)
  4. 輸出陣列大小
#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 outLILO,last in last out
想像排隊的隊伍,先到的一定先買東西對吧,但絕對沒有沒品的人插隊!
BFS 爆搜常用

在標頭檔 <queue> 中定義
queuedeque 的弱化版,不支援隨機存取
queue 是用 deque 實作的,和 stack 一樣

其實因為 queuestack 一樣是用 deque 來實作的
因此操作上比直接用 deque 還要多了一步,因此可能會慢 deque 大概 \(10\%\) 左右
不過因為他們可讀性很高,因此寫程式若沒有追求極致速度時,還是會選擇使用他們
順帶一提,不知為何 stack 常被 vector 取代,但 queue 比較少被 deque 取代
(所以我才給 stack 一星,queue 兩星)

注意:沒有 clear()
清除方式用遍歷

queue <int> q; while (!q.empty()) q.pop(); // while (q.size()) q.pop(); 也可以

圖示:

宣告:

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 中

不能用 \(\{1,\ 2,\ 3\}\) 這種傳統陣列的大括號來初始化喔

複雜度

  • 前出後推 \(O(1)\)
  • 讀取頭尾元素 \(O(1)\)
  • size \(O(1)\)
  • empty \(O(1)\)

成員函式

* 是常用等級
  • ***** push()
  • ***** pop()
  • ***** front()
  • **** back()
  • **** size()
  • *** empty() 等同 q.size() == 0
  • * emplace() 等同 push
  • swap()

使用範例

支援下列操作:

  1. 將元素推入陣列後方
  2. 刪除陣列最前方元素,並將其輸出 (若陣列為空視為無效操作)
  3. 輸出陣列最後方的值 (若陣列為空視為無效操作)
  4. 輸出陣列大小
#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>

注意:沒有 clear()
清除方式用遍歷

priority_queue <int> pq; while (!pq.empty()) pq.pop(); // while (pq.size()) pq.pop(); 也可以

宣告:

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寫法

好毒藏起來

operator overloading 重載小括號,不用 cmp 直接重載小於也可以

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)\)

成員函式

* 是常用等級
  • ***** push()
  • ***** pop()
  • ***** top()
  • **** size()
  • *** empty() 等同 pq.size() == 0
  • * emplace() 等同 push
  • swap()

使用範例

達成以下操作:

  1. 將元素加入陣列中
  2. 輸出陣列中最大值 (若陣列為空視為無效操作)
  3. 輸出陣列最大值並將其刪除 (若陣列為空視為無效操作)
  4. 輸出陣列大小
#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> 中定義,不支援隨機存取

常數極大!!慎用!

宣告:

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寫法

好毒藏起來

operator overloading 重載小括號,不用 cmp 直接重載小於也可以

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)\)

成員函式

* 是常用等級
  • ***** 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. 編歷陣列
#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 只有 keymap 是由一對 key, value 所組成
他不像 vector 等容器一般是連續記憶體,他的記憶體是跳著的,因此不能隨機存取

常數極大!!慎用!!

因為紅黑邊樹是自平衡二元樹,大家可以去看,他和 AVL tree 一樣都是以自旋 rotate 的方式來維護他的規則,因此,旋轉的次數、指標的操作都是增加常數的元凶

key:鍵值 (在 setmap 中唯一)
value: 值 (每一個 key 所對應到的值)

宣告:

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寫法

好毒藏起來

operator overloading 重載小括號,不用 cmp 直接重載小於也可以

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)\)

成員函式

* 是常用等級
  • ***** 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. 遍歷整個編隊 (輸出編號 人數)
#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

這些都是 mapset 的延伸,想看再打開

實用程度: :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))

宣告

multiset <T, cmp> mst;

使用範例

APCS 有出過這個 STL container 的應用
傳送門在這


multimap

這些都是 mapset 的延伸,想看再打開

實用程度: \(*\) 給小星星 (沒啥大用)

在標頭檔 <map> 中定義
沒有 <multimap>
我只用過一到兩次,這要在很特定題目中才有用
map 不一樣的地方就和 multiset 一樣,不再贅述

宣告

multimap <T1, T2, cmp> mm;

unordered_set (C++ 11)

這些都是 mapset 的延伸,想看再打開

實用程度: :star: :star:

在標頭檔 <unordered_set> 中定義
multiset 不一樣,不是在 <set>
在不需要排序的情形下才能用這個
比較少用,因為 set 題目很少壓這個
用哈希表 hash table 實作,而不是紅黑邊樹,因此才在不同標頭檔定義
最差插入、刪除複雜度 \(O(n)\) 是因為 hash table 建得不太好的原因
有時還可能比基本款還慢呢!
函式比 set 再多一點,因為他可以操縱 hash,成員函式中有一些專門用來處理 hash 的東東

但要注意:有時候內鍵 hash 不支援一些複雜的鍵值型別,例如 vector < pair<int, int> >

如果寫進去的話會吃 CE,這時候就乖乖用回原本的 setmap

宣告

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)

這些都是 mapset 的延伸,想看再打開

實用程度: :star: :star: :star:
在標頭檔 <unordered_map> 中定義
multimap 不一樣,不是在 <map>
有部份機車題目會壓這個 \(O(1)\)
map 不一樣的地方就和 unordered_set 一樣,不再贅述

宣告

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)

這些都是 mapset 的延伸,想看再打開

實用程度: \(0\)

在標頭檔 <unordered_set> 中定義
~~跟 unordered_set 一樣,不是在 <set> ~~
他同樣也是用 hash table 來實作,因此在 <unordered_set> 中定義
我根本沒用過


unordered_multimap (C++ 11)

這些都是 mapset 的延伸,想看再打開

實用程度: \(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


製作者 / 協作者:

製作者:

frankie 阮豐翗 (代課)Sat, Dec 10, 2022 10:37 PM

協作者:

第 11 屆進階助教 chrislaiisme 賴宇弘
第 11 屆進階教學 william 郭勝威 :poop:

引用講義:

第 11 屆初階教學 samsonjaw 趙炫翔

學長們的講義 (9th):

https://hackmd.io/@konchin/book/%2FuX4pl05vRpKAgiuR0XHi_g