C++ STL 之 set 详解：从底层红黑树到实际应用

1. 从序列式容器到关联式容器

在 STL 的庞大体系中，我们最先接触的往往是vector、list、deque、array以及string这类容器。它们有一个共同的特征：数据在逻辑结构上呈现为一条线。 比如一个vector<int>存放了10, 20, 30, 40，每个元素凭借其存储位置就能确定彼此的前后关系；即使我们交换其中两个元素的位置，比如变成10, 30, 20, 40，它仍然是一个有效的线性结构。 这类容器被 STL 归类为序列式容器（Sequence Container），它们最关心的问题是“元素放在哪里”，也就是位置关系。

但在真实的软件开发中，我们经常遇到另一类需求：判断一个数字是否曾经出现过、统计一篇英文文章中每个单词出现的频率、或者根据学生编号快速查找对应的成绩。在这些场景里，我们并不在意数据在内存中如何排列，而是更关心数据之间是否存在某种映射关系——比如“编号 1001 对应成绩 95”。这种“键值对”式的关联关系，是序列式容器难以高效表达的。为此，STL 专门提供了另一大类容器——关联式容器（Associative Container），其中最为核心的就是map、set以及它们的无序版本unordered_map和unordered_set。前两者（map/set）的底层实现是一棵红黑树，后两者则基于哈希表。本章我们先深入探讨set，因为它是理解“键值搜索”场景的基石，而map则是在set的基础上扩展出了“键值对”的映射关系。

2. set 的基本概念与核心特性

set是 STL 中一种非常纯粹的关联式容器，它的设计目标就是存储一组互不相同的元素，并且能够按照某种顺序自动维护这些元素。这种“自动排序”加上“元素唯一”的特性，使得set在很多需要去重和有序遍历的场景中显得格外顺手。

举个例子，如果我们向一个set<int>中依次插入10、10、20，那么最终容器里只会保留一个10和一个20——第二次插入的10会被忽略。与此同时，当我们用迭代器遍历这个set时，输出的顺序一定是10, 20，而不是插入时的先后顺序。这种有序性并非巧合，而是直接源于set的底层数据结构——红黑树。红黑树本质是一棵平衡的二叉搜索树，它满足“左子树所有节点的值小于根节点，右子树所有节点的值大于根节点”的性质。当我们对这样一棵树进行中序遍历（左 → 根 → 右）时，得到的结果自然就是升序序列。因此，set的迭代器遍历是有序的，而且增删查操作都能在 O(logN) 的时间复杂度内完成，这比线性容器的 O(N) 查找要高效得多。

3. 为什么底层选择红黑树而非其他结构？

这是一个非常经典的问题，也是很多初学者容易困惑的地方。既然set只需要存储唯一元素并支持快速查找，为什么不用哈希表（平均 O(1) 查找）？又为什么不用vector或链表？

我们来逐一比较：vector的查找需要遍历整个数组，复杂度为 O(N)；如果要在中间插入元素，还需要移动后续所有元素，代价很高。链表虽然插入和删除很快（O(1)），但查找依然是 O(N)，因为链表没有随机访问能力，也无法利用有序性进行二分查找。哈希表的确能提供平均 O(1) 的查找速度，但它有一个致命的弱点——无法保证元素的有序性。例如，向哈希表中插入5、2、8，遍历时得到的顺序可能是8、5、2，这完全取决于哈希函数和冲突解决策略。

而set的设计目标之一就是“有序遍历”，因此哈希表并不符合要求。红黑树恰好在这三者之间取得了完美的平衡：它既保证了 O(logN) 的查找、插入和删除效率，又天然维持了元素的有序性，同时它的树高被严格控制在 logN 级别，避免了二叉搜索树在最坏情况下退化为链表的窘境。正是这些综合优势，让 STL 最终选择红黑树作为set和map的底层实现。

红黑树

4. set 的模板参数解析

翻开set的声明，我们会看到这样的模板定义：

template < class T, class Compare = less<T>, class Alloc = allocator<T> > class set;

虽然有三个模板参数，但绝大多数情况下我们只需要关注前两个。第一个参数T非常直观——它表示set中存储的元素类型，比如set<int>就是存放整数的集合。

