6. set/multiset容器：从入门到实战

set和multiset，说白了就是C++里的「集合」。我刚开始学STL时，觉得这玩意儿不就是个数组吗？后来才发现，它背后的设计哲学其实挺讲究的。

6.1 set的基本概念

set是一个自动排序且元素唯一的容器。它底层用红黑树实现，插入、删除、查找的时间复杂度都是O(log n)。

我个人习惯把set理解成「有序的数学集合」。你想想看，数学里的集合有什么特点？元素不重复、没有顺序——但STL的set额外帮你排好序了。

我在项目中遇到过这样一个场景：需要统计用户访问的IP地址，并且要按字典序输出。用set简直不要太爽——插入时自动去重+排序，一行代码搞定。

6.2 set的构造与赋值

构造set的方式有几种，我直接上代码：

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

void test() {
    // 默认构造
    set<int> s1;
    
    // 初始化列表构造（C++11起）
    set<int> s2 = {5, 3, 8, 1, 3, 5};  // 实际存储：1, 3, 5, 8
    
    // 拷贝构造
    set<int> s3(s2);
    
    // 迭代器区间构造
    int arr[] = {9, 2, 7, 4};
    set<int> s4(arr, arr + 4);  // 存储：2, 4, 7, 9
    
    // 赋值操作
    set<int> s5;
    s5 = s2;
}

嗯，这里要注意：set的构造函数会自动去重。你看s2里我塞了两个3和两个5，实际只存了一份。

6.3 set的大小与交换

这部分比较简单，我快速过一下：

void test_size_swap() {
    set<int> s = {1, 2, 3, 4, 5};
    
    // 大小相关
    cout << "size: " << s.size() << endl;      // 5
    cout << "empty: " << s.empty() << endl;    // 0（非空）
    cout << "max_size: " << s.max_size() << endl; // 理论最大容量
    
    // 交换
    set<int> s2 = {10, 20};
    s.swap(s2);  // 现在s存{10,20}，s2存{1,2,3,4,5}
}

swap操作是O(1)的，因为它只交换内部指针。我曾经在需要频繁切换两个集合的场景下用过swap，性能很好。

6.4 set的插入与删除

插入和删除是set最常用的操作。我直接上实战代码：

void test_insert_erase() {
    set<int> s;
    
    // 插入方式1：insert返回pair<iterator, bool>
    pair<set<int>::iterator, bool> ret = s.insert(10);
    if (ret.second) {
        cout << "插入成功" << endl;
    }
    
    // 插入方式2：重复插入会失败
    ret = s.insert(10);  // 第二次插入，second为false
    if (!ret.second) {
        cout << "元素已存在，插入失败" << endl;
    }
    
    // 批量插入
    s.insert({20, 30, 40});
    
    // 删除
    s.erase(20);           // 按值删除
    s.erase(s.begin());    // 按迭代器删除
    s.erase(s.begin(), s.end());  // 清空区间
    s.clear();             // 清空所有元素
}

// 正确做法
for (auto it = s.begin(); it != s.end(); ) {
    if (*it % 2 == 0) {
        it = s.erase(it);  // erase返回下一个元素的迭代器
    } else {
        ++it;
    }
}

6.5 set的查找与统计

查找是set的强项。红黑树结构让查找变得非常快：

void test_find_count() {
    set<int> s = {1, 2, 3, 4, 5};
    
    // find：找到返回迭代器，找不到返回end()
    auto it = s.find(3);
    if (it != s.end()) {
        cout << "找到了: " << *it << endl;
    }
    
    // count：统计元素个数（set中要么0要么1）
    int cnt = s.count(3);  // 返回1
    cnt = s.count(10);     // 返回0
    
    // lower_bound / upper_bound
    auto low = s.lower_bound(3);   // 第一个>=3的元素
    auto up = s.upper_bound(3);    // 第一个>3的元素
    cout << "lower_bound: " << *low << endl;  // 3
    cout << "upper_bound: " << *up << endl;   // 4
}

为什么count在set里只有0或1？因为set不允许重复。但multiset就不一样了——这也是我们接下来要说的。

6.6 set与multiset的区别

void test_multiset() {
    multiset<int> ms;
    ms.insert(10);
    ms.insert(10);  // 可以重复插入
    ms.insert(20);
    
    cout << "count(10): " << ms.count(10) << endl;  // 2
    
    // 查找时注意：find返回第一个遇到的元素
    auto it = ms.find(10);
    // 如果要删除所有10
    ms.erase(10);  // 删除所有值为10的元素
}

6.7 pair对组创建

pair在set中随处可见——insert的返回值就是pair。它其实就是把两个值打包在一起：

void test_pair() {
    // 创建方式1：直接构造
    pair<string, int> p1("age", 25);
    cout << p1.first << ": " << p1.second << endl;
    
    // 创建方式2：make_pair
    auto p2 = make_pair("score", 98);
    
    // 创建方式3：拷贝
    pair<string, int> p3(p1);
    
    // 实际应用：set的insert返回值
    set<int> s;
    pair<set<int>::iterator, bool> ret = s.insert(42);
    if (ret.second) {
        cout << "插入成功，元素值: " << *(ret.first) << endl;
    }
}

pair说白了就是个「二合一」的容器。我在写图算法时经常用pair来存边的起点和终点，比定义结构体省事多了。

知识体系总览

下面这张图帮你理清set/multiset的核心脉络：

set和multiset就像一对双胞胎——长得像，但性格不同。set严谨，不允许重复；multiset随和，来者不拒。选哪个？看你的业务需求。

我个人更常用set，因为去重是刚需。但如果你在做词频统计之类的任务，multiset就派上用场了。