STL整理之set

_**转载请注明出处，部分内容引自李煜东《算法竞赛进阶指南》**_ ------------ ## 前置知识： $C++$、$C$语言入门 ------------ ## $Set$是什么 #### $Set$是$C++STL$中提供的容器，$set$是数学上的集合——具有唯一性，即每个元素只出现一次，而$multiset$则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同 ---------- ## $Set$的相关操作 ### 头文件 ``` #include<set> ``` ### 声明： 像这样： ``` set<类型>名称； ``` 比如： ``` set<int>s; set<vector<int> >s; //vector中提供重载< set<set<int> >s; //平衡树嵌套，哈哈 multiset<double>s; ``` 就像其他需要排序的数据类型一样，为一个结构体的$set$，需要重载小于号 ``` struct node{ ......; }; set<node>s; bool operator <(const node &ai,const node &bi) { return ai.x>bi.x; } ``` ### $set.size()$ 统计$set$中元素个数，函数返回一个整形变量，表示$set$中元素个数，时间复杂度O(1) ``` 用法：名称.size(); eg. int num=s.size(); ``` ### $set.empty()$ 检查$set$是否为空，返回一个$bool$型变量，1表示$set$为空，否则为非空，时间复杂度$O(1)$ ``` 用法：名称.empty(); eg. if(s.empty()) cout<<"Myset is Empty."<<endl; ``` ### $set.clear()$ 清空$set$，无返回值 ``` 用法：名称.clear(); eg. s.clear(); ``` ### $set.count(x)$ 返回$set$或$multiset$中值为$x$的元素个数，时间复杂度为$O(log n+ans)$ ``` 用法：名称.count(x) eg. if(!s.count(x)) ans++; ``` ### 迭代器 #### 双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持“++”，“--”这两个算术操作 引用和操作： ``` set<类型>::iterator it; eg. set<int>::iterator it=s.begin(); it++; it--; ``` 若把$it++$，则$it$将会指向“下一个”元素。这里的下一个是指在$key$从小到大排序的结果中，排在$it$下一名的元素。同理，若把$it--$，则$it$会指向排在上一个的元素 “++”，“--”操作的复杂度均为$O(log n)$ #### 遍历$set$及访问其中的元素 ``` //set for(set<int>::iterator it=s.begin();it!=s.end();it++) cout<<*it<<endl; //取出这个迭代器指向的元素 //set嵌套 for(set<set<int> >::iterator it=s.begin();it!=s.end();it++) { //首先取出set中嵌套的set for(set<int>::iterator rit=(*it).begin();rit!=(*it).end();rit++) cout<<*rit<<' '; //遍历这个set cout<<endl; } ``` ### $set.begin()$ 返回集合的首迭代器，即指向集合中最小元素的迭代器，时间复杂度为$O(1)$ ``` 用法：名称.begin(); eg. set<int>::iterator it=s.begin(); ``` ### $set.end()$ 返回集合的尾迭代器，众所周知，STL中区间都是左闭右开的，那么$end()$函数返回的迭代器即为指向集合中最大元素的下一个位置的迭代器，因此$--s.end()$才是指向集合中最大元素的迭代器，时间复杂度为$O(1)$ ``` 用法：名称.end(); eg. maxn=*(--s.end()); //取出最大元素 ``` ### $set.insert(x)$ 在$set$中插入元素，返回插入地址的迭代器和是否插入成功的$bool$并成的$pair$，时间复杂度为$O(log n)$ PS：$set$在进行插入的时候是不允许有重复的键值的，如果新插入的键值与原有的键值重复则插入无效（$multiset$可以重复） ``` 用法：名称.insert(set类型); eg. s.insert(3); ``` ### $set.erase($参数$)$ 删除，参数可以是元素或者迭代器，返回下一个元素的迭代器，时间复杂度为$O(log n)$，注意在$multiset$中$s.erase(x)$会删除所有值为$x$的元素 ``` 用法：名称.erase(参数); eg. set<int>::iterator it=s.begin(); s.erase(it); s.erase(3); ``` ### $set.find(x)$ 在$set$中查找值为$x$的元素，并返回指向该元素的迭代器，若不存在，返回$set.end()$，时间复杂度为$O(log n)$ ``` 用法：名称.find(x); eg. if(s.find(x)!=s.end()) cout<<"Have Found!"<<endl; ``` ### $set.lower$_$bound(x)/upper$_$bound(x)$ 两个神奇的东西，决定把他们放在一块谈一谈 用法与$find$类似，但查找的条件略有不同，时间复杂度$O(log n)$ $s.lower$_$bound(x)$表示查找$>=x$的元素中最小的一个，并返回指向该元素的迭代器 $s.upper$_$bound(x)$表示查找$>x$的元素中最小的一个，并返回指向该元素的迭代器 #### 举个例子： 在$set${$3,5,7,8,13,16$}中 对于在$set$中存在的元素，比如8 $s.lower$_$bound(8)$返回8所在位置的迭代器 $s.upper$_$bound(8)$返回13所在位置的迭代器 对于在$set$中不存在的元素，比如12 两个函数返回的则都是13所在位置的迭代器 #### 特殊地， 对于比$set$中最大的元素大的元素，比如20 两个函数返回的都是$s.end()$