第二个参数Compare才是理解set排序机制的关键。它默认是less<T>，这是一个函数对象（仿函数），其内部重载了operator()，默认行为是使用<运算符比较两个T类型的值。红黑树在构建和插入节点时，正是依靠这个比较器来决定新节点应该放在左子树还是右子树。当使用less<T>时，树的结构遵循“左小右大”，中序遍历得到升序；如果我们换成greater<T>，比较逻辑变成a > b，树的结构就会逆转，中序遍历自然得到降序。

所以，想要让set降序排列，只需这样声明：

set<int, greater<int>> s;

至于第三个参数Alloc，它通常用于定制内存分配策略，在一般应用中极少改动，我们暂且略过。理解Compare的作用，其实就是在理解红黑树的比较规则是如何影响整个容器的行为，这也为你后续学习自定义类型如何放入set（需要重载<运算符或提供自定义仿函数）打下了基础。

五、set 的构造与迭代器：遍历有序，但只读

5.1 set 的构造方式

set的构造方式和我们之前学过的vector、list非常相似，STL 容器在设计上保持了高度的一致性，这让我们学习新容器的成本大大降低。

最常用的是默认构造，创建一个空的set，后续再通过insert填入数据：

set<int> s;

迭代器区间构造则体现了 STL 容器之间通过迭代器解耦连接的设计思想。你可以从一个vector中取出一段迭代器范围，直接用来构造一个set，从而实现“去重 + 排序”一步到位：

vector<int> v = {1, 2, 3, 4, 2, 3}; set<int> s(v.begin(), v.end());

vector提供begin()和end()，set的构造函数接收两个迭代器作为first和last，逐个插入元素。至于这组迭代器来自vector、list还是原生数组，set并不关心——这就是迭代器作为“容器之间的通用桥梁”的意义。

C++11 之后还支持了初始化列表构造，写法更加简洁直观：

set<int> s = {5, 2, 8, 2, 1};

这里插入了两次2，但最终s中只会保留一个2，因为set的核心性质就是键值唯一。遍历这个s，你会看到1 2 5 8——已经自动排好序了。

课件中还提到了拷贝构造，用法跟其他容器完全一样，这里不再赘述。

5.2 迭代器遍历与中序

set支持正向迭代器和反向迭代器，这意味着你可以用begin()/end()正向遍历，也可以用rbegin()/rend()反向遍历。同时，支持迭代器也就意味着支持范围for循环：

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

关键问题来了：为什么输出是1 2 5 8，而不是插入顺序5 2 8 1？

答案藏在红黑树的结构里。当我们依次插入5、2、8、1时，红黑树内部会按照二叉搜索树的规则组织节点：

• 插入5作为根节点

• 插入2，比5小，放到左子树

• 插入8，比5大，放到右子树

• 插入1，比5小，往左走到2，比2小，放到2的左子树

最终树的结构大致如下（忽略红黑树的颜色平衡细节）：

5 / \ 2 8 / 1

当我们用迭代器遍历set时，底层走的是红黑树的中序遍历——先左子树，再根节点，最后右子树。所以遍历顺序是：1 → 2 → 5 → 8，天然升序。

课件里有一句话非常精炼地概括了这一点：

set 底层用红黑树实现，迭代器遍历走搜索树中序，因此元素有序。

5.3 迭代器为什么不能修改数据？

这是一个极其重要且容易踩坑的问题。我们来看这段代码：

set<int> s = {1, 2, 3}; auto it = s.begin(); *it = 10; // 编译报错

编译器会直接报错，提示无法给常量赋值。为什么set的迭代器不允许修改元素？

根本原因在于：修改set中的元素，本质上就是在修改红黑树节点的键值（key）。而红黑树的整个结构——哪个节点在左子树、哪个在右子树——完全依赖于这些键值的大小关系。一旦你随意修改了某个节点的值，整棵树的二叉搜索性质就可能被破坏。

举个具体的例子。假设红黑树目前的结构是：

5 / \ 3 8

如果我们把根节点5修改成100，树就变成了：

100 / \ 3 8

