本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-08 21:12:30

map/multimap运用

一、容器特性对比

二、核心操作详解

1. 基本操作

#include <map>
using namespace std;

map<string, int> mp;
multimap<int, string> mmp;

\/\/ 插入元素
mp["Alice"] = 95;                   \/\/ 直接赋值
mp.insert({"Bob", 88});             \/\/ 插入pair对象
mmp.emplace(90, "Charlie");         \/\/ 原地构造

\/\/ 删除元素
mp.erase("Alice");                  \/\/ 按key删除
mmp.erase(mmp.find(90));            \/\/ 按迭代器删除

\/\/ 查找操作
auto it = mp.find("Bob");           \/\/ 返回迭代器
int cnt = mmp.count(90);            \/\/ 统计key出现次数

\/\/ 范围迭代
auto [start, end] = mmp.equal_range(85); \/\/ 获取键值范围

2. 高级操作

\/\/ 自定义排序规则
struct cmp {
    bool operator()(const string& a, const string& b) const {
        return a.length() < b.length();
    }
};
map<string, int, cmp> lenMap;

\/\/ 合并map（C++17）
map<int, int> m1, m2;
m1.merge(m2);  \/\/ 合并后m2保留冲突键值

\/\/ 节点操作（C++17）
auto nh = mp.extract("Alice");      \/\/ 提取节点
mp.insert(move(nh));                \/\/ 重新插入

三、经典例题解析

例题1：POJ2503 Babelfish（字典查询）

题目要求：实现双语词典的单词翻译功能

map实现：

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

map<string, string> dict;

int main() {
    string line, en, foreign;
    while(getline(cin, line) && !line.empty()) {
        istringstream iss(line);
        iss >> en >> foreign;
        dict[foreign] = en;
    }
    
    while(cin >> foreign) {
        auto it = dict.find(foreign);
        if(it != dict.end()) 
            cout << it->second << endl;
        else 
            cout << "eh" << endl;
    }
    return 0;
}

例题2：洛谷P3374 【模板】树状数组 1（map模拟解法）

题目要求：实现单点修改、前缀求和操作

map优化解法：

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

map<int, int> tree;  \/\/ 离散化存储非零位置

void update(int pos, int val) {
    while(pos <= n) {
        tree[pos] += val;
        pos += pos & -pos;
    }
}

int query(int pos) {
    int sum = 0;
    while(pos > 0) {
        sum += tree[pos];
        pos -= pos & -pos;
    }
    return sum;
}

例题3：AtCoder ABC245D - Polynomial division（多项式除法）

题目要求：给定多项式A(x)*B(x)=C(x)，已知A和C求B

map存储系数解法：

#include <bits\/stdc++.h>
using namespace std;

map<int, int> read_poly(int n) {
    map<int, int> res;
    for(int i=0; i<=n; ++i) {
        int c; cin >> c;
        if(c != 0) res[i] = c;
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    auto A = read_poly(n);
    auto C = read_poly(n+m);
    
    map<int, int> B;
    for(int k=m; k>=0; --k) {
        int sum = 0;
        for(auto [i,a] : A) {
            if(B.find(k-i) != B.end())
                sum += a * B[k-i];
        }
        B[k] = (C[k] - sum) \/ A.begin()->second;
    }
    \/\/ ...输出B的系数...
    return 0;
}

四、进阶应用技巧

1. 离散化坐标压缩

vector<int> coords = {100, 5, 200, 5, 100};
map<int, int> mapping;
int idx = 1;
for(auto x : coords)
    if(!mapping.count(x))
        mapping[x] = idx++;

2. 时间线管理（扫描线算法）

map<int, int> timeline;  \/\/ 时间戳 -> 事件数量

void add_event(int t) {
    timeline[t]++;
}

void process_events() {
    auto it = timeline.begin();
    while(it != timeline.end()) {
        int t = it->first;
        int cnt = it->second;
        \/\/ 处理t时刻的cnt个事件
        it = timeline.erase(it);
    }
}

五、练习题推荐

1. 洛谷P1276 校门外的树（增强版）（区间状态维护）
2. POJ3481 Double Queue（双优先队列模拟）
3. AtCoder ABC217D - Cutting Woods（坐标离散化）
4. 洛谷P4056 [JSOI2009] 火星藏宝图（动态规划状态优化）
5. Codeforces 4C - Registration System（用户名计数）

六、常见错误与优化

典型错误案例

\/\/ 错误1：直接访问不存在的键
map<string, int> mp;
cout << mp["unknown"];  \/\/ 自动插入默认值0

\/\/ 正确做法
if(mp.count("unknown")) 
    cout << mp["unknown"];

\/\/ 错误2：错误删除范围
multimap<int, int> mmp;
mmp.erase(5);  \/\/ 删除所有key=5的元素

\/\/ 正确删除单个元素
auto it = mmp.find(5);
if(it != mmp.end()) mmp.erase(it);

性能优化技巧

1. 预分配内存（适用于已知规模）：

map<int, int> mp;
mp.reserve(1e5);  \/\/ C++23+支持

2. 批量插入优化：

vector<pair<int, int>> data{{1,2},{3,4}};
mp.insert(data.begin(), data.end());

3. 利用有序性进行范围统计：

\/\/ 统计[key1, key2)区间的value总和
auto it1 = mp.lower_bound(key1);
auto it2 = mp.lower_bound(key2);
int sum = accumulate(it1, it2, 0, 
    [](int s, auto& p){ return s + p.second; });

4. 使用emplace替代insert：

mp.emplace(5, 10);  \/\/ 避免临时对象构造