🌟🌟作者主页：ephemerals__
🌟🌟所属专栏：C++、STL
目录
前言
之前，我们已经探索了STL中的多个容器及容器适配器，如string、vector、list，以及stack和priority_queue等。今天，我们将进一步拓宽视野，深入学习STL中的容器——set及其变种multiset。
作为STL的重要组成部分，set以其独特的性质——元素自动排序且不重复，在解决许多实际问题时发挥着不可替代的作用。无论是处理需要唯一性的数据集合，还是实现高效的查找操作，set都以其简洁的接口和强大的功能赢得了开发者们的青睐。
一、序列式容器和关联式容器
之前我们学习的string、vector、list等容器都是序列式容器， 它们的逻辑结构都是线性序列。对于序列式容器，它们的元素之间通常没有相关性，其元素按照逻辑顺序进行存储和访问。
而set和multiset是关联式容器，它虽然也可以存储数据，但与序列式容器不同的是，其逻辑结构通常是非线性的，元素之间存在紧密联系，元素按照关键字进行存储和访问。如果擅自修改某个元素或者移动元素的逻辑位置，就会破坏它的存储结构。
二、set和multiset简介
set（集合）和multiset（多重集合）是STL中的容器，分别用于处理唯一元素和允许重复元素的场景，它们的底层结构都是红黑树（一种自平衡二叉搜索树）。
set和multiset有以下共同特点：
1. 容器元素自动按照升序排列（也可通过传入第二个模板参数调整排序规则）。
2. 元素插入、删除、查找的时间复杂度均为O(logN)。
set和multiset的核心区别是：set不允许容器内有重复元素，能够达到去重的效果；而multiset支持插入重复元素。
鉴于set和multiset的接口功能几乎没有区别，且set更为常用，所以接下来的内容将主要聚焦于set常用接口的使用方法。当然，我们也会在适当的时候提及multiset，以便大家能够对比两者的异同，从而更好地根据实际需求做出选择。
我们在使用 set 或 multiset 时，需要引头文件<set>，并且该容器定义在命名空间std当中。
set和multiset相关接口查阅：
三、set的默认成员函数
set显式实现的默认成员函数有三个：
构造函数(constructor)
c++14下，set有五种构造函数，其中较为常用的有以下四个：
| 函数原型 | 功能说明 |
| set(); | 无参构造 |
| set(InputIterator first, InputIterator last); | 迭代器区间构造 |
| set(const set& x); | 拷贝构造，用一个set对象构造另一个set对象 |
| set(initializer_list<value_type> il); | 初始化器构造 |
代码示例：
#include <iostream>
#include <set>
using namespace std;
template<class T>
void print(const T& con)
{
for (const auto& e : con)
{
cout << e << ' ';
}
cout << endl;
}
int main()
{
set<int> s1;//无参构造
set<int> s2({ 6,0,2,8,4 });//初始化器构造
set<int> s3(s2);//拷贝构造
set<int> s4(s2.begin(), s2.end());//迭代器区间构造
cout << "s1:";
print(s1);
cout << "s2:";
print(s2);
cout << "s3:";
print(s3);
cout << "s4:";
print(s4);
return 0;
}
析构函数
析构函数帮助我们自动释放容器动态申请的空间。
赋值重载
将新内容分配给已经存在的容器，替换其当前内容。
代码示例：
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s1({ 4,8,2 });
set<int> s2;
s2 = s1;//赋值
for (auto& e : s2)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
四、set的迭代器接口
与vector、list等容器相同，set也支持使用迭代器进行元素访问和遍历。
这里有三点需要注意：
1. set的迭代器是双向迭代器。
2. set迭代器进行顺序遍历的结果是有序的，这归因于它采用了红黑树的中序遍历算法。
3. 无论是使用普通迭代器还是const迭代器，都无法修改set元素的值。（set元素的值不支持修改）
set迭代器的使用方法与其他容器没什么区别，这里就不再赘述。
五、set的容量接口
empty
判断set容器是否为空。若为空，则返回true；否则返回false。
该函数不会以任何方式修改容器。
代码示例：
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s1;
set<int> s2({ 1,2,3 });
cout << s1.empty() << endl;
cout << s2.empty() << endl;
return 0;
}
size
返回set容器当中的元素个数。
代码示例：
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s1;
set<int> s2({ 1,2,3 });
cout << s1.size() << endl;
cout << s2.size() << endl;
return 0;
}
六、set的增删相关接口
insert
insert的功能是插入元素，支持单个值插入、指定位置插入（实际未必插入在指定位置，因为要保持有序性）、迭代器区间插入和初始化器插入。
注意：单个值插入函数的返回值是一个pair（二元组，之前的文章已经提到过），其具体内容如下：
当容器中没有相同值元素，则插入成功，返回值pair的第一个元素是指向新插入元素的迭代器，第二个元素是布尔类型，值为true；反之，当容器中已有相同值的元素，则意味着插入失败，返回值pair的第一个元素是指向已有元素的迭代器，第二个元素的值为false。
对于multiset而言，由于其允许相同元素存在，所以单个值插入接口的返回值是一个指向新插入元素的迭代器。
代码示例：
#include <iostream>
#include <set>
using namespace std;
template<class T>
void print(const T& con)
{
for (const auto& e : con)
{
cout << e << ' ';
}
cout << endl;
}
int main()
{
set<int> s1({ 1,2,3 });
multiset<int> s2({ 1,2,3 });
//插入操作
auto a = s1.insert(1);
auto b = s2.insert(1);
cout << "s1.insert(1):" << a.second << endl;
cout << "s2.insert(1):" << *b << endl;
cout << endl;
cout << "s1:";
print(s1);
cout << "s2:";
print(s2);
return 0;
}
erase
erase的功能是删除set容器内的元素， 它支持按值删除，迭代器删除和迭代器区间删除。对于按值删除，函数的返回值是成功删除的元素个数，其他两个函数的返回值是指向被删除元素（或区间）下一个元素的迭代器。
对于multiset，如果有多个val值，则该函数会删除所有的val，并返回下一个元素的迭代器。
代码示例：
#include <iostream>
#include <set>
using namespace std;
template<class T>
void print(const T& con)
{
for (const auto& e : con)
{
cout << e << ' ';
}
cout << endl;
}
int main()
{
set<int> s = { 1,2,3,4,5,6,7,8,9,10 };
cout << "s: ";
print(s);
cout << endl;
//迭代器删除
cout << "迭代器删除" << endl;
s.erase(s.begin());
cout << "s: ";
print(s);
cout << endl;
//按值删除
cout << "按值删除" << endl;
cout << "被删除的元素个数：" << s.erase(1) << endl;
cout << "s: ";
print(s);
cout << endl;
cout << "被删除的元素个数：" << s.erase(2) << endl;
cout << "s: ";
print(s);
cout << endl;
//迭代器区间删除
cout << "迭代器区间删除" << endl;
s.erase(s.begin(), s.end());
cout << "s: ";
print(s);
return 0;
}
swap
交换两个set容器的内容。两个容器大小可能不同。
在调用成员函数之后，所有迭代器、引用和指针对交换后的对象仍然有效。
请注意，存在一个名称相同的非成员函数swap，它用与该成员函数类似的优化重载了该算法。
代码示例：
#include <iostream>
#include <set>
using namespace std;
template<class T>
void print(const T& con)
{
for (const auto& e : con)
{
cout << e << ' ';
}
cout << endl;
}
int main()
{
set<int> s1 = { 1,2,3 };
set<int> s2 = { 4,5,6 };
cout << "s1: ";
print(s1);
cout << "s2: ";
print(s2);
s1.swap(s2);//交换
cout << endl << "交换后：" << endl;
cout << "s1: ";
print(s1);
cout << "s2: ";
print(s2);
return 0;
}
clear
从set容器中删除所有元素，容器的大小变为0。
七、set的其他操作接口
find
find的功能是查找（按值查找）。在容器中搜索与val等效的元素，如果找到则返回指向查找到的元素迭代器，否则返回尾迭代器。
对于multiset，如果找到的元素在容器中有重复值，则函数返回中序遍历序列的第一个找到的元素的迭代器。
代码示例：
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s = { 1,2,3,4,5 };
int num = 0;
while (cin >> num)
{
if (s.find(num) != s.end())
{
cout << "找到了！\n" << endl;
}
else
{
cout << "没找到\n" << endl;
}
}
return 0;
}
count
count返回容器中值为val的元素个数。
因为set容器中的所有元素都是唯一的，所以该函数只能返回1或0，因此可以判断一个元素是否在set容器中。但对于允许出现重复元素的multiset，它还可以用于统计某元素的个数。
代码示例：
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s = { 1,2,3 };
multiset<int> ms = { 1,2,2,2,3 };
cout << s.count(2) << endl;
cout << ms.count(2) << endl;
return 0;
}
接下来要介绍的 lower_bound、 upper_bound 和 equal_range 是multiset常用接口。
lower_bound和upper_bound
返回一个迭代器，指向容器中第一个不在val值之前的元素（查找区间左端点）。
也就是说当容器内部有形如{val, val, val,...}的子序列时，返回第一个val的迭代器。
如果val应位于所有元素之前，则函数返回当前第一个元素的迭代器。
反之，若val应位于所有元素之后，则函数返回尾迭代器。
upper_bount函数返回一个迭代器，指向容器中被认为是val之后的第一个元素（查找区间右端点）。至于为什么不返回第一个不在val值之后的元素，是因为STL的区间都遵循“左闭右开”。
也就是说当容器内部有形如{val, val, val,...}的子序列时，返回最后一个val的下个元素的迭代器。
如果val应位于所有元素之前，则函数返回当前第一个元素的迭代器。
反之，如果val应位于所有元素之后，则函数返回尾迭代器。
代码示例：
#include <iostream>
#include <set>
using namespace std;
int main()
{
multiset<int> ms = { 1,2,2,2,3 };
//查找2的左端点和右端点
auto begin = ms.lower_bound(2);
auto end = ms.upper_bound(2);
//打印容器中所有的2
for (auto it = begin; it != end; it++)
{
cout << *it << ' ';
}
cout << endl;
return 0;
}
equal_range
返回一个pair（两个迭代器），表示范围的边界（注意前闭后开），该范围包含容器中与val相等的所有元素。
如果val应位于所有元素之前，则返回的两个迭代器都指向第一个元素。
反之，如果val应位于所有元素之后，则返回的两个迭代器都是尾迭代器。
代码示例：
#include <iostream>
#include <set>
using namespace std;
int main()
{
multiset<int> ms = { 1,2,2,2,3 };
//找到2的范围
auto range = ms.equal_range(2);
//打印所有2
for (auto it = range.first; it != range.second; it++)
{
cout << *it << ' ';
}
cout << endl;
}
总结
通过本文的学习，我们深入了解了STL中的set容器及其变种multiset。set以其元素自动排序且不重复的特性，在需要唯一性数据集合和高效查找操作的场景中发挥着重要作用。
在了解set容器的基础上，之后我们会进一步引出STL中的另一个重要容器——map。与set类似，map也是关联式容器，其底层结构同样可以采用红黑树。不同的是，map存储的是键值对（key_value），且键（key）是唯一的，而值（value）可以是任意的。map容器以键为基准进行自动排序，并支持高效的查找、插入和删除操作。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