1. 从序列式容器到关联式容器在 STL 的庞大体系中我们最先接触的往往是vector、list、deque、array以及string这类容器。它们有一个共同的特征数据在逻辑结构上呈现为一条线。 比如一个vectorint存放了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在很多需要去重和有序遍历的场景中显得格外顺手。举个例子如果我们向一个setint中依次插入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的底层实现。红黑树功能复杂度查找O(logN)插入O(logN)删除O(logN)有序遍历支持4. set 的模板参数解析翻开set的声明我们会看到这样的模板定义template class T, class Compare lessT, class Alloc allocatorT class set;虽然有三个模板参数但绝大多数情况下我们只需要关注前两个。第一个参数T非常直观——它表示set中存储的元素类型比如setint就是存放整数的集合。第二个参数Compare才是理解set排序机制的关键。它默认是lessT这是一个函数对象仿函数其内部重载了operator()默认行为是使用运算符比较两个T类型的值。红黑树在构建和插入节点时正是依靠这个比较器来决定新节点应该放在左子树还是右子树。当使用lessT时树的结构遵循“左小右大”中序遍历得到升序如果我们换成greaterT比较逻辑变成a b树的结构就会逆转中序遍历自然得到降序。所以想要让set降序排列只需这样声明setint, greaterint s;至于第三个参数Alloc它通常用于定制内存分配策略在一般应用中极少改动我们暂且略过。理解Compare的作用其实就是在理解红黑树的比较规则是如何影响整个容器的行为这也为你后续学习自定义类型如何放入set需要重载运算符或提供自定义仿函数打下了基础。五、set 的构造与迭代器遍历有序但只读5.1 set 的构造方式set的构造方式和我们之前学过的vector、list非常相似STL 容器在设计上保持了高度的一致性这让我们学习新容器的成本大大降低。最常用的是默认构造创建一个空的set后续再通过insert填入数据setint s;迭代器区间构造则体现了 STL 容器之间通过迭代器解耦连接的设计思想。你可以从一个vector中取出一段迭代器范围直接用来构造一个set从而实现“去重 排序”一步到位vectorint v {1, 2, 3, 4, 2, 3}; setint s(v.begin(), v.end());vector提供begin()和end()set的构造函数接收两个迭代器作为first和last逐个插入元素。至于这组迭代器来自vector、list还是原生数组set并不关心——这就是迭代器作为“容器之间的通用桥梁”的意义。C11 之后还支持了初始化列表构造写法更加简洁直观setint s {5, 2, 8, 2, 1};这里插入了两次2但最终s中只会保留一个2因为set的核心性质就是键值唯一。遍历这个s你会看到1 2 5 8——已经自动排好序了。课件中还提到了拷贝构造用法跟其他容器完全一样这里不再赘述。5.2 迭代器遍历与中序set支持正向迭代器和反向迭代器这意味着你可以用begin()/end()正向遍历也可以用rbegin()/rend()反向遍历。同时支持迭代器也就意味着支持范围for循环setint 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 迭代器为什么不能修改数据这是一个极其重要且容易踩坑的问题。我们来看这段代码setint 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 的返回值为什么是 pair6.1 基本插入行为set的插入接口很直观支持单个元素插入、初始化列表插入、以及迭代器区间插入对于单个元素的insert由于set保证了键值唯一第二次插入相同的值会被静默忽略。比如上面的代码中2和8在初始化列表插入时已经存在于set中所以实际插入的只有3和9。把插入和遍历放在一起演示cpp #include iostream #include set using namespace std; int main() { // 去重 升序排序 setint 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; setstring 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单个元素的返回值类型是pairiterator, bool。很多初学者第一次看到这个时会困惑——为什么不直接返回bool表示成功或失败我们来看两种场景。场景一插入成功setint s;auto ret s.insert(10);此时ret.first是指向新插入元素10的迭代器ret.second是true。场景二插入失败元素已存在s.insert(10); // 第一次插入成功 auto ret s.insert(10); // 第二次插入失败此时ret.first指向已经存在于set中的那个10ret.second是false。所以pairiterator, bool的设计意义在于一次插入操作同时告诉你两个信息——元素在哪里迭代器以及插入是否成功bool。如果插入失败你还可以通过返回的迭代器拿到已存在的那个元素做进一步处理。这种“状态 结果”打包返回的设计在 STL 中屡见不鲜。使用时可以这样判断xxauto ret s.insert(10); if (ret.second) { cout 插入成功元素位于 *ret.first endl; } else { cout 插入失败元素已存在 *ret.first endl; }课件中把这一点放在了map的operator[]实现中重点展开因为map的[]正是利用insert的这个特性来实现“查找 插入 修改”三合一的。我们现在先把set的接口吃透后面讲map的时候就能顺理成章地理解。七、查找操作优先用容器自己的 find7.1 set::find 与算法库 std::findset提供了find成员函数用于快速查找某个键是否存在setint 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() { setint 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_bound8.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() { setint 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允许重复的 setmultiset和set几乎一模一样唯一的区别是multiset允许键值冗余即多个相同的元素可以共存。这个看似微小的差异导致了一系列行为上的不同需要你特别留意。课件中给出了一个完整的multiset使用样例#include iostream #include set using namespace std; int main() { // multiset 排序但不去重 multisetint 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 排序但不去重 multisetint 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) { setListNode* 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的接口使用层面构造方式、迭代器遍历以及为什么不能修改、插入重点理解pairiterator, bool的设计意图、查找优先用容器自带的find、删除三种形式的适用场景、以及lower_bound/upper_bound配合处理区间的技巧。最后通过multiset的对比和两道力扣题帮你建立起“什么场景用什么工具”的判断力。理解set的接口设计本质上是在理解一个原则底层数据结构红黑树的特性决定了上层接口的行为边界。红黑树有序所以set有序红黑树靠比较规则维护结构所以set的键不能改红黑树查找 O(log N)所以set::find比std::find快得多。把这条线索理清set就不再是一个需要死记硬背接口的容器而是一个你可以自如运用的工具。