现在问题来了：100的左子树里放着3和8，它们都比100小，这符合“左子树 < 根节点”的规则，看起来似乎没问题。但你再想一下——节点8原本在5的右子树，现在却成了100的左子树，而100的右子树是空的。这种结构混乱会导致后续所有的查找、插入、删除操作全部失效。

为了避免这种灾难，STL 的设计者直接把set的迭代器设计成了只读模式。无论是iterator还是const_iterator，解引用后得到的都是const T&引用，从语法层面彻底禁止了修改。

这里可以提前跟map做一个对比，帮助你建立清晰的概念边界：

• set中只存键（key），修改键会破坏树结构，所以键不可改

• map中存的是键值对（key-value），修改值（value）不影响树结构，所以值可以改，但键（key）同样不可改

这个区别会在后面讲map时反复体现，现在先留个印象。

六、插入操作：insert 的返回值为什么是 pair？

6.1 基本插入行为

set的插入接口很直观，支持单个元素插入、初始化列表插入、以及迭代器区间插入：

对于单个元素的insert，由于set保证了键值唯一，第二次插入相同的值会被静默忽略。比如上面的代码中，2和8在初始化列表插入时已经存在于set中，所以实际插入的只有3和9。

把插入和遍历放在一起演示：

cpp #include <iostream> #include <set> using namespace std; int main() { // 去重 + 升序排序 set<int> s; s.insert(5); s.insert(2); s.insert(7); s.insert(5); // 重复，插入失败 auto it = s.begin(); while (it != s.end()) { // *it = 1; // 编译错误：不能给常量赋值 cout << *it << " "; ++it; } cout << endl; // 插入 initializer_list，已存在的值插入失败 s.insert({2, 8, 3, 9}); for (auto e : s) { cout << e << " "; } cout << endl; set<string> strset = {"sort", "insert", "add"}; for (auto& e : strset) { cout << e << " "; // 按 ASCII 码字典序输出 } cout << endl; return 0; }

运行结果：

2 5 7 2 3 5 7 8 9 add insert sort

这个样例同时演示了三个关键点：去重（重复的 5 被忽略）、排序（升序输出）、以及迭代器只读（注释掉的赋值语句编译失败）。最后对string类型的set进行遍历，输出按字典序排列，这验证了set的比较器默认使用<来比较元素。

6.2 insert 的返回值

接下来是重点：insert单个元素的返回值类型是pair<iterator, bool>。很多初学者第一次看到这个时会困惑——为什么不直接返回bool表示成功或失败？

我们来看两种场景。

场景一：插入成功

set<int> s;

auto ret = s.insert(10);

此时ret.first是指向新插入元素10的迭代器，ret.second是true。

场景二：插入失败（元素已存在）

s.insert(10); // 第一次插入，成功 auto ret = s.insert(10); // 第二次插入，失败

此时ret.first指向已经存在于set中的那个10，ret.second是false。

所以pair<iterator, bool>的设计意义在于：一次插入操作，同时告诉你两个信息——元素在哪里（迭代器），以及插入是否成功（bool）。如果插入失败，你还可以通过返回的迭代器拿到已存在的那个元素，做进一步处理。这种“状态 + 结果”打包返回的设计，在 STL 中屡见不鲜。

使用时可以这样判断：x'x

auto ret = s.insert(10); if (ret.second) { cout << "插入成功，元素位于：" << *ret.first << endl; } else { cout << "插入失败，元素已存在：" << *ret.first << endl; }

课件中把这一点放在了map的operator[]实现中重点展开，因为map的[]正是利用insert的这个特性来实现“查找 + 插入 + 修改”三合一的。我们现在先把set的接口吃透，后面讲map的时候就能顺理成章地理解。

七、查找操作：优先用容器自己的 find

7.1 set::find 与算法库 std::find

set提供了find成员函数，用于快速查找某个键是否存在：

set<int> s = {4, 2, 7, 8, 5, 9}; auto pos = s.find(7); if (pos != s.end()) { cout << "找到了：" << *pos << endl; }

set::find利用红黑树的搜索特性，时间复杂度是 O(log N)。

但很多初学者容易犯一个错误——使用算法库中的std::find：

#include <algorithm> auto pos = find(s.begin(), s.end(), 7);

