C++ STL Map 容器完全指南：核心操作、性能特性與最佳實踐

C++ STL Map 容器完全指南：核心操作、性能特性與最佳實踐

std::map 是 C++ 標準庫中基於紅黑樹實現的關聯容器，提供鍵值對（Key-Value）存儲，鍵唯一且自動按鍵排序。本文系統梳理 Map 的特性、構造、增刪改查、遍歷、性能特點及常見陷阱。

核心特性

• 鍵值對存儲：Key 唯一，Value 可重複。
• 自動排序：默認按 std::less<Key> 升序，也可自定義比較函數。
• 對數級性能：查找、插入、刪除均為 O(log n)，n=100萬時最多 ~20 次比較。
• 迭代器穩定：插入/刪除不會使其他元素迭代器失效（被刪除元素除外）。
• Key 不可修改：只能通過刪除舊鍵、插入新鍵來「修改鍵」。

基本用法

頭文件與構造

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

map<int, string> mp;                    // 默認構造
map<int, string, greater<int>> mp_desc; // 降序
map<string, int> mp2 = {{"one",1}, {"two",2}}; // C++11 列表初始化

插入元素

mp[1] = "one";                    // 運算符[]：若鍵不存在會默認構造 Value，再賦值（兩次操作）
mp.insert({2, "two"});            // 推薦：單次操作，避免默認構造開銷
mp.insert(make_pair(3, "three")); // C++98 風格
mp.emplace(4, "four");            // C++11：原地構造，最高效

性能提示：高頻插入優先用 insert/emplace，避免 operator[] 的雙重查找與默認構造。

查找與訪問

auto it = mp.find(2);
if (it != mp.end()) cout << it->second; // 安全查找

// 檢查存在性
if (mp.count(2)) { ... } // 返回 0 或 1

// 訪問（僅當確定存在時）
string s = mp.at(2);       // C++11：不存在拋出異常
string s = mp[2];          // 不存在會插入空 Value

刪除元素

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

遍歷

first;

// C++17 結構化綁定
for (auto &[k, v] : mp) { ... }

進階操作

lower_bound / upper_bound

map<int,int> a{{1,10}}, b{{2,20}};
a.swap(b); // 或 std::swap(a,b)
// a={2,20}, b={1,10}

自定義比較器

函數說明
begin()/end()首/尾迭代器
rbegin()/rend()逆序迭代器
empty()是否為空
size()元素個數
max_size()最大容量
clear()清空
insert()插入
emplace()原地構造插入
erase()刪除
swap()交換內容
find()查找鍵
count()鍵計數(0/1)
lower_bound()首個不小於鍵
upper_bound()首個大於鍵
equal_range()鍵範圍
key_comp()鍵比較函數對象
value_comp()值比較函數對象
get_allocator()分配器


常見陷阱與最佳實踐

不要用 operator[] 只讀查找：會誤插入默認值。用 find 或 count。
遍歷中刪除：it = mp.erase(it) (C++11) 或 mp.erase(it++) (C++98)。
Key 為自定義類型：必須實現 operator< 或提供比較器，且嚴格弱序。
大量數據預知：考慮 reserve（無）或改用 vector+sort+unique 批量構建。
無序需求：改用 unordered_map (O(1) 平均)，但失去有序性。


總結
std::map 是鍵值關聯存儲的首選，紅黑樹保證對數級性能與有序遍歷。掌握 insert/emplace、find、lower_bound、安全遍歷刪除等核心用法，能編寫高效、健壯的 C++ 代碼。