之前咱们介绍过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差不多，能够看这篇文章：www.eriktse.com/technology/…

二、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原创，创造不易，假如对您有帮助，欢迎小伙伴们点赞、收藏⭐、留言