这个find是泛型算法，它不知道底层是红黑树，只能从begin到end一个一个地遍历比较，时间复杂度是 O(N)。

两种写法：

// 算法库的查找 O(N) auto pos1 = find(s.begin(), s.end(), x); // set 自身实现的查找 O(logN) auto pos2 = s.find(x);

务必记住：对于关联式容器，永远优先使用容器自带的find成员函数。这是性能和正确性兼得的最佳实践。

7.2 count 也可以用来查找

set还提供了count成员函数，返回某个值的个数。由于set不允许重复，返回值只能是 0 或 1，所以它也可以用来判断元素是否存在：

if (s.count(x)) { cout << x << " 存在" << endl; } else { cout << x << " 不存在" << endl; }

count的时间复杂度也是 O(log N)，用法比find更简洁——如果你只需要知道“在不在”，而不需要获取迭代器做后续操作，用count更省事。

样例完整展示了find、erase和count的配合使用：

#include <iostream> #include <set> using namespace std; int main() { set<int> s = {4, 2, 7, 2, 8, 5, 9}; for (auto e : s) { cout << e << " "; } cout << endl; // 删除最小值 s.erase(s.begin()); for (auto e : s) { cout << e << " "; } cout << endl; // 直接删除指定值 x int x; cin >> x; int num = s.erase(x); if (num == 0) { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; // 先用 find 查找，再用迭代器删除 cin >> x; auto pos = s.find(x); if (pos != s.end()) { s.erase(pos); } else { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; // 利用 count 间接实现快速查找 cin >> x; if (s.count(x)) { cout << x << "在！" << endl; } else { cout << x << "不存在！" << endl; } return 0; }

这个样例覆盖了三种删除方式（删除迭代器位置、删除指定值、删除区间）和两种查找方式（find和count），建议你自己运行一遍，观察每一步的输出，对set的行为建立直观感受。

八、区间查找：lower_bound 与 upper_bound

8.1 这两个接口是做什么的？

lower_bound和upper_bound是set提供的两个区间查找接口，它们经常配合使用来处理一段连续的有序区间。

• lower_bound(val)：返回第一个大于等于val的元素的迭代器

• upper_bound(val)：返回第一个大于val的元素的迭代器

两者结合，可以精确锁定一个左闭右开的区间[lower_bound(val1), upper_bound(val2))。

8.2 典型使用场景：删除一个值区间

课件中有一个非常经典的例子。假设set中存放了10, 20, 30, 40, 50, 60, 70, 80, 90，现在要删除所有在[30, 60]闭区间内的元素——也就是删掉30, 40, 50, 60。

如果用遍历加判断的方式，代码啰嗦且效率低。用lower_bound和upper_bound可以一行定位区间：

#include <iostream> #include <set> using namespace std; int main() { set<int> myset; for (int i = 1; i < 10; i++) { myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90 } for (auto e : myset) { cout << e << " "; } cout << endl; // lower_bound(30) 返回第一个 >= 30 的位置 → 指向 30 auto itlow = myset.lower_bound(30); // upper_bound(60) 返回第一个 > 60 的位置 → 指向 70 auto itup = myset.upper_bound(60); // 删除 [itlow, itup) 区间，即 30 40 50 60 myset.erase(itlow, itup); for (auto e : myset) { cout << e << " "; } cout << endl; return 0; }

运行结果：

10 20 30 40 50 60 70 80 90 10 20 70 80 90

这里的关键在于：erase接收的是左闭右开的迭代器区间[first, last)。lower_bound(30)恰好指向 30（包含），upper_bound(60)指向 70（不包含 70，但 60 在区间内）。所以erase(itlow, itup)正好删掉了30, 40, 50, 60。

如果需求改成删除(30, 60)开区间（不包含 30 和 60），那就用upper_bound(30)作为起点，lower_bound(60)作为终点——起点不包含 30，终点包含 60 但lower_bound(60)指向 60 本身，区间[40, 60)就只包含 40 和 50。灵活运用这两个接口，可以精确控制区间边界。

这两个函数的底层也是红黑树查找，时间复杂度 O(log N)，比从头遍历要高效得多。

九、multiset：允许重复的 set

multiset和set几乎一模一样，唯一的区别是：multiset允许键值冗余，即多个相同的元素可以共存。

