C++ 關聯容器完整指南：map、set 與無序容器實戰

C++ 標準庫提供 8 種關聯容器，依底層結構分為有序（紅黑樹）與無序（雜湊表）兩大陣營。本文系統整理其分類、核心操作、迭代器特性、鍵值對處理與效能選型指南，助你精準掌握鍵值查找利器。

一、八大關聯容器分類總覽

容器	底層	鍵值關係	鍵唯一性	有序性
map	紅黑樹	Key-Value	唯一	有序
set	紅黑樹	Key = Value	唯一	有序
multimap	紅黑樹	Key-Value	可重複	有序
multiset	紅黑樹	Key = Value	可重複	有序
unordered_map	雜湊表	Key-Value	唯一	無序
unordered_set	雜湊表	Key = Value	唯一	無序
unordered_multimap	雜湊表	Key-Value	可重複	無序
unordered_multiset	雜湊表	Key = Value	可重複	無序

核心概念：map 為關聯陣列，下標為鍵而非整數；set 僅存鍵。有序容器依鍵排序（預設 operator<），無序容器依雜湊值分桶。

二、定義與初始化

1. 列表初始化 (C++11)

std::map<std::string, int> scores = {{"Summer", 80}, {"Seven", 90}, {"Leg", 60}};
std::set<std::string> names = {"Summer", "Seven", "Leg"};

2. 從序列容器建構 (支援範圍建構)

std::vector<int> v;
for (int i = 0; i != 10; ++i) { v.push_back(i); v.push_back(i); } // 0-9 各兩個
std::set<int> iset(v.begin(), v.end());       // size() == 10 (去重)
std::multiset<int> miset(v.begin(), v.end()); // size() == 20 (保留重複)

三、鍵型別要求：嚴格弱序

有序容器要求鍵型別定義比較操作，預設用 operator<，亦可自訂比較函數。比較關係必須滿足嚴格弱序：

1. 非對稱性：k1 < k2 則不可 k2 < k1。
2. 傳遞性：k1 < k2 且 k2 < k3 → k1 < k3。
3. 等價性傳遞：若 !(k1<k2) && !(k2<k1) 則等價；等價關係具傳遞性。

四、pair 與鍵值對操作

std::pair (定義於 <utility>) 封裝兩個異質資料。map 元素型別即為 pair<const Key, Value>。

std::map<std::string, int> scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
std::vector<std::pair<std::string, int>> v;
for (const auto& kv : scores) {
    v.emplace_back(kv.first, kv.second); // 或 pair(kv.first, kv.second)
}
// 輸出：Leg 60  Seven 90  Summer 80 (自動按鍵排序)

五、關聯容器迭代器特性

• map 迭代器解參考得 pair<const Key, Value>，**鍵為 const 不可修改**，值可修改。
• set 迭代器解參考得 const Key，**完全不可修改**。
• 因此不可將關聯容器傳遞給會修改/重排元素的泛型演算法（如 sort、random_shuffle）。

auto it = scores.begin();
++(it->second); // OK: 修改值
// it->first = "New"; // 編譯錯誤：鍵為 const

六、核心操作詳解

1. 新增元素

insert 若鍵已存在則不覆蓋、不報錯、不動作。回傳 pair<iterator, bool>（唯一鍵容器）或單純 iterator（可重複鍵容器）。

// map 四種等價寫法
scores.insert({"CannonFly", 85});
scores.insert(std::make_pair("CannonFly", 85));
scores.insert(std::pair<std::string, int>("CannonFly", 85));
scores.insert(std::map<std::string, int>::value_type("CannonFly", 85));

// 利用回傳值判斷是否插入成功
auto ret = scores.insert({"NewKey", 100});
if (ret.second) { /* 插入成功 */ }
std::cout << ret.first->first << " " << ret.first->second;

2. 刪除元素

scores.erase("Summer");           // 按鍵刪除，回傳刪除筆數
scores.erase(scores.begin());     // 按迭代器刪除
scores.erase(scores.begin(), scores.end()); // 區間刪除

3. 存取與查找

• 下標運算子 operator[]：僅 map/unordered_map 支援。若鍵不存在，預設建構值並插入（可能非預期行為）。
• at(key)：C++11 起提供，鍵不存在拋出 std::out_of_range，較安全。
• find(key)：找到回傳迭代器，否則回傳 end()，不修改容器。
• count(key)：回傳鍵出現次數 (0/1 或 >1 for multi)。
• 範圍查找：lower_bound/upper_bound/equal_range 適用於有序容器，multimap/multiset 查找所有同鍵元素必備。

// 輸出 multiset 中所有 "Summer"
for (auto it = names.lower_bound("Summer"); it != names.upper_bound("Summer"); ++it)
    std::cout << *it << '\n';
// 或
for (auto range = names.equal_range("Summer"); range.first != range.second; ++range.first)
    std::cout << *range.first << '\n';

七、無序容器

底層為雜湊表，查找/插入/刪除平均 O(1)，最壞 O(N)。鍵型別需支援 operator== 並提供雜湊函數 (std::hash<Key> 預設支援內建型別與 string)。迭代順序不確定，但單一執行期間穩定（除非 rehash）。

• 適用：大量資料、頻繁查找、不需有序遍歷。
• 避免：需範圍查詢、有序輸出、鍵型別難定義雜湊函數。

有序/無序容器介面高度一致，通常可直接互換，僅需更換型別名稱與標頭檔。

八、效能選型速查表

| 情境 | 推薦容器 | 理由 | |------|----------|------| | 鍵值對、唯一鍵、需有序遍歷/範圍查詢 | map | 紅黑樹保證 O(log N) 有序 | | 唯一鍵集合、需有序 | set | 同上 | | 允許重複鍵、需有序 | multimap/multiset | 同紅黑樹支援等價鍵 | | 鍵值對、唯一鍵、極致查找速度、不需有序 | unordered_map | 雜湊表平均 O(1) | | 大量資料、自訂型別鍵、能寫好雜湊函數 | unordered_* | 需注意雜湊衝突與 rehash 成本 |

掌握關聯容器的特性與適用場景，能讓你在處理「鍵值查找」、「去重統計」、「頻率計數」等經典問題時，寫出既簡潔又高效的 C++ 程式碼。