C++算法
C++ STL set 系列：底层原理、核心接口与实战场景
C++ STL set 系列基于红黑树实现，具备自动排序与高效查找特性。 set 与 multiset 的区别，涵盖初始化、插入、查找、删除及区间操作等核心接口，并通过环形链表检测与数组交集等算法题展示实际应用场景，帮助开发者掌握有序数据管理技能。
C++ STL set 系列基于红黑树实现，具备自动排序与高效查找特性。 set 与 multiset 的区别，涵盖初始化、插入、查找、删除及区间操作等核心接口，并通过环形链表检测与数组交集等算法题展示实际应用场景，帮助开发者掌握有序数据管理技能。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
在 C++ STL 容器中，set 系列（set 与 multiset）是基于红黑树实现的关联式容器，核心特性是 '自动排序' 与 '高效查找'。它既能解决 '数据去重 + 排序' 的基础需求，也能在复杂场景中（如区间删除、频率统计）提供 O(log N) 级别的操作效率。本文将结合实战代码，从 set 的核心概念入手，拆解其构造、增删查、区间操作等关键接口，同时对比 set 与 multiset 的差异，帮你彻底掌握这一高频使用容器。
STL 容器的设计围绕 '数据如何存储与访问' 展开，序列式与关联式容器的核心差异体现在存储逻辑与访问方式上，具体对比如下：
| 特性 | 序列式容器（如 vector、list） | 关联式容器（如 set、map） |
|---|---|---|
| 存储逻辑 | 按插入顺序存储，元素位置由插入时机决定 | 按键（key）的内在规则存储（如排序规则） |
| 访问方式 | 通过下标/迭代器位置访问（如 vec[2]） | 通过键值匹配访问（如 set.find(3)） |
| 底层结构 | 动态数组（vector）、双向链表（list）等 | 平衡二叉搜索树（红黑树，set/map）、哈希表（unordered_set） |
| 核心优势 | 插入顺序稳定，适合频繁增删尾部元素 | 自动排序，查找/删除效率高（O(log N) 或 O(1)） |
| 典型使用场景 | 存储连续数据、需要按插入顺序遍历、动态扩容需求 | 去重排序、快速查找、键值映射、区间操作 |
补充说明：
set 与 multiset 底层均基于红黑树（一种自平衡二叉搜索树）实现，这一结构赋予它们以下核心特性：
set 的声明：
template<class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T>> // set::allocator_type
class set;
参考文档：set - C++ Reference
set 的构造相关接口：
// empty (1) 无参默认构造
explicit set(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template<class InputIterator>
set(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
// copy (3) 拷贝构造
set(const set& x);
// initializer list (5) initializer 列表构造
set(initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 迭代器是一个双向迭代器 iterator -> a bidirectional iterator to const value_type
// 正向迭代器 iterator begin(); iterator end();
// 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();
下面会通过多个测试函数覆盖 set 的核心操作，我们结合代码解析其使用方法与注意事项。
set 支持多种插入方式，插入后自动去重并按升序排列。代码示例（注意看注释）：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <set>
using namespace std;
// 测试 set 的插入与遍历（去重 + 自动排序）
void test_set1() {
set<int> s;
// 方式 1：单个元素插入
// s.insert(3); s.insert(1); s.insert(2); s.insert(5); s.insert(3); s.insert(5); s.insert(6);
// 方式 2：初始化列表批量插入
s.insert({3, 1, 2, 5, 3, 5, 6});
// 遍历方式 1：迭代器遍历（注意：*it 不可修改）
// 遍历结果：去重 + 有序
set<int>::iterator it = s.begin();
while (it != s.end()) {
//*it = 1; // 不能修改
cout << *it << " ";
++it;
}
cout << endl;
// 遍历方式 2：范围 for 循环
for (auto& e : s) {
cout << e << " ";
}
cout << endl;
}
int main() {
test_set1();
return 0;
}
关键说明：
set<int, greater<int>> s。set 提供 find（查找）、count（统计）、erase（删除）接口，支持按 key 或迭代器操作：
// 测试 set 的查找与删除
void test_set2() {
set<int> s;
s.insert({3, 1, 2, 5, 3, 5, 6}); // 去重后：1 2 3 5 6
int x = 0;
cin >> x;
cout << s.erase(x) << endl; // 删掉了几个返回值就是几，在 set 里就是 1，没删掉就是 0
// 查找元素：find 返回迭代器，未找到则返回 s.end()
// auto pos = s.find(x);
// if (pos != s.end()) { s.erase(pos); } // 找到后删除
// 统计元素个数：set 中仅返回 0 或 1（判断存在性）
if (s.count(x)) {}
for (auto& e : s) {
cout << e << " ";
}
cout << endl;
}
int main() {
test_set2();
return 0;
}
关键说明：
erase 的返回值是删除元素的个数，在 set 里要么是 0 要么是 1，multiset 删了几个就是几。count 在 set 中主要用于判断元素是否存在，在 multiset 中返回实际个数。set 的区间操作依赖 lower_bound 和 upper_bound，用于快速定位边界，结合 erase 可高效删除区间元素：
// 测试 set 的区间操作
void test_set3() {
set<int> s;
s.insert({3, 1, 2, 5, 3, 5, 6, 7, 9});
for (auto& e : s) {
cout << e << " ";
}
cout << endl;
// 需求：删除 [3, 8] 区间的元素（即>=3 且<=8）
// lower_bound(val)：返回第一个>=val 的迭代器（此处指向 3）
auto it1 = s.lower_bound(3);
// upper_bound(val)：返回第一个>val 的迭代器（此处指向 9）
auto it2 = s.upper_bound(8);
// 按迭代器区间删除：删除 [it1, it2) 内的元素
s.erase(it1, it2);
for (auto& e : s) {
cout << e << " ";
}
cout << endl;
}
int main() {
test_set3();
}
关键说明：
lower_bound 与 upper_bound 的时间复杂度均为 O(log N)，是区间操作的核心；[begin, end)）。multiset 与 set 接口一致，核心差异是允许重复 key，适用于需要存储相同元素并统计频率的场景：
// 测试 multiset（支持重复 key）
void test_multiset() {
multiset<int> s;
// 插入重复元素（不会去重）
s.insert({3, 1, 2, 5, 3, 5, 6, 3, 3});
// 1. 遍历：有序但保留重复元素
multiset<int>::iterator it = s.begin();
while (it != s.end()) {
//*it = 1; // 不能修改
cout << *it << " ";
++it;
}
cout << endl;
// 2. 查找：返回中序遍历的第一个目标元素
auto pos = s.find(3);
// 打印所有 3
while (pos != s.end() && *pos == 3) {
cout << *pos << " ";
++pos;
}
cout << endl;
// 3. 查找有 3 的区间，左闭右开，【)//std::pair<multiset<int>::iterator, multiset<int>::iterator> ret = s.equal_range(3);
auto ret = s.equal_range(3);
// 4. 统计：返回元素实际个数
cout << s.count(3) << endl; // 有几个 3
// 5. 删除：按 key 删除所有匹配元素
cout << s.erase(3) << endl; // 删掉所有的 3，并返回删掉的 3 的个数
s.erase(5); // 删掉所有的 5
for (auto& e : s) {
cout << e << " ";
}
cout << endl;
}
int main() {
test_multiset();
}
set 与 multiset 的核心差异总结：
| 操作 | set | multiset |
|---|---|---|
| 插入重复元素 | 自动去重，重复元素插入失败 | 不去重，保留所有重复元素，插入成功 |
find(key) | 返回唯一匹配元素的迭代器，未找到返回 end() | 返回中序遍历中第一个匹配元素的迭代器 |
count(key) | 返回 0 或 1（仅用于判断元素是否存在） | 返回元素在容器中实际出现的次数 |
erase(key) | 若元素存在则删除 1 个，不存在则删除 0 个 | 删除容器中所有与 key 匹配的元素 |
set 系列的 '自动排序 + 高效查找' 特性在算法与工程中应用广泛，以下是两个典型题目：
题目链接：142. 环形链表 II - 力扣（LeetCode） 题目要求：找到环形链表的入口结点 思路：用 set 存储遍历过的节点，若插入节点时发现已存在，该节点即为入口。
C++ 算法代码：
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
set<ListNode*> s;
ListNode* cur = head;
while (cur) {
auto ret = s.find(cur);
// 不存在就插入节点
if (ret == s.end()) s.insert(cur);
// 已经存在证明这就是入环节点
else return cur;
cur = cur->next;
}
return nullptr;
}
};
题目链接：349. 两个数组的交集 - 力扣（LeetCode） 题目要求：给定两个数组，计算它们的交集（结果需去重）。 思路：用 set 对两个数组去重 + 排序，再用双指针遍历两个 set，找到共同元素。
C++ 算法代码：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ret;
// 1. 用 set 对两个数组去重 + 排序
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
auto it1 = s1.begin();
auto it2 = s2.begin();
// 2. 双指针遍历，找共同元素
while (it1 != s1.end() && it2 != s2.end()) {
// 小的++
if (*it1 < *it2) ++it1;
else if (*it1 > *it2) ++it2;
// 相等的是交集，加入结果，然后同时++
else {
ret.push_back(*it1);
++it1;
++it2;
}
}
return ret;
}
};
差集和交集的实战使用：多端文件同步的逻辑
通过 '差集识别新增 / 缺失文件，交集比对时间戳确定更新方向'，避免全量传输，大幅减少带宽消耗和同步时间，是云存储、多端协作工具（如网盘、协同办公软件）的常见底层逻辑之一。
set 系列作为 STL 关联式容器的核心，以红黑树为支撑，实现了自动排序、高效查找与去重（或允许多重复）的能力，是处理 '有序数据管理' 场景的利器。掌握其接口与特性，既能简化代码逻辑，又能在算法、工程中提升性能，是 C++ 开发者的必备技能。