# 集合set

#include <set>

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

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

# 1. 常用方法

# 构造

set<类型, 比较器> st

  • 类型:要存储的数据类型
  • 比较器:比较大小使用的比较器,默认为less<类型>,可自定义
set<int,greater<int>> st2; //储存int的集合(从小到大)
set<int> stl;               // 储存int的集合(从大到小)
1
2

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

# 遍历

可使用迭代器进行遍历:

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

基于范围的循环(C++ 11):

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

# 其他

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

增删查时间复杂度为O(logn)O(\log n)

# 2. 适用情形

  • 元素去重:[1,1,3,2,4,4][1,2,3,4][1,1,3,2,4,4]\to[1,2,3,4]

  • 维护顺序:[1,5,3,7,9][1,3,5,7,9][1,5,3,7,9]\to[1,3,5,7,9]

  • 元素是否出现过:元素大小[1018,1018][-10^{18},10^{18}],元素数量10610^{6},vis数组无法实现,通过set可以完成。

    // 一般记录是否存在某个元素可用vis数组
    bool vis[100] = {false};
    vis[1] = true;  // 1存在
    
    //当元素比较多时:
    bool vis[1e19]; // 可能无法实现
    
    //此时可用set
    set<int> st;
    st.insert(1);
    if(st.count(1)) //用.count()判断
        cout << "yes";
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

# 3. 注意事项

# 不存在下标索引

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

cout << st[0];
1

# 元素可读

set的迭代器取到的元索是只读的(因为是 const 迭代器),不可修改其值如果要改,需要先 erase 再 insert下面是错误用法:

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

# 不可用迭代器计算下标

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

auto it = st.find(1);       //正确,返回2所在位置的迭代器
int idx = it -  st.begin(); //错误,不可相减得到下标
1
2
上次更新时间:: 2/16/2025, 12:37:58 AM