欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

set用法小结

程序员文章站 2022-09-16 08:27:07
set本质上是一棵红黑树,用法也就那么几个,插入删除lowerbound,再就是跌倒器之类的 基本用法 begin()--返回指向第一个元素的迭代器 #include #include int main() { std::sets; s.insert(5); s. ......

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

基本用法

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

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::set<int>s;
    s.insert(5);
    s.insert(4);
    s.insert(6);
    printf("%d",*s.begin());
    //输出4 
    return 0;
}
begin()

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

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::set<int>s;
    s.insert(5);
    s.insert(4);
    s.insert(6);
    printf("%d",*s.end());
    //注意这里的跌倒器指向的是一个空位置!
    //所以最好不要输出end()
    
    //输出末尾元素可以用下面的方法 
    //std::set<int>::iterator it=s.end(); 
    //printf("%d",*--it); 
    return 0;
}
end()

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

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

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

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

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

clear()--清除所有元素

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::set<int>s;
    s.insert(5);
    s.insert(4);
    s.insert(6);
    printf("%d\n",s.size());
    s.clear();
    printf("%d\n",s.size());
    return 0;
}
clear()

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

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::multiset<int>s;
    s.insert(5);
    s.insert(5);
    s.insert(6);
    printf("%d",s.count(5));
    return 0;
}
count

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

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

erase可以删除给定的元素,也可以删除跌倒器

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

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::set<int>s;
    s.insert(5);
    s.insert(4);
    s.insert(6);
    s.erase(5);
    s.erase(s.find(4));
    if(s.find(5)==s.end()) printf("5 is not found\n");
    if(s.find(4)==s.end()) printf("4 is not found\n");
    if(s.find(6)!=s.end()) printf("6 is found");
      return 0;
}
erase()

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

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::set<int>s;
    s.insert(5);
    s.insert(4);
    s.insert(6);
    printf("%d",*s.lower_bound(4));
    //输出为4 
      return 0;
}
lower_bound()

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

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::set<int>s;
    s.insert(5);
    s.insert(4);
    s.insert(6);
    printf("%d",*s.upper_bound(4));
    //输出为4 
      return 0;
}
upper_bound()

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

set用法小结
#include<cstdio>
#include<set>
int main()
{
    std::set<int>s;
    std::set<int>a;
    s.insert(4);
    s.insert(5);
    a.insert(6);
    s.swap(a);
    printf("%d",s.size());
    //输出为1 
      return 0;
}
swap()

几个常用操作

正序遍历所有元素

这个需要借助跌倒器来实现

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

 

#include<cstdio>
#include<set>
#define sit set<int>::iterator 
using namespace std;
int main()
{
    set<int>s;
    for(int i=1;i<=10;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 0;
}

倒序遍历所有元素

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

 set用法小结

#include<cstdio>
#include<set>
#define rsit set<int>::reverse_iterator 
using namespace std;
int main()
{
    set<int>s;
    for(int i=1;i<=10;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 0;
}

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(2);
    s.insert(2);
    s.insert(2);
    s.erase(2);
    printf("%d\n",s.count(2));
    
    s.insert(2);
    s.insert(2);
    s.insert(2);
    s.erase(s.find(2));
    printf("%d\n",s.count(2));
    //输出0 2 
    return 0;
}

自定义排序规则

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

#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=1;i<=10;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 0;
}

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

#include<cstdio>
#include<set>
#define sit set<node>::iterator 
using namespace std;
struct node
{
    int l,r;
    node(int l=0,int r=0):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=1;i<=10;i++) 
        s.insert(node(i,10-i+1));
    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 0;
}

 

在结构体中二分

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

#include<cstdio>
#include<set>
#define sit set<node>::iterator 
using namespace std;
struct node
{
    int l,r;
    node(int l=0,int r=0):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=1;i<=10;i++) 
        s.insert(node(i,i));
    sit it=s.lower_bound(node(1,2));
    printf("%d %d",it->l,it->r);
        
    //输出 2 2
    return 0;
}

 

题目

都是可以用set水的大水题

BZOJ2783

BZOJ2028

BZOJ1058