专业视角：set 和 multiset的原理与应用解析

文章目录

前言
- 关联式容器
- 键值对
- 树形结构的关联式容器
set
- 1. `set` 的定义
- 注意以下八点：
- 2. `set` 的常用操作
- 3. `set` 的迭代器
- 4. `set` 的底层实现
- 5. 自定义排序（比较器）
- 6. `set` 与 `multiset` 的区别
- 7. 示例：`set` 的完整代码
multiset

前言

关联式容器

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

那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的

键值对，在数据检索时比序列式容器效率更高。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代

表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然

有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应

该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结

构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使

用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一

个容器。

set

1. `set` 的定义

set 是 C++ 标准库中的一个关联容器，它存储的是唯一的元素，并且自动按一定的顺序排列元素。它通常基于平衡二叉搜索树（如红黑树）实现，提供 O(log n) 的查找、插入和删除时间复杂度。

特别记住两点：不重复，有序！

与 vector 或 list 等容器不同，set 会自动维护元素的顺序，通常是升序排序，但可以通过自定义比较函数来改变排序规则。

set的模板参数列表:

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。

Compare：set中元素默认按照小于来比较，也可以自己定义比较方式。

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

构造方式：

// 1. 默认构造函数// 创建一个空的 set，元素类型为 int，使用默认的比较函数 less<int>set<int> set1;// 2. 范围构造函数// 使用迭代器指定的范围来初始化 setvector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};set<int> set2(vec.begin(), vec.end());// 由于 set 中元素唯一，重复元素会被自动去除，且会按升序排列// 3. 拷贝构造函数// 创建一个新的 set，它是另一个 set 的副本set<int> set3(set2);// 4. 移动构造函数// 从另一个 set 中移动元素到新的 set 中，原 set 会变为空set<int> set4(move(set3));// 5. 初始化列表构造函数// 使用初始化列表来初始化 setset<int> set5 = {10, 20, 30, 40, 50};

set是按照一定次序存储元素的容器
在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。
set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行
排序。
set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对
子集进行直接迭代。
set在底层是用二叉搜索树(红黑树)实现的。

注意以下八点：

1. 与 map/multimap** 的区别：set 中只存 **value

区别：
- map 和 multimap 是键值对容器，每个元素是一个 <key, value> 对。
- set 中存储的仅是 value，但底层实现实际上将 value 视为 <value, value> 的键值对，这样可以复用相同的底层数据结构（如红黑树）。
插入元素：

std::set<int> s;
s.insert(5);  // 只插入 value，而不是 <key, value>

- `set` 中插入的只是单个值，而不是键值对。

2. 插入元素时，不需要构造键值对

由于 set 只需要存储 value，插入时直接提供单个值即可。底层数据结构会将其视为键值对 <value, value>，但用户无需关心这些细节。

示例：

std::set<int> s;
s.insert(10);  // 只需要传递单个值
s.insert(20);  // 不需要键值对

这种简化让 set 使用起来更加方便，因为它的重点是值本身，而不是键值关联。

3. set 中的元素不可以重复

特点：
set 保证存储的所有元素是唯一的。
实现方式：
- 当插入一个元素时，set 会根据比较规则（通常是 < 运算符）检查是否已经存在。
- 如果存在，则插入失败。

示例：

std::set<int> s;
s.insert(5);  // 插入成功
s.insert(5);  // 插入失败，值已经存在

应用场景：

去重。当需要去除数组或序列中的重复元素时，可以使用 std::set 或 std::unordered_set。将一组重复元素转化为唯一集合：

std::vector<int> v = {1, 2, 2, 3, 4, 4};
std::set<int> s(v.begin(), v.end());  // 自动去重

4. 使用 set 的迭代器遍历，可以得到有序序列

特点：
set 自动维护元素的顺序（通常是升序）。
遍历方式：
使用迭代器（begin() 和 end()）可以顺序访问元素。

示例：

std::set<int> s = {3, 1, 2};
for (auto it = s.begin(); it != s.end(); ++it) {std::cout << *it << " ";  // 输出：1 2 3
}

5. 默认按照“小于”比较排序

排序规则：
默认情况下，set 按照 < 运算符来比较元素。
自定义规则：
可以通过传入自定义比较器来改变排序方式。

示例：默认升序排序：

std::set<int> s = {3, 1, 2};
for (int x : s) {std::cout << x << " ";  // 输出：1 2 3
}

自定义降序排序：

std::set<int, std::greater<int>> s = {3, 1, 2};
for (int x : s) {std::cout << x << " ";  // 输出：3 2 1
}

6. 查找某个元素的时间复杂度为 O(log₂ n)

原因：
- set 底层实现基于红黑树（自平衡二叉搜索树），其深度为 O(log₂ n)。
- 插入、删除和查找的时间复杂度都与树的高度成正比，因此为 O(log₂ n)。

示例：

