set 與 map

「有沒有」和「對應到什麼」，都是 log n。 · ⏱ 約 35 分鐘

你會學到三件事

1. set 存不重複的東西、map 存「鍵 → 值」
2. 兩者都自動排序、查詢都是 O(log n)
3. ⚠️ m["不存在"] 會自己建一個，這是一個坑

開始之前

「這個數出現過嗎？」用 vector 要 O(n) 掃一遍。

n 是 10⁵、又要問 10⁵ 次的話，那是 10¹⁰ 次，超時（第 1 課）。

set 把每次查詢變成 O(log n)，總共 10⁵ × 17 ≈ 10⁶，夠快了。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、set：只管有沒有

set 裡的東西不會重複：

1set<int> s;2s.insert(3);3s.insert(3);          // 已經有了，不會變多4cout << s.size() << endl;      // 1

⚠️ set 是排好序的，所以 for (int x : s) 走出來是由小到大。 這常常剛好是你要的。

積木盤上它們寫著「建立 … 集合 …」「在 … 加入 …」 與「… 中 … 的數量」。

⚠️ 那顆「集合」是一格下拉：把它切成「可重複集合」，同一個值就留得住兩份 （C++ 那側從 set 變成 multiset）。而加入的那一顆對兩種都適用 ——留不留重複是容器的事，不是那個動作的事。

二、map：鍵 → 值

map 用鍵去拿值：

1map<string, int> m;2m["a"] = 1;3m["b"] = 2;4cout << m["a"] << endl;        // 1

用方括號存取，而鍵可以是任何東西：字串、pair、都行。

積木盤上這兩顆寫著「建立對照表 …（鍵 … 值 …）」 與「… 中鍵 … 的值」——map 的中文說法就是「對照表」。

三、🔴 m["不存在"] 會自己建一個

⚠️ 這兩行看起來都只是「問」，而第二行會改變那張表：

1cout << m.count("c") << endl;      // 0   ← 沒有 "c"2cout << m["c"] << endl;            // 0   ← 而【現在有了】3cout << m.size() << endl;          // 3   ← 🔴 多了一個

光是「讀」一個不存在的鍵，就會把它建出來（值是 0）。

這造成兩種真實的錯：

1. 在迴圈裡查詢，map 越查越大 → 記憶體爆掉
2. 「這個鍵有沒有」判斷錯 → 因為查過就有了

所以：

⚠️ 而這個行為也常常剛好是你要的：

1map<string, int> cnt;2for (string w : words) cnt[w]++;      // 🟢 沒見過的自動從 0 開始

計數是它最常見的用法，而那正好靠這個特性。

四、unordered_ 版本

unordered_set / unordered_map 用雜湊，查詢平均 O(1)，比 log n 快。

代價是：

⚠️ 競賽裡有人會故意出資料讓 unordered_map 退化成 O(n)。 不需要順序、而且不是對抗性題目的時候才用它。

積木盤上不必換一顆積木：「建立對照表」那顆的第一格是下拉， 切成「雜湊對照表」就是 unordered_map。 集合那一側同理——「集合」切成「可重複集合」就是 multiset。

⚠️ 而「沒有順序」是真的：unordered_map 走訪的順序 C++ 標準自己都沒有規定， 所以要印出來的時候用 map。

完成的樣子

1#include <iostream>2#include <map>3#include <set>4#include <vector>5using namespace std;6int main() {7    map<string, int> m;8    m["a"] = 1;9    m["b"] = 2;10    cout << m["a"] << endl;11    cout << m.count("c") << endl;12    set<int> s;13    s.insert(3);14    s.insert(3);15    cout << s.size() << endl;16    return 0;17}

換你了

讀一串字，數出每個字出現幾次，由小到大印出來。

（map 自動排序，所以印出來就是排好的，這是選 map 而不是 unordered_map 的理由。）

走訪 map 拿到的每一項是一個 pair，而取它的欄位那顆積木寫著 「結構 … 的欄位 …」——first 是鍵、second 是值。

到編輯器做這一題：練習：數出每個字幾次，由小到大印出來

做一個

兩份名單：ann bob cid 與 bob dan cid。印出同時在兩份裡面的名字。

🔴 用 set 的話這一題是一個迴圈加一次查詢；用 vector 的話是兩層迴圈。 ⚠️ 而輸出自動是排好的，那不是你做的，是 set 的性質。

到編輯器做這一題：做一個：兩份名單的交集

這一課你做了什麼

• 你用 set 存了不重複的東西
• 你用 map 做了鍵到值的對應
• 你知道 m[k] 會建出不存在的鍵，而 count 不會

如果卡住了