map

在ICPC算法竞赛中，映射（Map）是存储键值对（key-value）的核心容器，实现从键到值的一一映射，专门解决「键范围过大、键不是整数」无法用数组计数/存储的场景。C++ STL提供两类主流映射容器：

std::map：有序映射，底层红黑树实现，所有操作稳定 O(log n)，支持有序查询
std::unordered_map：无序哈希映射，底层哈希表实现，平均 O(1)，极端数据会退化

一、std::map（有序映射）

1. 基础准备

头文件：#include <map>
命名空间：std，竞赛通常配合 using namespace std; 使用
核心特性：键（key）唯一且自动按升序排序，底层为红黑树，所有操作时间复杂度稳定为 O(log n)

2. 定义与初始化

map<int, int> mp;                // 键为int，值为int
map<string, int> str_cnt;        // 字符串映射到整数（单词计数）
map<pair<int,int>, bool> vis;    // pair作为键（坐标标记、状态去重）
map<int, vector<int>> adj;       // 值为vector（存图、邻接表）

注意：map 的键必须支持小于比较。内置类型、pair、tuple 可直接作为键；自定义结构体作为键需要重载 < 运算符。

3. 核心常用操作

操作	作用	关键注意事项
`mp[key] = val`	插入/覆盖键值对	若key不存在，会自动插入默认值（如int为0）再赋值
`mp[key]++`	键对应的值+1	计数场景常用，不存在则默认从0开始+1
`mp.insert({key, val})`	插入键值对	若key已存在则插入失败，不会覆盖原值
`mp.emplace(key, val)`	原地构造插入	C++11引入，避免临时对象拷贝，性能略优
`mp.erase(key)`	按键删除元素	返回删除的元素个数（0或1）
`mp.erase(it)`	按迭代器删除	返回下一个迭代器（C++11起）
`mp.find(key)`	查找键	找到返回对应迭代器，找不到返回 `mp.end()`
`mp.count(key)`	统计键的个数	返回0或1（键唯一），用于快速判断键是否存在
`mp.size()`	返回键值对数量	返回 `size_t` 无符号类型
`mp.empty()`	判断是否为空	返回bool
`mp.clear()`	清空所有元素	O(n) 时间，栈没有该方法，但map有

⚠️ 最高频坑点：`[]` 运算符的副作用

[] 访问不存在的键时，会自动向map中插入该键并赋予默认值，这是竞赛中最容易导致WA/MLE的隐蔽错误。

// 错误写法：纯判断时用[]，会凭空插入元素
if (mp[x] == 5) { ... } // 若x不存在，map会插入(x, 0)，改变map大小

// 正确写法1：仅判断存在性
if (mp.count(x)) { ... }

// 正确写法2：取值+判断，只查找一次
auto it = mp.find(x);
if (it != mp.end()) {
    int val = it->second; // 通过迭代器取值
}

总结：写入/计数场景放心用[]，纯查找场景用find/count。

4. 有序性专属操作（竞赛高频）

map 因为有序，支持二分查找类操作，这是 unordered_map 不具备的核心优势。 - mp.lower_bound(key)：返回第一个键 ≥ key 的迭代器 - mp.upper_bound(key)：返回第一个键 > key 的迭代器

典型应用：找大于等于x的最小键、区间查询。

5. 遍历方式

map遍历结果默认按键升序排列，迭代器指向 pair<const Key, T>，first 是键，second 是值。

// 方式1：迭代器遍历
for (auto it = mp.begin(); it != mp.end(); ++it) {
    int key = it->first;
    int val = it->second;
}

// 方式2：范围for（C++11）
for (auto &p : mp) {
    int key = p.first;
    int val = p.second;
}

// 方式3：结构化绑定（C++17，竞赛推荐，写法最简洁）
for (auto &[k, v] : mp) {
    // 直接使用k和v
}

二、std::unordered_map（无序哈希映射）

1. 核心特性

头文件：#include <unordered_map>
底层：哈希表（散列表），键无序存储
时间复杂度：平均 O(1)，极端哈希冲突下退化为 O(n)
操作接口：和 map 基本一致（增删查、size/empty/clear等）
不支持：lower_bound、upper_bound 等有序操作，无法按顺序遍历

2. 与map的核心差异

键要求：键必须支持哈希计算。内置类型、string 可直接使用；pair、自定义结构体默认不能作为键，需要手动编写哈希函数。
性能：随机数据下比 map 快很多，但常数不稳定，极端构造数据会被卡超时（TLE）。

竞赛小技巧：需要用 pair 作为键时，优先选 map，无需额外写哈希函数，代码更简洁。

三、竞赛高频应用场景

场景1：元素计数（最常用）

统计数组/字符串中各元素出现次数，当元素范围很大（如1e9）或元素是字符串时，无法用数组，直接用映射。

vector<int> a = {1, 1000000000, 2, 1, 2};
unordered_map<int, int> cnt;
for (int x : a) {
    cnt[x]++; // 不存在则默认0，直接+1
}
// 输出每个数的出现次数
for (auto &[k, v] : cnt) {
    cout << k << "出现了" << v << "次\n";
}

场景2：离散化

处理数值范围极大但数量少的数据，将大数值映射为连续的小编号，配合数组使用。

vector<int> a = {9999, 12345, 9999, 56789};
map<int, int> disc; // 有序map保证编号按数值升序
int idx = 0;
for (int x : a) {
    if (!disc.count(x)) {
        disc[x] = ++idx;
    }
}
// disc[9999] = 1, disc[12345] = 2, disc[56789] = 3

场景3：字典映射

字符串/复杂状态与数字的互相转换，比如字符串转编号、坐标映射状态。

map<string, int> id_map;
id_map["apple"] = 1;
id_map["banana"] = 2;

场景4：有序键维护

需要按键的顺序处理数据、查找前驱后继，比如区间合并、调度问题，使用 map 的 lower_bound 高效处理。

四、常见坑点与避坑指南

空迭代器解引用：find 找不到元素时返回 end()，解引用会触发运行时错误，必须先判断。

删除时迭代器失效：遍历中删除元素，必须接收 erase 的返回值，或使用后置++：

// 正确写法：C++11及以上
for (auto it = mp.begin(); it != mp.end(); ) {
    if (需要删除) {
        it = mp.erase(it);
    } else {
        ++it;
    }
}

unordered_map被卡哈希：出题人构造冲突数据时会导致TLE，解决方式：
稳妥方案：换成 map，O(log n) 稳定不超时
优化方案：使用 __gnu_pbds 扩展库的 gp_hash_table，速度更快且抗卡常
修改键值：map的键是只读的（const），不能直接修改，只能删除旧键再插入新键。
无符号size比较：size() 返回 size_t 无符号数，和负数比较会出问题，直接用 empty() 判断更安全。

五、选型建议

容器	底层实现	时间复杂度	有序性	适用场景
普通数组	数组	O(1)	下标有序	键是整数且范围 ≤ 1e6
`map`	红黑树	稳定O(log n)	按键升序	需要有序操作、键是pair/结构体、怕被卡哈希
`unordered_map`	哈希表	平均O(1)，最坏O(n)	无序	纯计数查找、数据随机、追求极致速度

竞赛实战建议：简单计数优先用 unordered_map；涉及有序查询、键是pair、担心被卡常时用 map。

补充 pb_ds 高性能哈希表的用法

map