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++ 中的六種出現情形：

乘法 (a * b)
乘法賦值 (a *= b)
指標宣告 (int *a, *b)
call by address ( void modify(int *arr, const int len) )
取值 get value (指標，pointer ) (cout << *ptr << endl)
取值 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++ 中的六種出現情形：

位元運算 bitand (a & b)
位元 and 賦值 and_eq (a &= b)
邏輯運算 and (a && b)
參照宣告 (int &a, &b)
call by reference ( void modify(int &x, int &y) )
取址 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
不過注意 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() 就好

使用範例




















#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> 即可使用
不用再另外去找原本定義他的標頭檔
這裡的 calloc、malloc、realloc、free 四個函式就是例子
但小心 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 去乘上一個位置，也就是 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> 函式庫中定義
定義如下：

void *calloc( size_t count, size_t size )

他若沒有成功分配記憶體位置也會回傳空指標 nullptr、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;
}

相當於是


















#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 一樣，都會在記憶體分配失敗時回傳一個空指標 nullptr 或 NULL

程式碼舉例：






















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

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

數學類函式：

abs(int x) * 絕對值，但要注意這是 C 語言中 <stdlib.h> 所定義的 abs ，而不是 <math.h> 中定義的，他沒有 overload 浮點數
fabs(double x) 對浮點數取絕對值，有了 <math.h> 就不重要了
pow(double x, double a) * \(x^a\)
sqrt(double x) * 開平方根
exp(double x) * \(e^x\)
log(double x) * 小心這裡的 \(log\) 是自然對數 \(ln\)，也就是 \(log_e\)
log10(double x) * \(log_{10}\) 也就是常用對數 \(log\)
ceil(double x) * 取上界，正數進位，負數捨去小數
floor(double x) * 取下界，正數捨去小數，負數小數變 \(-1\)
trunc(double x) * 將小數捨去
round(double x) * 四捨五入到「整數位」
lround(double x) 將四捨五入完的數轉成 \(long\)
llround(double x) 將四捨五入完的數轉成 \(long long\)
fmod(double x, double denum) 小數取模，return 值為正
remainder(double x, double denum) 也是小數取模，return 值有可能為負
max(double a, double b) * 取大值
min(double a, double b) * 取小值
fmax(double a, double b) 小數用的，max 已經 overload 過了，沒用
fmin(double a, double b) 小數用的，min 已經 overload 過了，沒用
nextafter
nexttoward

字元分類和操作函式：

isalpha(char c) * 是字母
isalnum(char c) * 是英數字母
isblank(char c) * 是 ' '、'\t'
iscntrl(char c) 是控制字元
isdigit(char c) * 是數字
isgraph(char c) 不屬於 iscntrl && isblank
islower(char c) * 是小寫字母
isprint(char c) * 是可印字元，不屬於 iscntrl
ispunct(char c) 是符號
isspace(char c) * 是 ' '、'\t'、'\n'、'\v'、'\f'
isupper(char c) * 是大寫字母
isxdigit(char c) 屬於十六進位中的表示字元
tolower(char c) * 若為大寫字母轉小寫
toupper(char c) * 若為小寫字母轉大寫

簡單而言：

islower || isupper => isalpha
isalpha || isdigit => isalnum
isalnum || ispunct => isgraph
isgraph || isblank => isprint

字串操作函式：簡單介紹，好複雜

strcpy(char *dest, char *src) * 將 \(src\) 複製到 \(dest\)
strncpy(char *dest, char *sec, size_t n) * 和上面一樣但有指定大小
strcat
strncat
strcmp(char* a, char* b) * 比較兩個字元陣列，相同為 \(0\)，不同若前者字典序較後，return 1；後者字典序較後，reutrn -1
strncmpstrncpy(char *a, char *b, size_t n) * 和上面一樣但有指定大小
strcoll
strxfrm
strlen(char *str) * 回傳字元陣列大小，且不含 '\0' 字元
strerror
strchr(char* str, char c) * 找到最先出現的字元位置，回傳一個字元指標 char pointer，找不到回傳空指標 nullptr
strrchr(char* str, char c) * 找到最後出現的字元位置，回傳一個字元指標 char pointer，找不到回傳空指標 nullptr
strstr(char* str, char *s) * 找到最先出現的子字串位置，回傳一個指向找到的第一個字母其字元指標 char pointer，找不到回傳空指標 nullptr
strtok
strspn
strcspn

動態記憶體分配函式：上面都有介紹

malloc *
calloc *
realloc *
free *

輸出入函式：不介紹，有興趣可以自己查

fopen *
freopen *
fclose *
fread *
fwrite *
fgetc *
fgets *
fputc *
fputs *
getchar *
putchar *
puts *
getc *
putc *
ungetc
ftell
fseek
rewind
clearerr
feof
ferror
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

使用範例

在原本數列中進行以下操作：

