~set~
set可能算是一种比较冷门的STL容器了,
喜欢用它的人觉得set真牛逼
不喜欢它的人觉得set真垃圾
很不幸,我属于第一种
set作为一种封装好的数据容器
最吸引人的地方是它的自动排序功能
这也就是说你可以拥有一个实时的排好序的序列
或者可以用一个序列同时实现大根堆和小根堆
时间复杂度和空间都是两者和的1/2
善于运用set的自动排序特性可以为解题省去不少麻烦
啊就爽,就很爽。
继承STL容器的传统
set也有它自己专属的头文件 <set>
这个头文件内包含两种容器
set和multiset
set是自动排序还附带去重的序列(有序集合),其中的元素不可重复
multiset是自动排序不去重的序列(有序多重集),其中可以有许多相同的元素
个人感觉在实际OI问题中比较常用的是multiset这种不去重的
两者的实现原理都是一颗我不会打的红黑树,它们支持的函数基本相同
步入正题
首先我们来看一下怎么声明一个set和multiset并往其中插入元素
#include <iostream> #include <set> using namespace std; struct Node { int l, r, val; }; bool operator <(const Node &a, const Node &b) { return a.val < b.val; } int main() { set<int> p;//声明方式与其他容器并无太大差异 multiset<int> q; set<Node> fuc;//压入set的东西类型必须定义"<" }
当然,你也可以这么写(友元版)
#include <iostream> #include <set> using namespace std; struct Node { int l, r, val; bool friend operator <(const Node &a, const Node &b) {return a.val < b.val;} set<Node> fuc; }; int main() { set<int> p; multiset<int> q; }
这样就完成了以普通数据类型和结构体的sethemultiset的声明
同时切记:set和multiset内的数据类型必须已定义小于号
学完了声明就该学如何往容器内插入元素
(size函数,empty函数,clear函数在set中也有,与在vector中作用无异,故此处不提)
与vector不同,往set内插入元素不需要指定位置
元素进入set后自动根据“<”的定义找到自己的位置
set和multiset都使用insert函数插入元素
时间复杂度为O(logn)
代码如下
#include <iostream> #include <set> using namespace std; int x; int main() { set<int> p; multiset<int> q; int n; cin>>n; for(int i = 1; i <= n; i++) { cin>>x; q.insert(x); p.insert(x); } }
如此即可实现向set p和multiset q中插入n个元素
插入完元素后我们可以对这些元素进行操作
首先需要注意的是set不支持随机访问
也就是说不能通过下标的方式访问set中的元素
想想也很好理解,即使这货能用下标你也不知道排完序后哪个元素是哪个
所以set给了我们与之替代的两种数据查找方式
迭代器(可以理解为STL的指针)和find函数
set的迭代器声明方式与在vector中的声明方式无异
同样是声明一个名为it的迭代器
有set<int>::iterator it;
如果++it,
则it指向set中的下一个元素
因为set是有序集合,所以++it所表示的元素就是刚好比it所指向的元素大的第一个元素
同时set也有begin和end函数用来取队首和队尾(的迭代器)
begin在set中取的是最小元素的迭代器
end函数跟vector中一样返回队尾下个元素的迭代器
所以--end()表示的是队尾元素的迭代器
我们看一段遍历set的代码来帮助我们理解这些抽象的概念
#include <iostream> #include <set> using namespace std; int main() { set<int> a; multiset<int> b; a.insert(1); a.insert(2); a.insert(3); a.insert(1); b.insert(1); b.insert(2); b.insert(3); b.insert(1); cout<<"set 中的元素依次是 "; for(set<int>::iterator it = a.begin(); it != a.end(); it++) cout<<*it<<" "; cout<<endl; cout<<"multiset 中的元素依次是 "; for(multiset<int>::iterator it = b.begin(); it != b.end(); it++) cout<<*it<<" "; cout<<endl; return 0; }
程序输出结果是
set 中的元素依次是 1 2 3 multiset 中的元素依次是 1 1 2 3
在这个例子中我们可以了解到set中迭代器的用法和set与multiset的本质区别
有助于我们搞明白并在程序上实现set的基本操作
了解了迭代器
我们再来看看我认为能与迭代器平起平坐帮了大忙的find函数
find函数能够找到set中大小为x的元素并返回指向该元素的迭代器。
如果set中并不存在元素x则返回s.end()
x 多次出现则返回第一次出现时的迭代器
样例如下
#include <iostream> #include <set> using namespace std; int main() { set<int> p; multiset<int> q; p.insert(1); p.insert(2); p.insert(3); p.insert(1); q.insert(1); q.insert(2); q.insert(3); q.insert(1); int a = *p.find(1); int b = *q.find(3); cout<<a<<" "<<b<<endl; return 0; }
聪明的你已经看出来了
我这么写返回的一定是要查找的那个数
其实就是没屁用
啊就有的题可能会出现需要用到find函数的地方(装不下去了)
在实际应用中,我们需要对不需要的元素进行删除
set给了我们一个强大的数据删除函数erase()
括号内既可以是一个迭代器
erase删除这个迭代器所指的元素
括号内也可以是个值或者啥东西
erase在set或multiset中查找并删除和括号内这个东西一样的全部元素
那问题来了
在用multiset解决实际问题时
很多情况下我们并不想把所有相同的元素都删除
只想删除一个两个或几个(erase说没门儿
此时find函数突然出现
“劳资返回的是迭代器hahahahaha”
于是你就可以用find函数定位到元素x第一次出现的位置并返回此时的迭代器
再用erase通过迭代器删除的功能删除这个x
由于multiset恒为有序所以删除哪个x无关紧要
反正修改后的multiset都一样
所以我们就解决了这个问题(find函数大放异彩)