std::set<int> s = {3, 1, 2};
auto it = s.find(2);  // 查找值为 2 的元素
if (it != s.end()) {std::cout << "Found: " << *it << std::endl;
} else {std::cout << "Not found!" << std::endl;
}

7. set 中的元素不允许修改

原因：
- set 的底层实现依赖元素的排序规则。如果允许修改元素的值，可能破坏集合的有序性。
- 一旦元素被插入，红黑树会根据该值的位置平衡树的结构。如果值被修改，这种平衡可能失效。

示例：

std::set<int> s = {1, 2, 3};
auto it = s.find(2);
// *it = 5;  // 错误，不能直接修改元素

如果需要修改 set 中的元素，必须先删除该元素，再插入修改后的值：

s.erase(it);  // 删除元素
s.insert(5);  // 插入新值

8. 底层实现使用红黑树

红黑树简介：
红黑树是一种自平衡二叉搜索树，具有以下特点：

这些规则确保树的高度在 O(log₂ n) 范围内，从而保证插入、删除、查找操作的高效性。

- 每个节点要么是红色，要么是黑色。
- 树根是黑色。
- 红节点的子节点必须是黑色（即红节点不能连续）。
- 从根节点到任何叶子节点的路径中，黑节点数量相同。

红黑树在 set 中的作用：

确保 set 的元素总是有序。
保证查找、插入、删除的时间复杂度为 O(log₂ n)。

2. `set` 的常用操作

插入元素：insert() 方法插入一个元素。如果元素已经存在，则插入会失败，set 保证元素唯一性。

std::set<int> s;
s.insert(1);  // 插入元素 1
s.insert(2);  // 插入元素 2
s.insert(1);  // 插入失败，因为 1 已经存在

删除元素：erase() 方法用于删除指定的元素或通过迭代器删除元素。

s.erase(1);  // 删除元素 1

查找元素：使用 find() 查找元素，如果找到返回指向该元素的迭代器，若找不到返回 end() 迭代器。

auto it = s.find(2);  // 查找元素 2
if (it != s.end()) {std::cout << "Found: " << *it << std::endl;
}

访问元素：set 中的元素不能通过下标访问，必须使用迭代器。

for (auto it = s.begin(); it != s.end(); ++it) {std::cout << *it << " ";  // 输出 set 中的元素
}

大小和空检查：size() 方法返回容器中元素的个数，empty() 判断容器是否为空。

std::cout << "Size: " << s.size() << std::endl;
if (s.empty()) {std::cout << "Set is empty." << std::endl;
}

lower_bound(value)

功能：返回指向第一个**不小于 **value 的元素的迭代器。如果容器中不存在这样的元素，则返回指向 end() 的迭代器。

用法：常用于查找某个值或**第一个****大于等于**该值的元素。

示例代码

set<int> s = {10, 20, 30, 40, 50};int value = 25;auto it = s.lower_bound(value);  // 查找第一个不小于25的元素if (it != s.end()) {cout << "Lower bound of " << value << ": " << *it << endl;  // 输出 30} else {cout << "No element found." << endl;}

upper_bound(value)

功能：返回指向**第一个大于**** ****value** 的元素的迭代器。如果容器中不存在这样的元素，则返回指向 end() 的迭代器。
用法：常用于查找某个值的下一个元素，或第一个大于该值的元素。

示例代码

    set<int> s = {10, 20, 30, 40, 50};int value = 25;auto it = s.upper_bound(value);  // 查找第一个大于25的元素if (it != s.end()) {cout << "Upper bound of " << value << ": " << *it << endl;  // 输出 30} else {cout << "No element found." << endl;}

3. `set` 的迭代器

set 提供了双向迭代器，允许遍历容器中的元素。

begin()：返回指向容器第一个元素的迭代器。
end()：返回指向容器尾后位置的迭代器，即指向容器中最后一个元素的下一个位置。
rbegin()：返回指向容器最后一个元素的反向迭代器。
rend()：返回指向容器第一个元素前一个位置的反向迭代器。

示例：

std::set<int> s = {3, 1, 2};for (auto it = s.begin(); it != s.end(); ++it) {std::cout << *it << " ";  // 输出：1 2 3
}std::cout << std::endl;for (auto it = s.rbegin(); it != s.rend(); ++it) {std::cout << *it << " ";  // 输出：3 2 1
}

4. `set` 的底层实现

set 是基于平衡二叉搜索树（如红黑树或 AVL 树）实现的，这使得 set 能够提供 O(log n) 的查找、插入和删除操作。
每个节点包含一个元素和指向左右子节点的指针。树是自平衡的，即插入或删除操作后，树会通过旋转操作保持平衡，保证操作的时间复杂度为 O(log n)。

5. 自定义排序（比较器）

默认情况下，set 会按升序排列元素。如果想要按降序排列，或者按自定义规则排列，可以传入自定义的比较器。

例如，按降序排列：

#include <set>std::set<int, std::greater<int>> s;  // 使用 greater<int> 进行降序排列
s.insert(3);
s.insert(1);
s.insert(2);for (auto it = s.begin(); it != s.end(); ++it) {std::cout << *it << " ";  // 输出：3 2 1
}