前後插入
前後刪除，並將刪除元素輸出 (若陣列為空視為無效操作)
輸出陣列最前方或最後方元素
隨機存取 (若超過陣列大小視為無效操作)
刪除後方元素直到剩 n 位 (n <= 目前陣列大小)
存取陣列大小




















































#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

注意：沒有 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()

使用範例

支援下列操作：

將元素推入陣列後方
刪除陣列最後方元素，並將其輸出 (若陣列為空視為無效操作)
輸出陣列最後方的值 (若陣列為空視為無效操作)
輸出陣列大小


























#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 一樣

其實因為 queue 和 stack 一樣是用 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()

使用範例

支援下列操作：

將元素推入陣列後方
刪除陣列最前方元素，並將其輸出 (若陣列為空視為無效操作)
輸出陣列最後方的值 (若陣列為空視為無效操作)
輸出陣列大小




























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

使用範例

達成以下操作：

將元素加入陣列中
輸出陣列中最大值 (若陣列為空視為無效操作)
輸出陣列最大值並將其刪除 (若陣列為空視為無效操作)
輸出陣列大小


























#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)
支援下列操作：

輸出最大值、最小值 (若陣列為空視為無效操作)
刪除陣列中元素
在陣列中插入元素
刪除最大、最小值 (若陣列為空視為無效操作)
輸出陣列大小
查尋有無元素，若有，輸出 true；否則，輸出 false
找到第一個大於等於目標且存在於陣列中的值 (若陣列為空視為無效操作)
找到第一個大於目標且存在於陣列中的值 (若陣列為空視為無效操作)
編歷陣列











































































#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 所對應到的值)

宣告：

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 代表人數
支援以下操作：

輸出編碼最大值、最小值對應之人數 (若無任何人視為無效操作)
刪除陣列中編碼，代表廢止此編碼之使用，同時輸出此編碼廢止前之人數 (若代碼不存在視為無效操作，並輸出 -2147483648 (INT_MIN) )
在陣列中插入編碼 (若存在則將人數累加到此編碼中)
刪除最大編碼、最小編碼 (若無人視為無效操作)
輸出編隊大小
查尋有無此編號，若有，輸出 true；否則，輸出 false
找到第一個大於等於目標且存在於陣列中的編碼，並輸出人數 (若陣列為空視為無效操作)
找到第一個大於目標且存在於陣列中的編碼，並輸出人數 (若陣列為空視為無效操作)
查尋此編號之對應人數，若無人輸出 \(0\)
遍歷整個編隊 (輸出編號人數)


























































































#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

這些都是 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))

宣告

multiset <T, cmp> mst;

使用範例

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

multimap

這些都是 map、set 的延伸，想看再打開

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

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

宣告

multimap <T1, T2, cmp> mm;

unordered_set (C++ 11)

這些都是 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 吧

宣告

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)

這些都是 map、set 的延伸，想看再打開

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

這些都是 map、set 的延伸，想看再打開

實用程度： \(0\)

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

unordered_multimap (C++ 11)

這些都是 map、set 的延伸，想看再打開

實用程度： \(0\)

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

題目練習

初階班

進階班

製作者 / 協作者：

製作者：

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

協作者：

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

引用講義：

第 11 屆初階教學 samsonjaw 趙炫翔

學長們的講義 (9th)：

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

containers

前言

NOT STL containers

傳統一維陣列

指標 (pointer, *)

宣告指標

* 在 C++ 中的六種出現情形：

指標使用範例

參照 (reference, &)

宣告指標

& 在 C++ 中的六種出現情形：

參照使用範例

迭代器 (iterator)

成員函式存取 (. 、 ->)

使用範例

APCS考題範例

宣告：

使用範例

範例程式碼

malloc

memset

calloc

realloc

定義於 iostream 中的函式

傳統二維陣列

宣告：

傳統多維陣列

宣告：

string

宣告：

複雜度

成員函式 and 操作

使用範例

bitset

宣告：

成員函式 and 操作

成員函式

操作 (除了輸出、入，都有大量優化過)

使用範例

STL containers

list

宣告：

複雜度

成員函式

這很麻煩，我不想寫使用範例

forward_list (C++ 11)

宣告：

複雜度

成員函式

根本沒有用，不需要使用範例

pair

宣告：

用法

使用範例：sort cmp

tuple (C++ 11)

宣告：

用法

我會直接用 struct，沒有使用範例

array (C++ 11)

宣告：

成員函式

跟傳統陣列很像，也是 vector 的下位版，就不特別介紹了

vector

宣告：

複雜度

成員函式

使用範例

2D vector

宣告

deque

宣告：

複雜度

成員函式

使用範例

stack

圖示：

宣告：

複雜度

成員函式

使用範例

我會直接用 `struct`，沒有使用範例

跟傳統陣列很像，也是 `vector` 的下位版，就不特別介紹了