一、map 是什么

1
2
#include <map>
map<Key, Value> mp;
  • 键值对（key → value）
  • key 自动有序（默认升序）
  • 底层是红黑树
  • 操作复杂度：O(log n)

二、基本用法

1️⃣ 插入元素

1
2
3
4
5
map<int, int> mp;

mp[1] = 10;
mp[3] = 30;
mp[2] = 20;

⚠️ 用 [] 插入，如果 key 不存在，会自动创建并初始化 value

2️⃣ 访问元素

1
cout << mp[2];   // 20

❗注意：

1
cout << mp[100];   // 不存在，但会创建 key=100，value=0

3️⃣ 判断 key 是否存在（很重要）

❌ 错误写法：

1
if (mp[x])  // 不可靠

✅ 正确写法：

1
if (mp.count(x))  // 返回 0 或 1

或：

1
if (mp.find(x) != mp.end())

4️⃣ 删除元素

1
2
mp.erase(2);          // 按 key 删除
mp.erase(mp.begin()); // 删除迭代器指向的元素

5️⃣ map 的大小

1
int sz = mp.size();

三、遍历 map（必会）

1️⃣ 用迭代器

1
2
3
for (map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) {
    cout << it->first << " " << it->second << endl;
}

2️⃣ 用 range-for（推荐）

1
2
3
for (auto p : mp) {
    cout << p.first << " " << p.second << endl;
}

四、map 的有序性（考试常考）

1
2
3
4
map<int,int> mp;
mp[3] = 30;
mp[1] = 10;
mp[2] = 20;

遍历输出：

1
2
3
1 10
2 20
3 30

👉 自动按 key 从小到大排序

五、常见应用场景

1️⃣ 统计次数（最常用）

1
2
3
4
map<int,int> cnt;
for (int x : a) {
    cnt[x]++;
}

2️⃣ 字符 / 字符串计数

1
2
3
4
map<char,int> cnt;
string s;
cin >> s;
for (char c : s) cnt[c]++;

3️⃣ 映射关系

1
2
3
map<string, int> mp;
mp["apple"] = 5;
mp["banana"] = 3;

六、map vs unordered_map

对比 map unordered_map
是否有序 ✅ 有序 ❌ 无序
底层 红黑树 哈希表
复杂度 O(log n) 平均 O(1)
竞赛安全性 ✅ 稳定 ❌ 可能被卡

👉 竞赛默认用 map，追求速度才用 unordered_map

七、自定义排序（进阶）

key 降序

1
map<int,int, greater<int>> mp;

八、常见坑总结（很重要）

❌ mp[x] 判断存在性
❌ 忘记 map 自动排序
❌ 遍历时 erase 当前迭代器（会崩）

✅ 正确删除写法：

1
2
3
4
5
6
for (auto it = mp.begin(); it != mp.end(); ) {
    if (it->second == 0)
        it = mp.erase(it);
    else
        it++;
}

九、一句话记忆版

map = 有序的键值对容器，自动排序，查找/插入 O(log n)