
简介面向C初学者与需要快速上手STL的开发者这份代码资源围绕集合容器set展开用可运行的示例依次演示声明初始化、元素插入删除、迭代器与范围for遍历以及size、empty、find、count、lower_bound、upper_bound、merge等常用操作既说明set自动去重、按升序排列的特点也帮助读者将set应用到去重、快速查找、集合运算等实际场景。资源包共2个文件以cpp示例代码和txt说明文档为主整体仅714B轻量易读cpp部分可直接编译运行txt部分对关键函数、运行方式与注意事项作补充说明。目前已有207人学习读者可结合示例逐一尝试关注erase与find组合使用、lower_bound与upper_bound边界判断等细节加深对红黑树底层实现与O(log n)操作代价的理解。无论是准备面试、完成课程设计还是日常算法练习这份小而精的资料都能提供清晰的入门参考。 调试C代码的时候我经常看到新人拿着vector写完一堆逻辑去手动去重、排序最后代码又长又容易出错。其实STL里早就给你准备好了现成的容器——set。它内部基于红黑树实现所有元素自动按key排好序并且每个key只出现一次。在需要“去重有序快速查找”的场景里set几乎是最高效省心的选择也是C STL容器中最能体现标准库设计之美的容器之一。这篇内容我把自己使用set的心得和踩过的坑都整理出来从底层原理到实操代码从入门接口到性能优化希望对正在学C或准备用STL的你有帮助。无论你是刚接触C的小白还是想系统复习STL的开发者这篇都适合你读。1. set到底是个什么样的容器1.1 红黑树给set带来了什么set的全称是std::set定义在头文件中。它底层使用红黑树这是一种弱平衡二叉搜索树。这里不展开树的全部细节你只需要理解三个关键特性元素唯一你插入重复的值时set会忽略它。元素自动排序默认按升序排列插入之后容器始终有序。操作效率稳定插入、删除、查找都是O(log n)。要直观理解set可以把它类比成一个“永远排好序、不能放重复东西的袋子”。你每次往袋子里丢一个元素它会自己找到合适的位置插进去你不需要自己遍历、排序、去重。这个特性在不少场景下非常有用比如维护一组黑名单、统计一段时间内的不重复用户ID、在算法题中维护滑动窗口内的不同元素集合等。set的优势来自红黑树本身树的高度被约束在log n级别所以每轮查找和调整都在有限步数内完成不会像普通链表那样退化成O(n)。正因为有这样的结构支撑set才能在大数据量下保持稳定性能这也是STL选择它作为set底层实现的核心原因。1.2 set和vector、map的区别我经常被问“set和vector到底用哪个”这里给一个清晰的对比容器是否有序是否允许重复查找/插入时间复杂度适用场景vector可手动排序允许查找O(n)尾部插入O(1)数组式存储、随机访问set自动有序不允许O(log n)去重、有序集合、快速查找unordered_set无序不允许平均O(1)只关心快速查找不关心顺序multiset自动有序允许O(log n)需要有序多重集合从这个对比可以看出set不是万能的它的核心是“有序唯一”的平衡。如果你只想知道某个值存不存在且不关心顺序用unordered_set会更快如果你需要按顺序遍历元素set比unordered_set更好用。set和map的区别则在于map存储键值对set只存储键是“键即值”的容器。当你需要“键-值”的映射关系时应该选用map。1.3 说人话版本set能解决什么问题我用一个实际例子说明。某个业务场景需要实时维护“当前在线用户ID”要求不重复且最后按ID从小到大展示。如果用最笨的方法你得每次插入后sort一次复杂度O(n log n)如果自己写二叉搜索树又要处理平衡问题。而set只要一行声明然后不断insert就完事。再比如算法题里统计“一个字符串中有多少种不同字符”直接把每个字符丢进set最后size就是答案。这类“去重计数有序”的需求set就是正确工具。所以当你发现自己要手写排序去重逻辑时先停下来想想set大多数情况下标准库已经替你准备好了。2. 核心操作与使用姿势2.1 声明、插入与去重使用set之前要先包含头文件#include set具体示例std::setint s; s.insert(5); s.insert(2); s.insert(8); s.insert(5); // 重复set会忽略 std::cout s.size() std::endl; // 输出3你可能会好奇insert重复元素时发生了什么实际上std::set::insert返回一个pairiterator, boolbool表示是否插入成功。如果重复bool为false迭代器指向已存在的元素。很多新手容易忽略这个返回值导致误以为插进去了。如果对比insert和emplaceemplace在构造复杂对象时更高效因为它直接在节点内构造元素避免了一次拷贝或移动。对于int、double这类普通类型两者差别不大。insert的返回值在实战中很有用。例如在任务调度器中你要保证每个任务ID只出现一次同时还要判断是否真的插入了std::setint taskSet; taskSet.insert(101); auto [it, inserted] taskSet.insert(101); if (!inserted) { // 任务101已经存在 }C17的结构化绑定让这个操作非常优雅也让代码意图清晰很多。2.2 查找与边界查询set的查找接口主要有三个find、count、lower_bound/upper_bound。find(key)返回迭代器找不到返回end()。count(key)因为set不允许重复返回值只会是0或1所以常用来做存在性判断。lower_bound(key)返回第一个不小于key的迭代器。upper_bound(key)返回第一个大于key的迭代器。下面是一个实际例子std::setint s {1, 3, 5, 7, 9}; auto it s.find(3); if (it ! s.end()) { // 找到了 } if (s.count(7) 0) { // 存在 }在算法题里lower_bound非常香比如“找到大于等于x的最小值”auto it s.lower_bound(x); if (it ! s.end()) { std::cout *it std::endl; }这类“动态维护并查找最近比目标大的数”的需求如果改用vectorsort每次查找都要重新排序或者做二分代码复杂度和时间成本都更高。set天然有序配合lower_bound一行就能解决。2.3 删除元素set删除有三种常见方式s.erase(5); // 按值删除返回删除的个数0或1 s.erase(it); // 按迭代器删除 s.erase(start, end); // 按范围删除这里有一个特别重要的坑如果你写s.erase(it)后还要继续使用it就会面临迭代器失效问题。下面在第4节会详细讲。总之在遍历删除时建议统一使用“it s.erase(it)”的写法因为C11起set的erase会返回下一个迭代器。2.4 multiset和unordered_set是不是setmultiset允许重复元素set不允许unordered_set不排序。选择的时候要“按需选型”。如果你需要统计元素出现次数、同时又要求数据有序multiset是合适方案如果只做存在性判断unordered_set的哈希方案通常更快。但要注意unordered_set对自定义类型要求提供哈希函数门槛高一些。而set只需要提供比较函数或重载operator这点对很多场景来说更友好。我自己的经验是除非明确不需要顺序否则优先考虑set它能避免很多和哈希函数相关的坑。3. 实操从零搭建一个set应用3.1 环境准备VS Code MinGW或者Visual Studio都可以。set的使用很简单编译时加上-stdc17就能体验结构化绑定等现代特性。如果你还在用老旧的C98标准也没关系set的基础接口从C98就存在只是少了一些语法糖。在正式开始写代码前我建议先建一个空白cpp文件只包含和 把下面的示例逐个跑一遍。边跑边打印结果比自己只看文档印象深很多。3.2 示例1学生成绩去重排序假设有三份成绩单想要输出所有不重复的成绩并按从低到高排列#include iostream #include set int main() { std::setint scores; scores.insert(88); scores.insert(92); scores.insert(75); scores.insert(88); // 重复成绩 scores.insert(99); for (int score : scores) { std::cout score ; } std::cout std::endl; return 0; }运行结果75 88 92 99自动完成了去重和排序。如果自己写要先sort再unique最后还要考虑如何打印三行逻辑可能变成十几行。这种场景在作业和面试里非常常见也是set最基础、最典型的用法。3.3 示例2自定义结构体和排序规则如果存的是自定义类型比如学生你需要告诉set怎么比较两个学生。方法有两种第一种是重载运算符struct Student { int id; std::string name; bool operator(const Student other) const { return id other.id; } }; std::setStudent students;第二种是提供自定义比较器比如按分数降序struct ScoreDesc { bool operator()(const Student a, const Student b) const { return a.score b.score; } }; std::setStudent, ScoreDesc students;这里我踩过最大的坑是自定义类型的operator必须严格满足严格弱序strict weak ordering也就是不能既存在ab又存在ba。如果你只在id相等时返回true逻辑就会崩溃。所以比较函数一定要在设计时想清楚“相等就返回false”。对于需要按多个字段排序的场景可以通过级联比较实现bool operator(const Student other) const { if (id ! other.id) return id other.id; return name other.name; }这段代码先按id排序id相同再按name排序是很有用的写法。3.4 完整示例动态维护前k个最小值在实际项目里set还能配合lower_bound实现“动态有序集合”。例如维护当前数组里最大的三个数。思路很简单每插入一个数就放到set里如果set的size超过3就删除begin()也就是最小的那个数。这样set里就会一直保存着最大的三个数。这个技巧比每次重新排序要高效得多也是set“自动有序”在算法题里的典型应用。#include iostream #include set int main() { std::setint top3; int arr[] {5, 1, 9, 3, 7, 8, 2}; for (int x : arr) { top3.insert(x); if (top3.size() 3) { top3.erase(top3.begin()); } } for (int v : top3) { std::cout v ; } // 输出7 8 9 return 0; }这种写法在数据流场景里非常实用相当于做了一个在线算法不用等全量数据到来后再排序。4. 常见问题与排查技巧实录4.1 为什么不能直接修改set元素set里的元素是由const限定的你无法通过迭代器修改它的值即便对非const迭代器解引用返回的也是const T。原因很简单如果允许你直接修改一个元素红黑树的排序结构可能会被破坏。比如元素是5你把它改成100它原本在树中的位置已经不合法了。所以标准库干脆在访问层面禁止修改。正确的做法是删除旧元素插入新值。std::setint s {1, 3, 5}; auto it s.find(3); // *it 4; // 编译错误 s.erase(it); // 先删除 s.insert(4); // 再插入这个限制看似麻烦但其实是在保护你避免出现容器内部结构损坏的运行时bug。4.2 erase后迭代器失效问题当你用迭代器遍历set并删除当前元素时要注意迭代器失效。set有个和vector不同的特性删除当前元素不会让其他元素的迭代器失效但是当前迭代器在删除后不能再使用。安全的写法for (auto it s.begin(); it ! s.end(); ) { if (*it % 2 0) { it s.erase(it); // C11以后erase返回下一个迭代器 } else { it; } }这个写法很安全。如果你用s.erase(it);也可以但可读性稍差。我见过很多人在set删除上栽跟头核心原因就是混用了vector和set的使用习惯。vector的erase返回下一个元素迭代器set同样支持所以尽量统一写“it s.erase(it)”。4.3 set性能上值得注意的问题虽然set的插入删除是O(log n)但它的时间常数往往比vector大。如果数据量小比如几千个元素以内vectorsort可能反而更快。因为红黑树的节点在内存中散落分布缓存命中率低而vector是连续内存遍历非常快。这个结论不是黑set而是想提醒大家别滥用。对于小集合用vector、sort、unique就能搞定对于数据量大且需要动态插入删除的场景set才有明显优势。我在实际项目中遇到过因频繁插入大量随机数导致瓶颈的情况。当时用set之后发现性能不够后来改成分批处理或使用unordered_set才解决了问题。所以性能优化不是“无脑选set”要看数据规模和操作类型。4.4 快速排查速查表我把set使用中可能遇到的高频问题整理成表格方便大家遇到问题时快速定位现象原因解决办法插入了重复值size没变set去重特性用insert返回值判断是否插入成功遍历set顺序和插入顺序不一致set默认升序需要自定义比较器或改用vector修改set元素报编译错误set元素为const删除旧元素再插入新值删除迭代器后编译或运行异常迭代器失效使用erase返回的迭代器自定义结构体编译出错缺少operator或比较器实现严格弱序比较这张表基本能覆盖大多数初学者遇到的坑。当然更底层的做法是去读STL源码了解红黑树的旋转和调整逻辑但日常开发用上面这些经验就够了。最后再分享一点我自己的体会。学set最有效的方式不是死记接口而是拿真实场景练手。我建议你把之前写的“手动去重排序”代码全部重构成set版本体会代码量是如何减少的再去刷几道滑动窗口、区间合并类题目会非常明显地感受到set在动态有序场景下的优势。遇到问题要敢于去测试验证比如用insert返回值判断重复、用erase返回值安全删除这些细节用熟了之后你会发现自己对STL的理解上了一个台阶。本文还有配套的精品资源点击获取