【STL】set

在 $C$++ $STL$ 标准库中，$set$ 是一个关联式容器，表示一个集合，用于存储唯一元素的容器。$set$ 中的元素会自动按照一定的顺序排序（默认情况下是升序）。这意味着在 $set$ 中不能插入重复的元素，因为重复的元素会被忽略。

---

前言 —— 关联式容器

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。

关联式容器中的元素是按关键字（$key$）来保存和访问的。

$C$++ $STL$ 中主要提供了以下关联式容器：

1. $set/multiset$（集合$/$多重集合）

2. $map/multimap$（映射$/$多重映射）

3. $unordered\_set/unordered\_multiset$（无序集合$/$多重无序集合）

4. $unordered\_map/unordered\_multimap$（无序映射$/$多重无序映射）

$STL$ 标准库中的 $map$ 和 $set$ 底层是用红黑树实现的，红黑树是一颗平衡二叉搜索树。

$set$ 是 $key$ 搜索场景的结构，$map$ 是 $key/value$ 搜索场景的结构。

---

一、set 的介绍

$set$ 系列根据容器是否支持插入相同元素而分为了 $set$（集合）和 $multiset$（多重集合）。

$set$ 其实就是按特定顺序存储唯一元素的容器：

$multiset$ 其实就是按特定顺序存储元素的容器，其中多个元素可以具有等效的值：

由于最常用的还是 $set$ 容器，因此这里主要介绍的是 $set$，而 $multiset$ 和 $set$ 只有在一些地方有略微的不同，稍注意一下即可。

$set$ 的声明如下：

template < class T, 					// set::key_type/value_typeclass Compare = less<T>, 	// set::key_compare/value_compareclass Alloc = allocator<T> 	// set::allocator_type> class set;

1. $T$ 就是 $set$ 底层关键字的类型。

2. $set$ 默认要求 $T$ 支持小于比较（less<T>，升序排序），如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模板参数。

3. $set$ 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个模板参数。

注意：一般情况下，我们都不需要传后两个模版参数。

$set$ 底层是用红黑树实现的，增删查效率是 $O(logN)$，迭代器遍历是走的搜索树的中序，所以是有序的。

---

二、set 的使用（常用接口）

下面只列举了 $set$ 最常用的几个接口，更多详细信息可以自行查官方文档：$set$。

1. 常见构造

构造 $(constructor)$ 函数声明	接口说明
$set()$	无参默认构造
$set(constset\&x)$	拷贝构造
$set(InputIteratorfirst,InputIteratorlast)$	使用迭代器区间构造
$set(initializer\_list<value\_type>il)$	使用 $initializer$ 列表构造

1. 无参默认构造：

set<int> s1;					// 升序
set<int, greater<int>> s2;		// 降序

2. 拷贝构造：

set<int> s = { 3,1,2,4,5 };
set<int> s1(s);					// 升序
set<int, greater<int>> s2 = s;	// 降序

3. 迭代器区间构造：

int a[] = { 3,1,2,4,5 };
vector<int> v = { 3,1,2,4,5 };
set<int> s1(a ,a + 5);							// 升序
set<int, greater<int>> s2(v.begin() ,v.end());	// 降序

4. $initializer$ 列表构造：

set<int> s1 = { 3,1,2,4,5 };				// 升序
set<int, greater<int>> s2({ 3,1,2,4,5 });	// 降序

2. iterator 的使用

$iterator$ 的使用	接口说明
$begin()$ $+$ $end()$	正向迭代器（$iterator$）
$rbegin()$ $+$ $rend()$	反向迭代器（$reverse\_iterator$）

1. $set$ 的迭代器支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的是中序遍历。

2. 支持迭代器就意味着支持范围 $for$。

3. $set$ 的 $iterator$ 和 $const\_iterator$ 都不支持迭代器修改数据，修改关键字数据，就破坏了底层搜索树的结构。

4. $set$ 的迭代器是一个双向迭代器：iterator -> a bidirectional iterator to const value_type。
   

