Algorithm20.2 STL set
[TOC]
STL - set
set基础语法整理博客：
https://www.luogu.com.cn/blog/communist/stl-zheng-li-zhi-set
set底层：红黑树
set关键字唯一性【类似于map中的key，只出现一次】：保证set中所有元素只出现一次
set序列递增性：如果不是int的话需要重载运算符
使用场景：维护一个不重复的数据结构 =》 类似于unique的结构【拓展延伸：可以维护一个结构体，然后来看是否重复】
multiset底层：红黑树
multiset关键字不唯一，可重复性
map与unordered_map VS set与multiset:
map有序，而unordered_map的无序性，但是两者都保持的是key唯一。
set唯一，而multiset不唯一，可重复，但是两者都保持的是有序。
basic
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a+i);
set<int> s(a+1, a+1+n);
auto iter = s.begin();
// 输出，发现保证了有序性
while (iter != s.end()) {
printf("%d ", *iter);iter++;
}
// 然后再插入新的元素，查看是否有去重复
cin>>t;
s.insert(t);
cout<<endl;
auto iter2 = s.begin();
while (iter2 != s.end()) {
printf("%d ", *iter2);iter2++;
} // 输出之后，发现已经去重了
return 0;
}
过程：输入4 1 3 2 4=》第一次输出为1 2 3 4，再输入2，在第二次输出还是1 2 3 4，set自动去重
查看和已有的最小差值之和
https://www.luogu.com.cn/problem/P2234
1、set.lowerbound() vs lowerbound
#include <iostream>
using namespace std;
#include <set>
set<int> s;
int n, t, ans;
int main() {
scanf("%d%d", &n, &ans);n--;
s.insert(192608170);
s.insert(-192608170);
s.insert(ans);
while (n--) {
scanf("%d", &t);
auto iter = s.lower_bound(t);auto iter2 = iter;
if (*iter != t) {
ans += min(abs(*(--iter2)-t), abs(*iter-t));
s.insert(t);
}
}
printf("%d\n",ans);
return 0;
}
利用set在序列中只出现一次+结构体重载来判断
题目大意：左右端点有重合的，就要被移除掉。问每一次拿出新的之后，
https://www.luogu.com.cn/problem/P2161
1、通过重载运算符来判重，可以利用set的比较来判断，判断规则就是利用小于号来判断，所以只需要重载一下小于号即可
struct node {
int l, r;
bool operator < (const node n) {return r < n.l;} // 所以此时看边界是否是这种关系，如果是的话就是小于，如果不是的话就是等于
}
2、搜索已经存在元素并且计数然后移除的方法：利用find函数，结合while循环，每次find到新的之后，就把当前iter的移除，并赋上find到的下一个元素的迭代器，然后再重复移除->赋值，直到最后找不到了，得到的是s.end()
auto iter = s.find()
while (iter!=s.end()) {
cnt++;
s.erase(iter);
iter = s.find(nw);
}
完整代码：
#include <iostream>
using namespace std;
struct node {
int l, r;
bool operator < (const node n) const {return r < n.l;}
};
int t, tl, tr;
char type[2];
#include <set>
set<node> s;
int main() {
scanf("%d", &t);
while (t--) {
int cnt = 0;
scanf("%s", type);
if (type[0] == 'A') {
scanf("%d%d", &tl, &tr);
node nw = (node){tl, tr};
// erase
auto iter = s.find(nw);
while (iter!=s.end()) {cnt++;s.erase(iter);iter = s.find(nw);}
s.insert({tl, tr});
printf("%d\n", cnt);
}else printf("%d\n", s.size());
}
return 0;
}