集合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的集合(从大到小)

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法(重载小括号运算符/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)
查看大小/清空/判空	略	略

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

2. 适用情形

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

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

• 元素是否出现过：元素大小$[-10^{18},10^{18}]$，元素数量$10^{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";
  

3. 注意事项

不存在下标索引

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

cout << st[0];

元素可读

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

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

不可用迭代器计算下标

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

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