C++ STL set与map核心用法：选型、实战与避坑指南

开头

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> set<int> 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> map<string, 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) { ... } // C++17结构化绑定遍历

这里最大的坑就是operator[]。mp[key]在key不存在时会自动插入一个默认值（int就是0，string就是空串），然后返回引用。这意味着：

• 你只是想查找一个key存不存在，如果写if (mp["somekey"] > 0)，那么当key不存在时，它会先插入一个0，把map悄悄变大。这是典型的隐蔽bug，会让结果莫名其妙多出一些键。
• 什么时候该用operator[]？计数时。mp[word]++的语义在"单词不存在时先置0再自增"的场景下非常优雅，严格来说是"插入+修改"，但结果恰好是我们想要的。或者你确定key存在，想修改value时也可以用。

那"只查不改"怎么做？用find()或者C++20的contains()（mp.contains(key)返回bool），实在不行还有at()，mp.at(key)在key不存在时直接抛out_of_range异常。刷题场景里，我习惯是：要计数用[]，要纯查找用find()或contains()。

2.3 自定义类型做key：重载运算符是必修课

set和map底层是红黑树，树节点需要比较大小，所以自定义类型做元素或key时必须定义"小于"规则。最简单的方式是重载operator<：

struct Node { int x, y; bool operator<(const Node& other) const { if (x != other.x) return x < other.x; return y < other.y; } }; set<Node> s; // 按(x, y)字典序排序 map<Node, int> mp; // 同理

如果不写operator<，编译直接报错，报错信息还特别长，新手极易被吓住。实际上STL容器在比较时会用bool operator<(const T&, const T&)，你只要保证这个比较满足严格弱序（strict weak ordering）就行，也就是：不能同时a<b和b<a，且比较结果要有传递性。常见错误是只比较了一部分字段，导致两个"按理说不同"的对象被当成相等，或者反过来。

这里再提一个进阶点：如果你不希望改变结构体的全局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; // 按距离排序 } }; set<Node, 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输出。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s(nums1.begin(), nums1.end()); set<int> ans; for (int x : nums2) { if (s.count(x)) ans.insert(x); } return vector<int>(ans.begin(), ans.end()); }

这里我故意用了两个set，而不是"一个set加一个vector去重"：因为vector去重要么排序后unique，要么自己维护一个标记数组，代码都不够简洁；直接用set承接答案，最后构造vector返回，逻辑最清晰。而且set<int> 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"]，K=2时输出["i", "love"]。

这道题的核心两步：先用map统计每个单词的出现次数，再把map里的键值对取出来按规则排序。

vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> cnt; for (auto& w : words) cnt[w]++; vector<pair<string, 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; }); vector<string> 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里，比较逻辑是"次数从大到小，次数相同按字典序"，这里pair<string,int>的默认比较是先比first（string）再比second（int），但我们这里要求的优先级正好相反，所以必须自定义比较器。第三，注意sort是不稳定排序，所以字典序这种次要规则必须在比较器里显式写出来，不能依赖稳定性。

如果你是C++11之前的老写法，没有lambda，那就要么写个全局仿函数，要么用std::bind拼比较器，可读性差很多。所以刷OJ尽量用支持C++11以上的编译器，lambda让这类题目代码量锐减。

这里再补充一个更进阶的做法：用"桶排序"的思想，可以做到O(n)统计完直接按桶取单词。但实际比赛里数据量不大，sort的O(n log n)完全够用，而且代码简单不容易错。优先保正确，再考虑优化，是我刷题的一贯原则。

3.3 题目三：存在重复元素III（set维护滑动窗口）

这道题是set"有序性"的封神场景之一。题面：给定整数数组nums和整数k、t，判断是否存在两个不同的下标i和j，满足abs(i - j) <= k且abs(nums[i] - nums[j]) <= t。

如果只需要判断重复元素，unordered_set就够了。但这里不只是查重，还要判断"有没有值在我的附近"，也就是要在一个窗口内找最接近某个数的元素。最接近这个需求，恰好就是lower_bound的用武之地。

思路：维护一个大小为k+1的滑动窗口，窗口内元素放在set中。遍历每个元素x时：

1. 在set里找第一个 >= x - t 的元素，用lower_bound(x - t)。
2. 如果找到了，且该元素 <= x + t，说明窗口内有元素与x的差的绝对值 <= t，直接返回true。
3. 把x插入set，如果set大小超过k+1，删除最左端的元素（即nums[i - k]）。

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { set<long 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]一定在窗口内，因为窗口大小k+1，所以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列表里。

vector<vector<string>> groupAnagrams(vector<string>& strs) { map<string, vector<string>> mp; for (auto& s : strs) { string key = s; sort(key.begin(), key.end()); mp[key].push_back(s); } vector<vector<string>> 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会导致后面所有元素前移，迭代器集体失效。

所以下面这种循环删除是安全的：

map<string, int> mp; for (auto it = mp.begin(); it != mp.end(); ) { if (it->second == 0) { it = mp.erase(it); // C++11后erase返回下一个迭代器 } else { ++it; } }

如果编译器支持C++11，erase(it)会返回被删除元素的下一个迭代器，直接赋值给it即可。在C++11之前，erase返回void，你必须在erase前先保存下一个迭代器：auto next_it = next(it); mp.erase(it); it = next_it;。现在OJ基本都支持C++17了，用第一种写法就行，但面试时旧编译器环境也说不准，知道两种写法总没坏处。

4.2 一眼看去是map，其实用vector更好

这是我见过最多的"杀鸡用牛刀"：当key是连续且稀疏的整数（比如0到100000，但只有少数几个出现），有人习惯用map<int, int>或者unordered_map<int, int>，既写起来啰嗦，又有哈希/红黑树开销。此时直接开vector<int>当桶用，下标就是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记录出现顺序，或者用map<string, int>记录编号，再按编号排序。之前我见过有人误以为unordered_map"看起来像乱序就是按某种顺序"，这是一个误解，unordered_map的内部顺序取决于哈希函数和桶数量，分分钟改变，不能依赖。

这点在OJ题目里经常是个隐藏关卡：题目要求按"第一次出现顺序"输出，如果你直接遍历map，按字典序输出，就会得到错误答案。遇到输出顺序敏感的题，先问自己：这个顺序是"排序序"还是"插入序"？不同答案对应的容器策略完全不同。

4.5 性能对比速查表

最后放一张我在实际测试中总结的选型表，配合前面的讲解，遇到具体场景可以直接查：

写在最后

最后再分享一个我自己的习惯：刷题时遇到一道"一看能用map"的题，我会先在注释里写下"我需要快速根据XX查YY吗？需要有序吗？",想清楚再动手。set和map最怕的不是不会语法，而是用错场景。语法多敲几次就熟了，场景判断需要的是在题目里反复体会。

至于那些"unable to locate the codex cli binary"之类的报错，本质上和set/map没关系，那是我在配本地开发环境时遇到的另一次折腾。跑C++ OJ题其实不需要那么重的工具链，一个支持C++17的编译器加一个终端就完全够了，先把容器用明白，再考虑其他花活。