C++ set用法详解_C++ set去重原理与自定义排序规则

set通过红黑树实现自动排序与去重，插入、删除、查找时间复杂度为O(log n)，基于比较函数判断唯一性而非等于操作，支持自定义排序规则，适用于需有序无重复数据的场景。

在C++中，set 是一个非常实用的关联容器，位于 #include <set> 头文件中。它能够自动对元素进行排序，并保证元素的唯一性（即去重）。这使得 set 在处理需要有序且无重复数据的场景中非常高效。

set 基本特性

set 的底层通常由红黑树（一种自平衡二叉搜索树）实现，因此具备以下特点：

• 元素自动排序：插入后按升序排列（默认）
• 不允许重复元素：相同值只能存在一份
• 插入、删除、查找的时间复杂度为 O(log n)
• 不支持通过下标访问，需使用迭代器遍历

基本用法示例如下：

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

int main() {
    set<int> s;
    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(2); // 重复插入无效

    for (int x : s) {
        cout << x << " "; // 输出：2 5 8
    }
    return 0;
}

set 去重原理

set 能够去重，关键在于其插入逻辑。每次调用 insert() 时，set 会先通过比较函数查找是否存在相同值的节点。由于底层是二叉搜索树结构，查找过程基于“键值比较”。

立即学习“C++免费学习笔记（深入）”；

对于基本类型（如 int、double），set 使用默认的小于运算符 < 判断是否相等。两个元素 a 和 b 被认为“相等”，当且仅当：

这意味着只要 a 不小于 b，同时 b 也不小于 a，就视为相同元素，插入失败。这种机制避免了对 == 操作符的依赖，而是基于排序关系判断唯一性。

因此，即使你插入两个“数值相同”的元素，set 也会根据比较规则识别为重复项，从而实现去重。

v0.dev

Vercel推出的AI生成式UI工具，通过文本描述生成UI组件代码

261

查看详情

自定义排序规则

默认情况下，set 按升序排列。若想改变排序方式，比如降序或按自定义逻辑排序，可以通过提供比较函数或仿函数来实现。

以降序为例：

struct greater_cmp {
    bool operator()(const int& a, const int& b) const {
        return a > b;
    }
};

set<int, greater_cmp> s;
// 或使用标准库提供的 greater
// set<int, greater<int>> s;

s.insert(5);
s.insert(2);
s.insert(8);

for (int x : s) {
    cout << x << " "; // 输出：8 5 2
}

对于自定义类型（如结构体），必须显式提供比较规则：

struct Person {
    string name;
    int age;
    Person(string n, int a) : name(n), age(a) {}
};

struct cmp_person {
    bool operator()(const Person& a, const Person& b) const {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    }
};

set<Person, cmp_person> people;
people.insert(Person("Alice", 25));
people.insert(Person("Bob", 20));
people.insert(Person("Charlie", 25)); // 同龄但名字不同，仍可插入

注意：比较函数必须严格定义“严格弱序”（strict weak ordering），否则可能导致未定义行为。返回 true 表示第一个参数应排在第二个之前。

常见操作与技巧

除了 insert，set 还提供多种常用方法：

• find(x)：查找元素，返回迭代器，未找到则返回 end()
• count(x)：返回 0 或 1（因唯一性）
• erase(x)：删除指定值或迭代器指向的元素
• size()：元素个数
• empty()：判断是否为空

利用 find 可以判断某个值是否已存在：

if (s.find(5) != s.end()) {
    cout << "5 exists in set" << endl;
}

基本上就这些。掌握 set 的去重机制和自定义排序，能让你在去重+排序的一体化处理中游刃有余。关键是理解它依赖“比较函数”而非“等于判断”来实现唯一性，这也是其强大灵活性的来源。

以上就是C++ set用法详解_C++ set去重原理与自定义排序规则的详细内容，更多请关注php中文网其它相关文章！