3、关联式容器set/multiset：红黑树原理简介、set的构造与查找、multiset与set区别、自定义比较器、实战：单词去重与词频统计

好，咱们今天来聊聊关联式容器。说到关联式容器，set和multiset绝对是绕不开的两个角色。我个人习惯把它们叫做“自动排序的集合”。你想想看，如果你有一堆数据，既想快速查找，又想自动排好序，那set就是你的首选。

3.1 红黑树原理简介

set和multiset的底层实现，说白了就是红黑树。红黑树是什么？它是一种自平衡的二叉查找树。嗯，这里要注意，它可不是普通的二叉查找树——普通的树在极端情况下会退化成链表，查找效率直接掉到O(n)。

红黑树通过几个简单的规则，保证了树的高度始终在O(log n)级别：

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

我在项目中遇到过一个问题：当时有个同事用vector存了10万个IP地址，每次查找都遍历一遍，慢得不行。我建议他换成set，查找时间从毫秒级降到了微秒级。这就是红黑树的威力。

3.2 set的构造与查找

set的构造方式有好几种，我平时最常用的是默认构造和初始化列表构造。来看个例子：

#include <set>
#include <iostream>

int main() {
    // 默认构造
    std::set<int> s1;
    
    // 初始化列表构造
    std::set<int> s2 = {3, 1, 4, 1, 5, 9, 2, 6};
    // 输出：1 2 3 4 5 6 9（自动去重+排序）
    
    // 范围构造
    std::vector<int> vec = {5, 3, 8, 1, 9};
    std::set<int> s3(vec.begin(), vec.end());
    
    // 拷贝构造
    std::set<int> s4(s2);
    
    return 0;
}

查找操作是set的强项。它提供了find、count、lower_bound、upper_bound等方法。我个人最常用的是find：

std::set<int> s = {1, 2, 3, 4, 5};

// find查找
auto it = s.find(3);
if (it != s.end()) {
    std::cout << "找到了: " << *it << std::endl;
}

// count统计（对于set，结果只能是0或1）
if (s.count(3)) {
    std::cout << "3存在于集合中" << std::endl;
}

// lower_bound/upper_bound
auto low = s.lower_bound(3);  // 第一个 >= 3 的元素
auto up = s.upper_bound(3);   // 第一个 > 3 的元素
// 区间 [low, up) 就是所有值为3的元素

3.3 multiset与set的区别

set和multiset最大的区别就一句话：set不允许重复元素，multiset允许重复元素。就这么简单。

但实际使用中，这个区别会带来一些行为上的变化：

特性	set	multiset
元素唯一性	不允许重复	允许重复
插入重复元素	插入失败，返回pair<iterator, bool>	插入成功，返回迭代器
count返回值	0或1	0到n（实际重复次数）
erase删除	删除单个元素	删除所有匹配元素

我曾经在做一个日志分析工具时，需要统计不同IP的访问次数。当时我用了multiset，把每个访问记录的IP都插进去，最后用count统计每个IP出现的次数。虽然也能用，但说实话，后来我改用map了——毕竟map直接存键值对更直观。

3.4 自定义比较器

默认情况下，set使用std::less进行排序，也就是升序。但有时候我们需要自定义排序规则，比如降序，或者按照某个结构体的特定字段排序。

自定义比较器有两种方式：函数对象和lambda表达式。我个人更喜欢lambda，写起来更简洁：

// 方式1：函数对象
struct Descending {
    bool operator()(int a, int b) const {
        return a > b;  // 降序
    }
};
std::set<int, Descending> s1 = {3, 1, 4, 1, 5};

// 方式2：lambda（C++11起）
auto cmp = [](int a, int b) { return a > b; };
std::set<int, decltype(cmp)> s2(cmp);

// 实战：按字符串长度排序
auto len_cmp = [](const std::string& a, const std::string& b) {
    if (a.length() != b.length())
        return a.length() < b.length();
    return a < b;  // 长度相同时按字典序
};
std::set<std::string, decltype(len_cmp)> words(len_cmp);
words.insert("apple");
words.insert("banana");
words.insert("cherry");
words.insert("date");

3.5 实战：单词去重与词频统计

好了，理论讲完了，咱们来点实战。这个例子我经常在面试中用到——单词去重和词频统计。它完美展示了set和multiset的典型应用场景。

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

// 单词去重
std::set<std::string> wordDedup(const std::string& text) {
    std::set<std::string> unique_words;
    std::istringstream stream(text);
    std::string word;
    
    while (stream >> word) {
        // 转小写，忽略大小写
        for (char& c : word) {
            c = std::tolower(c);
        }
        unique_words.insert(word);
    }
    return unique_words;
}

// 词频统计
std::multiset<std::string> wordFrequency(const std::string& text) {
    std::multiset<std::string> freq;
    std::istringstream stream(text);
    std::string word;
    
    while (stream >> word) {
        for (char& c : word) {
            c = std::tolower(c);
        }
        freq.insert(word);
    }
    return freq;
}

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog the fox";
    
    // 去重结果
    auto unique = wordDedup(text);
    std::cout << "去重后单词数: " << unique.size() << std::endl;
    for (const auto& w : unique) {
        std::cout << w << " ";
    }
    std::cout << std::endl;
    
    // 词频统计
    auto freq = wordFrequency(text);
    std::cout << "\n词频统计:" << std::endl;
    for (const auto& w : unique) {
        std::cout << w << ": " << freq.count(w) << std::endl;
    }
    
    return 0;
}

输出结果：

去重后单词数: 8
brown dog fox jumps lazy over quick the 

词频统计:
brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
the: 3

你看，set自动帮我们去重并排序，multiset则记录了每个单词出现的次数。这个例子虽然简单，但很实用。我在做文本分析工具时，就是用的这个思路。

好了，set和multiset的内容就讲到这里。记住它们的核心：红黑树保证有序和高效查找，set去重，multiset允许重复。自定义比较器让你能灵活控制排序规则。这些知识点在实际项目中非常实用，尤其是做数据处理和统计分析的时候。

---

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