第9章 std::map / std::multimap 详解

课程目录第9章 std::map / std::multimap 详解

第9章 std::map / std::multimap 详解：键值对存储、红黑树实现、operator[] 的陷阱、插入与查找

map 和 multimap，说白了就是 C++ 里最经典的「字典」。你给一个键，它给你一个值。我当年刚入行时，第一个接触的 STL 容器就是 map，那时候觉得这东西简直是神器——再也不用自己手写二分查找或者哈希表了。

但用久了你会发现，map 虽然好用，坑也不少。尤其是那个 operator[]，看起来人畜无害，实际上暗藏杀机。今天咱们就把 map 和 multimap 彻底聊透。

9.1 红黑树：map 的幕后功臣

先问一个问题：map 为什么能保持有序？为什么插入和查找都那么快？

答案就是红黑树。map 底层是一棵自平衡的二叉搜索树，具体来说是红黑树。它保证了最坏情况下插入、删除、查找的时间复杂度都是 O(log n)。

我个人习惯把红黑树理解成「带规则的二叉搜索树」。它通过给每个节点涂上红色或黑色，并遵守几条简单的规则，来保证树的高度不会长得太歪。具体规则我就不背了，你只需要记住：红黑树能保证从根到叶子的最长路径不超过最短路径的两倍。这就够了。

核心要点：map 和 multimap 的有序性来源于红黑树。这意味着遍历 map 时，键是按升序排列的。如果你需要无序的键值对，请用 unordered_map。

下面这张图展示了红黑树的基本结构：

9.2 map 的基本用法

map 存储的是 pair<const Key, T> 类型的元素。每个键唯一，键不能修改，但值可以改。

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

int main() {
    // 创建一个 map，键是 string，值是 int
    std::map<std::string, int> ages;
    
    // 插入方式一：用 operator[]
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    
    // 插入方式二：用 insert
    ages.insert({"Charlie", 35});
    ages.insert(std::make_pair("David", 28));
    
    // 遍历
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << "\n";
    }
    
    return 0;
}

输出结果会按字母顺序排列：Alice、Bob、Charlie、David。这就是红黑树在背后起作用。

9.3 operator[] 的陷阱——我踩过的坑

operator[] 是 map 最方便的特性，但也是最危险的。为什么？

因为 operator[] 在键不存在时会自动插入一个默认构造的值。

你想想看，如果你只是想查一下某个键在不在，结果它给你插进去了，这多吓人。

std::map<std::string, int> scores;
scores["Alice"] = 95;

// 我只是想查一下 Bob 的分数
int bobScore = scores["Bob"];  // 糟糕！Bob 被插入了，值为 0
std::cout << "Bob's score: " << bobScore << "\n";
std::cout << "Map size: " << scores.size() << "\n";  // 输出 2，不是 1

我曾经在线上服务中犯过这个错误。当时用 operator[] 去查一个配置项，结果把一堆不存在的配置项全插进去了，内存暴涨。排查了半天才发现是 operator[] 的「好心办坏事」。

正确的做法是：用 find() 或者 at() 来查找。

// 方法一：用 find
auto it = scores.find("Bob");
if (it != scores.end()) {
    std::cout << "Bob's score: " << it->second << "\n";
} else {
    std::cout << "Bob not found\n";
}

// 方法二：用 at（C++11 起）
try {
    int bobScore = scores.at("Bob");  // 如果不存在，抛出 std::out_of_range
} catch (const std::out_of_range& e) {
    std::cout << "Bob not found\n";
}

我的建议：如果你只是想读取，用 at() 或 find()。只有当你确实想插入或修改时，才用 operator[]。这个习惯能帮你省去很多调试时间。

9.4 插入操作的几种方式

map 提供了多种插入方式，每种方式的行为略有不同：

方式	语法	行为
operator[]	m[k] = v	键存在则覆盖，不存在则插入
insert	m.insert({k, v})	键存在则不插入，返回 pair<iterator, bool>
insert_or_assign	m.insert_or_assign(k, v)	C++17 起，键存在则覆盖，不存在则插入
emplace	m.emplace(k, v)	原地构造，避免拷贝
try_emplace	m.try_emplace(k, v)	C++17 起，键存在则不插入，且不移动参数

这里有个细节：insert 返回一个 pair，first 是迭代器，second 是 bool 表示是否成功插入。

auto [it, inserted] = m.insert({"key", 42});
if (inserted) {
    std::cout << "插入成功\n";
} else {
    std::cout << "键已存在，值为 " << it->second << "\n";
}

9.5 查找与删除

查找用 find()，删除用 erase()。这两个操作的时间复杂度都是 O(log n)。

std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

// 查找
auto it = m.find(2);
if (it != m.end()) {
    std::cout << "Found: " << it->second << "\n";
}

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

注意：erase 按键删除时，返回被删除的元素个数（对于 map 来说，要么是 0 要么是 1）。对于 multimap，可能返回大于 1 的值。

9.6 multimap：允许重复键

multimap 和 map 几乎一样，唯一的区别是：multimap 允许键重复。

但要注意，multimap 不支持 operator[]。为什么？因为键不唯一，operator[] 不知道该返回哪个值。

std::multimap<std::string, int> mm;
mm.insert({"Alice", 90});
mm.insert({"Alice", 95});  // 允许重复键
mm.insert({"Bob", 85});

// 遍历所有 Alice 的成绩
auto range = mm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";
}
// 输出：90 95

equal_range 返回一对迭代器，表示该键对应的所有元素的范围。这在处理一对多关系时非常有用。

9.7 性能与最佳实践

map 的插入和查找都是 O(log n)，但插入涉及到内存分配和红黑树的平衡操作，比 vector 的 push_back 要慢不少。如果你对性能有极致要求，考虑用 unordered_map（哈希表，平均 O(1)）。

但 map 的优势在于：有序遍历。比如你需要按时间顺序输出日志，或者按字母顺序显示菜单，map 就是天然的选择。

我个人习惯：

需要有序：用 map
不需要有序，追求速度：用 unordered_map
键可能重复：用 multimap 或 unordered_multimap
只读查找：用 at() 或 find()，别用 operator[]

嗯，map 的内容差不多就这些了。记住 operator[] 的陷阱，用好 find 和 at，你的代码会健壮很多。

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

📚 课程目录