C++ STL 入門：map 關聯容器完整指南——構造、插入、查找、刪除與排序

map 概覽

std::map<Key, Value> 是基於紅黑樹實現的有序關聯容器，鍵唯一、按 operator< 自動排序，查找/插入/刪除均為 O(log n)。

1. 構造與基本插入

map<int, string> mp;
// 三種插入方式
mp.insert({1, "one"});                    // C++11 列表初始化
mp.insert(make_pair(2, "two"));           // pair
mp[3] = "three";                          // 下標運算符（若鍵存在則覆蓋）

2. 插入返回值與去重

insert 返回 pair<iterator, bool>，second 指示是否插入成功（鍵已存在則失敗）。operator[] 會覆蓋舊值。

3. 遍歷方式

• 正向迭代器：for (auto it = mp.begin(); it != mp.end(); ++it)
• 反向迭代器：for (auto it = mp.rbegin(); it != mp.rend(); ++it)
• 範圍 for（C++11）：for (const auto& [k, v] : mp)

4. 查找與邊界

auto it = mp.find(2);
if (it != mp.end()) cout << it->second;

auto range = mp.equal_range(2);  // pair
auto it_low = mp.lower_bound(2); // 首個 >= key
auto it_up = mp.upper_bound(2);  // 首個 > key

5. 刪除

mp.erase(2);              // 按鍵刪除，返回刪除數量
mp.erase(it);             // 按迭代器刪除
mp.erase(it1, it2);       // 區間刪除
mp.clear();               // 清空

6. 自定義鍵排序

鍵為類類型時，需重載 operator< 或提供比較函數對象：

struct Student { int id; string name; };
struct Cmp {
    bool operator()(const Student& a, const Student& b) const {
        return a.id < b.id || (a.id == b.id && a.name < b.name);
    }
};
map<Student, int, Cmp> scoreMap;

7. 實用技巧

• mp.emplace(key, val) 原地構造，避免臨時 pair。
• try_emplace（C++17）僅當鍵不存在時構造 value，更高效。
• mp.contains(key)（C++20）替代 find != end。

總結

map 以有序、唯一鍵、對數級操作著稱。掌握其插入語義差異（insert vs []）、迭代器失效規則（僅被刪除元素迭代器失效）與自定義比較，即可高效解決鍵值映射問題。