C++笔记——STL map

在 C++ STL 中，map是有序键值对（key-value）关联容器，它的核心特点是键唯一、自动排序、高效查找，是开发中处理映射关系（如字典、配置、索引）最常用的容器之一。

这篇笔记会从核心特性、头文件、常用操作、底层原理、适用场景、避坑指南全面掌握map。

一、map 核心特性（必记）

1. 存储结构：以键值对（pair<key, value>）为单元存储。
2. 键的规则：键（key）唯一不可重复，值（value）可重复。
3. 排序规则：默认按照键（key）升序排序（底层红黑树自动排序）。
4. 访问方式：支持通过键快速访问值（map[key]）。
5. 底层实现：红黑树（平衡二叉搜索树）。
6. 效率：
   • 查找、插入、删除：O(log n)（对数时间，效率极高）。
7. 与 unordered_map 区别：
   • map：有序，底层红黑树，查找 / 插入稳定。
   • unordered_map：无序，底层哈希表，查找更快（O (1)）。

二、必备头文件

使用map必须包含以下头文件：

#include <map> // map 核心头文件 #include <iostream> using namespace std;

三、map 常用操作（完整代码示例）

1. 定义与初始化

map模板参数：map<key类型, value类型>

// 1. 空map map<int, string> m1; // 2. 初始化列表（C++11及以上） map<int, string> m2 = {{1, "张三"}, {2, "李四"}, {3, "王五"}}; // 3. 拷贝初始化 map<int, string> m3(m2);

2. 插入元素（4 种常用方式）

map插入会自动去重、自动排序。

map<int, string> m; // 方式1：[] 赋值（最简单，若键已存在则覆盖值） m[1] = "张三"; m[2] = "李四"; // 方式2：insert + pair（推荐，键已存在则插入失败，不覆盖） m.insert(pair<int, string>(3, "王五")); // 方式3：insert + make_pair（简化版） m.insert(make_pair(4, "赵六")); // 方式4：emplace（C++11，直接构造，效率最高） m.emplace(5, "孙七");

3. 访问元素

map<int, string> m = {{1, "张三"}, {2, "李四"}}; // 方式1：[] 访问（键不存在会自动插入默认值） cout << m[1] << endl; // 输出：张三 // 方式2：at() 访问（键不存在会抛异常，更安全） cout << m.at(2) << endl; // 输出：李四 // 方式3：通过迭代器访问 auto it = m.find(1); if (it != m.end()) { cout << it->first << "：" << it->second << endl; // first=键，second=值 }

4. 查找元素（最常用）

find(key)：找到返回迭代器，没找到返回end()。

map<int, string> m = {{1, "张三"}, {2, "李四"}}; // 查找键为 2 的元素 auto it = m.find(2); if (it != m.end()) { cout << "找到：" << it->second << endl; } else { cout << "未找到" << endl; } // 统计键的个数（map 键唯一，结果只有 0 或 1） cout << m.count(1) << endl; // 输出 1

5. 删除元素

map<int, string> m = {{1, "张三"}, {2, "李四"}, {3, "王五"}}; // 方式1：按键删除 m.erase(2); // 删除键为 2 的元素 // 方式2：按迭代器删除 auto it = m.find(3); m.erase(it); // 方式3：清空所有元素 m.clear();

6. 容量操作

map<int, string> m = {{1, "张三"}, {2, "李四"}}; // 获取元素个数 cout << m.size() << endl; // 输出 2 // 判断是否为空 cout << m.empty() << endl; // 输出 0（false）

7. 遍历元素（3 种方式）

map<int, string> m = {{1, "张三"}, {2, "李四"}, {3, "王五"}}; // 方式1：迭代器遍历 for (auto it = m.begin(); it != m.end(); ++it) { cout << it->first << "：" << it->second << endl; } // 方式2：范围for（最简洁，推荐） for (auto& p : m) { // p 是 pair<int, string> cout << p.first << "：" << p.second << endl; } // 方式3：auto + 结构化绑定（C++17，最优雅） for (auto [key, val] : m) { cout << key << "：" << val << endl; }

8. 自定义排序（改变默认升序）

默认map按键升序，可改为降序：

// 降序 map map<int, string, greater<int>> m = {{1, "张三"}, {2, "李四"}};

四、map 底层原理

map底层是红黑树（一种自平衡二叉搜索树）：

1. 所有元素按照键（key）排序。
2. 插入 / 删除 / 查找都能保持树平衡，效率稳定在O(log n)。
3. 因为是红黑树，迭代器遍历是有序的。

五、适用场景

优先使用map的场景：

1. 需要键值映射（如 ID→姓名、单词→解释、配置项→值）。
2. 需要按键有序遍历。
3. 需要高效查找、插入、删除（百万级数据无压力）。

不建议使用map的场景：

1. 追求极致查找速度 → 用unordered_map（哈希表）。
2. 键允许重复 → 用multimap。

六、常见坑点（避坑指南）

1. 键不能重复：重复插入同一个键，insert 会失败，[] 会覆盖值。
2. [] 访问危险：使用m[key]时，如果key 不存在，会自动插入默认值。
3. 迭代器失效：map插入 / 删除操作，除被删除节点外，其他迭代器都不失效。
4. 排序只看键：map只根据key排序，与 value 无关。
5. 不能修改键：键（it->first）是只读的，修改会破坏红黑树结构。

总结

1. map是有序、键唯一的键值对容器，底层红黑树。
2. 核心操作：[]访问、insert插入、find查找、erase删除。
3. 查找 / 插入 / 删除效率：O(log n)。
4. 适用：需要映射关系 + 有序 + 稳定效率的场景。
5. 与unordered_map互补：有序用map，极速查找用unordered_map。