37、STL容器（set与map）：红黑树、有序关联容器、pair

说实话，C++ 里容器那么多，但真正让我觉得「设计得真漂亮」的，就是 set 和 map 这对兄弟。它们底层共用一颗红黑树，却对外展现出完全不同的接口。我当年第一次搞懂红黑树时，拍着桌子感叹：这玩意儿简直是数据结构与工程结合的典范。

今天咱们就聊聊这两个有序关联容器。别被「红黑树」三个字吓到，你不需要手写它，但得知道它为什么快、好在哪。

红黑树：set 和 map 的幕后功臣

先说说底层。set 和 map 在大多数标准库实现里，底层都是一颗红黑树。它是一种自平衡的二叉搜索树。

什么叫自平衡？你想想看，普通二叉搜索树如果插入有序数据，会退化成链表，查找变成 O(n)。红黑树通过颜色约束和旋转操作，保证树的高度始终在 O(log n) 级别。

红黑树的规则其实就五条：

• 每个节点要么红要么黑
• 根节点是黑的
• 叶子节点（NIL）是黑的
• 红色节点的子节点必须是黑的（不能有连续红节点）
• 从任一节点到其每个叶子的路径，黑色节点数相同

嗯，这里要注意——你不需要背这些规则。但你要记住一个结论：红黑树的插入、删除、查找，最坏情况都是 O(log n)。我在项目中用 set 做实时数据去重，几百万条数据插进去，查询响应时间稳得像条直线。

set：简单但强大的有序集合

set 说白了就是一个不重复的有序集合。元素自动按升序排列，插入重复元素会被忽略。

我个人习惯用 set 做两件事：去重和快速查找。比如日志分析时，我需要统计所有出现过的 IP 地址——直接往 set 里扔，完事。

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> ips;
    
    ips.insert("192.168.1.1");
    ips.insert("10.0.0.1");
    ips.insert("192.168.1.1");  // 重复，被忽略
    
    std::cout << "不重复 IP 数量: " << ips.size() << "\n";
    
    // 查找
    if (ips.find("10.0.0.1") != ips.end()) {
        std::cout << "找到了 10.0.0.1\n";
    }
    
    // 遍历（自动有序）
    for (const auto& ip : ips) {
        std::cout << ip << "\n";
    }
    
    return 0;
}

输出结果：

不重复 IP 数量: 2
找到了 10.0.0.1
10.0.0.1
192.168.1.1

看到没？插入顺序是 192.168.1.1 先，但遍历时 10.0.0.1 排前面——因为字符串按字典序排了。

map：键值对的有序字典

map 比 set 多存了一个「值」。每个元素是一个 pair<const Key, Value>，按键排序，键唯一。

我记得有一次做配置管理系统，需要按配置名快速查找配置值——map 简直是天选之子。几万条配置，查找时间几乎不变。

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

int main() {
    std::map<std::string, int> scores;
    
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    
    // 使用 insert 返回 pair<iterator, bool>
    auto result = scores.insert({"David", 88});
    if (result.second) {
        std::cout << "插入成功\n";
    }
    
    // 查找
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << "Bob 的分数: " << it->second << "\n";
    }
    
    // 遍历（按键排序）
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }
    
    return 0;
}

输出：

插入成功
Bob 的分数: 87
Alice: 95
Bob: 87
Charlie: 92
David: 88

这里有个坑——operator[] 如果键不存在，会自动插入一个默认值。我曾经在排查一个 bug 时发现 map 里莫名其妙多了很多空条目，就是因为用了 [] 做查找。所以，只读查找请用 find() 或 at()。

pair：把两个值绑在一起

pair 是 C++ 里最朴实无华的工具。它就是把两个值打包成一个对象。map 的每个元素就是一个 pair。

我经常用 pair 做函数返回值——比如同时返回状态码和结果数据。比传引用参数清爽多了。

#include <iostream>
#include <utility>  // pair
#include <string>

// 返回 pair 的函数
std::pair<bool, std::string> lookup(int id) {
    if (id == 1) {
        return {true, "找到数据了"};
    }
    return {false, "没找到"};
}

int main() {
    auto [found, message] = lookup(1);  // C++17 结构化绑定
    if (found) {
        std::cout << message << "\n";
    }
    
    // 传统方式
    std::pair<int, double> p(42, 3.14);
    std::cout << "first: " << p.first 
              << ", second: " << p.second << "\n";
    
    return 0;
}

输出：

找到数据了
first: 42, second: 3.14

set 和 map 的对比

特性	set	map
存储内容	单个键	键值对 (pair)
键唯一性	是	是
有序性	是（默认升序）	是（按键升序）
查找复杂度	O(log n)	O(log n)
插入复杂度	O(log n)	O(log n)
典型用途	去重、集合运算	字典、配置表

避坑指南

我曾经在项目里犯过一个低级错误——用 std::map::operator[] 做查找，结果插入了大量空值，导致内存暴涨。排查了半天才发现是 [] 的副作用。从那以后，我只在确定要插入或修改时才用 []，只读查找一律用 find()。

还有一个坑：set 和 map 的迭代器在插入/删除操作后，只有被删除的那个迭代器会失效，其他迭代器依然有效。这是红黑树的特性——不像 vector 那样会全部失效。但别因此就掉以轻心，该注意的还是要注意。

知识体系总览

下面这张图帮你理清 set 和 map 的关系：

从这张图可以看得很清楚：set 和 map 共享同一套底层红黑树机制，区别只在于存储的内容和对外接口。pair 则是它们存储数据的基本单元——map 直接存 pair，set 存的是单个值但内部实现也依赖 pair 的机制。

好了，set 和 map 的核心内容就这些。记住一句话：需要有序、唯一、对数级查找时，优先考虑 set 或 map。它们不是万能的，但在 90% 的场景下，比你自己手写的数据结构要靠谱得多。

---