STL--set

一：set的基本概念
基本功能：提供一个自动排序去重的容器
原理：其内部封装的对象为二叉树。
时间复杂度：O(log2N）

二：set的操作方法
1：定义与赋值

set<int>s1;
set<string>s2;
set<vector<int> >s3;
set<pair<int,double> >s1;

三：常用的函数方法与操作
常用的一些函数方法1
（1）begin（） 返回set容器第一个元素的迭代器
（2）end（） 返回一个指向当前set末尾元素的下一位置的迭代器.
（3）clear（）删除set容器中的所有的元素
（4）size()返回当前set容器中的元素个数
（5）empty（）判断set容器是否为空

例如：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    set<int> st;
    st.insert(1);
    st.insert(10);
    st.insert(7);
    st.insert(10);
    set<int>::iterator it;
    for(it=st.begin();it!=st.end();it++)
    {
        cout<<*it<<endl;
     } 
     cout<<st.size()<<endl;
     st.clear();
     if(st.empty()==true)cout<<"yes"<<endl;
    return 0;
} 

输出的结果

常用的函数方法2
rbegin()返回的值和end()前一个元素相同 但属于迭代器
rend() 返回的值和begin()后一个元素相同 但属于迭代器
max_siaze() 返回set容器可能包含的元素最大个数(最多放多少个元素)
count()用来查找set中某个某个键值出现的次数。即判断某一键值是否在set出现过了。
例如：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    set<int> st;
    st.insert(1);
    st.insert(10);
    st.insert(7);
    st.insert(10);
    set<int>::reverse_iterator rit;
    cout<<st.max_size()<<endl;
    for(rit=st.rbegin();rit!=st.rend();rit++)
    {
        cout<<*rit<<endl;//反向遍历 
     } 
     cout<<st.count(7)<<" "<<st.count(2)<<endl;
     cout<<"size="<<st.size()<<endl;
    return 0;
} 

运行结果：

常用函数方法3：
(1)insert（） 添加
(2)erase() 删除
(3)find() 查找
(4)lower_bound() 返回第一个大于等于key_value的定位器
(5)upper_bound() 返回最后一个大于等于key_value的定位器
(6)equal_range()返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，
这个返回值是一个pair类型

例如：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    set<int> st;int n=1;
    int num[10]={1,2,3,4,5,6,7,8,9,10};
    st.insert(1);
    st.insert(10);
    st.insert(num+2,num+6);
    set<int>::iterator it;
    for(it=st.begin();it!=st.end();it++)
    {
        cout<<"第一组"<<*it<<endl; 
     } 
     st.erase(2);
     st.erase(st.begin());
     set<int>::iterator imt=st.begin();
     while(n--)imt++;
     st.erase(st.begin(),imt);
    for(it=st.begin();it!=st.end();it++)
    {
        cout<<"第二组"<<*it<<endl; 
     } 
     set<int>::iterator iter;
     if((iter=st.find(7))!=st.end())
     {
     cout<<*iter<<endl;
     }

     cout<<*st.lower_bound(6)<<endl;//第一个大于大于6的数 
     cout<<*st.upper_bound(6)<<endl;//最后一个大于等于6的数 

     pair<set<int>::const_iterator,set<int>::const_iterator>pr;
     pr = st.equal_range(4);
    cout<<"第一个大于等于4的数是"<<*pr.first<<endl;
    cout<<"第一个大于4的数是"<<*pr.second<<endl;
    return 0;
} 
} 

输出的结果：

四.自定义重载运算符

struct myComp  
{  
    bool operator()(const your_type &a,const your_type &b)  
    {  
        return a.data-b.data>0;  
    }  
}  
set<int,myComp>s;  

set<int,myComp>::iterator it;  
(2)如果元素是结构体，可以直接将比较函数写在结构体内。
[cpp] view plain copy


struct Info  
{  
    string name;  
    float score;  
    //重载“<”操作符，自定义排序规则  
    bool operator < (const Info &a) const  
    {  
        //按score从大到小排列  
        return a.score<score;  
    }  
}  
set<Info> s;  
......  
set<Info>::iterator it;  

参考引用：
set用法详解

acm在线模板