2.6 集合 set

#include <set>

提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。

集合三要素 解释 set multiset unordered_set 确定性 一个元素要么在集合中，要么不在 ✔ ✔ ✔ 互异性 一个元素仅可以在集合中出现一次 ✔ ❌（任意次） ✔ 无序性 集合中的元素是没有顺序的 ❌（从小到大） ❌（从小到大） ✔

2.6.1 常用方法

构造 set<类型, 比较器> st

• 类型：要储存的数据类型
• 比较器：比较大小使用的比较器，默认为 less<类型>，可自定义

set<int> st1;               // 储存int的集合（从小到大）
set<int, greater<int>> st2; // 储存int的集合（从大到小）

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 / lambda 表达式），在此就不展开讲了。

遍历

可使用迭代器进行遍历：

for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;

基于范围的循环（C++ 11）：

for (auto &ele : st)
    cout << ele << endl;

其他

作用 用法 示例 插入元素 .insert(元素) st.insert(1); 删除元素 .erase(元素) st.erase(2); 查找元素 .find(元素) auto it = st.find(1); 判断元素是否存在 .count(元素) st.count(3); 查看大小 / 清空 / 判空 略 略 增删查时间复杂度均为

2.6.2 适用情形

1. 元素去重：
2. 维护顺序：
3. 元素是否出现过：元素大小 $[-10^{18}, 10^{18}]$，元素数量 $10^6$，vis 数组无法实现，通过 set 可以完成。

2.6.3 注意事项

不存在下标索引

set 虽说可遍历，但仅可使用迭代器进行遍历，它不存在下标这一概念，无法通过下标访问到数据。下面是错误用法：

cout << st[0] << endl;

元素只读

set 的迭代器取到的元素是只读的（因为是 const 迭代器），不可修改其值。如果要改，需要先 erase 再 insert. 下面是错误用法：

cout << *st.begin() << endl; // 正确。可读。
*st.begin() = 1;             // 错误！不可写！

不可用迭代器计算下标

set 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：

auto it = st.find(2);      // 正确，返回2所在位置的迭代器。
int idx = it - st.begin(); // 错误！不可相减得到下标。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com