C++set(详解)

1. 基本概念

• 定义：set是一种有序的、包含唯一元素的容器，它内部基于红黑树（一种自平衡二叉查找树）实现，这使得元素的插入、查找和删除操作都能在对数时间复杂度内完成。简单来说，它就像是一个自动帮你排好序且不允许有重复元素的 “盒子”，你可以往里面放各种类型的数据（只要这些数据支持比较操作）。
• 头文件：使用set需要包含<set>头文件，例如：#include <set>。

2. 常用操作

• 声明与初始化：
  • 可以声明一个空的set，例如：std::set<int> mySet;，这里声明了一个存储int类型元素的set。
  • 也可以在声明时进行初始化，如：std::set<int> anotherSet = {3, 1, 2};，初始化后的anotherSet中元素会按照从小到大的顺序自动排序，实际存储顺序为{1, 2, 3}。
• 插入元素：
  • 使用insert方法插入元素，例如：

std::set<int> mySet;
mySet.insert(5);
mySet.insert(3);

• 如果插入的元素已经存在于set中，那么这个插入操作会被忽略，因为set不允许有重复元素。比如再次插入5，set中的元素数量并不会增加。
• 查找元素：
  • 可以使用find方法来查找元素是否存在于set中，它返回一个迭代器指向被查找的元素，如果元素不存在，则返回指向set末尾的迭代器（通常用end()表示）。示例代码如下：

std::set<int> mySet = {1, 2, 3};
auto it = mySet.find(2);
if (it!= mySet.end()) {
    std::cout << "元素 2 存在于 set 中" << std::endl;
} else {
    std::cout << "元素 2 不存在于 set 中" << std::endl;
}

• 删除元素：
  • 使用erase方法删除元素，有几种不同的用法：
    • 通过指定元素的值来删除，例如：

std::set<int> mySet = {1, 2, 3};
mySet.erase(2);

这样就会把值为2的元素从set中删除。

• 通过迭代器来删除，例如：

auto it = mySet.find(3);
if (it!= mySet.end()) {
    mySet.erase(it);
}

先找到要删除元素对应的迭代器，然后用erase根据这个迭代器来删除元素。

• 遍历元素：
  • 可以使用迭代器来遍历set中的元素，常见的方式是通过for循环，如下所示：

std::set<int> mySet = {1, 2, 3};
for (auto it = mySet.begin(); it!= mySet.end(); ++it) {
    std::cout << *it << " ";
}
// 输出结果为：1 2 3

这里begin()返回指向set中第一个元素的迭代器，end()返回指向set末尾（最后一个元素之后的位置）的迭代器，通过不断递增迭代器并取出其指向的元素值，就可以遍历整个set。 

3. 特点和优势

• 有序性：元素总是按照特定的顺序（默认是从小到大，对于自定义类型可以通过重载比较运算符来指定顺序）存储在set中，这使得查找和遍历等操作都具有可预测的顺序，方便进行范围查找等操作。
• 唯一性：保证容器内不会出现重复的元素，这在很多场景下可以避免数据冗余，比如统计不同的数字出现的次数等应用场景中，使用set能自动过滤重复项。

4. 适用场景

• 去重：当你有一组数据，但希望得到其中不重复的元素集合时，set是很好的选择。例如，从一个包含重复整数的数组中提取出所有不同的整数。
• 排序与查找：如果需要对一些数据进行排序并快速查找其中某个元素是否存在，set基于红黑树的实现能提供高效的查找性能（时间复杂度为），像在一个单词集合中查找某个特定单词是否存在等场景就可以使用。

5. 自定义类型在 set 中的使用

如果要将自定义类型的对象放入set中，需要为该类型定义比较规则（通常是重载<运算符），因为set要根据这个比较规则来确定元素的顺序以及判断元素是否重复。例如：

class Person {
public:
    std::string name;
    int age;
    Person(const std::string& n, int a) : name(n), age(a) {}
};

// 重载 < 运算符，用于定义比较规则
bool operator<(const Person& p1, const Person& p2) {
    if (p1.name < p2.name) return true;
    if (p1.name == p2.name) return p1.age < p2.age;
    return false;
}

int main() {
    std::set<Person> peopleSet;
    peopleSet.insert(Person("Alice", 25));
    peopleSet.insert(Person("Bob", 30));
    return 0;
}

在上述代码中，通过重载<运算符为Person类定义了比较规则，这样就可以将Person类型的对象存入set中，并且set能按照定义好的规则来管理这些对象（排序和去重等）。

总之，C++ 中的set是一个非常实用的容器，在很多需要有序、去重的场景中都能发挥重要作用。

关于set的接口问题请点击下面博客链接

C++set的常用接口-CSDN博客