set用法小结

set本质上是一棵红黑树，用法也就那么几个，插入删除lowerbound，再就是迭代器之类的

基本用法

begin()--返回指向第一个元素的迭代器

#include<cstdio>

#include<set>

int main()

{

    std::set<int>s;

    s.insert();

    s.insert();

    s.insert();

    printf("%d",*s.begin());

    //输出4

    return ;

}

begin()

end()--返回指向最后一个元素的迭代器

#include<cstdio>

#include<set>

int main()

{

    std::set<int>s;

    s.insert();

    s.insert();

    s.insert();

    printf("%d",*s.end());

    //注意这里的跌倒器指向的是一个空位置！

    //所以最好不要输出end()

    //输出末尾元素可以用下面的方法

    //std::set<int>::iterator it=s.end();

    //printf("%d",*--it);

    return ;

}

end()

rbegin()--返回指向集合中最后一个元素的反向迭代器

rend()--返回指向集合中第一个元素的反向迭代器

find()--返回一个指向被查找到元素的迭代器

insert()--在集合中插入元素

size()--集合中元素的数目

clear()--清除所有元素

#include<cstdio>

#include<set>

int main()

{

    std::set<int>s;

    s.insert();

    s.insert();

    s.insert();

    printf("%d\n",s.size());

    s.clear();

    printf("%d\n",s.size());

    return ;

}

clear()

count()--返回某个值元素的个数//主要应用于multiset

#include<cstdio>

#include<set>

int main()

{

    std::multiset<int>s;

    s.insert();

    s.insert();

    s.insert();

    printf("%d",s.count());

    return ;

}

count

empty()--如果集合为空，返回true

erase()--删除集合中的元素

erase可以删除给定的元素，也可以删除迭代器

在multiset中，删除给定的元素是全部删除，而删除迭代器只会删除一次，下面还会讲到

#include<cstdio>

#include<set>

int main()

{

    std::set<int>s;

    s.insert();

    s.insert();

    s.insert();

    s.erase();

    s.erase(s.find());

    if(s.find()==s.end()) printf("5 is not found\n");

    if(s.find()==s.end()) printf("4 is not found\n");

    if(s.find()!=s.end()) printf("6 is found");

      return ;

}

erase()

lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器

#include<cstdio>

#include<set>

int main()

{

    std::set<int>s;

    s.insert();

    s.insert();

    s.insert();

    printf("%d",*s.lower_bound());

    //输出为4

      return ;

}

lower_bound()

upper_bound()--返回大于某个值元素的迭代器

#include<cstdio>

#include<set>

int main()

{

    std::set<int>s;

    s.insert();

    s.insert();

    s.insert();

    printf("%d",*s.upper_bound());

    //输出为4

      return ;

}

upper_bound()

swap()--交换两个集合变量

#include<cstdio>

#include<set>

int main()

{

    std::set<int>s;

    std::set<int>a;

    s.insert();

    s.insert();

    a.insert();

    s.swap(a);

    printf("%d",s.size());

    //输出为1

      return ;

}

swap()

几个常用操作

正序遍历所有元素

这个需要借助迭代器来实现

set中是重载了迭代器的++和--运算符的，所以直接使用就可以了

#include<cstdio>

#include<set>

#define sit set<int>::iterator

using namespace std;

int main()

{

    set<int>s;

    for(int i=;i<=;i++)

        s.insert(i);

    for(sit i=s.begin();i!=s.end();i++)

        printf("%d ",*i);

    //输出1 2 3 4 5 6 7 8 9 10

    return ;

}

倒序遍历所有元素

可以使用rbegin和rend实现，他们与begin和end的关系如下图所示

#include<cstdio>

#include<set>

#define rsit set<int>::reverse_iterator

using namespace std;

int main()

{

    set<int>s;

    for(int i=;i<=;i++)

        s.insert(i);

    rsit it=s.rbegin();

    for(rsit i=s.rbegin();i!=s.rend();i++)

        printf("%d ",*i);

    //输出10 9 8 7 6 5 4 3 2 1

    return ;

}

multiset中删除元素

在multiset中，如果仅仅用erase($x$)来删除$x$元素，那么$x$的出现次数会变为$0$

解决方法是先找到$x$对应的迭代器，然后将迭代器删除，这样就可以使$x$只删除一次

#include<cstdio>

#include<set>

#define sit set<int>::iterator

using namespace std;

int main()

{

    multiset<int>s;

    s.insert();

    s.insert();

    s.insert();

    s.erase();

    printf("%d\n",s.count());

    s.insert();

    s.insert();

    s.insert();

    s.erase(s.find());

    printf("%d\n",s.count());

    //输出0 2

    return ;

}

自定义排序规则

如果元素不在结构体中，需要自定义结构体并重载“$()$”运算符

#include<cstdio>

#include<set>

#define sit set<int>::iterator

using namespace std;

struct comp

{

    bool operator ()(const int &a,const int &b)

    {

        return a>b;

    }

};

int main()

{

    set<int,comp>s;

    for(int i=;i<=;i++)

        s.insert(i);

    for(sit i=s.begin();i!=s.end();i++)

        printf("%d ",*i);

    //输出10 9 8 7 6 5 4 3 2 1

    return ;

}

若元素在结构体中，则需要重载$<$运算符

#include<cstdio>

#include<set>

#define sit set<node>::iterator

using namespace std;

struct node

{

    int l,r;

    node(int l=,int r=):l(l),r(r){};

    bool operator < (const node &a) const

    {

        return r==a.r?l<a.l:r<a.r;

    }

};

int main()

{

    set<node>s;

    for(int i=;i<=;i++)

        s.insert(node(i,-i+));

    for(sit i=s.begin();i!=s.end();i++)

        printf("%d %d\n",i->l,i->r);

    //输出

    /*

    10 1

    9 2

    8 3

    7 4

    6 5

    5 6

    4 7

    3 8

    2 9

    1 10

    */

    return ;

}

在结构体中二分

只要重载了$<$，就可以在结构体中二分了

#include<cstdio>

#include<set>

#define sit set<node>::iterator

using namespace std;

struct node

{

    int l,r;

    node(int l=,int r=):l(l),r(r){};

    bool operator < (const node &a) const

    {

        return r==a.r?l<a.l:r<a.r;

    }

};

int main()

{

    set<node>s;

    for(int i=;i<=;i++)

        s.insert(node(i,i));

    sit it=s.lower_bound(node(,));

    printf("%d %d",it->l,it->r);

    //输出 2 2

    return ;

}

题目

都是可以用set水的大水题

BZOJ2783

BZOJ2028

BZOJ1058

巴特西