C++中Set容器的使用与技巧

C++中set是基于红黑树的关联容器，自动排序且元素唯一，支持O(log n)的插入、删除和查找。1. 基本操作包括insert、erase、find、size和empty，重复插入无效；2. 可通过greater或自定义比较结构体实现降序或结构体排序；3. 提供lower_bound、upper_bound和equal_range用于高效范围查询；4. 使用建议：考虑unordered_set提升性能、批量插入优化、避免频繁size调用、优先使用范围for遍历。熟练掌握set可高效处理有序去重数据。

在C++中，set 是一种关联式容器，用于存储唯一且自动排序的元素。它基于红黑树实现，插入、删除和查找操作的时间复杂度为 O(log n)。掌握 set 的基本用法和一些实用技巧，能显著提升代码效率和可读性。

1. 基本操作与初始化

set 会自动对元素进行升序排列，并去除重复值。常用操作包括插入、删除、查找和遍历。

• 插入元素： 使用 insert() 方法，重复插入无效（不会覆盖，也不会报错）
• 删除元素： 使用 erase()，可传值或迭代器
• 查找元素： 使用 find()，返回迭代器，未找到则返回 end()
• 判断是否为空： empty()
• 获取大小： size()

示例代码：

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

int main() {
    set<int> s;
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(5); // 重复，不插入

    cout << "Size: " << s.size() << endl; // 输出 3

    if (s.find(3) != s.end()) {
        cout << "Found 3" << endl;
    }

    s.erase(1);
    for (int x : s) {
        cout << x << " "; // 输出：3 5
    }
    return 0;
}

2. 自定义排序规则

默认情况下，set 按升序排列。可以通过提供比较函数来改变排序方式，比如降序或自定义结构体排序。

例如，让 set 按降序排列：

set<int, greater<int>> s;
s.insert(3);
s.insert(1);
s.insert(4);
for (int x : s) {
    cout << x << " "; // 输出：4 3 1
}

对于结构体，需重载比较运算符或提供仿函数：

struct Person {
    string name;
    int age;
};

struct cmp {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age; // 按年龄升序
    }
};

set<Person, cmp> people;
people.insert({"Alice", 25});
people.insert({"Bob", 20});

3. 多种查找与范围操作

除了 find，set 还提供 lower_bound 和 upper_bound，适用于高效范围查询。

• lower_bound(x)： 找到第一个 ≥ x 的元素
• upper_bound(x)： 找到第一个 > x 的元素
• equal_range(x)： 返回包含上下界的 pair

这些操作在处理区间问题时非常有用，比如统计某个范围内的元素个数：

set<int> s = {1, 3, 5, 7, 9};
auto it1 = s.lower_bound(4); // 指向 5
auto it2 = s.upper_bound(8); // 指向 9
// [it1, it2) 范围内的元素满足 4 ≤ x ≤ 8

4. 性能优化与使用建议

虽然 set 功能强大，但也有开销。以下是一些实用技巧：

• 如果不需要排序或唯一性，考虑使用 unordered_set（哈希表），平均 O(1) 查找
• 批量插入时，使用 insert({}) 一次性插入多个元素更高效
• 避免频繁调用 size()，某些实现中可能不是 O(1)
• 遍历时尽量使用 const_iterator 或范围 for 循环，简洁安全

例如批量插入：

s.insert({10, 20, 30, 40});

基本上就这些。熟练使用 set 能帮你快速处理去重和有序数据问题，结合自定义比较和范围查询，应对多数算法场景都游刃有余。

本文转载于：互联网 如有侵犯，请联系zhengruancom@outlook.com删除。
免责声明：正软商城发布此文仅为传递信息，不代表正软商城认同其观点或证实其描述。