这个看似微小的差异，导致了一系列行为上的不同，需要你特别留意。

课件中给出了一个完整的multiset使用样例：

#include <iostream> #include <set> using namespace std; int main() { // multiset 排序但不去重 multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9}; auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; // find 查找中序的第一个 int x; cin >> x; auto pos = s.find(x); while (pos != s.end() && *pos == x) { cout << *pos << " "; ++pos; } cout << endl; // count 返回实际个数 cout << s.count(x) << endl; // erase 按值删除会删除所有匹配的元素 s.erase(x); for (auto e : s) { cout << e << " "; } cout << endl; return 0; }

我们来逐一拆解这些差异：

第一，insert永远成功。向multiset中插入一个已经存在的值，不会像set那样被忽略，而是会新增一个副本。所以multiset中的元素是排序的，但不去重。

第二，find返回中序的第一个匹配位置。当有多个相同的值时，find返回的是中序遍历中第一个等于该值的位置。如果你想遍历所有相同的值，需要从find返回的位置开始往后走，直到遇到不同的值为止（如样例中的while循环所示）。

第三，count返回实际个数。在set中count只能返回 0 或 1，但在multiset中它会返回匹配元素的实际数量。

第四，erase按值删除会删除所有匹配的元素。s.erase(x)会把所有值为x的元素全部删掉，返回删除的个数。这一点和set的“最多删一个”完全不同。

multiset的使用场景是：你需要保留所有数据（不去重），同时又希望它们始终保持有序。比如记录一组考试成绩，允许并列分数存在，但需要按分数从低到高遍历。

十、两道力扣题：set 如何让复杂问题变得简单

最后用两道力扣题展示了set的实战价值，我们简要拆解一下，让你感受“用对工具”的力量。

两个数组的交集

题目要求返回两个数组的交集，且结果中每个元素只能出现一次。

set的解法极其简洁：

cpp #include <iostream> #include <set> using namespace std; int main() { // multiset 排序但不去重 multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9}; auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; // find 查找中序的第一个 int x; cin >> x; auto pos = s.find(x); while (pos != s.end() && *pos == x) { cout << *pos << " "; ++pos; } cout << endl; // count 返回实际个数 cout << s.count(x) << endl; // erase 按值删除会删除所有匹配的元素 s.erase(x); for (auto e : s) { cout << e << " "; } cout << endl; return 0; }

两个set各自完成了“去重 + 排序”，然后双指针同步遍历，值相等就是交集。这个解法的优雅之处在于：你不用手动排序、不用手动去重、不用考虑重复元素会多次加入结果——set把底层脏活累活全包了。

142. 环形链表 II

这道题的常规解法需要快慢指针加数学推导，证明过程比较绕。用set来解，思路直接降维到“记录已访问节点”：

class Solution { public: ListNode* detectCycle(ListNode* head) { set<ListNode*> s; ListNode* cur = head; while (cur) { auto ret = s.insert(cur); if (!ret.second) { return cur; // 插入失败，说明 cur 之前访问过，这就是环的入口 } cur = cur->next; } return nullptr; } };

遍历链表，把每个节点的地址存入set。如果某个节点已经存在，说明链表有环，而且这个节点就是环的入口。这就是set的“去重 + 快速查找”能力在算法题中的降维打击——把复杂问题变成了“查重”问题。

十一、小结

这一部分我们完整覆盖了set的接口使用层面：构造方式、迭代器遍历（以及为什么不能修改）、插入（重点理解pair<iterator, bool>的设计意图）、查找（优先用容器自带的find）、删除（三种形式的适用场景）、以及lower_bound/upper_bound配合处理区间的技巧。最后通过multiset的对比和两道力扣题，帮你建立起“什么场景用什么工具”的判断力。

理解set的接口设计，本质上是在理解一个原则：底层数据结构（红黑树）的特性，决定了上层接口的行为边界。红黑树有序，所以set有序；红黑树靠比较规则维护结构，所以set的键不能改；红黑树查找 O(log N)，所以set::find比std::find快得多。把这条线索理清，set就不再是一个需要死记硬背接口的容器，而是一个你可以自如运用的工具。