乐趣区

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

jiezi

之前咱们介绍过 vector, queue, stack，map。咱们晓得前三者是线性构造，而map 是一种树状构造，明天咱们要介绍另外一个树状构造实现的 stl 容器：set。

🎈 作者：Eriktse
🎈 简介：19 岁，211 计算机在读，现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换 C ++/Python 算法。（优质好文继续更新中……）🚀
🎈 集体博客：www.eriktse.com

本文仅从入门和实用角度进行解说，次要针对初学者或比赛向。如有不谨严的中央欢送斧正！

什么是 set？

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

C++ STL Set

Set 是 C ++ 规范模板库（STL）中较为重要的容器，原生反对有序，惟一。

一个大小为 n 的set所需的空间约为 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()函数的返回值为 true 或false，如果 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 原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬

退出移动版