【C++历险记】STL之set详解

个人主页：兜里有颗棉花糖💪
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由兜里有颗棉花糖原创
收录于专栏【C++之路】💌
本专栏旨在记录C++的学习路线，望对大家有所帮助🙇‍
希望我们一起努力、成长，共同进步。🍓

set

集合（Set）：是一种不允许重复元素的容器，它的元素是按照某种特定顺序组织的。

头文件：

#include<set>

迭代器访问：

// 方式1:
set<int>::iterator it = s.begin();
while (it != s.end())
{
	cout << *it << ' ';
	it++;
}
// 方式2
for (auto e : s)
	cout << e << ' ';
// 方式3
for (set<int>::iterator it1 = s.begin(); it1 != s.end(); it1++)
	cout << *it1 << ' ';
// 其实这里方式1和方式3是等同的

Modifiers

insert（插入数据）

void test_set1()
{
	set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(4);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << ' ';
		it++;
	}
	cout << endl;
}

运行结果如下：
在这里插入图片描述
可以看到结果中并没有打印两个4，因为set容器会对其中的元素进行去重操作。

erase(删除元素)

void test_set2()
{
	set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(4);
	set<int>::iterator it = s.begin();
	for (auto e : s)
		cout << e << ' ';
	cout << endl;
	// 删除元素方式1
	auto pos = s.find(3);
	s.erase(pos);
	//s.erase(3); // 删除元素方式2
	for (auto e : s)
		cout << e << ' ';
	cout << endl;
}

运行结果如下：

上面提供了两种删除元素的方式，我们要根据不同的场景来选择不同的方式来进行删除元素。

Operations:

find（查找数据）

set的find函数用于在set中查找指定的元素，如果找到了，它返回指向该元素的迭代器；如果没有找到，返回一个指向set末尾元素的迭代器。

请看举例：

void test_set3()
{
	set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(4);
	auto pos1 = s.find(5);
	auto pos2 = s.find(4);
	if (pos1 != s.end())
		s.erase(pos1);
	else
		cout << "没找到该元素" << endl;
	if (pos2 != s.end())
		s.erase(pos2);
	for (auto e : s)
		cout << e << ' ';
}

运行结果如下：

在这里插入图片描述
需要注意的是，set的find函数和库中的find函数是不同的函数。

区别主要是查找速度上，set的find函数查找元素的时间复杂度是O(logN)

而库中的find函数查找的速度是O(N)

所以日常当中如果我们需要使用set中的find函数来查找元素时，我们可以这样使用，请看：

set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(4);
if (s.find(4) != s.end())
	cout << "该元素已被找到" << endl;
else
	cout << "未找到该元素" << endl;

count

如果该元素存在的话则返回1，否则返回0。

这里只举一个简单的例子即可，请看：

set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(4);
if (s.count(4))
	cout << "集合中存在该元素" << endl;
else
	cout << "集合中不存在该元素" << endl;

运行结果如下：
在这里插入图片描述

find函数和count函数的区别

set的find函数和count函数都是用来查找集合元素的函数，但要说区别的话还是有的。

返回值：find函数返回一个指向集合元素的迭代器，如果集合中不存在该元素，则迭代器指向集合的末尾；而count函数则返回集合中值等于给定值的元素数量，因为集合中元素是唯一的，所以返回值只能是0或1。

时间复杂度：count函数的时间复杂度要比find函数快，因为count函数只需要确定是否存在该元素，而不必遍历整个集合。

如果只需要知道一个元素是否存在于集合中，可以使用count函数；如果需要获取该元素的迭代器，或者对集合进行修改、删除、插入等操作，就需要使用find函数。

lower_bound & upper_bound

lower_bound函数用于查找大于或等于指定元素的第一个元素的迭代器，如果找到指定元素，则返回指向该元素的迭代器，否则返回指向set末尾（即end）的迭代器。

upper_bound函数用于查找大于指定元素的第一个元素的迭代器；如果没有找到则返回指向set末尾（即end）的迭代器。

请看举例：

void test_set5()
{
	set<int> s;
	for (int i = 1; i <= 10; i++) s.insert(i * 10); // 10 20 30 40 50 60 70 80 90 100

	set<int>::iterator itlow, itup;
	itlow = s.lower_bound(30), itup = s.upper_bound(60);
	cout << *itlow << ' ' << *itup << endl;
	s.erase(itlow, itup);
	for (auto e : s) cout << e << ' ';
	cout << endl;
}

运行结果如下：
在这里插入图片描述

这里我们需要注意的是，erase函数删除的范围是左闭右开的，即实际删除的元素包括第一个迭代器指向的元素，但不包括第二个迭代器指向的元素。
同时这里要再次强调lower_bound函数查找的是大于或等于指定元素的第一个元素的迭代器，而upper_bound用于查找大于指定元素的第一个元素的迭代器。

补充（multiset）

这里要补充一点，在C++中set和multiset是C++标准库中的两个关联容器，二者的唯一区别在于容器中的元素是否唯一。

这里举一个简单的例子即可，请看：

void test_set6()
{
	multiset<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(4);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(3);
	s.insert(6);
	for (auto e : s) cout << e << ' ';
	cout << endl;
	cout << "容器中元素5的个数是:" << s.count(5) << endl;
	
	auto ret = s.equal_range(5);
	auto itlow = ret.first;
	auto itup = ret.second;
	s.erase(itlow, itup);
	for (auto e : s) cout << e << ' ';
	cout << endl;
}

运行结果如下：

这里我们要注意的是，如果multiset容器中有多个元素5，那么，如果使用find函数来查找元素5的话，此时应该返回的是中序的第一个元素5。请看举例：

multiset<int> s;
s.insert(1);
s.insert(2);
s.insert(4);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(3);
s.insert(6);
for (auto e : s) cout << e << ' ';
cout << endl;
auto pos = s.find(5);
while (pos != s.end())
{
	cout << *pos << ' ';
	pos++;
}
cout << endl;

运行结果如下：

equal_range

我们其实可以认为count函数和equal_range函数就是专门为multiset容器设计的。因为set容器中不存在相等的值，而multiset容器才存在相等的值。

下面我们来看一下multiset容器是如何使用equal_range函数的。

方式1：

void test_multiset1()
{
	multiset<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(4);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(3);
	s.insert(6);
	for (auto e : s) cout << e << ' ';
	cout << endl;
	auto ret = s.equal_range(5);
	auto itlow = ret.first;
	auto itup = ret.second;

	s.erase(itlow, itup);
	for (auto e : s) cout << e << ' ';
	cout << endl;
}