set学习笔记
2023-01-30 18:43:04
set 是一个有序集合，具有互异性
STL 的 set 集合用二叉树实现的，集合中的每个元素只出现一次，并且是排好序的（默认按键值升序排列），访问元素的时间复杂度是 $O(\log_2n)$
```c++
set<int> s; // 以int型为例 默认按键值升序
set<int,greater<int>> s; // 降序排列
s.insert(x); // 将x插入
s.erase(x); // 删除x元素,返回0或1,0表示set中不存在
s.clear(); // 清空
s.empty(); // 判断是否为空，若是返回1，否则返回0
s.size(); // 返回元素的个数
s.find(x); // 查找x，返回x的迭代器，若x不存在，则返回指向q尾部的迭代器即 s.end()
s.lower_bound(x); // 返回一个迭代器，指向第一个键值不小于x的元素
s.upper_bound(x); // 返回一个迭代器，指向第一个键值大于x的元素
s.rend(); // 返回第一个元素的的前一个元素迭代器
s.begin(); // 返回指向第一个元素的迭代器
s.end(); // 返回指向q最后一个元素下一个位置的迭代器
s.rbegin(); // 返回最后一个元素
```
_注：lower\_bound 和 upper\_bound 不是 set 特有的。_
```cpp
#include <iostream>
#include <set>
using namespace std;
set<int > s;
void print(){
for(auto it = s.begin(); it != s.end(); it++){
cout << *it << " ";
}cout << endl;
}
int main() {
s.insert(1);
s.insert(4);
s.insert(2);
cout << "lower_bound " << *q.lower_bound(2) << endl; //返回2
cout << "upper_bound " << *q.upper_bound(2) << endl; //返回4
print(); //有序的
//因为 set 是有序的，所以给一个下标插入是无意义的
s.insert(s.begin(),5);
print();
s.clear(); //清除
s.insert(2);
s.insert(2);
s.insert(2);
s.insert(2);
s.insert(2);
print(); //互异的
return 0;
}
```
删除数据
```cpp
#include <iostream>
#include <set>
using namespace std;
set<int > s;
void print(){
for(auto it = s.begin(); it != s.end(); it++){
cout << *it << " ";
}cout << endl;
}
int main() {
s.insert(1);
s.insert(4);
s.insert(2);
print();
s.erase(s.begin()); //可以给定下标删除
print();
s.insert(1);
s.erase(2); //因为没有重复的，可以直接给定内容删除
print();
return 0;
}
```