set<int> s = { 3,5,4,2,1 };// 1.正向迭代器
auto it = s.begin();
while (it != s.end())
{cout << *it << " ";++it;
}
cout << endl;// 2.反向迭代器
auto rit = s.rbegin();
while (rit != s.rend())
{cout << *rit << " ";++rit;
}
cout << endl;// 3.范围for
for (auto& e : s)
{cout << e << " ";
}
cout << endl;

输出：

1 2 3 4 5
5 4 3 2 1
1 2 3 4 5

3. 增删查

$set$ 增删查	接口说明
$insert$	插入 $val$ 数据
$erase$	删除 $val$ 数据
$find$	查找 $val$，返回 $val$ 位置的迭代器（没找到返回 $end()$）
$count$	查找 $val$，返回 $val$ 的个数
$lower\_bound$	返回大于等于 $val$ 位置的迭代器
$upper\_bound$	返回大于 $val$ 位置的迭代器

1. 插入数据（insert）：

vector<int> v = { 1,2,5 };
set<int> s;// 1.直接插入
s.insert(3);
// 2.指定位置插入
s.insert(s.begin(), 4);
// 3.迭代器区间插入
s.insert(v.begin(), v.end());
// 4.initializer插入
s.insert({ 6,7,8 });for (const auto& e : s) cout << e << " "; cout << endl;

输出：

1 2 3 4 5 6 7 8

2. 查找 + 删除数据（find + erase）：

set<int> s = { 1,2,3,4,5,6,7,8 };// 1.指定位置删除
s.erase(s.begin());
// 2.指定数据删除
s.erase(5);
// 3.迭代器区间删除
auto it = s.find(4);		// 返回值对应的迭代器（没找到就返回s.end()）
if(it != s.end())s.erase(s.begin(),it);	// 前闭后开[s.begin(),it)for (const auto& e : s) cout << e << " "; cout << endl;

输出：

4 6 7 8

3. lower_bound / upper_bound：

set<int> s = { 1,2,3,4,5,6,7,8 };auto it1 = s.lower_bound(3);	// 返回第一个值 >= 3的迭代器
auto it2 = s.upper_bound(7);	// 返回第一个值 > 3的迭代器// 删除[3,7]区间的数据
s.erase(it1,it2);for (const auto& e : s) cout << e << " "; cout << endl;

输出：

1 2 8

4. multiset 和 set 的差异

$multiset$ 和 $set$ 的使用基本完全类似，主要区别点在于 $multiset$ 支持值冗余。

那么 $insert/find/count/erase$ 都围绕着支持值冗余有所差异：

1. $insert$ 可以插入相同的值：

multiset<int> s = { 1,2,3,4,5,6,7,8 };
s.insert(6);
s.insert(6);
s.insert(6);for (const auto& e : s) cout << e << " "; cout << endl;

输出：

1 2 3 4 5 6 6 6 6 7 8

2. 如果要查找的 $x$ 有多个值，$find$ 会返回中序的第一个：

multiset<int> s = { 1,2,3,4,5,6,6,6,6,7,8 };auto it = s.find(6);
while (it != s.end() && *it == 6)
{cout << *it << " ";++it;
}
cout << endl;

输出：

6 6 6 6

3. $count$ 会返回 $x$ 的实际个数：

multiset<int> s = { 1,2,3,4,5,6,6,6,6,7,8 };cout << "6的个数：" << s.count(6) << endl;
cout << "9的个数：" << s.count(9) << endl;

输出：

6的个数：4
9的个数：0

4. $erase$ 指定值删除时，会删除所有的 $x$：

multiset<int> s = { 1,2,3,4,5,6,6,6,6,7,8 };// 1.指定迭代器删除只会删除一个值
auto it = s.find(6);
s.erase(it);
for (const auto& e : s) cout << e << " "; cout << endl;// 2.指定值删除会删除所有的值
s.erase(6);
for (const auto& e : s) cout << e << " "; cout << endl;

输出：

1 2 3 4 5 6 6 6 7 8
1 2 3 4 5 7 8

---

三、set 的模拟实现

---

总结