今天你学C++了吗？——set

用户11352420

发布于 2025-04-08 00:46:02

11100

代码可运行

文章被收录于专栏：编程学习编程学习

运行总次数：0

代码可运行

前面我们已经了解到了二叉搜索树的底层结构，而与它息息相关的就是容器——map和set，这一篇博客我们就开始探索map和set，准备好了吗~我们发车去探索C++的奥秘啦~🚗🚗🚗🚗🚗

序列式容器和关联式容器

序列式容器（Sequential Containers）

定义逻辑结构为线性序列的容器，元素按存储位置的物理顺序排列，彼此无紧密关联。
核心特性
- 顺序无关性：元素交换位置后，容器性质不变（如 vector 中交换元素仍是合法序列）。
- 访问方式：通过元素在容器中的位置（如索引、迭代器）进行访问。
- 典型容器：vector, list, deque, array, forward_list, string。
适用场景 需要高效遍历或按位置操作元素的场景，如动态数组、链表等。

关联式容器（Associative Containers）

定义逻辑结构为非线性（通常为树或哈希表），元素通过关键字（Key）建立强关联关系。
核心特性
- 有序性约束：元素按关键字排序（如 map/set）或哈希分布（如 unordered_map/set）。
- 访问方式：通过关键字直接访问元素，而非物理位置。
- 典型容器：
  - 有序系列：map, set, multimap, multiset（基于红黑树）。
  - 无序系列：unordered_map, unordered_set（基于哈希表）。
适用场景 需要高效查找、插入或删除特定关键字的场景，如字典、集合等。

核心区别

对比维度	序列式容器	关联式容器
逻辑结构	线性序列（顺序无关）	非线性结构（树/哈希表，有序/无序）
元素关系	位置相邻，无键值关联	通过关键字强关联
访问方式	按物理位置（索引/迭代器）	按关键字（find, [] 运算符）
典型操作效率	插入/删除中间元素可能低效	查找/插入/删除平均高效（哈希表）或对数时间（树）
内存布局	连续或节点式存储	树节点或哈希桶分散存储

序列式容器适合按位置操作或遍历的场景，强调元素的物理顺序。
关联式容器适合按关键字快速访问的场景，强调元素间的逻辑关联。
两者共同构成STL容器体系的核心，分别应对不同的数据操作需求。

set

什么是set？

set（集合）是一个关联容器，它只存储键，不存储值（也就是我们前面说的key场景）。set中的元素是唯一的，multiset中的元素不是唯一的，但是它们都会进行自动排序，set底层使用红黑树进行实现，本质上是一颗平衡二叉搜索树，我们后面的博客会对红黑树进行实现~我们这里主要讲元素唯一的set容器~

特点：
- 元素是唯一的。
- 自动排序（默认情况下，使用<运算符排序，但可以自定义排序规则）。
- 查找、插入和删除操作的时间复杂度通常为O(log n)，因为set内部通常实现为红黑树。
用途：
- 当你需要快速查找、插入和删除元素时。
- 当你需要存储唯一元素的数据集时。
- 例如，如果你想检查一个元素是否存在于某个集合中，set就非常合适。

set的使用

通过查阅文档，我们可以发现set提供了很多的接口，这里我们直接在代码里面使用，有一些注意点会在代码注释里面进行讲解~更加简洁明了~

#include<iostream>
using namespace std;
#include<set>//包含头文件

