乐趣区

关于c++:CSTL教程5set是什么怎么用零基础都能看懂的入门教程

之前咱们介绍过 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()

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

以上例子中,咱们申明了一个 set,而后调用它的 empty() 函数判断 set 是否为空,empty()函数的返回值为 truefalse,如果 set 不为空,则返回false,反之,则返回true

判断元素是否存在汇合中

count(x)办法返回 set 中元素 x 的个数,因为个数只能是 0 或 1,所以当返回值非 0 时示意元素在汇合中,反之不在。

multiset 中一个元素能够存在屡次。

count()办法十分罕用,用于判断是否曾经计算过从而剪枝,或者图论中的判重等等。

遍历 set

一、迭代器的应用

迭代器的应用,是一种很罕用的遍历办法,应用它能够让咱们很不便地遍历 set 中的元素,示例代码如下:

#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 原创,创作不易,如果对您有帮忙,欢送小伙伴们点赞👍、珍藏⭐、留言💬

退出移动版