---

C++ | map 容器详解

在 C++ 标准库中，map 是最常用的关联式容器之一，它以 键值对（key-value） 形式存储数据，并保证按照 键的有序性 自动排序。凭借高效的查找、插入、删除性能以及灵活的接口，map 广泛应用于各种工程项目中。

本文将从基础用法到底层实现，再到常见技巧一次讲清楚。

---

1. map 简介

std::map 是一个 有序关联容器：

• 内部以 红黑树（RB-tree） 存储节点
• 元素为 pair<const Key, T>
• 按 key 自动升序排序（默认使用 <）
• key 唯一，不可重复
• 插入、查询、删除时间复杂度约为 O(log n)

如果需要允许重复 key，使用 std::multimap。

---

2. map 的常用操作

2.1 初始化

map<int, string> m1;

map<int, string> m2 = {
    {1, "apple"},
    {2, "banana"},
    {3, "orange"}
};

map<int, string> m3(m2); // 拷贝构造

---

2.2 插入元素

insert()

m.insert({4, "pear"});

返回值：

auto ret = m.insert({1, "watermelon"});
if(!ret.second) {
    cout << "Key already exists\n";
}

operator[]

m[5] = "grape";  // 若不存在 key=5，则创建

注意：
operator[] 一定会创建一个新元素（默认构造 value），因此查找 key 推荐使用 find()。

---

2.3 查找元素

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

其他查找相关接口：

m.count(key);         // map 中是 0 或 1
m.lower_bound(key);   // 第一个 >= key 的迭代器
m.upper_bound(key);   // 第一个 > key 的迭代器

---

2.4 删除操作

m.erase(2);            // 按 key 删除
m.erase(m.begin());    // 按迭代器删除
m.erase(m.begin(), m.end()); // 范围删除

---

2.5 遍历

for (const auto& p : m) {
    cout << p.first << " -> " << p.second << endl;
}

---

3. map 的底层原理

🚩 关键点：map 底层是 红黑树

红黑树是一种自平衡二叉搜索树，具有：

• O(log n) 的查找与插入性能
• 左右平衡性通过颜色 + 旋转维持
• 元素存储有序

因此 map 的 key 排序是 自动的、实时的。

这也意味着：

• 插入大量随机 key 时性能稳定
• 不适合大批量连续插入（可以考虑 unordered_map）

---

4. map 与 unordered_map 的对比

特性	map（有序）	unordered_map（哈希）
底层结构	红黑树	哈希表
元素顺序	有序	无序
查找/插入	O(log n)	平均 O(1)
内存占用	较大	较小
支持 lower_bound 等接口	✔️	❌
大量数据性能	稳定	在 hash 冲突多时退化

总结：

• 若你需要排序 → map
• 若你只需要最快速度 → unordered_map

---

5. 自定义排序

map 可通过比较函数自定义排序方式：

struct Cmp {
    bool operator()(const int& a, const int& b) const {
        return a > b;  // 降序
    }
};

map<int, string, Cmp> m;

---

6. 自定义结构作为 key

关键：必须定义可比较的 < 运算符。

struct Person {
    int id;
    string name;

    bool operator<(const Person& other) const {
        return id < other.id;
    }
};

map<Person, int> mp;

---

7. map 的常见使用技巧

7.1 使用 operator[] 进行计数

map<string, int> cnt;
cnt[word]++;

7.2 使用 emplace() 避免额外构造

m.emplace(10, "test");

比 insert(make_pair(...)) 更高效。

---

8. 常见坑点总结

坑点	说明
m[key] 会创建新节点	若 key 不存在，会默认构造 value
map 插入效率不如 vector	每次插入都需要树旋转维护平衡
遍历时不能修改 key	key 是 const 数据成员
不要频繁 erase + insert	会导致频繁旋转，建议局部更新

---

9. 实战示例：按频率统计单词

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

int main() {
    map<string, int> freq;
    string word;

    while (cin >> word) {
        freq[word]++;
    }

    for (auto& p : freq) {
        cout << p.first << " : " << p.second << endl;
    }
}

---

10. 小结

内容	结论
map 底层实现	红黑树（自动排序）
key 是否唯一	是
查找/插入复杂度	O(log n)
使用场景	需要排序、需要稳定查找性能

map 是 C++ STL 中最经典、最稳定的关联容器之一，无论在算法题还是工程代码里都非常常见。

---