专业视角set-和-multiset的原理与应用解析
专业视角：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++ 标准库中的一个关联容器，它存储的是
唯一的元素
，并且自动按一定的顺序排列元素。它通常基于
平衡二叉搜索树
（如红黑树）实现，提供
<u>O(log n)</u>
的查找、插入和删除时间复杂度。
特别记住两点：不重复，有序！
与
vector
或
list
等容器不同，
set
会自动维护元素的顺序，
通常是升序排序
，但可以通过自定义比较函数来改变排序规则。
- set的模板参数列表:
T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于来比较，也可以自己定义比较方式。
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
构造方式：
// 1. 默认构造函数
// 创建一个空的 set，元素类型为 int，使用默认的比较函数 less<int>
set<int> set1;
// 2. 范围构造函数
// 使用迭代器指定的范围来初始化 set
vector<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. 初始化列表构造函数
// 使用初始化列表来初始化 set
set<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); // 插入失败，值已经存在
应用场景 ：
- 去重。当需要去除数组或序列中的重复元素时，可以使用
<font style="color:rgba(0, 0, 0, 0.85);">std::set</font>或<font style="color:rgba(0, 0, 0, 0.85);">std::unordered_set</font>。将一组重复元素转化为唯一集合：
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 和 multiset
std::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); // 删除唯一的 5
myMultiset.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中的元素构造set
int 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: 0multiset
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 ( l o g 2 N ) O(log_2 N)
O
(
l
o
g
2
N
)
multiset的作用：可以对元素进行有重复的排序
- 📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
- 本人也很想知道这些错误，恳望读者批评指正！
- 我是：勇敢滴勇~感谢大家的支持！