STL containers == Standard Template Library containers
這是我怕有些初階班剛上進階班對 containers
還不熟,所以才寫了這 \(35000\) 多字的講義 (經過一些增修後超過了 49000
字)
雖然和學長的講義很像,而且可能也沒有比較詳細,但還是加減看一下 :poop:
實用程度: :star: :star: :star: :star: :star:
初階班前幾堂就會碰到了,這邊小講一下
使用時不用任何標頭檔,他是你為這一個變量分配一串記憶體
可以看 \(pointer\) 初階班講義 \(by\) 第 \(11\) 屆初階教學 samsonjaw
指標是可以存取一個記憶體位置的變數,但說穿了他和 int
之類的一樣是型別
他的宣告方式,在變數名字前加一個 *
要取值的話也是在指標變數前加一個 *
若沒有初始化或被指派,去存取他的值會出問題 (大概率 RE
)
因此我們常在宣告時就直接指派一個空指標 nullptr
給他
指標更多的用法是用 new
來分配新的記憶體給他,讓他不用依賴其他變數的記憶體位置
(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)
有的人又叫他參考、引用,上次 APCS 有考出這個菜鳥殺手
和 pointer
一樣,若要宣告一個參照型別 (reference type)
,在變數名字前加一個 &
而且在宣告時就要初始化他所參照的對象
可以將參照想像成是將要替代的東西取一個別名,兩者指向同一個記憶體位址,而且都可以對其進行存取、修改
而 call by reference
只有 C++ 才有,C 語言只有 call by pointer
call by reference
相較之下方便、好寫很多
參照是直接拿取記憶體位置,因此如果在大量需要呼叫 (\(e.g.\) 遞迴、快速冪) 等程式碼中,若沒有加參考可能會將時間浪費在拷貝數據上,進而導致 TLE
順帶一提,最基本的 call by value
就是將你給的變數複製一份到新的記憶體位置上再進行運作
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)
他跟指標 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()
就好以下程式碼輸出為何? (APCS 考題以 C 語言命題)
答對了嗎?因為沒有加 reference
,這一題是 call by value
,在上面函數內改動的值不會影響到 main
中變數的值
但是很多人會答出 \(2\ 2\)
不過通常 APCS 都是考 C 語言,而非 C++,因此不會有 call by reference
出現
若要傳遞陣列到函式中,要注意用法:
試著將一串 \(0\) 的陣列變成一串 \(1\) 的陣列 (使用 call by pointer
)
範例 code
:
將一串數字進行 bubble sort
vector
:先宣告一個整數指標、所需長度
用 malloc
分配記憶體給他
他是 C 語言時期的產物,因此他也位於 <stdlib.h>
標頭檔中
但許多在 C 語言時期就存在的函式在 C++ 中被寫入 iostream
也就是說,這些函式只要 #include <iostream>
即可使用
不用再另外去找原本定義他的標頭檔
這裡的 calloc
、malloc
、realloc
、free
四個函式就是例子
但小心 memset
沒有被定義
在標頭檔 <cstdlib>
中 malloc
函數定義如下:
當我們用完之後,他回傳的是一個 void*
的記憶體位置,我們應該要將他指定為 int*
以避免後面操作時出問題
而要小心的部份是,若沒有成功分配記憶體位置 (過大),則函式會 return
一個空指標
nullptr
,而在 C 語言中是 NULL
因此分配完後在不確定的情形下,應該進行檢查:
memset
在標頭檔 <cstring>
中定義如下:
同樣是 C 語言時期的產物,因此他也位於 <string.h>
標頭檔中
第一格放要指派的記憶體位置
第二格放指定的數字
最後放大小,而大小是用「字節」(位元組) 為單位,也就是以 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
和 malloc
不同之處在於 calloc
在分配記憶體位置時會同時將他初始化為 \(0\)
參數的傳入也有所不同,他要求兩個參數,前者為數量,後者則是每格記憶體位置大小
同時他也在 <cstdlib>
函式庫中定義
定義如下:
他若沒有成功分配記憶體位置也會回傳空指標 nullptr
、NULL
以上面的程式碼為例:
相當於是
realloc
是針對已分配的記憶體來重行分配
與下面會提到的 resize
相似
和 malloc
不同之處在於他會保留原本已被分配的值
他的處理方式有分為 \(3\) 種情形
不過因為和我們的應用較沒關係,因此這邊不多做介紹,有興趣可以自己去上網學習
他需要兩個參數,前者是分配的基礎,後者則是分配的記憶體總量
和上面的兩個 alloc
一樣,都會在記憶體分配失敗時回傳一個空指標 nullptr
或 NULL
程式碼舉例:
數學類函式:
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)
* 若為小寫字母轉大寫簡單而言:
字串操作函式:簡單介紹,好複雜
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
,初階班也一定教過和用過,這邊也是小提一下就好
而若用動態二維陣列就是:
若想學二維動態陣列的請自學 (但對你們知道其實有了 vector
就不會有人用動態記憶體配置了,而且我也沒有用過),喔然後自學也是學程式很重要的一部份,像這位 Frankie
學長也是從高一自學到現在才那麼電的,反正最後我想說,
幫我開直播 拿著 照我 師傅確定要拍嗎? 我中了兩槍… 希望大家 如果我這一次不幸死的話 請大家一定要傳承我的精神一定要傳承我的精神 啊啊啊啊啊啊啊啊 請大家照顧我的老婆跟小孩拜託大家 拜託大家還有我的媽媽 拜託大家 啊啊啊啊啊啊啊啊
就這樣,祝各位有個美好的一天
如果 Frankie
講到這邊,我應該不是躺在床上耍廢就是去溫泉
就是傳統二維陣列的延伸
有的!
實用程度::star: :star: :star: :star: :star:
大家在初階班應該都已經學過很多,他只要 #include <iostream>
就可以使用
但有部份功能需要 #include <string>
才能使用 (應該吧?)
其實他和 vector
幾乎一模一樣,只是多了以 operator +
來串接字符、字串
可以把他當作 vector <char>
的加強版
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
比對兩個字串相同與否
11th 進階教學覺得很香,可以看看 :poop:
實用程度: :star:
在標頭檔 <bitset>
中定義,他內部已經有 #include <string>
他對空間優化極大,相對於 bool array
每一格是 1 byte
他每一格只占 1 bit
,是普通陣列的 \(\frac{1}{8}\)
不過在一些題目中,他對數字的二進位運算非常強大,有優化常數大約 \(32\) 倍左右,不無小補
bitset
最右方是第 \(0\) 格,和平時的陣列相反,請大家注意
operator[]
count()
return
true
的數量to_string()
to_ulong()
to_ullong()
C++11size()
flip()
將每一位都取反set()
將整個設成 \(1\)reset()
將整個設成 \(0\)all()
是不是都是 \(1\) C++11any()
有沒有 \(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]
(b2 = b & b1)
(b &= b1)
(b2 = b | b1)
(b |= b1)
(b2 = b ^ b1)
(b ^= b1)
(b = ~b1)
(b = b1 << 1)
(b = b1 >> 1)
(b <<= 1)
(b >>= 1)
(cin >> b)
(cout << b)
經典問題:集合之聯集、差集、交集
他全名是 Standard Template Library containers
,是利用 template
的實作,來使每一個容器可以自定義要放入的元素為何,而重點就在於 < >
這兩片角括號能不能放多樣型別
實用程度: :star:
在標頭檔 <list>
中定義
這難用又跟 deque
很像,不過是用分隔的記憶區塊串接的,不支援隨機存取
他所有的出現幾乎都要和 hash table
搭配
也就是說,他都要與 unordered_map
搭配使用,非常複雜
若真的要用,建議自己使用 vector <struct>
來代替他的性質
他用 double-linked-list
實作,所以移動刪除都是 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()
實用程度:\(0\)
在標頭檔 <forward_list>
中定義
這更難用,以 single-linked-list
實作而成
只能單向操作,顯然用 vector
更好,同樣不支援隨機存取,不要用他
連 size()
都沒有是要玩啥
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()
實用程度: :star: :star: :star: :star:
在標頭檔 <utility>
中定義
<algorithm>
已經有 #include <utility>
因此也可以直接 #include <algorithm>
但其實自己寫一個 struct
可能有時也比 pair
更方便,兩者看個人偏好
make_pair(a, b)
來構造出一個 pair
,直接用 {a, b}
呼叫建構元也可以他常搭配 sort
使用,但自定義比較要有 cmp
函式,下一章會提到
struct
啦!實用程度: :star:
在標頭檔 <tuple>
中定義
其實要用 tuple
(元組) 還不如用更多樣性的 struct
(結構體) 所以常常被取代
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
參照 (引用)
實用程度: :star: :star:
在標頭檔 <array>
中定義
他是將一維傳統陣列,以 STL
方式實作而成,一樣大小不可變
好處是可以在 vector
等其他容器內
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
的下位版,就不特別介紹了實用程度: :star: :star: :star: :star: :star:
在標頭檔 <vector>
中定義
vector
是傳統陣列的加強版,他可變大小,而且支援隨機存取,非常好用
可以直接用他取代傳統陣列,而且他能抓取的記憶體較傳統陣列來得多
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
由小至大排序一串數字
我要把這個單獨拿出來講,這就是 STL
包著另一個 STL
的例子,也是我們最常碰到的一個
他和傳統二維陣列一樣,只是每一列都是可變陣列 vector
,而且也可加欄 column
十分好用,我們常拿他來建圖,而且有時他可能比傳統二維陣列還要省空間
矩陣運算時,他也可以在函式之間傳遞,不像傳統二維陣列一樣麻煩
實用程度: :star: :star: :star: :star: :star:
全名是: double ended queue
雙向佇列
在標頭檔 <deque>
中定義
deque
又是 vector
的加強版,他可雙向增刪,非常好用
但要小心他的常數比 vector
略高,不過通常題目不會卡這點小東西
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
<=
目前陣列大小)實用程度: :star:
中文名是堆疊、棧、堆棧
他的重點就是 FILO,first in last out
或 LIFO,last in first out
想像一罐洋芋片,一定得從最上面拿起對吧
DFS
爆搜常用到概念,但還是被 vector
取代
在標頭檔 <stack>
中定義
stack
是 vector
的弱化版,不支援隨機存取,而且還用 deque
實作,常數大,不如用 vector
注意:沒有 clear()
喔
清除方式用遍歷
push()
pop()
top()
size()
empty()
等同 sk.size() == 0
emplace()
等同 push
swap()
支援下列操作:
實用程度: :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()
喔
清除方式用遍歷
不能用 \(\{1,\ 2,\ 3\}\) 這種傳統陣列的大括號來初始化喔
push()
pop()
front()
back()
size()
empty()
等同 q.size() == 0
emplace()
等同 push
swap()
支援下列操作:
實用程度: :star: :star: :star:
他叫優先佇列,是由一個很猛的東西: heap
所實作而成,如果只要求極值非他莫屬
在標頭檔 <queue>
中定義
沒有 <priority_queue> 啦
同樣不支援隨機存取
頂端元素預設最大值
若要改成最小值應該在宣告時將 cmp
格從預設的 less<T>
改成 greater<T>
注意:沒有 clear()
喔
清除方式用遍歷
用 operator overloading
重載小括號,不用 cmp
直接重載小於也可以
push()
pop()
top()
size()
empty()
等同 pq.size() == 0
emplace()
等同 push
swap()
達成以下操作:
實用程度: :star: :star: :star:
因為和 map
功能相同,因此很常被 map
取代
詳細的留到 map
說明
在標頭檔 <set>
中定義,不支援隨機存取
常數極大!!慎用!
用 operator overloading
重載小括號,不用 cmp
直接重載小於也可以
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
實用程度: :star: :star: :star: :star:
在標頭檔 <map>
中定義,不支援隨機存取,只能以遍歷方式來走訪每一個節點
不論 set
還是 map
都是用紅黑邊樹來實作,紅黑邊樹是一個自平衡二元樹
相較於 set
只有 key
,map
是由一對 key, value
所組成
他不像 vector
等容器一般是連續記憶體,他的記憶體是跳著的,因此不能隨機存取
常數極大!!慎用!!
因為紅黑邊樹是自平衡二元樹,大家可以去看,他和 AVL tree
一樣都是以自旋 rotate
的方式來維護他的規則,因此,旋轉的次數、指標的操作都是增加常數的元凶
key:鍵值 (在
set
、map
中唯一)
value: 值 (每一個key
所對應到的值)
用 operator overloading
重載小括號,不用 cmp
直接重載小於也可以
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
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))
APCS 有出過這個 STL container
的應用
傳送門在這
map
、set
的延伸,想看再打開實用程度: \(*\) 給小星星 (沒啥大用)
在標頭檔 <map>
中定義
沒有 <multimap>
我只用過一到兩次,這要在很特定題目中才有用
和 map
不一樣的地方就和 multiset
一樣,不再贅述
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
吧
hash table
的特性map
、set
的延伸,想看再打開實用程度: :star: :star: :star:
在標頭檔 <unordered_map>
中定義
跟 multimap
不一樣,不是在 <map>
喔
有部份機車題目會壓這個 \(O(1)\)
和 map
不一樣的地方就和 unordered_set
一樣,不再贅述
hash table
的特性map
、set
的延伸,想看再打開實用程度: \(0\)
在標頭檔 <unordered_set>
中定義
~~跟 unordered_set
一樣,不是在 <set>
~~
他同樣也是用 hash table
來實作,因此在 <unordered_set>
中定義
我根本沒用過
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
製作者:
frankie 阮豐翗 (代課)Sat, Dec 10, 2022 10:37 PM
協作者:
第 11 屆進階助教 chrislaiisme 賴宇弘
第 11 屆進階教學 william 郭勝威 :poop:引用講義:
第 11 屆初階教學 samsonjaw 趙炫翔
學長們的講義 (9th):