C++ set 使用完全指南

概述

std::set 是 C++ STL 中的有序集合容器，具有以下核心特性：

  • 元素唯一性：不会存储重复元素
  • 自动排序：元素默认按升序排列（可自定义规则）
  • 对数复杂度：所有查找、插入、删除操作均为 O(log n)
  • 红黑树实现：底层基于平衡二叉搜索树

与之对应的 std::unordered_set 基于哈希表实现，元素无序但平均操作复杂度为 O(1)。

基本操作

头文件与声明

1
2
3
4
5
6
7
8
9
10
11
#include <set>
using namespace std;

// 默认升序
set<int> s1;

// 降序
set<int, greater<int>> s2;

// 初始化列表
set<int> s3 = {1, 3, 5, 2, 4};

插入元素

1
2
3
4
5
6
7
8
9
10
11
s.insert(10);           // 插入元素，若已经存在，则无法插入，返回 pair<iterator, bool>
s.emplace(20);         // 原地构造（对非POD类型更高效）
s.insert({1, 2, 3});   // 批量插入

// insert 返回值示例
auto result = s.insert(10);
if (result.second) {
    cout << "插入成功，位置：" << *result.first << endl;
} else {
    cout << "元素已存在" << endl;
}

删除元素

1
2
3
4
s.erase(5);            // 按值删除，返回删除个数（0或1）
s.erase(s.begin());    // 按迭代器删除
s.erase(it1, it2);     // 删除区间 [it1, it2)
s.clear();             // 清空集合

查找元素

1
2
3
4
5
6
7
8
9
auto it = s.find(10);   // 查找元素，返回迭代器
if (it != s.end()) {
    cout << "找到：" << *it << endl;
}

// count 检查存在性
if (s.count(10)) {
    cout << "元素存在" << endl;
}

边界查询

1
2
3
4
5
6
7
8
9
10
set<int> s = {2, 4, 6, 8, 12, 16, 24, 32};

// 第一个 >=10 的元素
auto lb = s.lower_bound(10);  // 指向 12

// 第一个 >10 的元素  
auto ub = s.upper_bound(10);  // 指向 12

// 相等范围
auto range = s.equal_range(10);  // [lb, ub)

大小与状态

1
2
cout << "元素个数：" << s.size() << endl;
cout << "是否为空：" << s.empty() << endl;

复杂度分析

  • insert(): O(log n)
  • erase(): O(log n)
  • find(): O(log n)
  • lower_bound(): O(log n)
  • count(): O(log n)
  • 遍历：O(n)

遍历与有序查询

基本遍历方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 正向遍历
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
}

// 范围for（C++11）
for (int x : s) {
    cout << x << " ";
}

// 逆序遍历
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << " ";
}

范围查询（利用有序性）

1
2
3
4
5
6
7
// 查询 (5, 20] 范围内的元素
auto left = s.upper_bound(5);   // 第一个 >5 的元素
auto right = s.upper_bound(20); // 第一个 >20 的元素

for (auto it = left; it != right; ++it) {
    cout << *it << " ";
}

集合运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>

set<int> a = {1, 3, 5};
set<int> b = {2, 3, 4};

vector<int> result;

// 并集
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// 交集  
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// 差集
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// 对称差集
set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

高级用法：自定义比较器

基本自定义比较器

1
2
3
4
5
6
7
8
9
// 降序比较器
struct Descending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

set<int, Descending> s = {1, 3, 2, 5, 4};
// 元素顺序：5, 4, 3, 2, 1

结构体集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Student {
    int id;
    string name;
    int score;
};

// 比较器：先按分数降序，再按ID升序
struct StudentCmp {
    bool operator()(const Student& a, const Student& b) const {
        if (a.score != b.score) {
            return a.score > b.score;  // 高分在前
        }
        return a.id < b.id;  // 同分时ID小的在前
    }
};

set<Student, StudentCmp> students;
students.insert({3, "Li", 90});
students.insert({1, "Zhang", 95});
students.insert({2, "Wang", 95});

// 遍历顺序：
// {1, "Zhang", 95}
// {2, "Wang", 95}
// {3, "Li", 90}

严格弱序要求

自定义比较器必须满足严格弱序（Strict Weak Ordering）：

  1. 非自反性：comp(a, a) 为 false
  2. 不对称性：若 comp(a, b) 为 true，则 comp(b, a) 为 false
  3. 传递性：若 comp(a, b) 且 comp(b, c)，则 comp(a, c)
  4. 等价传递：若 !comp(a, b) && !comp(b, a) 且 !comp(b, c) && !comp(c, b)，则 !comp(a, c) && !comp(c, a)

与 unordered_set 的对比

特性 set（有序集合） unordered_set（哈希集合）
底层结构 红黑树（平衡BST） 哈希表
元素顺序 自动排序 无序（插入顺序不保证）
时间复杂度 查找/插入/删除：O(log n) 平均 O(1)，最坏 O(n)
内存占用 较低（每个节点额外指针） 较高（哈希桶和负载因子）
迭代器稳定性 插入/删除不使其他迭代器失效 重新哈希会使所有迭代器失效
特殊操作 支持 lower_bound()、upper_bound() 不支持有序查询

