[C++STL教程]5.set是什么?怎么用?零基础都能看懂的入门教程

发布于 2023-03-17  295 次阅读


之前我们介绍过vector, queue, stackmap。我们知道前三者是线性结构,而map是一种树状结构,今天我们要介绍另外一个树状结构实现的stl容器:set

🎈 作者:Eriktse
🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀
🎈 个人博客:www.eriktse.com

本文仅从入门和实用角度进行讲解,主要针对初学者或竞赛向。如有不严谨的地方欢迎指正!

什么是 set?

set意为集合,在高中我们学习过集合的三大性质:确定性、互异性、无序性。在C++的STL中的集合,容器内会默认按照“升序”排列,但同样遵循确定性和互异性

C++ STL Set

Set是C++标准模板库(STL)中较为重要的容器,原生支持有序,唯一。

一个大小为nset所需的空间约为nlogn个单位。set的插入、删除、查找操作复杂度均为O(logn)

关键特性

  • 唯一性:Set容器内的元素都是唯一的,也就是说,每个元素都是不同的

  • 有序性:Set容器内的元素总是排序的,向Set中添加元素,它将自动插入到正确的位置中,不需要手动排序

  • 查找/插入快速:因为Set容器的元素是排序的,所以在Set中查找和插入元素都很快

适用场景

Set容器的有序性和唯一性特性极大地减少了大量重复和排序等工作,在很多场景下Set容器更具优势,下列情况是使用Set容器合适的情况:

  1. 存储元素类型不能够重复的场景,比如存储用户的唯一ID
  2. 操作多个对象时,必须使用排序算法的场景
  3. 需要快速查找插入元素的场景

通过Set容器,可以快速获取唯一和有序的结果,同时在大数据量下性能也相对较高,因此使用场景广泛。

初始化 set

在使用set之前,需要引入头文件#include <set>,当然你也可以用#include <bits/stdc++.h>(竞赛选手推荐)。

用以下代码,声明一个空的set

set<int> st;//声明一个存储类型为 int 的 set 容器

插入元素

insert(x)方法:将元素x插入到set对象中,如果set中已经有了x元素,则不会插入(保证set中每个元素最多出现一次)。

C++中的STL中提供了一种集合容器——Set,static set它是一个拥有特殊功能(无序、不允许重复)的容器。STL中Set如何插入元素呢?

1.使用insert函数插入元素:

(1)一个元素的插入:

set容器提供的insert函数可以将一个元素插入到容器中,代码如下:

set<int> a;
a.insert(10);

此外,也可以插入pair类型的数据,如:

set<pair<int, int> > b;
b.insert(std::make_pair(2, 3));

(2)多个元素的插入:

vector<int> array{1, 2, 3};
set<int> a;
a.insert(array.begin(), array.end());

2.使用emplace函数插入元素:

emplace函数向set容器中添加一个新元素,但不复制或移动现有元素,而是直接在容器存储区中构造元素。它的作用和insert函数相同,但emplace函数的效率会更高。

set<int> a;//a : {empty}
a.emplace(10);//a : {10}

删除元素

在使用set删除元素之前,需要理解关于set的删除元素方式,目前c++ STL提供了三种删除set元素的方式: clear()erase() 、 和 pop_back()

要删除set中的元素,通常是使用erase()函数:

// 声明一个set容器
std::set<int> st;
// 添加元素到容器

st.insert(9);
st.insert(5);
st.insert(1);
// 如果要删除set中的某个值

int value = 5;
st.erase(value);//删除st中value = 5的数据项

// 如果要删除set中的某个指定的位置的值

std::set<int>::iterator it = /* Set Iterator */;
st.erase(it);

// 此外,还提供了clear()函数来清空set中的所有元素:
st.clear();

// 最后,也可以使用pop_back()函数来删除set中的一个元素:
st.pop_back();

查找元素

C++STL的set提供了非常方便的查找操作,也即我们常说的find操作。find操作的使用非常简单,可以使用Iterator类型的游标变量,对Set成员集合进行定位,若要查找的元素存在,则会返回该元素的位置信息,若不存在,则返回set末尾迭代器(未设定取值)。

set<int> myset;
set<int>::iterator it;//声明一个iterator
//向Set中添加一系列元素
for(int i=1; i<10; i++)myset.insert(i*10);

//输出原始Set集合元素
cout<<"The original set elements are:"<<endl;
for(it=myset.begin(); it!=myset.end(); it++)cout<<*it<<" ";
cout << endl;

//查找Set中是否包含指定的元素
int num = 50;
it =myset.find(num);//返回迭代器
cout<<"输入要查找的元素:" << num << endl;

if(it != myset.end())cout << "找到指定元素:" << *it << endl;
else cout << "未找到指定元素!" << endl;

获取元素个数

获取set中元素的个数可以调用其内置的函数size()

cout << "the size of set is: " << s.size() << endl;

以上例子中,我们声明了一个set,然后调用它的size()函数获取set中元素的个数,即可以获取到set中元素的个数。

判断是否为空

判断set是否为空可以调用其内置函数empty()

```c++
cout << "The set is empty? " << (s.empty() ? "Yes" : "No") << endl;

以上例子中,我们声明了一个set,然后调用它的`empty()`函数判断set是否为空,`empty()`函数的返回值为`true`或`false`,如果set不为空,则返回`false`,反之,则返回`true`。

## 判断元素是否存在集合中

`count(x)`方法返回`set`中元素`x`的个数,由于个数只能是0或1,所以当返回值非0时表示元素在集合中,反之不在。

>multiset中一个元素可以存在多次。

`count()`方法非常常用,用于判断是否已经计算过从而剪枝,或者图论中的判重等等。

## 遍历 set

#### 一、迭代器的使用

迭代器的使用,是一种很常用的遍历方法,使用它可以让我们很方便地遍历set中的元素,示例代码如下:

```cpp
#include<iostream>
#include<set>
using namespace std;
int main( )
{
    //定义一个set
    set<int> mySet;
    mySet.insert(20);
    mySet.insert(40);
    mySet.insert(30);
    mySet.insert(50);
    //定义一个迭代器
    set<int>::iterator it;
    //遍历set
    for(it = mySet.begin( ); it != mySet.end( ); it++)
    {
        cout<<*it<<" ";
    }
    cout<<endl;
    return 0;
}

用auto关键字也可以进行遍历,和遍历map差不多,可以看这篇文章:https://www.eriktse.com/technology/1069.html

二、for_each的使用

要使用for_each对set中的元素进行遍历,需要将其传入一个可调用的对象,可以使用仿函数。示例代码如下:

#include<set>
#include<iostream>
#include<algorithm>

struct MyPrinter
{
    void operator()(int val)
    {
        std::cout<<val<<" ";
    }
};

int main()
{
    //定义一个set
    set<int> mySet;
    mySet.insert(20);
    mySet.insert(40);
    mySet.insert(30);
    mySet.insert(50);
    //有点怪异的写法
    for_each(mySet.begin(),mySet.end(),MyPrinter());
    cout<<endl;
    return 0;
}

总结

以上是set容器的简单总结,set容器拥有唯一性,有序性以及快速插入,在一定场景下,可以帮助我们快速解决问题。

🎈 本文由eriktse原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞👍、收藏⭐、留言💬

19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2023-03-17