6. `set` 与 `multiset` 的区别

1. 元素唯一性

set：不允许重复的元素。
multiset：允许存储重复的元素。

2. 插入规则

set：插入时会检查是否已有相同的元素，如果存在，则插入失败。
multiset：可以插入相同的元素，multiset 会记录每个重复值。

3. 元素计数

set：每个值在集合中最多出现一次，count() 的返回值是 0 或 1。
multiset：可以存储相同的元素，count() 返回指定值的出现次数。

4. 查找和删除

set：
- find()：返回指定元素的迭代器（如果存在）。
- erase()：删除指定值的唯一实例。
multiset：
- find()：返回指向第一个匹配值的迭代器。
- erase()：删除某个值的所有实例，或者通过迭代器删除指定的单个实例。

5. 其他特性

两者底层都使用红黑树，时间复杂度为 O(log n)。
都是有序容器，默认按升序排列元素。

#include <iostream>
#include <set>int main() {// 创建 set 和 multisetstd::set<int> mySet;std::multiset<int> myMultiset;// 插入元素mySet.insert(5);mySet.insert(3);mySet.insert(5);  // 重复插入失败myMultiset.insert(5);myMultiset.insert(3);myMultiset.insert(5);  // 重复插入成功// 遍历元素std::cout << "set elements: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << "\n";std::cout << "multiset elements: ";for (const auto& elem : myMultiset) {std::cout << elem << " ";}std::cout << "\n";// 查找元素auto itSet = mySet.find(5);if (itSet != mySet.end()) {std::cout << "Found 5 in set.\n";}auto itMultiset = myMultiset.find(5);if (itMultiset != myMultiset.end()) {std::cout << "Found 5 in multiset.\n";}// 统计元素数量std::cout << "Count of 5 in set: " << mySet.count(5) << "\n";std::cout << "Count of 5 in multiset: " << myMultiset.count(5) << "\n";// 删除元素mySet.erase(5);  // 删除唯一的 5myMultiset.erase(5);  // 删除所有 5// 遍历删除后的容器std::cout << "set after erase: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << "\n";std::cout << "multiset after erase: ";for (const auto& elem : myMultiset) {std::cout << elem << " ";}std::cout << "\n";return 0;
}

输出示例

set elements: 3 5 
multiset elements: 3 5 5 
Found 5 in set.
Found 5 in multiset.
Count of 5 in set: 1
Count of 5 in multiset: 2
set after erase: 3 
multiset after erase: 3

总结

相同点：
- 都是有序容器，支持高效的插入、查找和删除操作（O(log n)）。
- 使用迭代器遍历时，元素按照排序规则输出。
不同点：
- set 不允许重复元素，multiset 允许。
- set.count(x) 的值是 0 或 1，而 multiset.count(x) 可以大于 1。

选择 set 或 multiset，取决于是否需要支持重复的元素存储。

7. 示例：`set` 的完整代码

#include <iostream>
#include <set>int main() {// 用数组array中的元素构造setint array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };set<int> s(array, array+sizeof(array)/sizeof(array));cout << s.size() << endl;// 正向打印set中的元素，从打印结果中可以看出：set可去重for (auto& e : s)cout << e << " ";cout << endl;// 使用迭代器逆向打印set中的元素for (auto it = s.rbegin(); it != s.rend(); ++it)cout << *it << " ";cout << endl;// set中值为3的元素出现了几次cout << s.count(3) << endl;// 创建一个空的 set 容器std::set<int> s;// 插入元素s.insert(3);s.insert(1);s.insert(2);// 遍历 set 并输出元素for (auto it = s.begin(); it != s.end(); ++it) {std::cout << *it << " ";  // 输出：1 2 3}std::cout << std::endl;// 查找元素auto it = s.find(2);if (it != s.end()) {std::cout << "Found: " << *it << std::endl;}// 删除元素s.erase(2);// 输出删除后的元素for (auto it = s.begin(); it != s.end(); ++it) {std::cout << *it << " ";  // 输出：1 3}std::cout << "\nSize: " << s.size() << std::endl;std::cout << "Is empty: " << s.empty() << std::endl;return 0;
}

输出：

1 2 3 
Found: 2
1 3 
Size: 2
Is empty: 0

multiset

multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成
的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值**不能在容器
**中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则
进行排序。
multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭
代器遍历时会得到一个有序序列。
multiset底层结构为二叉搜索树(红黑树)。

注意：

multiset中再底层中存储的是<value, value>的键值对
mtltiset的插入接口中只需要插入即可
与set的区别是，multiset中的元素可以重复，set是中value是唯一的
使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
multiset中的元素不能修改
在multiset中找某个元素，时间复杂度为 $O(log_2 N)$
multiset的作用：可以对元素进行有重复的排序

📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
本人也很想知道这些错误，恳望读者批评指正！
我是：勇敢滴勇~感谢大家的支持！