# 集合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
2
对于需要自定义比较器的情况,涉及一些初学时容易看迷糊的语法(重载小括号运算符/lambda 表达式),在此就不展开讲了。
# 遍历
可使用迭代器进行遍历:
for(set<int>::iterator it = st.begin(); it != st.end(); ++it)
cout << *it << endl;
1
2
2
基于范围的循环(C++ 11):
for( auto &ele : st)
cout << ele <<endl;
1
2
2
# 其他
作用 | 用法 | 示例 |
---|---|---|
插入元素 | .insert(元素) | st.insert(1); |
删除元素 | .erase(元素) | st.erase(2); |
查找元素 | .find(元素) | auto it = st.find(1); |
判断元素是否存在 | .count(元素) | st.count(3) |
查看大小/清空/判空 | 略 | 略 |
增删查时间复杂度为
# 2. 适用情形
元素去重:
维护顺序:
元素是否出现过:元素大小,元素数量,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
2
# 不可用迭代器计算下标
set的迭代器不能像vector一样相减得到下标,下面是错误用法:
auto it = st.find(1); //正确,返回2所在位置的迭代器
int idx = it - st.begin(); //错误,不可相减得到下标
1
2
2