特別感謝「星城數位科技」
由於疫情關係,電腦教室鍵盤暫停使用,請同學改用螢幕小鍵盤或 Remote Mouse
- 下載
- 安裝(管理員密碼:sova)
- 查看 IP
(210.60.35.*)
請注意,「Remote Mouse」是中囯軟體喔.
vector
: 動態陣列,可高效地在尾端修改deque
list
: 雙向鏈結串列,可高效地任意修改
b031 - Broken Keyboard cont.,這是上次社課最後面提到的例題的加強版,值得一試。
\ | 二分搜尋樹 | 雜湊表 (C++11↑) |
---|---|---|
單一鍵值 | set, map | unordered_set, unordered_map |
多重鍵值 | multiset, multimap |
unordered_multiset, unordered_multimap |
- 將具有相同性質的物件聚集在一起的整體
- 無序性:集合的元素可不考慮其排列的次序
- 互異性:集合中的元素不可重複出現
- 無序性
- 既然集合中元素的各種排列等價,則我們可以定義出一種唯一表示法
- C++ 中預設將 set 由小到大排好
- 互異性
- C++ set 中的元素不會重複出現
- 是一顆自平衡的紅黑樹 (
RB-Tree
) - 可以對數時間快速地插入、移除、搜尋
union
intersection
difference
symmetric difference
includes
以上算法其實只要使用前容器有序即可。
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
等質數取模,那如果大量插入這些質數的倍數,就會導致容器效率趨近最差情況。