之前咱们介绍过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原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言