set学习笔记

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 3.2k | 阅读时长 ≈ 3 分钟

1.什么是set 和 set的好处

$set$的翻译为集合，是一个内部自动有序且不含重复元素(即满足集合的互异性)的$STL$容器，其内部采用“红黑树”实现。

什么是集合？点这

$set$的好处在于自动完成去重和按升序排序

2.举个栗子

比如这题

1.普通作法

看到数据范围这么水肯定想到用桶排

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int b[1001],n,i,j,m=0,x;
    memset(b,0,sizeof(b));
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        if(b[x]==0) m++;
        b[x]++;
    }
    cout<<m<<endl;
    for(i=0;i<=1000;i++)
      if(b[i]>0) cout<<i<<" ";
    cout<<endl;
    return 0;
}

2.set

如果你会了$set$，这道题就可以这么打

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n;
set<int> st;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        st.insert(x);
    }
    printf("%d\n",st.size()); 
    for(set<int>::iterator it= st.begin(); it!=st.end(); it++)
    {
        printf("%d ",*it);
    }
    return 0;
}

如果数据范围大了话，明显不能用桶排解决，这时候$set$的好处就可以体现出来。

领会了$set$的好处之后，接下来让我们了解

3.set的定义

使用$set$之前，必须添加$set$头文件，即

1
#include<set>

也可以打好我们的$bits/stdc++.h$

同时必须要有

1
using namespace std;

定义一个$set$的方法：

1
set<typename> name;

其中$typename$为任何基本类型或者容器，$name$为这个集合的名字

同时$set$也支持定义数组，如:

1
set<typename> name[MAXN]

即定义了$MAXN$个$set$容器

4.set的访问

一大坑点是$set$只能通过迭代器访问

1.定义一个迭代器

1
set<typename>::iterator it;

即定义一个名为$it$的迭代器

2.通过迭代器访问

注意事项：

  • 1 $set$不支持类似*$(it+i)$的访问

  • 2 $set$也不支持$it<name.end()$这种访问

我们需要使用*$it$来访问$set$中的元素

5.set的常用函数

1.insert()

1.作用

$insert()$用来插入一个数到$set$中，并自动排序+去重

2.时间复杂度

$O(log_{2}n)$

3.用法

例如，以下一段代码输出$1$ $2$ $3 $

1
2
3
4
5
6
for(int i=3;i>=1;i--) a.insert(i);
a.insert(1);
for(set<int>::iterator it=a.begin();it!=a.end();it++)
{
    cout<<*it<<" ";
}

2.begin()和end()

1.作用

分别用来获取$set$容器的首地址和尾地址

用法跟其他$STL$容器一样这里不再赘述

3.size()

1.作用

用于获取$set$容器中元素的个数

2.时间复杂度

$O(1)$

3.用法

例如，以下一段代码输出$3$

1
2
3
for(int i=3;i>=1;i--) a.insert(i);
a.insert(1);
cout<<a.size();

4.clear()

1.作用

用于清空$set$容器中的所有元素

2.时间复杂度

$O(n)$ ($n$为$set$中的元素个数)

3.用法

例如，以下一段代码输出$1$

1
2
3
4
for(int i=3;i>=1;i--) a.insert(i);
a.clear();
a.insert(1);
cout<<a.size();

5.erase()

1.作用

可以用来删除单个元素也可以用来删除一段区间的元素

1.删除单个元素

1.时间复杂度

$O(1)$ (使用迭代器)

$O(log_{2}n)$ (使用欲删除元素的值)

2.用法

1.$erase(it)$

$it$为欲删除的元素的迭代器

例如，以下一段代码输出$2$ $3$

1
2
3
4
5
6
for(int i=3;i>=1;i--) a.insert(i);
a.erase(a.begin());
for(set<int>::iterator it=a.begin();it!=a.end();it++)
{
    cout<<*it<<" ";
}

2.$erase(value)$

$value$为欲删除元素的值

例如以下一段代码输出$1$ $3$

1
2
3
4
5
6
for(int i=3;i>=1;i--) a.insert(i);
a.erase(2);
for(set<int>::iterator it=a.begin();it!=a.end();it++)
{
    cout<<*it<<" ";
}

2.删除一个区间的元素

1.时间复杂度

$O(right-left)$ $(左闭右开区间[left,right))$

2.用法

$erase(left,right)$用来删除左闭右开区间[$left$,$right$)之间的元素

例如，以下一段代码输出$1$ 

1
2
3
4
5
6
7
for(int i=5;i>=1;i--) a.insert(i);
set<int>::iterator it=a.find(2);
a.erase(it,a.end());
for(set<int>::iterator it=a.begin();it!=a.end();it++)
{
    cout<<*it<<" ";
}

6.find()

1.作用

返回元素在$set$中的迭代器

2.时间复杂度

$O(log_{2}n)$ ($n$为$set$中的元素个数)

3.用法

例如，以下一段代码输出$2$

1
2
for(int i=5;i>=1;i--) a.insert(i);
cout<<*a.find(2);

6.推荐例题

之后还会继续放上