stl-set

1、 set的概念

set翻译为集合，是一个内部有序且不含重复元素的容器，可用于删除重复元素的题目。

2、 set的基本操作

头文件#include<set>

set<typename> s;定义一个set;

s.insert(x);将x插入set容器中，并自动排序和去重 O（logN）//注意此时间复杂度，非O（1），插入后需要排序

s.find(value);返回set中对应值为value的迭代器 ,找不到则返回s.end(); O（logN）

s.size();获得set内元素的个数 O（1）

s.clear();清空set中所有的元素 O（N）

s.count(value);判断元素是否存在，存在返回1，不存在返回0 O(nlogn)

s=st;类型相同时可以将st直接赋值给s；

3、 元素的删除

因为元素的唯一性，参数既可以是迭代器，也可以是value,但是时间复杂度不一样，value需要先查找此元素

s.erase(it);删除单个元素 O(1)

s.erase(value);删除单个元素 O（logn）

s.erase(it1,it2)删除区间内元素 O（it1-it2）

set map等非线性容器内，删除此元素后迭代器不再存在，可以it=s.erase(it);指向下一个迭代器

4、 set元素的访问

set中元素只能通过迭代器（正向和反向）访问，且迭代器只能进行it++;it—操作；

只有vector和string支持*（it+i）的操作

5、set内元素的排序（map与此类似）

     Set默认从小到大排序，可以自己更改排序规则

     最简单的更改方式：

     Set<typename,greater<typename>> s;构建从大到小排序的set;也可以自己写伪函数，类似于下列结构体的排序规则；

  

当set中存的是结构体的时候，set不会自动排序，这时候需要自己重载运算符；

两种重载运算符规则如下：

#include<iostream> #include<set> using namespace std; struct node { int x; /*friend bool operator<(const node &a,const node &b) { return a.x<b.x;从小到大 }结构体外重载*/ }s[10]; /*bool operator<(const node &a,const node &b) { return a.x>b.x;从大到小 } 结构体外重载*/ int main() { set<node> st; set<node>::iterator it; for(int i=0;i<5;i++) s[i].x=i, st.insert(s[i]); for(it=st.begin();it!=st.end();it++) { cout<<it->x<<"　"; //it->x相当于（*it）.x；注意->的优先级大于* } }自己写伪函数更改运算规则（自己注意格式）

#include<iostream> #include<set> using namespace std; struct node { int x; }s[10]; struct cmp { bool operator()(const node &a,const node &b)//const保证此作用域中不更改，&表示引用，运算更快，int char longlong不需要引用 { return a.x>b.x; } }; int main() { set<node,cmp> st; set<node>::iterator it; for(int i=0;i<5;i++) s[i].x=i, st.insert(s[i]); for(it=st.begin();it!=st.end();it++) { cout<<it->x<<"　"; //it->x相当于（*it）.x；注意->的优先级大于* } }