map、set 與迭代器

用名字查東西

vector 用編號查：v[3] 是「第 4 格」。可是現實裡你想查的通常是「"pear" 賣多少錢」「"A" 這個頂點連到誰」。名字不是編號，沒辦法當索引用，於是你只剩一條路：從頭一筆一筆比對過去。

那條路有多慢，跑一次就知道：

N=100000，查詢 Q=1000，預期命中 0
vector：命中 0，耗時 [依環境而異] us
unordered_set：命中 0，耗時 [依環境而異] us
本次耗時比：[依環境而異] 倍

map 與 set 提供依鍵查詢的介面。先看資料要保存鍵值還是只有鍵，再看是否需要順序，才能挑選合適的容器。

[編譯失敗]
cell.cpp: In function ‘int main()’:
cell.cpp:5:5: error: ‘map’ was not declared in this scope
    5 |     map<string, int> price;      // 忘了 #include <map>

map<K, V>：一張鍵對值的表

宣告的時候要講清楚兩件事：鍵長什麼樣、值長什麼樣。map<string, int> 就是「用字串查整數」。Python 的 dict 不必先講，因為它同一個容器裡可以塞各種型別；C++ 的容器是同質的，型別在編譯期就釘死。

pair<K, V> 把一個鍵與一個值包成一組，成員名稱是 first 與 second。make_pair(k, v) 會依引數建立這一組資料；獨立使用時應明確引入 <utility>。下面先用它把 "kiwi" 與 60 一起交給 insert。

size = 3
apple 賣 45
有沒有 kiwi？ 1
有沒有 mango？ 0
改價後 apple 賣 50，size 還是 3
刪掉 pear 後 size = 2

count 說 pear 在
find 找到 pear = 30
find 找不到 mango，回傳的是 end()

m[k] 查不到，會自己建一個 與 Python 差最多的一點

Python 的 d["mango"] 查不到會立即丟出 KeyError。C++ 的 m["mango"] 則會靜默插入一筆，再回傳那筆的值；若原意只是查詢，這項改動可能到較後面的結果才被發現。

一開始 size = 1
查 mango：0
查完 size = 2
又查三個之後 size = 4
count 查 durian：0
用 count 查完 size = 4

set<T>：一個「這個我見過沒有」的容器

三個特性，一次到手：不重複、自動排序、查得快。你只要問它「這個在不在」，它不存值。

丟了 5 次，size = 3
走訪：apple kiwi pear
apple 在嗎？ 1
erase 之後還在嗎？ 0，size = 2

兩套實作，同一組介面

map 與 unordered_map 的常用介面相近，但契約不同：map 依比較器維持鍵的次序，unordered_map 依雜湊與相等判定查找鍵。這裡比較介面、順序與查詢成本；使用這些類別不需要先實作內部資料結構。

插入順序      ： kiwi apple durian pear mango guava lychee fig
map 走訪      ： apple durian fig guava kiwi lychee mango pear
unordered_map ： [順序未指定]
桶數 bucket_count = [由實作與目前狀態決定]

走訪： 58:Bob 64:Dee 77:Cid 91:Ann
最低分 58
最高分 91
第一個不低於 70 的： 77

什麼時候用哪個

begin()／end()：所有 STL 容器的共同語言

迭代器是一個「指著容器裡某個位置」的東西，用起來像指標：*it 取值、++it 往前一格、it-> 存取成員。學會這四個符號，vector、set、map、list 就全部會走訪了。

[begin, end)：左閉右開，end() 站在門外

end() 不是最後一個元素，是最後一個元素的再下一格。整個範圍是「含頭、不含尾」， 這種區間叫左閉右開 —— C++ 所有吃一對迭代器的東西（走訪、P5 的範圍建構式、sort）都是這個慣例：

它像指標，但不是指標

對 vector 來說，迭代器的行為特別像指標：連 begin() + i 這種「往後跳 i 格」都支援 （P4 的指標算術），所以 *(v.begin() + 2) 拿到第三個元素。 但別的容器就不行了 —— 差別整理成一句：

*it          = 10
*(begin()+2) = 30
sub          = 20 30
list ++lit   = 20

vector： 31 17 93
set   ： 17 31 93
map   ： apple=45 pear=30 

<algorithm>：把一對迭代器交給現成的演算法

sort、find 這些不是容器的成員函式，你不會寫 v.sort()。它們是 <algorithm> 這個標頭裡的自由函式， 你要做的是把「從哪到哪」用一對迭代器告訴它：sort(v.begin(), v.end()) 的意思是「把 [begin, end) 這一段排好」。 這正是左閉右開慣例的回報 —— 演算法只認得迭代器，不認得容器，所以同一套 find、count 通吃 vector、string、陣列， 一個都不用重寫。

