共计 3599 个字符,预计需要花费 9 分钟才能阅读完成。
之前咱们介绍过 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 容器适合的状况:
- 存储元素类型 不可能反复 的场景,比方存储用户的惟一 ID
- 操作多个对象时,必须应用排序算法 的场景
- 须要 疾速查找 和插入元素 的场景
通过 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 原创,创作不易,如果对您有帮忙,欢送小伙伴们点赞👍、珍藏⭐、留言💬