17370845950

set是C++ STL基于红黑树实现的有序去重关联容器，支持O(log n)插入/查找/删除，默认升序；不可下标访问或修改元素，可自定义排序规则，重复插入无效。

set 是 C++ STL 中的关联容器，底层通常基于红黑树实现，它天然支持自动排序和元素去重，插入、查找、删除时间复杂度均为 O(log n)。

set 的基本用法与自动排序

定义一个 set 后，所有插入的元素会按升序自动排列（默认使用 std::less 比较规则）。无需手动调用 sort，也不用担心顺序问题。

示例：

#include 
#include 
using namespace std;

int main() {
    set s;
    s.insert(5);
    s.insert(1);
    s.insert(8);
    s.insert(1); // 重复插入，无效

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

set 的去重机制

set 不允许重复元素。相同值的多次 insert 只保留一个；尝试插入已存在的元素时，操作被忽略，且返回一个 pair，其中 second 表示是否成功插入。

常用判断方式：

• auto ret = s.insert(x); → ret.second 为 true 表示新元素插入成功
• s.find(x) != s.end() 判断是否存在
• s.count(x) 返回 0 或 1（注意：对 set 来说 count 效率不如 find）

自定义排序规则（降序或结构体）

可通过传入比较函数对象改变默认升序行为。例如实现降序：

set> s_desc; // 降序
s_desc.insert(3); s_desc.insert(1); s_desc.insert(4);
// 遍历输出：4 3 1

对结构体排序需提供仿函数或 lambda（C++20 起支持直接用 lambda 声明，但需注意生命周期）：

struct Person {
    string name;
    int age;
};
struct CompareByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age; // 按年龄升序
    }
};
set people;

常见操作与注意事项

• 不能通过下标访问（s[0] 非法），只能用迭代器遍历或 find 查找
• 元素是 const 的：迭代器解引用后不可修改（*it = 10 编译报错），如需修改应先 erase 再 insert
• 清空用 s.clear()，判空用 s.empty()，大小用 s.size()
• 若需保留重复元素，改用 multiset；若需哈希无序去重，改用 unordered_set