sorted  : 17 17 31 55 93
find 55 : *it = 55，索引 3
find 99 : 找不到，回傳的就是 end()
reversed: 93 55 31 17 17
count 17: 2 次
min/max : 3 / 8

從 it->first 到 auto& [k, v]

map 裡每一筆資料是一組 pair<const K, V>：first 是鍵、second 是值。走訪就是把這些 pair 一組一組拿出來。

auto 與範圍 for：各省下什麼？

語法糖（syntax sugar）讓常見操作有更簡潔的寫法。這裡分成兩件事：auto 讓編譯器從初值推導型別，省下型別名稱；範圍 for 則把 begin()、end()、前進與取元素的步驟包起來，省下走訪的迴圈控制。兩者可以分開使用。

Des Moines
4
Sacramento is the capital of California
Des Moines is the capital of Iowa
Salt Lake City is the capital of Utah
Madison is the capital of Wisconsin

把上面程式的 for 迴圈換成以下寫法。capitals.begin() 回傳 map<string, string>::iterator，因此 auto it 的型別在編譯時就已確定。

再改成範圍 for，直接為每個元素取名 entry。現在存取的是元素本身，使用 entry.first 與 entry.second。

這三種走訪都會印出相同的州名與首府。auto 與範圍 for 從 C++11 就能使用；後面的 auto& [key, value] 則再加上 C++17 的結構化繫結。

auto 不會替你加上 &

map<string, string> 的元素型別是 pair<const string, string>。決定「拿副本還是改原元素」的是宣告中的 &：

所以 for (pair<const string, string> entry : capitals) 能正常印出資料，但 entry.second = "Unknown"; 只會改到副本。要改原本的首府，寫 for (auto& entry : capitals)；完整寫法則是 for (pair<const string, string>& entry : capitals)。只要印出資料時，可用 const auto& 避免複製。

對這個 map，上面的範圍 for 可對照成以下 iterator 寫法。關鍵是每一輪的 auto& entry = *it;；拿掉 &，就會複製目前的元素。

元素中的 first 是 const string，即使使用 auto&，也不能改鍵；second 才是可修改的值。程式裡把迴圈變數命名為 entry，可以清楚區分變數名稱與型別名稱 pair。

再把鍵和值各取一個名字

apple 45 / kiwi 60 / pear 30 /
apple 45 / kiwi 60 / pear 30 /
apple 45 / kiwi 60 / pear 30 /
全部漲五元後：apple=50 kiwi=65 pear=35 

計數、去重、分組

計數、去重與分組都可以用已學過的容器操作組合起來，不需要自己實作容器內部。先看一段完整程式，再比較每個核心敘述會不會新增鍵、會不會改變元素數量。

計數： applex2 figx1 kiwix2 pearx3
去重： 4 種 → apple fig kiwi pear
依長度分組：
  3 個字母： fig
  4 個字母： pear pear kiwi pear kiwi
  5 個字母： apple apple 

Design: Ada Ben (2 people)
Support: Cora (1 people)
Training: (0 people)
departments = 3

兩題確認觀念

P6 速查表

四個容器怎麼選

語法骨架（整段可以直接貼進 notebook）

Python ↔ C++ 對照

四條記得住的規則

延伸閱讀

自我檢測：map、set 與迭代器 隨堂自測 · 6 題

每個選項都有解說：選錯也點開看看為什麼錯。全對之後再往下翻詞彙卡。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m;
    m["pear"] = 30;
    cout << m["mango"] << " ";
    cout << m.count("kiwi") << " ";
    cout << m.size() << endl;
    return 0;
}

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(93); s.insert(17); s.insert(93);
    s.insert(31); s.insert(17);
    cout << s.size() << ": ";
    for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
        cout << *it << " ";
    cout << endl;
    return 0;
}

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    string w[5] = {"b", "a", "b", "c", "b"};
    map<string, int> freq;
    for (int i = 0; i < 5; i++) freq[w[i]]++;
    for (auto& [k, n] : freq) cout << k << n << " ";
    cout << endl;
    return 0;
}

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m;
    m["pear"] = 30;
    map<string, int>::iterator it = m.find("kiwi");
    if (it == m.end()) cout << "miss ";
    else cout << it->second << " ";
    cout << m.size() << endl;
    return 0;
}

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

int main() {
    map<string, vector<string>> adj;
    adj["A"].push_back("B");
    adj["A"].push_back("C");
    adj["B"].push_back("C");
    cout << adj.size() << " ";
    cout << adj["C"].size() << " ";
    cout << adj.size() << endl;
    return 0;
}

關鍵詞彙卡：點卡片翻面

先看正面術語，心中默想定義再翻面對答案；洗牌後再過一輪，直到每張都能不假思索說出來。