13. map与multimap容器：从构造到实战

map 和 multimap，说白了就是「键值对」的集合。你想想看，我们写程序时经常需要根据一个 key 快速找到对应的 value——比如根据学号查姓名、根据单词查释义。这时候 map 就派上用场了。

我个人习惯把 map 叫做「字典」。它内部是红黑树实现的，所以元素默认按 key 升序排列。查找、插入、删除的时间复杂度都是 O(log n)，相当稳定。

13.1 map 的构造与基本操作

先看一个最简单的例子：

#include <iostream>
#include <map>
#include <string>

int main() {
    // 默认构造
    std::map<int, std::string> students;
    
    // 插入数据
    students[1001] = "张三";
    students[1002] = "李四";
    students[1003] = "王五";
    
    // 遍历
    for (const auto& pair : students) {
        std::cout << pair.first << " - " << pair.second << std::endl;
    }
    
    return 0;
}

这里要注意，students[1001] 这种写法如果 key 不存在，会自动创建一个默认值。嗯，这个特性有时候会坑人。

map 还支持拷贝构造和范围构造：

// 拷贝构造
std::map<int, std::string> students2(students);

// 从迭代器范围构造
std::map<int, std::string> students3(students.begin(), students.end());

13.2 map 的插入方式——四种姿势

插入数据有四种常见方式，我按推荐程度排个序：

方式	代码示例	特点
1. insert(pair)	m.insert({1, "a"});	key 已存在时不会覆盖
2. insert_or_assign	m.insert_or_assign(1, "b");	C++17 引入，存在则覆盖
3. emplace	m.emplace(1, "c");	原地构造，效率最高
4. operator[]	m[1] = "d";	最方便，但会默认构造

我个人最常用 emplace，因为它避免了临时对象的拷贝。但如果你需要「存在就覆盖」的语义，insert_or_assign 更合适。

// 实战对比
std::map<int, std::string> m;

// 方式1：insert 不会覆盖
auto [it, inserted] = m.insert({1, "hello"});
if (!inserted) {
    std::cout << "key 1 已存在，值为: " << it->second << std::endl;
}

// 方式2：insert_or_assign 会覆盖
m.insert_or_assign(1, "world");  // 现在值为 "world"

// 方式3：emplace 最高效
m.emplace(2, "foo");  // 直接在节点内构造

// 方式4：operator[] 最简洁
m[3] = "bar";  // 如果 key 3 不存在，先默认构造，再赋值

13.3 map 的查找与统计

查找是 map 最常用的操作。我建议用 find() 而不是 operator[]，原因前面说过了。

std::map<int, std::string> scores;
scores[1] = "优秀";
scores[2] = "良好";
scores[3] = "及格";

// 推荐：find 查找
auto it = scores.find(2);
if (it != scores.end()) {
    std::cout << "学号2的成绩: " << it->second << std::endl;
} else {
    std::cout << "未找到该学号" << std::endl;
}

// 统计某个 key 出现的次数（map 只有 0 或 1）
if (scores.count(4) == 0) {
    std::cout << "学号4不存在" << std::endl;
}

// lower_bound / upper_bound 用于范围查找
auto lower = scores.lower_bound(2);  // 第一个 >=2 的元素
auto upper = scores.upper_bound(2);  // 第一个 >2 的元素

为什么 map 的 count() 只能返回 0 或 1？因为 map 不允许重复 key。但 multimap 就不一样了——它允许重复 key，所以 count() 可以返回大于 1 的值。

13.4 multimap 的应用场景

multimap 和 map 的区别就一句话：允许重复 key。但正是这个特性，让它有了独特的用武之地。

我在项目中遇到过这样一个场景：需要记录每个部门的所有员工。一个部门有多个员工，这就是典型的「一对多」关系。

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    // 部门 - 员工 的多重映射
    std::multimap<std::string, std::string> dept_employees;
    
    dept_employees.insert({"技术部", "张三"});
    dept_employees.insert({"技术部", "李四"});
    dept_employees.insert({"市场部", "王五"});
    dept_employees.insert({"技术部", "赵六"});
    
    // 查找技术部所有员工
    auto range = dept_employees.equal_range("技术部");
    std::cout << "技术部员工: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";
    }
    std::cout << std::endl;
    
    // 统计每个部门人数
    std::cout << "技术部人数: " << dept_employees.count("技术部") << std::endl;
    
    return 0;
}

你看，equal_range 返回一对迭代器，正好圈定所有相同 key 的元素。这个函数在 multimap 中特别常用。

其他典型场景：

• 词典：一个单词有多个释义
• 课程表：一个时间段有多门课
• 标签系统：一篇文章有多个标签

13.5 知识体系总览

下面这张图帮你理清 map 和 multimap 的核心脉络：

13.6 避坑总结

最后，我把这些年踩过的坑总结一下：

• 别用 operator[] 做查找——它会插入默认值，破坏数据
• multimap 没有 operator[]——想用下标访问？编译器直接报错
• emplace 比 insert 快——省去了临时对象的构造和析构
• equal_range 是 multimap 的好搭档——一次调用拿到所有相同 key 的元素

map 和 multimap 在实际项目中用得非常多。我个人觉得，掌握好它们的插入和查找操作，就够应付 80% 的场景了。剩下的 20%，遇到具体问题再查文档也不迟。

---

公众号:蓝海资料掘金营，微信deep3321