特別感謝「星城數位科技」
由於疫情關係，電腦教室鍵盤暫停使用，請同學改用螢幕小鍵盤或 Remote Mouse
- 下載
- 安裝（管理員密碼：sova）
- 查看 IP
(210.60.35.*)
請注意，「Remote Mouse」是中囯軟體喔．
vector: 動態陣列，可高效地在尾端修改dequelist: 雙向鏈結串列，可高效地任意修改
b031 - Broken Keyboard cont.，這是上次社課最後面提到的例題的加強版，值得一試。
| \ | 二分搜尋樹 | 雜湊表 (C++11↑) |
|---|---|---|
| 單一鍵值 | set, map | unordered_set, unordered_map |
| 多重鍵值 | multiset, multimap |
unordered_multiset, unordered_multimap |
- 將具有相同性質的物件聚集在一起的整體
- 無序性：集合的元素可不考慮其排列的次序
- 互異性：集合中的元素不可重複出現
- 無序性
- 既然集合中元素的各種排列等價，則我們可以定義出一種唯一表示法
- C++ 中預設將 set 由小到大排好
- 互異性
- C++ set 中的元素不會重複出現
- 是一顆自平衡的紅黑樹 (
RB-Tree) - 可以對數時間快速地插入、移除、搜尋
unionintersectiondifferencesymmetric differenceincludes
以上算法其實只要使用前容器有序即可。
b034: Arvin 拉麵店，以 multiset 實作 min-max heap。
TCIRC Judge:
GreenJudge:
ZeroJudge:
這類資料結構有許多不同的別名，像是 map, dictionary, associative array，其中，由最後一個稱呼，我們可以推測，它是一個行為模仿陣列下標操作的容器。
更精準的說，map 是個對應關係。陣列或 vector 都以非負整數作為索引下標，而 map 是可以自訂下標的容器。
因此， map 的元素由兩個部分組成，索引的下標稱之為 key，所對應的資料就是 value。在 C++ 中兩者可以綁在一起變成一個 pair，我們以 .first 存取 key，.second 存取 value。
TCIRC Judge:
ZeroJudge:
- a743: 10420 - List of Conquests
- d492: 10226 - Hardwood species
- b515: 摩斯電碼-商競103
- a135: 12250 - Language Detection
- c012: 10062 - Tell me the frequencies!
- c044: 10008 - What's Cryptanalysis
Policy-based Data Structures 是 gcc 獨有的擴充。mac 上預設的 clang 不支援。大部分 OJ、比賽及檢定都支援。
依據 STL 風格寫成，提供很多神奇的資料結構，俗稱黑魔法。
如同前述，set 其實可以視作 key 為 null 之 map，故 PBDS 不特別提供集合類容器。
標準庫中的 set, map 雖然內部是紅黑樹結構，然而許多功能被封裝起來，而 PBDS 提供的 tree，如 .find_by_order(), .order_of_key() 還有節點的更新等。
雜湊函數並非完美。當不同的 key 經過 hash 得到相同的值，稱為碰撞 (collision)。處理碰撞的方式理論上有三種，常見有兩種：
- collision-chaining 拉表法 (?
- cc_hash_table
- probing 探測法
- gp_hash_table
第三種是「沒有一次 hash 解決不了的事，如果有，那就再 hash 一次」，不過實務上不方便。
題外話，已知雜湊函數則我們可以構造特殊測資針對產生大量碰撞。例如 STL 預設整數雜湊函數是對
126271、107897等質數取模，那如果大量插入這些質數的倍數，就會導致容器效率趨近最差情況。