首页 > 编程笔记 > C++笔记 阅读：1

C++ std::set容器用法详解（附带实例）

在 C++ 标准模板库中，集合（set）是一个关联容器，使用红黑树作为底层数据结构实现。集合中的元素是唯一的，并且按照一定的顺序存储和访问。默认情况下，集合会以升序排序，但也可以通过提供自定义的比较函数来实现其他排序方式。

由于集合内部使用了红黑树，因此需要动态维护元素，且要求快速查找、删除和添加元素的场景中非常有用。例如，如果需要确保集合中没有重复元素，并且需要频繁地进行插入、删除和查找操作，那么使用集合是一个理想的选择。

C++ set的结构

集合提供了一种高效且便捷的方式管理一个有序且唯一的元素集合。如下图所示，集合的结构可以简单理解为一个数学意义上的集合，用户无须深入理解其内部的树形结构。


图 1 集合的结构

这意味着，只需将集合视为一个自动排序且不含重复元素的容器即可。

C++ set的初始化

在使用集合之前，需要引入头文件 <set>。如果已经包含万能头文件 <bits/stdc++.h> ，则无须再次引入。 
#include <set>
// #include <bits/stdc++.h>        // 万能头文件中包含集合头文件
using namespace std;               // 集合在std命名空间中

要声明一个集合，可以使用以下代码： 
set<T> mySet; // T可以是int、double、char等基本数据类型，也可以是自定义的结构体
需要注意的是，当使用自定义结构体作为集合的元素数据类型时，必须重载小于号（<）运算符，或者创建一个自定义比较类并重载 () 运算符。这是因为集合内部使用红黑树来维护元素的顺序，而红黑树的实现依赖于元素的比较操作。

通常情况下，我们只需要声明一个空的集合，然后通过插入操作向其中添加元素。例如： 
set<int> mySet;   // 创建一个整数集合mySet
mySet.insert(1);  // 向集合中插入元素1
mySet.insert(2);  // 向集合中插入元素2
mySet.insert(3);  // 向集合中插入元素3

示例程序： 
#include <set>
#include <iostream>
using namespace std;
using ll = long long;

// 定义结构体 Node，包含两个整数 x 和 y，并重载小于（<）运算符
struct Node {
    int x, y;
    bool operator<(const Node &u) const {
        return x == u.x ? y < u.y : x < u.x;
    }
};

// 定义比较类 cmp，重载 () 运算符，将比较符号改为大于号，即产生一个小根堆
struct cmp {
    bool operator()(const int u, const int v) const {
        return u > v;
    }
};

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    // 声明一个以结构体 Node 为类型的集合
    set<Node> st;

    // 声明一个以 int 为类型、cmp 为比较类的集合
    set<int, cmp> st_int;

    // 向 st 中插入元素
    for (int i = 1; i <= 5; ++i) {
        st.insert({i, 2 * i});   // 使用花括号构造 Node
        st_int.insert(i);        // 向 st_int 中插入元素
    }

    // 输出 st 中的元素
    for (const auto &i : st)
        cout << i.x << ' ' << i.y << '\n';

    // 输出 st_int 中的元素
    for (const auto &i : st_int)
        cout << i << '\n';

    return 0;
}
运行结果为：

1 2
2 4
3 6
4 8
5 10
5
4
3
2
1

C++ set集合的基本操作

集合是一种关联容器，用于存储唯一对象的集合。当把对象插入集合中时，集合会按照一定的顺序（默认为升序）自动排序，并确保每个对象只出现一次。下表列出了集合的一些常用操作及其时间复杂度。

表：集合常用操作方法及其时间复杂度
方法 作用 时间复杂度
insert(x) 将元素插入集合中 O(log n)
erase(it or val) 从集合中删除指定元素，可以传入一个迭代器或一个值 O(log n)
clear() 清空集合中的所有元素 O(n)
find(x) 返回 x 在集合中的位置（迭代器），如果 x 不存在，则返回 end() O(log n)
count(x) 返回 x 在集合中出现的次数，返回值仅为 0 或 1 O(log n)
size() 返回集合中的元素个数 O(1)
empty() 判断集合是否为空，若为空，则返回 true，否则返回 false O(1)
begin() 返回指向集合中第一个元素的迭代器 O(1)
end() 返回指向集合中最后一个元素的下一个位置的迭代器 O(1)

