最近被一道题绊住了思路题目本身不复杂却把集合这个C里最容易被低估的容器考点翻了个底朝天。题目大概是这样的小蓝定义了一个Fibonacci集合F集合的元素初值为最小的5个Fibonacci数之后每次从集合中取出最小值用它和集合中其他元素做运算把产生的新数放回集合问你若干轮之后第N小的元素是多少。我当时第一反应是用优先队列堆来做但一细想光靠堆还不行——集合里不能有重复元素而不同的运算路径完全可能得到同一个数。这恰恰就是std::set最擅长的场景去重、有序、动态取最小。这篇文章就把集合容器从原理到实战彻底捋一遍适合刚学C的初学者也适合准备蓝桥杯、GESP这类算法竞赛的人以及写业务代码时想用集合优化查找逻辑的朋友。1. 集合容器的底层逻辑与选型思路1.1 std::set 与 std::unordered_set 的本质区别C里叫集合的容器主要有两个std::set和std::unordered_set。名字长得像底层完全是两个世界。std::set是一棵红黑树属于平衡二叉搜索树所有元素按比较规则自动排序存放。任何插入删除操作都会触发树的旋转调整保证树的高度维持在O(log n)所以它的查找、插入、删除复杂度都是O(log n)。std::unordered_set则是哈希表元素经过哈希函数映射到桶里平均情况下查找、插入、删除都是O(1)但元素之间没有任何顺序关系。可以对比着理解std::set就像图书馆里按编号排列的书架你要找一本叫《C Primer》的书可以按索引一步步缩小范围std::unordered_set则像快递站的储物柜每个包裹根据快递单号算出抽屉号直接去对应抽屉翻就行了。前者多了一个编号顺序的维度后者牺牲顺序换来了更快的定位速度。还有个经常被忽略的点内存占用。哈希表为了减少冲突会维持一定的负载因子元素数/桶数通常要预留大量空桶内存开销明显比红黑树大。如果你存的是几百万个整数unordered_set可能比set多出一倍以上的内存。官方文档里建议优先使用unordered_set来提升性能但我觉得这得看场景为了那点平均时间付出两倍内存在小内存环境下并不划算。1.2 动手之前先回答三个问题我在实际接手一个需求或者刷一道题时选容器之前会先问自己三个问题要不要有序要不要去重要不要频繁取最小或最大值这三个问题答完选型基本就定了。第一需要有序遍历、求第K小、找前驱后继的用std::set。比如有序集合中找出大于x的最小元素set::lower_bound直接搞定哈希表压根没有这个概念。第二只需要判断某个元素在不在集合里、不关心顺序的用std::unordered_set。比如历史记录去重、黑白名单过滤插进去就是O(1)查存在性也是O(1)。第三既要快速取最小又要去重的set就是天然答案——*begin()直接拿到最小元素插入时自动去重完全不需要额外维护vis数组。用一个简单的表格做对照能看得更清楚使用场景推荐容器理由取第N小元素、遍历有序std::set红黑树天然有序直接取begin或按迭代器走只判断存在性、大量查找std::unordered_set哈希表平均O(1)查找动态生成序列且要求不重复std::set插入即去重且能随时取最小只需去重但顺序无需求std::unordered_set省去排序成本需要按插入顺序存取且去重std::unordered_set vector哈希表保唯一vector保顺序这个表格不是万能的参考模板但覆盖了绝大多数C集合应用场景。做竞赛题的时候我还会多想一层如果生成过程需要每轮取当前最小的元素再插入若干新元素set几乎完美适配因为取最小和插入去重都是它的看家本领。2. Fibonacci集合这类题到底在考什么2.1 剥掉Fibonacci外壳之后的真相那道小蓝Fibonacci集合的题目表面上是考数列生成实际上考的容器能力极其明确去重、有序、动态维护最值。Fibonacci只是生成规则的外壳换个规则——比如用质数集合、完全平方数集合——内核完全一样。题目如果展开讲大概是这样的规则F集合初始包含最小的5个Fibonacci数1、1、2、3、5之后每轮取出集合的最小值x把x与集合中的每个元素y相加得到xy并放回集合。重复这个过程N轮之后问你集合中第M小的数是多少。这里有两个关键考验点第一个要去重。112213而初始集合本身就有2和3。如果不用集合而用普通的数组或vector重复添加会越积越多最后第N小的数根本数不对。第二个要有序。每轮必须取出最小值这不是随便拿一个就行——只有每次从最小值开始扩散才能保证生成的数按照从小到大的顺序逐步推进最终答案就是集合里的某个前缀元素。2.2 用set模拟集合的插入与去重std::set::insert的返回值是一个非常实用的设计pairiterator, bool。迭代器指向插入位置的元素bool表示本次插入是否真的成功。如果集合中已经有了相同元素插入会失败bool为false迭代器指向已有的那个元素。std::setint s; auto res s.insert(5); std::cout res.second std::endl; // 输出 1插入成功 res s.insert(5); std::cout res.second std::endl; // 输出 0插入失败因为5已存在这一点在生成元素时特别好用我们可以统计本轮有多少个新元素被成功加入判断集合扩展的速度。如果一整个循环下来没有任何新元素加入说明生成规则已经进入了稳态可以提前结束。我在做这题时写了一个简单版本能直观看到去重效果#include set #include vector #include iostream int main() { std::setint fibSet; std::vectorint seeds {1, 1, 2, 3, 5}; for (int x : seeds) { fibSet.insert(x); } for (int round 0; round 10; round) { int x *fibSet.begin(); fibSet.erase(fibSet.begin()); int newCount 0; std::vectorint newElements; for (int y : fibSet) { int val x y; if (fibSet.insert(val).second) { newElements.push_back(val); newCount; } } // 注意本轮生成的元素不能马上参与本轮后面的加法 // 否则会生成超出规则范围的新组合这里需要用一个临时数组记录。 std::cout round round pick x insert newCount new elements; if (!newElements.empty()) { std::cout : ; for (int v : newElements) std::cout v ; } std::cout , set size fibSet.size() std::endl; } return 0; }这段代码有一个很重要的细节每次从fibSet中取出最小元素x后先把x删除再遍历集合中剩余的元素做加法。新生成的数不能立刻参与当前轮次的循环否则xnewVal这种组合也会被错误地加进去生成顺序就乱了。所以我先把新元素用临时数组存起来等遍历完再统一插入。这个细节我在第一次写的时候没注意结果输出的序列乱七八糟。2.3 有序遍历与最小元素的提取std::set的迭代器按升序访问元素这一点在生成类题目中是决定性优势。每次取最小值直接就是*begin()取最大值是*rbegin()。如果题目让求第K小只需要从begin开始走K步或者更高效地利用advance函数auto it fibSet.begin(); std::advance(it, k - 1); // 第k小的元素下标从1开始 std::cout *it std::endl;当然这种走到第K个的操作复杂度是O(k)不是O(log n)。如果频繁要求随机访问第K小那set就不是最优解了应该考虑pbds的树或平衡树加子树大小维护。不过大多数考题一次只问一个第N小O(k)完全可以接受。Fibonacci集合这题跑起来前几轮的结果长这样轮次取出的最小值新增元素部分集合大小013, 4, 612,13,157125, 7, 823,25,2610238, 9, 935,36,3612349, 9, 1014看到没第2轮和第3轮出现了大量重复值比如8、9被反复生成。如果没有set去重集合早就膨胀得没法看了。去重不是锦上添花是整个方案能否成立的前提。3. 集合差集、交集、并集的实战姿势3.1 从基于链表的两个集合差集说起热搜词里有个基于链表的两个集合差集这让我想起大学数据结构课的经典实验题用链表表示集合求两个链表的差集A-B。这类题在工程上早被STL替代了但作为练习题它逼着你理解集合运算的本质。链表的做法很简单对A和B分别排序去重或先建一个带有去重的链表然后用双指针遍历两个有序链表。A中元素如果比B中当前元素小说明这个元素不会出现在B里加入差集如果相等跳过A中的元素如果A的元素比B大B指针往前移。复杂度主要取决于排序排序后一趟就能完成差集运算。但我想说的是如果在竞赛或实际工程里遇到同样的需求别自己写链表了std::set STL算法直接秒杀。下面这段代码就实现了差集#include set #include algorithm #include iterator #include iostream int main() { std::setint A {1, 2, 3, 4, 5, 10}; std::setint B {3, 5, 6, 7, 8}; std::setint diff; std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::inserter(diff, diff.begin())); std::cout A - B ; for (int x : diff) std::cout x ; // 1 2 4 10 std::cout std::endl; std::setint inter; std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::inserter(inter, inter.begin())); std::cout A B ; for (int x : inter) std::cout x ; // 3 5 std::cout std::endl; return 0; }set_difference、set_intersection、set_union三个算法都要求输入的两个集合有序而std::set天然有序配合得天衣无缝。输出端用一个std::inserter迭代器适配器自动把结果插入目标容器。这里有个很多人踩过的坑如果目标容器是set一定要用inserter(diff, diff.begin())不要用back_inserter因为set根本没有push_back这样的操作。3.2 无序集合的差集现代写法如果两个集合是unordered_set那就不能用set_difference了因为元素无序。这时候思路反过来遍历较小的那个集合在较大的集合里查存在性。把数量少的集合元素作为基准可以有效减少哈希查找次数std::unordered_setint Au {1, 2, 3, 4, 5, 10}; std::unordered_setint Bu {3, 5, 6, 7, 8}; const auto small (Au.size() Bu.size()) ? Au : Bu; const auto large (Au.size() Bu.size()) ? Bu : Au; std::unordered_setint diff; for (int x : small) { if (large.find(x) large.end()) { diff.insert(x); } }这个版本的复杂度是O(min(m,n))的平均时间只取决于较小集合的大小非常适合一个集合巨大、一个集合很小的情况。不过需要注意的是这里求的是对称差还是差集要看业务定义。我写的是只从小的那个集合里筛如果题目要的是A-B就固定遍历A查B不要被这个选小集合的优化套路带偏。3.3 各种实现方式的性能对照实现方式时间复杂度适用场景有序set set_differenceO(m n)两个集合都有序大量数据unordered_set遍历小集合O(min(m,n)) 平均差集方向明确集合无序链表朴素双重循环O(m × n)基本只存在于教科书和数据结构作业排序数组 双指针O(m log m n log n)集合已经存在vector中允许排序实践下来如果是百万级元素set_difference的稳定性最好因为红黑树遍历是严格顺序的算法本身不会因为哈希冲突而退化。unordered_set虽然平均快但哈希退化时可能变成O(n)这在比赛和线上环境里是不可控的风险。我的习惯是搞不清数据分布时优先用有序方案性能可预测性比极端情况下的最快更重要。4. 集合实操中的高频翻车点4.1 循环删除元素的迭代器陷阱很多人第一次在set里做条件删除时会写成for循环加erase。但是erase(it)之后迭代器it就失效了再执行it就是未定义行为。在Visual C调试模式下可能直接断言崩溃在Linux上可能表现为莫名其妙的死循环非常难排查。我推荐的写法是C11之后的版本直接用返回值for (auto it s.begin(); it ! s.end();) { if (需要删除的条件(*it)) { it s.erase(it); // erase返回下一个有效迭代器 } else { it; } }对于std::setC11标准规定erase(iterator)返回下一个迭代器所以上面这段是安全的。还有一种更省事的写法是用std::erase_if但那个要求C20很多竞赛环境的编译器版本不支持手写反而更稳妥。对于unordered_set删除元素后其他元素迭代器不失效只有被删的那个失效但对于insert如果发生rehash所有迭代器都可能失效这点在遍历中插入元素时要特别小心。4.2 自定义类型的比较器陷阱std::set默认用operator排序要求满足严格弱序strict weak ordering。最典型的问题是比较器只比较了部分字段导致原本不同的元素被认为相等。举个例子用std::pairint, int存坐标很多人写比较器只看第一个值struct Cmp { bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.first b.first; // 错误完全忽略了second } }; std::setstd::pairint, int, Cmp badSet; badSet.insert({1, 2}); badSet.insert({1, 3}); // 实际上第二个插入被判定为已存在插入失败这样(1,2)和(1,3)被认为是同一个元素数据悄无声息地丢了。正确的做法是用std::pair自带的比较运算它按字典序比较first再比较second或者比较器写成if (a.first ! b.first) return a.first b.first; return a.second b.second;另外还有一个很难发现的坑比较器不具备传递性。比如用两个整数的差的绝对值小于5认为相等这种带容差的比较器红黑树会直接乱套。集合去重本质上是等价关系必须是严格的相等判断。带容差的模糊匹配应该用排序加相邻扫描而不是塞进set里。4.3 哈希函数与冲突的隐患std::unordered_set自定义类型默认没有哈希函数需要自己提供std::hash的特化或者传入哈希函数对象。我见得最多的翻车方式是给string或者pair用了质量很差的哈希导致大量元素塞进同一个桶时间复杂度直接退化到O(n)。检查方法很简单打印一下负载因子和桶分布std::unordered_setint u; for (int i 0; i 1000; i) u.insert(i); std::cout bucket_count u.bucket_count() std::endl; std::cout load_factor u.load_factor() std::endl; std::cout max_load_factor u.max_load_factor() std::endl;如果load_factor超过max_load_factorunordered_set会自动rehash这个过程中的性能毛刺在某些实时系统里是不能接受的。使用reserve可以提前分配桶数减少动态扩容。我自己遇到过一个更隐蔽的问题用指针作为unordered_set的键时哈希的是指针地址而不是指向的内容。两个内容相同的对象地址不同在哈希集合里就是两个不同的元素。如果业务上要求按内容去重必须自定义哈希函数取*ptr的hash值。5. 完整实现Fibonacci集合的第N小元素5.1 一类生成式集合问题的通用策略Fibonacci集合这题属于很常见的生成式集合问题规则是初始给定若干种子元素之后根据规则由已有元素生成新元素要求输出过程中某次排序后的结果。解决这类问题的策略是高度统一的维护一个有序且去重的容器反复取出最小元素生成新元素放回直到够了需要的数量。这种策略的合理性在于从小到大的生成过程保证了取出的顺序就是元素大小的顺序。每次取出的最小值在当前集合里已经没有比它更小的元素了所以新生成的元素如果比它还小规则允许的话就需要放回去重新排序如果规则只会产生更大的元素那取出的序列天然有序。Fibonacci集合的加法规则正属于新元素比当前最小值大的场景所以用set每次取begin()是绝对安全的。有一个类似的经典问题是丑数Ugly Number集合初始包含1每次取出最小值分别乘以2、3、5放入集合求第N个丑数。一模一样的思想很多教科书用三指针做但用set的办法更直观、更不容易出错尤其适合竞赛现场快速coding。5.2 完整代码与运行验证我把Fibonacci集合的完整求解写成了下面这个版本直接从集合中依次取出前N个元素#include set #include vector #include cstdint #include iostream int main() { // 初始最小的5个Fibonacci数1, 1, 2, 3, 5 std::setstd::int64_t fibSet {1, 1, 2, 3, 5}; int total 20; std::vectorstd::int64_t answers; while (static_castint(answers.size()) total) { std::int64_t x *fibSet.begin(); fibSet.erase(fibSet.begin()); // 取出的x就是当前集合中最小元素先加入结果 // 通常题目要求的是第N小生成过程取出顺序就是递增顺序 if (answers.empty() || answers.back() ! x) { answers.push_back(x); } // 用x与集合中其他元素相加生成新元素 std::vectorstd::int64_t newlyGenerated; for (std::int64_t y : fibSet) { std::int64_t val x y; if (fibSet.insert(val).second) { newlyGenerated.push_back(val); } } // 新元素不立即参与本轮的其他加法所以这里什么都不需要做 // newlyGenerated 只是为了调试时查看这一轮新增了哪些数 (void)newlyGenerated; } for (std::size_t i 0; i answers.size(); i) { std::cout 第 i 1 小元素: answers[i] std::endl; } return 0; }跑出来的前几项应该是第 1 小元素: 1 第 2 小元素: 2 第 3 小元素: 3 第 4 小元素: 4 第 5 小元素: 5 第 6 小元素: 6 第 7 小元素: 7 第 8 小元素: 8 ...注意代码里我把1初始插入了两次但set自动去重所以集合里只有一份1。这正好呼应了前面的重点集合的最重要的特性之一就是天然不重复。如果题目要求的是聚合到第10000小int可能不够用我统一用std::int64_t避免在生成过程中溢出。int最大约21亿Fibonacci序列增长很快第50项就开始逼近这个阈值用64位是必须的。5.3 常见变形与进阶优化这题有个变体是每轮取出最小值后把最小值乘2、乘3、乘5加入集合而不是加法。这种情况下集合中每个元素都是2、3、5因子组合的乘积同样用set畅通无阻。还有变体是要求输出前K个不重复的数这时答案收集逻辑里的去重判断就变得至关重要——虽然set内部不会有重复但如果你在取出的序列里也放了重复值比如某次取出的x和上次相同最终答案就会重复计数。如果数据规模再大到千万级别set的操作开销可能会成为瓶颈。一个常见的优化是小根堆标记集合用小根堆快速取最小用unordered_set记录元素是否已经生成过避免重复入堆。这样插入堆是O(log n)判存在是O(1)整体性能比纯set好一些。代价是需要维护两个容器逻辑稍微复杂一点。我的建议是竞赛题数据量在10万以下直接set代码短、不易错数据量到百万以上再考虑堆加标记的优化方案。实测中还有一个性能细节提前用set::reserve是不可能的因为set没有这个接口。但是unordered_set有reserve。所以如果预估集合会非常大用unordered_set做标记、用小根堆做排序性能比纯set好不少。这也是为什么方案选型要在动手前想清楚而不是写完了再改。一些个人体会回到开头那道Fibonacci集合题我最后在比赛环境里用的是纯set方案两百多行的题核心代码只占了不到四十行剩下的全是输入输出和边界处理。这让我更确信一件事C集合容器不是会用insert和find就行更重要的是理解有序性去重性最小/最大访问这三个维度各自在什么问题里能发挥优势。我个人在实际做题和写业务代码时最大的体会是拿到一个需求先别急着写容器先在纸上画一下数据流——元素怎么产生、怎么被查询、要不要排序、有没有重复。把这几条理顺了选型几乎是白送的。set在很多场景确实好用但它有红黑树旋转的开销和更高的内存占用如果只是判存在性unordered_set往往又快又省心。最后再分享一个小技巧调试集合类问题时别只盯着断点看变量值。把集合的前几个元素和大小打印出来基本一眼就能看出比较器写没写对、去重是否生效、生成顺序有没有乱。我在写Fibonacci集合时就是因为多打印了每轮的新增元素才及时发现新元素提前参与加法导致序列错乱的问题。这种打印观察的习惯在集合相关的调试里比任何IDE的watch窗口都管用。