博主会持续更新

本篇文章主要讲解 C++容器set的相关用法 的相关内容

1. 关联式容器

我已经在之前介绍过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>（上一篇文章讲过）结构的键值对，在数据检索时比序列式容器效率更高。

2. 树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。首先来看一下set。

3. set的介绍以及相关使用操作

3.1 set的介绍

链接：set介绍

1. 唯一性： std::set 中的元素是唯一的，即集合中不允许重复元素。

2. 排序： std::set 会根据元素的值自动进行排序，默认情况下，它使用元素类型的比较函数来实现排序。

3. 内部实现： std::set 使用红黑树作为底层数据结构来实现，这使得它的插入、删除和查找操作的时间复杂度都是 O(log n)。

4. 使用方法： 要使用 std::set，首先需要包含 <set> 头文件。然后，你可以声明一个 std::set 对象，并使用Insert() 方法向其中插入元素。你还可以使用 erase() 方法来删除元素，使用 find() 方法来查找元素，以及使用size() 方法获取集合的大小。

5. 迭代器： std::set 支持迭代器，你可以使用迭代器遍历集合中的元素，并对其进行操作。

6. 自定义排序： 如果你想要按照自定义的方式对元素进行排序，可以提供自定义的比较函数作为 std::set 的模板参数之一。

3.2 set的相关使用操作

set的模板参数列表

• : set中存放元素的类型，实际在底层存储<value, value>的键值对。
• Compare：set中元素默认按照小于来比较
• Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

set的功能

• set可以帮你完成去重+排序，例如：

void settest1()
{
	set<int> s1;
	s1.insert(1);
	s1.insert(11);
	s1.insert(3);
	s1.insert(1);
	s1.insert(4);
	s1.insert(2);

	for (auto e : s1)
	{
		cout << e << " ";
	}
}

set的构造函数

• 迭代器区间构造：

void settest1()
{
	vector<int> v = { 3,2,8,1,10,2 };
	set<int> s2(v.begin(), v.end());
	for (auto e : s2)
	{
		cout << e << " ";
	}
	cout << endl;
}

• Initializer_list构造：

void settest1()
{
	set<int> s3 = { 3,2,8,1,10,2 };
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;
}

set的删除

void settest1()
{
	set<int> s3 = { 3,2,8,1,10,2 };
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;
	s3.erase(8);
	s3.erase(18);
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;
}

set的查找

void settest1()
{
	set<int> s3 = { 3,2,8,1,10,2 };
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;
	s3.erase(8);
	s3.erase(18);
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;


	auto pos = s3.find(10);
	if (pos != s3.end())
	{
		cout << *pos << endl;
		s3.erase(pos);
	}
	else
	{
		cout << "找不到" << endl;
	}
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;
}

lower_bound和upper_bound

• lower_bound找 >= x 的值，返回第一个 >= x 的值的位置
• upeer_bound找 >x 的值，返回第一个 >x 的值的下一个位置

void settest2()
{
	std::set<int> myset;
	for (int i = 1; i < 10; i++)
		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90

	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

	auto itlow = myset.lower_bound(25);                // >= x
	auto itup = myset.upper_bound(60);                 // > x

	// [30, 70)
	myset.erase(itlow, itup);                     // 10 20 70 80 90

	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
}