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<int> s;
s.insert(3);
s.insert(3);          // 已經有了，不會變多
cout << s.size() << endl;      // 1

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

二、map：鍵 → 值

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

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

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

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

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

這造成兩種真實的錯：

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

所以：

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

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

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

四、unordered_ 版本

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

代價是：

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

完成的樣子

int main() {
    map<string, int> m;
    m["a"] = 1;
    m["b"] = 2;
    cout << m["a"] << endl;
    cout << m.count("c") << endl;
    set<int> s;
    s.insert(3);
    s.insert(3);
    cout << s.size() << endl;
    return 0;
}

換你了

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

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

這一課你做了什麼

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

如果卡住了