void test1()
{
	//构造使用
	set<int> s;//支持默认构造
	//插入数据
	//set里面元素唯一——所以插入数据（去重+排序）
	//默认为升序
	s.insert(2);
	s.insert(5);
	s.insert(7);
	s.insert(7);
	s.insert(1);
	s.insert(9);
	s.insert(0);
	s.insert(2);

	//迭代器使用
	//set<int>::iterator it = s.begin();
	auto it = s.begin();//使用auto更加方便
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//同样支持范围for
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//数据删除
	s.erase(2);
	s.erase(0);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

插入数据排降序

我们插入数据的时候是去重+默认排升序，那如果是我们希望排降序呢？这个时候我们就需要看一看set的构造函数：

我们需要就需要更改第二个参数，默认是less那我们就更改为greater：

void test2()
{
	//构造使用
	set<int,greater<int>> s;//支持默认构造
	//插入数据
	//set里面元素唯一——所以插入数据（去重+排序）
	//修改第二个参数排为降序
	s.insert(2);
	s.insert(5);
	s.insert(7);
	s.insert(7);
	s.insert(1);
	s.insert(9);
	s.insert(0);
	s.insert(2);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

双向迭代器

此外，我们还可以知道set的迭代器是双向的~

void test3()
{
	//构造使用
	set<int> s;//支持默认构造
	s.insert(2);
	s.insert(5);
	s.insert(7);
	s.insert(7);
	s.insert(1);
	s.insert(9);
	s.insert(0);
	s.insert(2);
	//双向迭代器
	auto it1 = s.begin();//使用auto更加方便
	while (it1 != s.end())
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;

	auto it2 = s.rbegin();//使用auto更加方便
	while (it2 != s.rend())
	{
		cout << *it2 << " ";
		it2++;
	}
	cout << endl;
}

初始化列表

set同样支持创建的时候就给值进行初始化~后面会取出初始化列表的值来进行插入，并且去重和排序~

void test4()
{
	//构造使用
	set<int> s = { 1,2,8,9 };//支持初始化列表
	s.insert(2);
	s.insert(5);
	s.insert(7);
	s.insert(7);
	s.insert(1);
	s.insert(9);
	s.insert(0);
	s.insert(2);
	
	auto it1 = s.begin();
	while (it1 != s.end())
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
}

find

我们知道算法库里面也有一个find（）函数，那么为什么set里面还要提供find呢？算法库里面的find只需要依靠单向迭代器就可以了，那也就说明了查找的时间复杂度为O（N），我们知道set底层也就是一颗平衡二叉搜索树，那么查找时间复杂度为O（log N),明显更胜一筹~

算法库的find():

set函数的find():

代码测试：

void test5()
{
	set<int> s = { 3455,789,90,5555,5555555 };
	srand((unsigned int)time(NULL));//以时间为种子
	for (int i = 0; i < 10000000; i++)
	{
		s.insert(rand()%10000000);//生成随机数进行插入
	}
	//测试查找时间
	int begin1 = clock();//执行到当前代码时间
	s.find(5555555);
	int end1 = clock();
	cout << "set函数find时间：" << end1 - begin1 << endl;
	int begin2 = clock();
	find(s.begin(), s.end(), 5555555);
	int end2 = clock();
	cout << "算法库函数find时间：" << end2 - begin2 << endl;
	
}

可以发现set函数的find时间在0ms以下，而算法库里面的却达到了3ms~这就证明了我们的观点~

erase

我们如果想要删除元素可以给迭代器位置或者迭代器区间或者删除的值，这里我们来进行一下测试~有的人可能会觉得奇怪，删除指定的值为什么返回值是int呢？不是bool类型也不是void类型，这是因为要与multiset版本相符合，multiset版本允许重复，一次删除的可能有多个

void test6()
{
	set<int> s = { 1,2,8,9,5,7,6,0 };
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//1、给值
	//该版本erase的返回值给整型的原因是multiset版本相符合
	//multiset版本允许重复，一次删除的可能有多个
	int e1 = s.erase(6);
	cout << "e1==" << e1 << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	int e2 = s.erase(10);
	cout << "e2==" << e2 << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//2、给相应位置的迭代器并且迭代器是有效的
	auto ret = s.find(8);
	if (ret != s.end())//判断是否为有效的迭代器
	{
		s.erase(ret);
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//3、给一段迭代器区间
	auto ret2 = s.find(5);
	if (ret2 != s.end())
	{
		s.erase(s.begin(), ret2);
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

swap

swap很明显就是完成两个set的交换操作~只需要一个参数就可以了~

void test7()
{
	set<int> s1 = { 2,4,7,0,1,5 };
	set<int> s2 = { 2,9,3 };
	cout << "交换前s1:" << endl;
	for (auto e1 : s1)
	{
		cout << e1 << " ";
	}
	cout << endl;
	cout << "交换前s2:" << endl;
	for (auto e2 : s2)
	{
		cout << e2 << " ";
	}
	cout << endl;
	s1.swap(s2);
	cout << "交换后s1:" << endl;
	for (auto e1 : s1)
	{
		cout << e1 << " ";
	}
	cout << endl;
	cout << "交换后s2:" << endl;
	for (auto e2 : s2)
	{
		cout << e2 << " ";
	}
	cout << endl;
}

clear

clear也就是对所有的元素进行清除了~我们同样可以进行测试~

count

count返回的是该元素的个数，返回值同样是无符号整型，这也是因为与multiset相符合，事实上判断某一个元素是否存在使用count更加方便~因为不需要再看是否是末尾迭代器了~

lower_bound和upper_bound

在 set 中，lower_bound 和 upper_bound 提供了高效的有序查找能力，尤其适合范围查询和边界处理~

lower_bound

功能：返回指向第一个 大于等于 给定值的元素的迭代器。
行为：
- 若值存在，返回指向该元素的迭代器。
- 若值不存在，返回指向第一个比它大的元素的迭代器。
- 若所有元素都小于该值，返回 end()。

upper_bound

功能：返回指向第一个 严格大于 给定值的元素的迭代器。
行为：
- 若值存在，返回指向该元素下一个位置的迭代器。
- 若值不存在，返回指向第一个比它大的元素的迭代器。
- 若所有元素都小于等于该值，返回 end()。

简单对比

函数	条件	返回值指向
lower_bound	存在等于值	该元素
	不存在等于值	第一个比它大的元素
upper_bound	存在等于值	该元素的下一个位置
	不存在等于值	第一个比它大的元素

测试

void test8()
{
	set<int> s = { 10,20,30,45,50,60,70,80,90,95,100 };
	//现在我们想删除40——90这段区间的值
	//我们没有办法直接找到
	//使用lower_bound找到大于等于40后返回迭代器
	auto loit = s.lower_bound(40);
	//使用upper_bound找到严格大于90后返回迭代器
	auto upit = s.upper_bound(90);

	//删除找到的迭代器区间
	s.erase(loit, upit);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

我们也可以打印观察：

multiset

前面我们知道set和multiset其实是差不多的，他们之间主要的差别是mulset支持重复，而set是不支持的~

我们可以看到它们的接口是基本上是一致的，multiset支持值冗余，所以insert/find/count/erase都围绕着因为支持值冗余有所差异~我们这里就主要来看看它们的差异了~

insert

set：
- 插入重复值时失败，返回 pair<iterator, bool>，其中 second 为 false
- 插入成功时，second 为 true，iterator 指向新元素

multiset：

允许插入重复值，返回的迭代器始终指向新插入的元素（即使值已存在）。
返回类型为 iterator，而非 pair。

void test9()
{
	set<int> s = { 1,4,7,3,9 };
	multiset<int> ms = { 1,4,7,3,9 };

	auto d1 = s.insert(4);//不支持重复
	auto d2 = ms.insert(4);//支持重复
	for (auto e1 : s)
	{
		cout << e1 << " ";
	}
	cout << endl;
	for (auto e2 : ms)
	{
		cout << e2 << " ";
	}
	cout << endl;
}

我们可以通过监视窗口查看它们的返回值类型

运行结果：

可以看出ms成功插入，而s插入失败，后面的博客我们会对pair这一个返回值类型进行讲解~

find

set 和 multiset：
- 均返回指向第一个等于给定值的元素的迭代器
- 若不存在，返回 end()
差异：
- set：最多有一个匹配元素
- multiset：可能有多个匹配元素，但 find 仅返回第一个

count

set：

只能返回 0（不存在）或 1（存在）

multiset：

返回等于给定值的元素数量（可能大于1）

代码测试：

void test10()
{
	set<int> s = { 1,4,7,3,9,5 };
	multiset<int> ms = { 1,4,7,3,9,4,3,5,4 };

	auto d1 = s.find(4);
	auto d2 = ms.find(4);

	cout << s.count(4) << endl;
	cout << ms.count(4) << endl;
}

erase

set：
- erase(value)：删除所有等于 value 的元素（最多1个）
- erase(iterator)：删除指定位置的元素
- erase(iterator first, iterator last)：删除区间 [first, last) 内的元素
multiset：
- erase(value)：删除所有等于 value 的元素
- 其他重载与 set 一致

代码测试：

void test11()
{
	set<int> s1 = { 1,4,7,4,3,9,5 };//去重+排序
	set<int> s2 = { 1,4,7,4,3,9,5 };//去重+排序
	multiset<int> ms1 = { 1,4,7,3,9,4,3,5,4,4,1 };//排序
	multiset<int> ms2 = { 1,4,7,3,9,4,3,5,4,4 ,1 };//排序
	cout << "删除前：" << endl;
	cout << "s1.count(4) = " << s1.count(4) << endl;
	cout << "ms1.count(4) = " << ms1.count(4) << endl;
	cout << "s2.count(1) = " << s2.count(1) << endl;
	cout << "ms2.count(1) = " << ms2.count(1) << endl;
	s1.erase(4);//删除一个4
	s2.erase(s2.begin());//删除开头元素
	ms1.erase(4);//删除所有4
	ms2.erase(ms2.begin());//只删除开头元素
	cout << "删除后：" << endl;
	cout << "s1.count(4) = " << s1.count(4) << endl;
	cout << "ms1.count(4) = " << ms1.count(4) << endl;
	cout << "s2.count(1) = " << s2.count(1) << endl;
	cout << "ms2.count(1) = " << ms2.count(1) << endl;
	
}

接口差异总结

接口	set	multiset
insert	拒绝重复，返回 pair	允许重复，返回 iterator
find	返回唯一匹配	返回中序遍历第一个匹配
count	仅返回 0 或 1	返回实际数量
erase	删除单个元素	可删除多个元素