选择建议

  • 使用 set 的场景：

    • 需要元素自动排序
    • 需要范围查询或边界查找
    • 需要按顺序遍历
    • 元素数量不大或对最坏性能有要求

  • 使用 unordered_set 的场景：

    • 只需快速查找存在性
    • 不需要元素有序
    • 大量数据且哈希函数良好
    • 对平均性能要求高
1
2
3
4
5
6
7
8
9
10
#include <unordered_set>

set<int> ordered_set = {8, 4, 16, 2, 24, 12};
unordered_set<int> unordered_set = {8, 4, 16, 2, 24, 12};

cout << "set (有序): ";
for (int x : ordered_set) cout << x << " ";  // 2 4 8 12 16 24

cout << "\nunordered_set (无序): ";
for (int x : unordered_set) cout << x << " ";  // 顺序不确定

常见问题与最佳实践

1. 遍历时安全删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
set<int> s = {1, 2, 3, 4, 5};

// 错误：删除后迭代器失效
for (auto it = s.begin(); it != s.end(); ++it) {
    if (*it % 2 == 0) {
        s.erase(it);  // 错误！it 已失效
    }
}

// 正确：使用返回值更新迭代器
for (auto it = s.begin(); it != s.end(); ) {
    if (*it % 2 == 0) {
        it = s.erase(it);  // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

2. 元素不可变性

1
2
3
4
5
6
7
8
9
10
11
12
13
set<int> s = {1, 2, 3, 4, 5};

// 错误：修改元素可能破坏有序性
for (int& x : s) {
    x = x * 2;  // 错误！不能修改 set 元素
}

// 正确：先删除再插入
auto it = s.find(3);
if (it != s.end()) {
    s.erase(it);
    s.insert(6);  // 使用新值
}

3. 性能优化

1
2
3
4
5
6
7
8
9
10
11
12
13
// 批量构造比逐个插入快
vector<int> data = {5, 3, 1, 4, 2};

// 较慢：O(n log n)
set<int> s1;
for (int x : data) s1.insert(x);

// 较快：O(n log n) 但常数更小
set<int> s2(data.begin(), data.end());

// 最快：如果数据已排序
sort(data.begin(), data.end());
set<int> s3(data.begin(), data.end());  // O(n)

4. 与 vector 互转

1
2
3
4
5
6
7
// set 转 vector（已排序）
set<int> s = {3, 1, 4, 1, 5, 9};
vector<int> v(s.begin(), s.end());  // {1, 3, 4, 5, 9}

// vector 转 set（去重排序）
vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6};
set<int> s2(data.begin(), data.end());  // {1, 2, 3, 4, 5, 6, 9}

实战示例

示例1：两集合乘积去重排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 计算两个集合的乘积集，去重并排序
vector<int> productSet(const vector<int>& A, const vector<int>& B) {
    set<int> result;
    for (int a : A) {
        for (int b : B) {
            result.insert(a * b);
        }
    }
    return vector<int>(result.begin(), result.end());
}

int main() {
    vector<int> A = {2, 4, 8};
    vector<int> B = {1, 2, 3, 4};
    
    auto products = productSet(A, B);
    // 输出：2 4 6 8 12 16 24 32
    for (int p : products) cout << p << " ";
    
    return 0;
}

示例2：范围统计系统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class RangeCounter {
private:
    set<int> points;
    
public:
    // 添加点
    void addPoint(int x) {
        points.insert(x);
    }
    
    // 统计 [l, r] 范围内的点数
    int countInRange(int l, int r) {
        auto left = points.lower_bound(l);
        auto right = points.upper_bound(r);
        return distance(left, right);
    }
    
    // 获取范围内的所有点
    vector<int> getPointsInRange(int l, int r) {
        vector<int> result;
        auto left = points.lower_bound(l);
        auto right = points.upper_bound(r);
        
        for (auto it = left; it != right; ++it) {
            result.push_back(*it);
        }
        return result;
    }
};

示例3：最近邻查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 在有序集合中查找最近邻
pair<int, int> findNearest(set<int>& s, int target) {
    if (s.empty()) return {INT_MIN, INT_MIN};
    
    // 查找第一个 >= target 的元素
    auto it = s.lower_bound(target);
    
    int right = (it != s.end()) ? *it : INT_MIN;
    int left = (it != s.begin()) ? *prev(it) : INT_MIN;
    
    return {left, right};
}

int main() {
    set<int> s = {1, 4, 7, 10, 15};
    
    auto nearest = findNearest(s, 8);
    // nearest = {7, 10}，距离8最近的是7和10
    
    nearest = findNearest(s, 20);
    // nearest = {15, INT_MIN}，只有左邻居
}

总结

std::set 是 C++ 中功能强大的有序集合容器：

  1. 适用场景：需要元素唯一且有序的场景，如去重排序、范围查询、最近邻查找等

  2. 性能特点：

    • 所有操作 O(log n) 时间复杂度
    • 适合元素数量适中（数千到数百万）
    • 对最坏情况性能有保障

  3. 使用建议：

    • 优先使用 emplace() 而非 insert() 减少拷贝
    • 利用有序性进行范围查询和边界查找
    • 避免在遍历时直接修改元素
    • 根据需求选择 set 或 unordered_set

  4. 扩展学习：

    • multiset：允许重复元素的有序集合
    • map：键值对的有序映射
    • unordered_map：哈希映射

掌握 set 的用法能够极大提升处理有序唯一数据的能力，是 C++ 开发者的必备技能之一。