此外，集合还支持其他一些高级操作，例如 lower_bound()、upper_bound() 等，这些高级操作允许执行更复杂的搜索和遍历功能，例如查找某个值的下界和上界，时间复杂度同样为 O(logn)。

请注意，调用 erase() 函数并传入迭代器时，必须确保该迭代器是有效的。如果迭代器无效，会导致程序陷入无限查找状态，进而产生运行时错误（RE）或超时错误（TLE）。

以下为包含错误的示例代码： 
#include <set>
#include <iostream>
using namespace std;
using ll = long long;

const int N = 2e5 + 9;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 声明一个以 int 为类型的集合
    set<int> st;

    // 插入一些元素
    for (int i = 1; i <= 5; ++i)
        st.insert(i);

    // 此处的循环存在逻辑错误
    // 当 i = 6 时，调用 st.begin() 已经返回非法迭代器
    for (int i = 1; i <= 6; ++i)
        st.erase(st.begin());

    // 输出集合中的剩余元素
    for (const auto &i : st)
        cout << i << '\n';

    return 0;
}
程序陷入死循环，导致超时错误（TLE）。

在上述代码中，当 i=6 时，集合已经被完全清空，此时 st.begin() 返回的迭代是非法的，试图使用它会导致运行时错误。

确保 erase() 操作时集合不为空，例如将第二个 for 循环中的 6 改为小于或等于集合的初始大小，这样可以避免非法迭代器的访问，程序将正常运行。

C++ set实际应用

【实例】排序去重问题。给定一个大小为 n 的数组 a，请将 a 中元素去重后，从小到大排序输出。

输入格式：
第一行包含一个整数T，表示测试样例的数量（1≤T≤100）。

对于每一个测试样例：
输出格式：
对于每个测试样例，输出一行去重排序后的结果。

样例：


解题思路：可以使用两种方法来解决：使用向量配合 sort、erase 和 unique 函数；使用集合来解决（集合内部自动排序去重）。这两种方法的时间复杂度相同。

实现方案一： 
#include <bits/stdc++.h>
using namespace std;

// 定义一个函数，用于处理输入并输出去重后的有序数组
void solve() {
    int n;                      // 定义一个整数变量 n，用于存储输入的数组长度
    cin >> n;                   // 从标准输入读取数组长度

    vector<int> v;              // 定义一个整数向量 v，用于存储输入的数组元素
    for (int i = 1; i <= n; ++i) {   // 循环读取 n 个整数
        int x;                  // 定义一个整数变量 x，用于存储当前读取的整数
        cin >> x;               // 从标准输入读取整数 x
        v.push_back(x);         // 将整数 x 添加到向量 v 中
    }

    sort(v.begin(), v.end());                           // 对向量 v 进行排序
    v.erase(unique(v.begin(), v.end()), v.end());       // 去除向量 v 中的重复元素

    for (auto i : v) cout << i << ' ';  // 遍历向量 v 并输出每个元素，用空格分隔
    cout << '\n';                       // 输出换行符，表示一行结束
}

// 主函数，程序入口
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);          // 优化输入/输出性能

    int t;                      // 定义一个整数变量 t，用于存储测试用例的数量
    cin >> t;                   // 从标准输入读取测试用例的数量
    while (t--) solve();        // 对于每个测试用例，调用 solve 函数进行处理

    return 0;                   // 程序正常结束，返回 0
}

实现方案二： 
#include <bits/stdc++.h>
using namespace std;

// 定义一个函数，用于处理输入并输出去重后的有序数组
void solve() {
    int n;              // 定义一个整数变量 n，用于存储输入的数组长度
    cin >> n;           // 从标准输入读取数组长度

    set<int> st;        // 定义一个整数集合 st，用于存储不重复的元素

    for (int i = 1; i <= n; ++i) {   // 循环读取 n 个整数
        int x;          // 定义一个整数变量 x，用于存储当前读取的整数
        cin >> x;       // 从标准输入读取整数 x
        st.insert(x);   // 将整数 x 添加到集合 st 中
    }

    // 遍历集合 st 并输出每个元素，用空格分隔
    for (auto i : st) cout << i << ' ';
    cout << '\n';       // 输出换行符，表示一行结束
}

// 主函数，程序入口
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);  // 优化输入/输出性能

    int t;              // 定义一个整数变量 t，用于存储测试用例的数量
    cin >> t;           // 从标准输入读取测试用例的数量
    while (t--) solve(); // 对于每个测试用例，调用 solve 函数进行处理

    return 0;           // 程序正常结束，返回 0
}

相关文章