set和multiset

关联容器 - 有序集合

set 概述

set 是基于红黑树实现的有序集合，特点是：

常用场景

  • 去重：快速去除重复元素
  • 排序：自动维护有序性
  • 查找：快速判断元素是否存在
  • 区间查询：查找大于/小于某个值的元素

set 基本用法


#include <set>
using namespace std;

int main() {
    // 创建 set
    set s;

    // 插入元素
    s.insert(5);
    s.insert(3);
    s.insert(7);
    s.insert(3);  // 重复元素不会被插入

    // s: {3, 5, 7}

    // 查找元素
    if (s.find(5) != s.end()) {
        cout << "找到 5" << endl;
    }

    if (s.count(10)) {  // count 返回 0 或 1
        cout << "存在 10" << endl;
    }

    // 删除元素
    s.erase(5);  // 删除值为5的元素

    // 遍历
    for (int x : s) {
        cout << x << " ";  // 3 7
    }

    // 大小操作
    cout << s.size() << endl;   // 2
    cout << s.empty() << endl;  // false
    s.clear();

    return 0;
}

set 交互演示

输入数字，观察 set 如何自动排序和去重：

set 为空

set 高级操作

1. 获取边界元素


set s = {1, 3, 5, 7, 9};

// 最小和最大元素
cout << *s.begin() << endl;    // 1 (最小)
cout << *s.rbegin() << endl;   // 9 (最大)

// 大于等于某个值的第一个元素
auto it = s.lower_bound(4);  // 指向 5
if (it != s.end()) {
    cout << *it << endl;  // 5
}

// 大于某个值的第一个元素
it = s.upper_bound(5);  // 指向 7
if (it != s.end()) {
    cout << *it << endl;  // 7
}

// 删除范围内的元素
s.erase(s.lower_bound(3), s.upper_bound(7));
// s: {1, 9}

2. 自定义排序


// 降序排列
set> s = {1, 3, 5, 7, 9};
// s: {9, 7, 5, 3, 1}

// 自定义比较函数
struct cmp {
    bool operator()(int a, int b) const {
        return a % 10 < b % 10;  // 按个位数排序
    }
};

set s2 = {13, 22, 35, 41};
// s2: {41, 22, 13, 35} (个位数 1, 2, 3, 5)

3. 存储复杂数据类型


// 存储 pair
set> s;
s.insert({1, 2});
s.insert({2, 1});
s.insert({1, 2});  // 重复，不会插入

// 存储 pair 时，先比较 first，再比较 second
// {1, 2} < {1, 3} < {2, 1}

// 存储 pair 时常用技巧
typedef pair PII;

// 排序规则：按 first 升序，first 相同按 second 降序
set> s2([](PII a, PII b) {
    if (a.first != b.first)
        return a.first < b.first;
    return a.second > b.second;
});

s2.insert({1, 3});
s2.insert({1, 2});
s2.insert({2, 1});
// s2: {{1, 3}, {1, 2}, {2, 1}}

multiset 概述

multiset 与 set 类似，但允许重复元素。


#include <set>
using namespace std;

int main() {
    multiset ms;

    // 插入元素（允许重复）
    ms.insert(3);
    ms.insert(1);
    ms.insert(3);
    ms.insert(2);
    ms.insert(3);

    // ms: {1, 2, 3, 3, 3}

    // count 返回元素出现次数
    cout << ms.count(3) << endl;  // 3

    // find 返回第一个匹配的迭代器
    auto it = ms.find(3);  // 指向第一个 3

    // 删除指定值的所有元素
    ms.erase(3);
    // ms: {1, 2}

    // 删除指定位置的元素
    it = ms.begin();
    ms.erase(it);  // 删除第一个元素
    // ms: {2}

    // 删除指定位置的某个元素
    it = ms.find(2);
    ms.erase(it, ms.end());  // 删除从 it 到 end 的元素

    return 0;
}

set vs multiset

  • set：元素唯一，count() 返回 0 或 1
  • multiset：允许重复，count() 返回实际个数
  • erase(x)：set 删除 x，multiset 删除所有 x

复杂度分析

操作 set/multiset unordered_set
插入$$ O(\log n) $$$$ O(1) $$
删除$$ O(\log n) $$$$ O(1) $$
查找$$ O(\log n) $$$$ O(1) $$
区间查询$$ O(\log n) $$不支持
顺序遍历有序无序

选择建议

  • 需要有序：使用 set
  • 不需要有序，追求速度：使用 unordered_set
  • 需要允许重复：使用 multiset
  • 需要区间查询：使用 set（lower_bound/upper_bound）

实际应用示例

1. 去重


vector v = {1, 2, 2, 3, 3, 3, 4};

// 方法1：使用 set
set s(v.begin(), v.end());
vector result(s.begin(), s.end());
// result: {1, 2, 3, 4}

// 方法2：使用 unique（需要先排序）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// v: {1, 2, 3, 4}

2. 区间查询


set scores = {60, 65, 70, 75, 80, 85, 90, 95};

// 查找大于等于75的最低分
auto it = scores.lower_bound(75);
cout << *it << endl;  // 75

// 查找大于75的最低分
it = scores.upper_bound(75);
cout << *it << endl;  // 80

// 统计区间内的元素数量
int start = 70, end = 85;
int count = distance(scores.lower_bound(start), scores.upper_bound(end));
cout << count << endl;  // 4 (70, 75, 80, 85)

3. 滑动窗口最大值


vector maxSlidingWindow(vector& nums, int k) {
    multiset ms;
    vector result;

    for (int i = 0; i < nums.size(); i++) {
        ms.insert(nums[i]);

        if (i >= k) {
            // 移除滑出窗口的元素
            ms.erase(ms.find(nums[i - k]));
        }

        if (i >= k - 1) {
            // 当前窗口的最大值
            result.push_back(*ms.rbegin());
        }
    }

    return result;
}