基本模板
#include <map>
#include <string>
std::map<int, std::string> mp; // 鍵 int, 值 string，按鍵升序自動排序
// 等價於 std::map<int, std::string, std::less<int>> mp;
插入元素 (三種方式)
// 1. insert + pair (C++98)
mp.insert(std::make_pair(1, "one"));
mp.insert(std::pair<int,std::string>(2, "two"));
// 2. 下標運算符 [] (會覆蓋同鍵)
mp[3] = "three"; // 不存在則插入，存在則賦值
mp[1] = "ONE"; // 覆蓋 key=1 的值
// 3. emplace / emplace_hint (C++11 原地構造，避免拷貝)
mp.emplace(4, "four");
mp.emplace_hint(mp.end(), 5, "five"); // 提示插入位置，若正確可達 O(1)
迭代器與遍歷
" << val << '\n';
}
// 反向遍歷
for (auto it = mp.rbegin(); it != mp.rend(); ++it)
std::cout << it->first << " -> " << it->second << '\n';
// 經典迭代器 (C++98)
for (std::map<int,std::string>::const_iterator it = mp.begin(); it != mp.end(); ++it)
std::cout << it->first << " -> " << it->second << '\n';
查找與存在性判斷
second << '\n';
// count: 返回 0 或 1 (map 鍵唯一)
if (mp.count(3)) std::cout << "Exists\n";
// C++20 contains (僅判斷存在)
if (mp.contains(3)) std::cout << "Exists (C++20)\n";
// lower_bound / upper_bound / equal_range (利用有序性)
auto range = mp.equal_range(3); // pair
for (auto it = range.first; it != range.second; ++it) ...
邊界與特殊值
- `mp.begin()`：指向**最小鍵**元素。
- `mp.end()`：指向**最後一個元素之後**的「過去尾」位置，**不可解引用**。
- 空 map：`begin() == end()`。
- `mp.rbegin()` / `mp.rend()`：反向迭代器，對應最大鍵到最小鍵。
刪除元素
size_t n = mp.size(); // 元素個數
bool empty = mp.empty(); // 是否為空
mp.swap(other_map); // 交換內容 (O(1))
auto cmp = mp.key_comp(); // 獲取比較仿函數 (默認 std::less)
map vs unordered_map 快速選擇
| 需求 | 選擇 |
|---|
| 需要鍵有序遍歷、區間查詢、lower_bound | map |
| 純點查找/插入/刪除，極致速度，無序無所謂 | unordered_map |
| 鍵類型只有 operator<，無現成哈希 | map |
| 數據量極小 (≤50)，代碼簡潔優先 | map |
總結
`std::map` 是 **有序關聯容器**，紅黑樹實現，保證 O(log n) 增刪改查，鍵自動排序。掌握 `insert/emplace`、`[]`、`find/count`、`begin/end`、`erase` 核心操作，配合 C++17 結構化綁定 `for (auto& [k,v] : mp)`，即可高效處理鍵值映射問題。
