开头STL里的set和map说难不难说简单也不简单。很多初学者一开始觉得它们就是能自动排序的容器或者带键值对的数组真到OJ上做题时才发现用错容器导致超时、迭代器失效、结构体做key编译不过、erase在循环里踩坑……各种问题接踵而至。这篇博客我就用实际的OJ题场景把set和map的基础用法、核心使用场景、以及那些文档里不会明说的坑一次讲透希望能帮正在刷题或者做项目的人少走弯路。我会按照先搞懂选型逻辑 → 再上手基础API → 然后用中等难度OJ题串起核心场景 → 最后整理高频坑位的顺序来写。内容适合三种人刚开始学C STL的学生、准备机试/面试需要快速巩固容器用法的求职者、以及写业务代码时对容器选型拿不准的开发者。1. 内容整体设计与思路拆解1.1 为什么偏偏是set和map先抛一个问题如果你需要维护一个不重复且有序的数据集合你会怎么做最简单的想法是开一个数组每次插入后sort一下或者插入时保持有序。但这样的复杂度是O(n log n)的插入在数据量到十万、百万级别时直接被卡爆。而set底层是红黑树插入、删除、查找都是O(log n)这就是它在OJ题目里被高频使用的原因。再看map本质是键值对版的set底层同样是红黑树按照key有序排列。它解决的痛点是根据某个键快速找到对应的值。你可能会说这不就是数组下标访问吗但数组的下标必须是整数map的键可以是字符串、自定义结构体、甚至另一个容器。当你需要统计每个单词出现次数根据用户ID查资料这类场景时map几乎是首选。1.2 一个核心纠结set/map还是unordered_set/unordered_map很多教程会告诉你能用unordered就用unordered哈希O(1)更快。这话对但不够全面。我刷题和实际写代码的经验是需要有序遍历、求前驱后继、做范围查询比如lower_bound找第一个不小于x的元素时只能用set/map因为unordered系列不保证顺序更不存在lower_bound这种有序操作。对顺序无要求、只需要快速插入删除查找时unordered系列确实平均更快但它有哈希冲突退化到O(n)的风险而且自定义类型要提供hash函数比较麻烦。OJ题里如果数据是随机生成的整数unordered_set在大多数情况下表现更好但如果数据是精心构造的卡哈希数据比如大量冲突的字符串unordered系列会直接超时而红黑树的set稳定不慌。所以我的建议是不确定的时候就先用set/map它永远是对的等真正成为性能瓶颈了再换unordered。红黑树版本的时间复杂度是明确的O(log n)不会出幺蛾子这在竞赛和机试里是一种保守但可靠的策略。1.3 本文用哪些OJ题来串场景光讲API没意思也记不住。我选了四道中等难度、覆盖典型场景的题目两个数组的交集set最基本的去重和集合运算。前K个高频单词map统计频率再结合排序覆盖map做计数的经典用法。存在重复元素III滑动窗口配合set的有序能力这是set的独特优势场景。字母异位词分组map的key用排序后的字符串覆盖自定义键的思路。四道题分别从去重计数有序窗口Key变形四个维度打穿set/map的核心能力。下面每道题我都会给出完整思路、代码和踩坑点。2. 核心细节解析与实操要点2.1 set的基础操作与注意事项先列一份set常用的操作清单这些都是刷题时命中率极高的#include set setint s; s.insert(5); // 插入如果元素已存在则什么都不做 s.erase(5); // 删除指定值返回删除个数0或1 s.erase(s.find(5)); // 用迭代器删除前提是元素存在 s.find(5) ! s.end(); // 判断是否存在不要用全局find s.count(5); // 判断是否存在0或1 s.size(); // 元素个数 s.empty(); // 是否为空 s.lower_bound(3); // 第一个 3 的元素的迭代器 s.upper_bound(3); // 第一个 3 的元素的迭代器 for (int x : s) { ... } // 从小到大遍历有几个细节必须强调。第一判断元素是否存在用find或者count都行但不要用count做后续的删除前确认因为count本身是一次O(log n)的查找find也是一次先用count再find就是两次了。直接find判断返回是否等于end()效率更高。第二lower_bound和upper_bound是set最值钱的两个函数很多有序场景比如找最接近某值的元素都靠它俩。第三set不支持像vector那样的下标访问也不支持*(s.begin() 2)的随机访问因为它不是连续内存迭代器是双向迭代器。2.2 map的基础操作与operator[]陷阱map的操作和set大同小异但多了一个键值对的概念#include map mapstring, int mp; mp[hello] 1; // 插入键值对 mp.insert({world, 2}); // 另一种插入方式 mp[hello]; // 值自增经典计数写法 mp.find(hello) ! mp.end(); // 判断key是否存在 mp.erase(hello); // 删除key for (auto [k, v] : mp) { ... } // C17结构化绑定遍历这里最大的坑就是operator[]。mp[key]在key不存在时会自动插入一个默认值int就是0string就是空串然后返回引用。这意味着你只是想查找一个key存不存在如果写if (mp[somekey] 0)那么当key不存在时它会先插入一个0把map悄悄变大。这是典型的隐蔽bug会让结果莫名其妙多出一些键。什么时候该用operator[]计数时。mp[word]的语义在单词不存在时先置0再自增的场景下非常优雅严格来说是插入修改但结果恰好是我们想要的。或者你确定key存在想修改value时也可以用。那只查不改怎么做用find()或者C20的contains()mp.contains(key)返回bool实在不行还有at()mp.at(key)在key不存在时直接抛out_of_range异常。刷题场景里我习惯是要计数用[]要纯查找用find()或contains()。2.3 自定义类型做key重载运算符是必修课set和map底层是红黑树树节点需要比较大小所以自定义类型做元素或key时必须定义小于规则。最简单的方式是重载operatorstruct Node { int x, y; bool operator(const Node other) const { if (x ! other.x) return x other.x; return y other.y; } }; setNode s; // 按(x, y)字典序排序 mapNode, int mp; // 同理如果不写operator编译直接报错报错信息还特别长新手极易被吓住。实际上STL容器在比较时会用bool operator(const T, const T)你只要保证这个比较满足严格弱序strict weak ordering就行也就是不能同时ab和ba且比较结果要有传递性。常见错误是只比较了一部分字段导致两个按理说不同的对象被当成相等或者反过来。这里再提一个进阶点如果你不希望改变结构体的全局operator比如其他地方有别的排序需求可以用set/map的模板参数传一个仿函数struct Cmp { bool operator()(const Node a, const Node b) const { return a.x * a.x a.y * a.y b.x * b.x b.y * b.y; // 按距离排序 } }; setNode, Cmp s;在OJ题里这种自定义排序规则的set非常实用比如按绝对值排序、按出现次数排序都靠它。3. 实操过程与核心环节实现3.1 题目一两个数组的交集set去重与集合运算题面很直接给定两个数组nums1和nums2返回它们的交集结果中每个元素必须唯一可以不考虑输出顺序。比如nums1 [1,2,2,1], nums2 [2,2]输出[2]。先想想如果不让用set你该怎么写暴力二重循环去重时间复杂度O(n*m)数据一大就废。用set就很自然把nums1的所有元素塞进set天然去重排序再遍历nums2用count()或find()判断元素是否在set里是则加入答案集合最后把答案集合转成vector输出。vectorint intersection(vectorint nums1, vectorint nums2) { setint s(nums1.begin(), nums1.end()); setint ans; for (int x : nums2) { if (s.count(x)) ans.insert(x); } return vectorint(ans.begin(), ans.end()); }这里我故意用了两个set而不是一个set加一个vector去重因为vector去重要么排序后unique要么自己维护一个标记数组代码都不够简洁直接用set承接答案最后构造vector返回逻辑最清晰。而且setint s(nums1.begin(), nums1.end())这种用迭代器区间构造的写法非常值得记很多STL容器都支持能少写一个循环。延伸思考如果题目改成返回有序数组的并集或对称差集思路也是类似的先用set去重再用algorithm里的set_intersection、set_union等函数。这些函数要求输入有序set正好天然有序属于天作之合。不过实际OJ中手写循环更常见因为标准库的集合算法要预先准备好输出容器写起来并不短。3.2 题目二前K个高频单词map计数排序经典题目给一个单词列表返回出现频率最高的前K个单词。频率相同时按字典序排列。比如[i, love, leetcode, i, love, coding]K2时输出[i, love]。这道题的核心两步先用map统计每个单词的出现次数再把map里的键值对取出来按规则排序。vectorstring topKFrequent(vectorstring words, int k) { mapstring, int cnt; for (auto w : words) cnt[w]; vectorpairstring, int v(cnt.begin(), cnt.end()); sort(v.begin(), v.end(), [](const auto a, const auto b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; }); vectorstring ans; for (int i 0; i k; i) ans.push_back(v[i].first); return ans; }注意几个细节。第一cnt[w]是map计数的经典写法因为它会先利用operator[]的特性key不存在时插入value为0再自增简直是为计数场景量身定做。第二sort的lambda里比较逻辑是次数从大到小次数相同按字典序这里pairstring,int的默认比较是先比firststring再比secondint但我们这里要求的优先级正好相反所以必须自定义比较器。第三注意sort是不稳定排序所以字典序这种次要规则必须在比较器里显式写出来不能依赖稳定性。如果你是C11之前的老写法没有lambda那就要么写个全局仿函数要么用std::bind拼比较器可读性差很多。所以刷OJ尽量用支持C11以上的编译器lambda让这类题目代码量锐减。这里再补充一个更进阶的做法用桶排序的思想可以做到O(n)统计完直接按桶取单词。但实际比赛里数据量不大sort的O(n log n)完全够用而且代码简单不容易错。优先保正确再考虑优化是我刷题的一贯原则。3.3 题目三存在重复元素IIIset维护滑动窗口这道题是set有序性的封神场景之一。题面给定整数数组nums和整数k、t判断是否存在两个不同的下标i和j满足abs(i - j) k且abs(nums[i] - nums[j]) t。如果只需要判断重复元素unordered_set就够了。但这里不只是查重还要判断有没有值在我的附近也就是要在一个窗口内找最接近某个数的元素。最接近这个需求恰好就是lower_bound的用武之地。思路维护一个大小为k1的滑动窗口窗口内元素放在set中。遍历每个元素x时在set里找第一个 x - t 的元素用lower_bound(x - t)。如果找到了且该元素 x t说明窗口内有元素与x的差的绝对值 t直接返回true。把x插入set如果set大小超过k1删除最左端的元素即nums[i - k]。bool containsNearbyAlmostDuplicate(vectorint nums, int k, int t) { setlong long window; for (int i 0; i nums.size(); i) { auto it window.lower_bound((long long)nums[i] - t); if (it ! window.end() *it (long long)nums[i] t) { return true; } window.insert(nums[i]); if (window.size() k) { window.erase(nums[i - k]); } } return false; }这题我踩过的坑有三个。第一个是用int直接爆精度nums[i] - t可能超出int范围所以要么强转long long要么把t当long long用否则样例里出现大数时会得到错误答案。第二个是erase前要确定元素存在这里nums[i-k]一定在窗口内因为窗口大小k1所以erase不会出问题但你如果自己改窗口逻辑必须先确认。第三个是lower_bound的参数是值而不是索引很多人刚接触会搞混以为lower_bound是在下标范围内查找实际上set的lower_bound只看元素值。这道题的价值在于当你需要在动态集合中反复查询某元素的最近邻时set或map的lower_bound是O(log n)一把梭。换成vector加二分当然也可以但插入和删除就是O(n)了窗口滑动时会很痛。3.4 题目四字母异位词分组map的Key变形经典题给定字符串数组把字母异位词由相同字母组成、排列不同分到同一组。比如[eat, tea, tan, ate, nat, bat]输出分组后每组内的字符串。核心洞察异位词有一个公共特征——把字符排序后得到的字符串相同。eat和tea排序后都是aet。所以我们可以用排序后的字符串作为map的key原始字符串放进对应的value列表里。vectorvectorstring groupAnagrams(vectorstring strs) { mapstring, vectorstring mp; for (auto s : strs) { string key s; sort(key.begin(), key.end()); mp[key].push_back(s); } vectorvectorstring ans; for (auto [k, v] : mp) ans.push_back(v); return ans; }这个代码看起来简单但背后的思想特别重要map的key不一定是原始数据它可以是原始数据的某种规范化形式。类似思路在同构字符串排列组合分组等题目里反复出现。另外注意mp[key].push_back(s)里operator[]的语义在这里也刚刚好key不存在时先构造一个空的vector再push_back省掉了find然后分情况处理的代码。如果想再优化可以不用sort而是用字符计数数组作为key比如把每个字符的出现次数拼成字符串#1#0#2...。这样可以把每组异位词的复杂度从O(L log L)降为O(L)L是字符串长度。不过在实际OJ中sort法已经完全够用代码又短是更推荐的入门写法。Map的key是一个规范化签名这个思路本身比具体用哪种签名更重要。4. 常见问题与排查技巧实录4.1 迭代器失效erase到底会不会崩这是set/map使用中最高频的问题。先说结论set和map的erase只让被删除元素的迭代器失效其他迭代器不受影响。这是因为红黑树节点在内存中是分散的删除一个节点不会移动其他节点的地址。这一点和vector完全不同——vector的erase会导致后面所有元素前移迭代器集体失效。所以下面这种循环删除是安全的mapstring, int mp; for (auto it mp.begin(); it ! mp.end(); ) { if (it-second 0) { it mp.erase(it); // C11后erase返回下一个迭代器 } else { it; } }如果编译器支持C11erase(it)会返回被删除元素的下一个迭代器直接赋值给it即可。在C11之前erase返回void你必须在erase前先保存下一个迭代器auto next_it next(it); mp.erase(it); it next_it;。现在OJ基本都支持C17了用第一种写法就行但面试时旧编译器环境也说不准知道两种写法总没坏处。4.2 一眼看去是map其实用vector更好这是我见过最多的杀鸡用牛刀当key是连续且稀疏的整数比如0到100000但只有少数几个出现有人习惯用mapint, int或者unordered_mapint, int既写起来啰嗦又有哈希/红黑树开销。此时直接开vectorint当桶用下标就是key简单粗暴还快。判断key范围有限、连续时数组永远是第一选择。反过来如果key是字符串、浮点数、结构体或者key范围极大比如1e9量级再用vector就爆内存了这时map/unordered_map才合理。选容器之前先问自己三个问题数据范围多大是否需要有序是否只有整数这三个问题问完用哪个基本就定了。4.3 结构体当key重载operator却忘记加const很多人在结构体里写了bool operator(const Node other)编译时报一堆错。原因多半是少写了末尾的const。STL容器要求比较操作不能修改对象本身所以必须写成bool operator(const Node other) const { ... }这个const是给this指针限定的表示这个成员函数不会修改当前对象。少了它容器内部调用比较时无法对const对象调用非const成员函数就会编译失败。另一种替代方案是定义友元函数friend bool operator(const Node a, const Node b)不依赖this也不容易漏const。我建议直接用友元函数的形式从源头避免这个坑。4.4 输出有序但要求按插入顺序map做不到map永远按key排序unordered_map则不保证顺序。如果你要按元素第一次出现的顺序遍历比如记录字符串第一次出现顺序map和unordered_map都帮不上忙。常见的方案是再维护一个vector记录出现顺序或者用mapstring, int记录编号再按编号排序。之前我见过有人误以为unordered_map看起来像乱序就是按某种顺序这是一个误解unordered_map的内部顺序取决于哈希函数和桶数量分分钟改变不能依赖。这点在OJ题目里经常是个隐藏关卡题目要求按第一次出现顺序输出如果你直接遍历map按字典序输出就会得到错误答案。遇到输出顺序敏感的题先问自己这个顺序是排序序还是插入序不同答案对应的容器策略完全不同。4.5 性能对比速查表最后放一张我在实际测试中总结的选型表配合前面的讲解遇到具体场景可以直接查场景推荐容器原因去重且需要从小到大遍历set红黑树天然有序去重且只需要快速查重unordered_set平均O(1)统计字符串/单词频率map 或 unordered_map计数语义顺手按key范围查询某个值maplower_bound/upper_bound滑动窗口内找最近元素set插入删除O(log n)lower_boundkey是连续整数vector数组直接下标零额外开销需要按value排序map转vector再sortmap只按key有序遍历顺序要求第一次出现序辅助vectorunordered_map记录顺序自定义对象需要专属排序规则setType, Cmp仿函数控制排序写在最后最后再分享一个我自己的习惯刷题时遇到一道一看能用map的题我会先在注释里写下我需要快速根据XX查YY吗需要有序吗,想清楚再动手。set和map最怕的不是不会语法而是用错场景。语法多敲几次就熟了场景判断需要的是在题目里反复体会。至于那些unable to locate the codex cli binary之类的报错本质上和set/map没关系那是我在配本地开发环境时遇到的另一次折腾。跑C OJ题其实不需要那么重的工具链一个支持C17的编译器加一个终端就完全够了先把容器用明白再考虑其他花活。