前言在 C 标准模板库STL中容器可以分为两大类序列式容器和关联式容器。序列式容器如vector、list、deque等元素按线性顺序存储每个位置没有内在的“意义”交换两个元素不会破坏容器的结构。关联式容器则不同它们通常基于树或哈希表实现元素之间通过关键字key建立紧密的关联关系交换两个元素可能完全破坏容器的逻辑结构。map和set是 STL 中最经典的关联式容器底层采用红黑树一种自平衡二叉搜索树实现。它们提供了对数时间复杂度的插入、查找、删除操作并且能够按照关键字的有序方式进行遍历。本文将从零开始详细讲解set/multiset和map/multimap的使用方法、内部原理、常见陷阱并结合力扣题目展示它们的实战技巧。全文约 5000 字适合所有 C 开发者阅读。阅读本文前建议先了解二叉搜索树的基本概念可参考我的前一篇文章《深入剖析二叉搜索树》。一、序列式容器 vs 关联式容器在学习具体容器之前我们先明确两类容器的本质区别。1.1 序列式容器逻辑结构线性序列。访问方式按元素在容器中的存储位置下标或迭代器访问。典型代表vector、list、deque、array、forward_list。特点元素之间没有强制性的比较或顺序关系你可以随意交换两个元素容器依然合法。vectorint v {3, 1, 4}; swap(v[0], v[2]); // 变成 {4, 1, 3}仍然是合法的vector1.2 关联式容器逻辑结构非线性结构通常是树或哈希表。访问方式按元素的关键字key访问。典型代表set、map、multiset、multimap红黑树实现unordered_set、unordered_map哈希表实现。特点元素的位置由关键字决定交换两个不同的关键字元素会破坏容器的排序性质导致未定义行为。setint s {3, 1, 4}; // swap(*s.begin(), *s.rbegin()); // 绝对不要这样做会破坏有序性关联式容器的两大分类有序关联容器本章重点底层为红黑树元素始终按关键字排序查找时间复杂度 O(log n)。无序关联容器下一章讲解底层为哈希表元素无序查找平均 O(1)。二、set 系列容器详解set代表“集合”它的特点是存储唯一的关键字并且按关键字升序排列。如果你需要存储重复的关键字应该使用multiset。2.1 set 的模板声明template class T, // 关键字类型 class Compare lessT, // 比较仿函数默认升序 class Alloc allocatorT // 空间配置器一般不改 class set;T存储在 set 中的元素类型也就是 key 的类型。Compare用于比较两个关键字的函数对象默认std::lessT要求T支持operator。如果你想实现降序可以传std::greaterT。Alloc内存分配器几乎永远使用默认值。2.2 set 的核心特性唯一性不允许重复的关键字。插入重复值时插入操作失败。有序性按照Compare规则元素总是有序的。默认升序中序遍历红黑树得到递增序列。不可修改因为修改关键字会破坏有序结构所以set的迭代器是常量迭代器const_iterator不能通过迭代器修改元素值。效率插入、删除、查找都是 O(log n)。2.3 set 的构造与遍历常用构造函数构造函数说明set()空构造set(InputIterator first, InputIterator last)迭代器区间构造set(const set x)拷贝构造set(initializer_listvalue_type il)列表初始化C11迭代器begin() / end()正向迭代器双向迭代器但只能读。rbegin() / rend()反向迭代器。示例代码#include iostream #include set using namespace std; int main() { // 默认升序 setint s1 {5, 2, 8, 2, 5, 1}; // 重复值自动去重 for (int x : s1) cout x ; // 输出1 2 5 8 cout endl; // 降序 setint, greaterint s2 {5, 2, 8, 2, 5, 1}; for (int x : s2) cout x ; // 输出8 5 2 1 cout endl; // 迭代器遍历 setstring strSet {apple, banana, cherry}; auto it strSet.begin(); while (it ! strSet.end()) { // *it xxx; // 错误不能修改 cout *it ; it; } return 0; }2.4 set 的插入set提供了多个insert重载pairiterator,bool insert (const value_type val); // 插入单个元素 void insert (initializer_listvalue_type il); // 插入列表 template class InputIterator void insert (InputIterator first, InputIterator last); // 插入区间返回值单个元素插入返回pairiterator, bool其中bool表示是否插入成功true成功插入新元素false已存在且未插入iterator指向已存在元素或新插入元素的位置。示例setint s; auto ret s.insert(10); if (ret.second) cout 插入成功元素 *ret.first endl; else cout 已存在 endl; s.insert({20, 30, 10}); // 10 已存在不会重复插入2.5 set 的查找与计数成员函数说明find(const key_type k)返回指向 k 的迭代器若不存在则返回end()。count(const key_type k)返回 k 在 set 中的个数只能是 0 或 1对 multiset 有用。lower_bound(const key_type k)返回第一个 k的迭代器。upper_bound(const key_type k)返回第一个 k的迭代器。为什么推荐使用 set 自己的 find 而不是全局 find全局std::find是线性遍历 O(n)而set::find利用红黑树特性 O(log n)。数据量大时差异巨大。setint s {10, 20, 30, 40, 50}; auto pos s.find(30); if (pos ! s.end()) cout 找到了 endl; // 用 count 快速判断存在 if (s.count(25)) cout 存在 endl; else cout 不存在 endl;2.6 set 的删除iterator erase(const_iterator position); // 删除迭代器指向的元素 size_type erase(const key_type k); // 删除所有等于 k 的元素返回删除个数 iterator erase(const_iterator first, const_iterator last); // 删除区间注意erase(key)返回size_type对于set最多返回 1对于multiset可能返回 1。setint s {1,2,3,4,5}; s.erase(3); // 删除 3 auto it s.find(2); if (it ! s.end()) s.erase(it); // 迭代器删除 // 删除区间 [lower, upper) auto low s.lower_bound(2); auto up s.upper_bound(4); s.erase(low, up); // 删除 2,3,4注意 upper_bound(4) 指向 52.7 multiset 的特点multiset与set几乎一样唯一区别是允许关键字重复。这导致以下行为差异insert永远成功不会因为重复而失败。find返回中序遍历下第一个等于该值的元素的迭代器。count返回实际重复个数。erase(value)会删除所有等于 value 的元素返回删除个数。没有operator[]set 本来就没有multiset 也没有。multisetint ms {1,2,2,3,2}; for (int x : ms) cout x ; // 1 2 2 2 3 cout ms.count(2); // 输出 3 ms.erase(2); // 删除所有 22.8 实战力扣 349. 两个数组的交集题目给定两个数组返回它们的交集每个元素唯一顺序任意。思路将两个数组分别存入set去重并排序然后利用双指针因为set有序找出公共元素。class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { setint s1(nums1.begin(), nums1.end()); setint s2(nums2.begin(), nums2.end()); vectorint ret; auto it1 s1.begin(), it2 s2.begin(); while (it1 ! s1.end() it2 ! s2.end()) { if (*it1 *it2) it1; else if (*it1 *it2) it2; else { ret.push_back(*it1); it1; it2; } } return ret; } };时间复杂度 O(n log n)主要是构造 set 的开销比暴力 O(n²) 优雅得多。2.9 实战力扣 142. 环形链表 II题目给定一个链表返回链表开始入环的第一个节点。如果不带环返回 nullptr。传统解法快慢指针 数学推导。使用 set遍历链表将每个节点的地址存入set第一个出现重复地址的节点就是环的入口。代码极其简洁体现了关联容器的“降维打击”。class Solution { public: ListNode *detectCycle(ListNode *head) { setListNode* s; ListNode* cur head; while (cur) { if (s.count(cur)) return cur; // 或者用 find s.insert(cur); cur cur-next; } return nullptr; } };注意空间复杂度 O(n)而快慢指针法 O(1)。但在面试或竞赛中如果空间充足使用 set 可以大幅降低编码难度。三、map 系列容器详解map是“映射”表存储的是键值对key-value pair。每个 key 唯一通过 key 快速访问对应的 value。multimap允许 key 重复。3.1 map 的模板声明template class Key, // 关键字类型 class T, // 映射值类型 class Compare lessKey, // 比较仿函数 class Alloc allocatorpairconst Key,T class map;Key键的类型不能修改。T值的类型可以修改。内部存储的节点类型是pairconst Key, T键部分为 const确保不会破坏排序。3.2 pair 类型pair是一个简单的结构体定义在utility但map已包含。它有两个公有成员first和second。template class T1, class T2 struct pair { T1 first; T2 second; pair(); pair(const T1 a, const T2 b); // ... 其他构造函数 };常用辅助函数make_pair可以自动推导类型。3.3 map 的构造与基本使用构造函数与set类似支持空构造、区间构造、拷贝构造、列表初始化。mapstring, string dict { {left, 左边}, {right, 右边}, {insert, 插入} }; // 或者使用 initializer_list dict.insert({auto, 自动的}); // 遍历 for (const auto kv : dict) { cout kv.first - kv.second endl; }迭代器的使用注意迭代器指向的是pairconst Key, T所以可以通过it-second修改值但不能修改it-first。3.4 map 的插入insert的签名与set类似但参数是pairconst Key, Tpairiterator,bool insert (const value_type val);多种插入写法mapstring, int m; // 1. 使用 pair 构造函数 m.insert(pairstring, int(apple, 1)); // 2. 使用 make_pair m.insert(make_pair(banana, 2)); // 3. 使用 {}C11 统一初始化 m.insert({cherry, 3}); // 4. 直接用 [] 赋值后面会讲 m[durian] 4;返回值与set含义相同first指向已存在或新插入的迭代器second表示是否插入成功。3.5 map 的查找与删除find(key)返回指向 key 所在节点的迭代器若不存在返回end()。count(key)返回 key 出现的次数0 或 1。erase(key)删除 key 及其映射值返回删除个数0 或 1。其他与set基本一致。auto it dict.find(left); if (it ! dict.end()) { cout it-second endl; // 输出左边 it-second 左侧; // 修改 value 合法 } int n dict.erase(right); // n 13.6 map 的 operator[] —— 多功能神器map最独特也最容易让人困惑的接口就是operator[]。它的声明如下mapped_type operator[] (const key_type k);行为如果k在 map 中返回对应value的引用。如果k不在 map 中则自动插入一个键值对(k, mapped_type())其中mapped_type()是值类型的默认构造值例如 int 为 0string 为空字符串然后返回该value的引用。内部实现原理简化mapped_type operator[](const key_type k) { // insert 返回 pairiterator, bool无论插入成功还是失败iterator 都指向 k 所在节点 pairiterator, bool ret insert({k, mapped_type()}); return ret.first-second; // 返回 value 的引用 }因此operator[]实际上完成了查找 插入若不存在 返回 value 引用。这使得代码可以非常简洁。典型应用统计单词频率mapstring, int freq; string words[] {apple, banana, apple, apple, banana}; for (const auto w : words) { freq[w]; // 第一次遇到 w 时插入并初始化为 0然后 变成 1后续遇到直接 } for (const auto p : freq) { cout p.first : p.second endl; }注意陷阱operator[]在访问不存在的 key 时会插入一个新元素。如果只是想查询用find更安全。不要试图用operator[]来遍历 map它会插入新的默认元素改变容器大小。3.7 multimap 的特点multimap允许 key 重复因此insert总是成功。find返回中序第一个匹配的迭代器。count返回重复次数。erase(key)删除所有该 key 的元素。不支持operator[]因为 key 不唯一无法通过一个 key 确定唯一的 value。multimap常用于一对多的映射例如一个学生可以选修多门课程。multimapstring, string courses; courses.insert({张三, 数学}); courses.insert({张三, 英语}); auto range courses.equal_range(张三); // 返回 pairiterator,iterator 表示区间 for (auto it range.first; it ! range.second; it) cout it-second ;3.8 实战力扣 138. 随机链表的复制题目一个链表每个节点除了next指针还有一个random指针指向链表中的任意节点或空。要求深拷贝原链表。常规解法在原链表中穿插拷贝节点再拆分极其繁琐。使用 map第一遍遍历建立原节点 → 拷贝节点的映射第二遍遍历利用映射设置next和random。代码清晰易懂。class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; mapNode*, Node* nodeMap; Node* cur head; // 第一遍创建新节点建立映射 while (cur) { nodeMap[cur] new Node(cur-val); cur cur-next; } // 第二遍连接 next 和 random cur head; while (cur) { nodeMap[cur]-next nodeMap[cur-next]; nodeMap[cur]-random nodeMap[cur-random]; cur cur-next; } return nodeMap[head]; } };时间复杂度 O(n)空间复杂度 O(n)。比传统方法简单了不止一个数量级。3.9 实战力扣 692. 前K个高频单词题目给一个单词列表返回出现频率最高的 k 个单词。若频率相同按字典序从小到大排列。分析先用map统计频率map 自动按单词字典序排序然后将键值对放入vector再按照频率降序、字典序升序的自定义规则排序取前 k 个。解法一使用 stable_sort由于map已经按照字典序排好我们只需要按频率稳定排序即可相同频率时保持原来的字典序顺序。stable_sort是稳定的排序算法。class Solution { public: vectorstring topKFrequent(vectorstring words, int k) { mapstring, int cnt; for (auto w : words) cnt[w]; vectorpairstring, int v(cnt.begin(), cnt.end()); // 按频率降序稳定排序保证相同频率时字典序小的在前面 stable_sort(v.begin(), v.end(), [](const pairstring,int a, const pairstring,int b) { return a.second b.second; }); vectorstring res; for (int i 0; i k; i) res.push_back(v[i].first); return res; } };解法二自定义比较的 sort直接使用sort在比较函数中同时判断频率和字典序。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 pairstring,int a, const pairstring,int b) { return a.second b.second || (a.second b.second a.first b.first); }); vectorstring res; for (int i 0; i k; i) res.push_back(v[i].first); return res; }解法三使用优先队列最小堆也可以用小根堆只保留前 k 个但注意自定义比较器的写法优先队列默认大堆比较函数与 sort 相反。这里不再展开。四、总结与进阶建议4.1 核心知识点回顾容器是否有序是否允许重复 key是否允许修改 key是否允许修改 valueoperator[]set是升序/降序否否const迭代器—无multiset是是否—无map是按key升序否否是通过迭代器或[]有多功能multimap是是否是无4.2 使用建议需要集合元素唯一且有序→set。需要字典映射key 唯一value 可变→map。需要一对多映射或允许重复 key→multimap或multiset。只关心存在性不关心顺序→unordered_set/unordered_map哈希实现O(1) 平均。不要再自己手写二叉搜索树除非学习目的。工程上直接用 STL 容器。4.3 性能与注意事项红黑树的插入、删除、查找都是 O(log n)但常数较大。对于小数据量 1000vector 线性查找可能更快。避免在循环中频繁使用operator[]进行查找因为它会在缺失时插入改变容器大小。erase在迭代器失效方面map的erase(iterator)只使被删迭代器失效其他迭代器包括end()仍然有效。这是与vector的重要区别。尽量使用const_iterator如果你不打算修改元素以表明意图。4.4 延伸学习无序关联容器unordered_set、unordered_map。它们基于哈希表查找平均 O(1)但元素无序且需要提供哈希函数。红黑树原理理解旋转、颜色规则对理解map的平衡机制有帮助。自定义比较函数当你的 key 类型不支持operator或者你需要特殊比较逻辑时可以传入仿函数或 lambda。结语map和set是 C STL 中最常用、最强大的容器之一。掌握它们不仅能让你的代码更加简洁高效还能在算法竞赛和日常开发中如虎添翼。本文从基本概念到进阶实战涵盖了所有常用接口和典型场景。希望你能够亲自敲一遍示例代码并尝试解决文中的力扣题目。如果遇到问题欢迎在评论区交流讨论。
深入浅出 STL 之 map 与 set：从入门到实战
发布时间：2026/6/8 6:30:50
前言在 C 标准模板库STL中容器可以分为两大类序列式容器和关联式容器。序列式容器如vector、list、deque等元素按线性顺序存储每个位置没有内在的“意义”交换两个元素不会破坏容器的结构。关联式容器则不同它们通常基于树或哈希表实现元素之间通过关键字key建立紧密的关联关系交换两个元素可能完全破坏容器的逻辑结构。map和set是 STL 中最经典的关联式容器底层采用红黑树一种自平衡二叉搜索树实现。它们提供了对数时间复杂度的插入、查找、删除操作并且能够按照关键字的有序方式进行遍历。本文将从零开始详细讲解set/multiset和map/multimap的使用方法、内部原理、常见陷阱并结合力扣题目展示它们的实战技巧。全文约 5000 字适合所有 C 开发者阅读。阅读本文前建议先了解二叉搜索树的基本概念可参考我的前一篇文章《深入剖析二叉搜索树》。一、序列式容器 vs 关联式容器在学习具体容器之前我们先明确两类容器的本质区别。1.1 序列式容器逻辑结构线性序列。访问方式按元素在容器中的存储位置下标或迭代器访问。典型代表vector、list、deque、array、forward_list。特点元素之间没有强制性的比较或顺序关系你可以随意交换两个元素容器依然合法。vectorint v {3, 1, 4}; swap(v[0], v[2]); // 变成 {4, 1, 3}仍然是合法的vector1.2 关联式容器逻辑结构非线性结构通常是树或哈希表。访问方式按元素的关键字key访问。典型代表set、map、multiset、multimap红黑树实现unordered_set、unordered_map哈希表实现。特点元素的位置由关键字决定交换两个不同的关键字元素会破坏容器的排序性质导致未定义行为。setint s {3, 1, 4}; // swap(*s.begin(), *s.rbegin()); // 绝对不要这样做会破坏有序性关联式容器的两大分类有序关联容器本章重点底层为红黑树元素始终按关键字排序查找时间复杂度 O(log n)。无序关联容器下一章讲解底层为哈希表元素无序查找平均 O(1)。二、set 系列容器详解set代表“集合”它的特点是存储唯一的关键字并且按关键字升序排列。如果你需要存储重复的关键字应该使用multiset。2.1 set 的模板声明template class T, // 关键字类型 class Compare lessT, // 比较仿函数默认升序 class Alloc allocatorT // 空间配置器一般不改 class set;T存储在 set 中的元素类型也就是 key 的类型。Compare用于比较两个关键字的函数对象默认std::lessT要求T支持operator。如果你想实现降序可以传std::greaterT。Alloc内存分配器几乎永远使用默认值。2.2 set 的核心特性唯一性不允许重复的关键字。插入重复值时插入操作失败。有序性按照Compare规则元素总是有序的。默认升序中序遍历红黑树得到递增序列。不可修改因为修改关键字会破坏有序结构所以set的迭代器是常量迭代器const_iterator不能通过迭代器修改元素值。效率插入、删除、查找都是 O(log n)。2.3 set 的构造与遍历常用构造函数构造函数说明set()空构造set(InputIterator first, InputIterator last)迭代器区间构造set(const set x)拷贝构造set(initializer_listvalue_type il)列表初始化C11迭代器begin() / end()正向迭代器双向迭代器但只能读。rbegin() / rend()反向迭代器。示例代码#include iostream #include set using namespace std; int main() { // 默认升序 setint s1 {5, 2, 8, 2, 5, 1}; // 重复值自动去重 for (int x : s1) cout x ; // 输出1 2 5 8 cout endl; // 降序 setint, greaterint s2 {5, 2, 8, 2, 5, 1}; for (int x : s2) cout x ; // 输出8 5 2 1 cout endl; // 迭代器遍历 setstring strSet {apple, banana, cherry}; auto it strSet.begin(); while (it ! strSet.end()) { // *it xxx; // 错误不能修改 cout *it ; it; } return 0; }2.4 set 的插入set提供了多个insert重载pairiterator,bool insert (const value_type val); // 插入单个元素 void insert (initializer_listvalue_type il); // 插入列表 template class InputIterator void insert (InputIterator first, InputIterator last); // 插入区间返回值单个元素插入返回pairiterator, bool其中bool表示是否插入成功true成功插入新元素false已存在且未插入iterator指向已存在元素或新插入元素的位置。示例setint s; auto ret s.insert(10); if (ret.second) cout 插入成功元素 *ret.first endl; else cout 已存在 endl; s.insert({20, 30, 10}); // 10 已存在不会重复插入2.5 set 的查找与计数成员函数说明find(const key_type k)返回指向 k 的迭代器若不存在则返回end()。count(const key_type k)返回 k 在 set 中的个数只能是 0 或 1对 multiset 有用。lower_bound(const key_type k)返回第一个 k的迭代器。upper_bound(const key_type k)返回第一个 k的迭代器。为什么推荐使用 set 自己的 find 而不是全局 find全局std::find是线性遍历 O(n)而set::find利用红黑树特性 O(log n)。数据量大时差异巨大。setint s {10, 20, 30, 40, 50}; auto pos s.find(30); if (pos ! s.end()) cout 找到了 endl; // 用 count 快速判断存在 if (s.count(25)) cout 存在 endl; else cout 不存在 endl;2.6 set 的删除iterator erase(const_iterator position); // 删除迭代器指向的元素 size_type erase(const key_type k); // 删除所有等于 k 的元素返回删除个数 iterator erase(const_iterator first, const_iterator last); // 删除区间注意erase(key)返回size_type对于set最多返回 1对于multiset可能返回 1。setint s {1,2,3,4,5}; s.erase(3); // 删除 3 auto it s.find(2); if (it ! s.end()) s.erase(it); // 迭代器删除 // 删除区间 [lower, upper) auto low s.lower_bound(2); auto up s.upper_bound(4); s.erase(low, up); // 删除 2,3,4注意 upper_bound(4) 指向 52.7 multiset 的特点multiset与set几乎一样唯一区别是允许关键字重复。这导致以下行为差异insert永远成功不会因为重复而失败。find返回中序遍历下第一个等于该值的元素的迭代器。count返回实际重复个数。erase(value)会删除所有等于 value 的元素返回删除个数。没有operator[]set 本来就没有multiset 也没有。multisetint ms {1,2,2,3,2}; for (int x : ms) cout x ; // 1 2 2 2 3 cout ms.count(2); // 输出 3 ms.erase(2); // 删除所有 22.8 实战力扣 349. 两个数组的交集题目给定两个数组返回它们的交集每个元素唯一顺序任意。思路将两个数组分别存入set去重并排序然后利用双指针因为set有序找出公共元素。class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { setint s1(nums1.begin(), nums1.end()); setint s2(nums2.begin(), nums2.end()); vectorint ret; auto it1 s1.begin(), it2 s2.begin(); while (it1 ! s1.end() it2 ! s2.end()) { if (*it1 *it2) it1; else if (*it1 *it2) it2; else { ret.push_back(*it1); it1; it2; } } return ret; } };时间复杂度 O(n log n)主要是构造 set 的开销比暴力 O(n²) 优雅得多。2.9 实战力扣 142. 环形链表 II题目给定一个链表返回链表开始入环的第一个节点。如果不带环返回 nullptr。传统解法快慢指针 数学推导。使用 set遍历链表将每个节点的地址存入set第一个出现重复地址的节点就是环的入口。代码极其简洁体现了关联容器的“降维打击”。class Solution { public: ListNode *detectCycle(ListNode *head) { setListNode* s; ListNode* cur head; while (cur) { if (s.count(cur)) return cur; // 或者用 find s.insert(cur); cur cur-next; } return nullptr; } };注意空间复杂度 O(n)而快慢指针法 O(1)。但在面试或竞赛中如果空间充足使用 set 可以大幅降低编码难度。三、map 系列容器详解map是“映射”表存储的是键值对key-value pair。每个 key 唯一通过 key 快速访问对应的 value。multimap允许 key 重复。3.1 map 的模板声明template class Key, // 关键字类型 class T, // 映射值类型 class Compare lessKey, // 比较仿函数 class Alloc allocatorpairconst Key,T class map;Key键的类型不能修改。T值的类型可以修改。内部存储的节点类型是pairconst Key, T键部分为 const确保不会破坏排序。3.2 pair 类型pair是一个简单的结构体定义在utility但map已包含。它有两个公有成员first和second。template class T1, class T2 struct pair { T1 first; T2 second; pair(); pair(const T1 a, const T2 b); // ... 其他构造函数 };常用辅助函数make_pair可以自动推导类型。3.3 map 的构造与基本使用构造函数与set类似支持空构造、区间构造、拷贝构造、列表初始化。mapstring, string dict { {left, 左边}, {right, 右边}, {insert, 插入} }; // 或者使用 initializer_list dict.insert({auto, 自动的}); // 遍历 for (const auto kv : dict) { cout kv.first - kv.second endl; }迭代器的使用注意迭代器指向的是pairconst Key, T所以可以通过it-second修改值但不能修改it-first。3.4 map 的插入insert的签名与set类似但参数是pairconst Key, Tpairiterator,bool insert (const value_type val);多种插入写法mapstring, int m; // 1. 使用 pair 构造函数 m.insert(pairstring, int(apple, 1)); // 2. 使用 make_pair m.insert(make_pair(banana, 2)); // 3. 使用 {}C11 统一初始化 m.insert({cherry, 3}); // 4. 直接用 [] 赋值后面会讲 m[durian] 4;返回值与set含义相同first指向已存在或新插入的迭代器second表示是否插入成功。3.5 map 的查找与删除find(key)返回指向 key 所在节点的迭代器若不存在返回end()。count(key)返回 key 出现的次数0 或 1。erase(key)删除 key 及其映射值返回删除个数0 或 1。其他与set基本一致。auto it dict.find(left); if (it ! dict.end()) { cout it-second endl; // 输出左边 it-second 左侧; // 修改 value 合法 } int n dict.erase(right); // n 13.6 map 的 operator[] —— 多功能神器map最独特也最容易让人困惑的接口就是operator[]。它的声明如下mapped_type operator[] (const key_type k);行为如果k在 map 中返回对应value的引用。如果k不在 map 中则自动插入一个键值对(k, mapped_type())其中mapped_type()是值类型的默认构造值例如 int 为 0string 为空字符串然后返回该value的引用。内部实现原理简化mapped_type operator[](const key_type k) { // insert 返回 pairiterator, bool无论插入成功还是失败iterator 都指向 k 所在节点 pairiterator, bool ret insert({k, mapped_type()}); return ret.first-second; // 返回 value 的引用 }因此operator[]实际上完成了查找 插入若不存在 返回 value 引用。这使得代码可以非常简洁。典型应用统计单词频率mapstring, int freq; string words[] {apple, banana, apple, apple, banana}; for (const auto w : words) { freq[w]; // 第一次遇到 w 时插入并初始化为 0然后 变成 1后续遇到直接 } for (const auto p : freq) { cout p.first : p.second endl; }注意陷阱operator[]在访问不存在的 key 时会插入一个新元素。如果只是想查询用find更安全。不要试图用operator[]来遍历 map它会插入新的默认元素改变容器大小。3.7 multimap 的特点multimap允许 key 重复因此insert总是成功。find返回中序第一个匹配的迭代器。count返回重复次数。erase(key)删除所有该 key 的元素。不支持operator[]因为 key 不唯一无法通过一个 key 确定唯一的 value。multimap常用于一对多的映射例如一个学生可以选修多门课程。multimapstring, string courses; courses.insert({张三, 数学}); courses.insert({张三, 英语}); auto range courses.equal_range(张三); // 返回 pairiterator,iterator 表示区间 for (auto it range.first; it ! range.second; it) cout it-second ;3.8 实战力扣 138. 随机链表的复制题目一个链表每个节点除了next指针还有一个random指针指向链表中的任意节点或空。要求深拷贝原链表。常规解法在原链表中穿插拷贝节点再拆分极其繁琐。使用 map第一遍遍历建立原节点 → 拷贝节点的映射第二遍遍历利用映射设置next和random。代码清晰易懂。class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; mapNode*, Node* nodeMap; Node* cur head; // 第一遍创建新节点建立映射 while (cur) { nodeMap[cur] new Node(cur-val); cur cur-next; } // 第二遍连接 next 和 random cur head; while (cur) { nodeMap[cur]-next nodeMap[cur-next]; nodeMap[cur]-random nodeMap[cur-random]; cur cur-next; } return nodeMap[head]; } };时间复杂度 O(n)空间复杂度 O(n)。比传统方法简单了不止一个数量级。3.9 实战力扣 692. 前K个高频单词题目给一个单词列表返回出现频率最高的 k 个单词。若频率相同按字典序从小到大排列。分析先用map统计频率map 自动按单词字典序排序然后将键值对放入vector再按照频率降序、字典序升序的自定义规则排序取前 k 个。解法一使用 stable_sort由于map已经按照字典序排好我们只需要按频率稳定排序即可相同频率时保持原来的字典序顺序。stable_sort是稳定的排序算法。class Solution { public: vectorstring topKFrequent(vectorstring words, int k) { mapstring, int cnt; for (auto w : words) cnt[w]; vectorpairstring, int v(cnt.begin(), cnt.end()); // 按频率降序稳定排序保证相同频率时字典序小的在前面 stable_sort(v.begin(), v.end(), [](const pairstring,int a, const pairstring,int b) { return a.second b.second; }); vectorstring res; for (int i 0; i k; i) res.push_back(v[i].first); return res; } };解法二自定义比较的 sort直接使用sort在比较函数中同时判断频率和字典序。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 pairstring,int a, const pairstring,int b) { return a.second b.second || (a.second b.second a.first b.first); }); vectorstring res; for (int i 0; i k; i) res.push_back(v[i].first); return res; }解法三使用优先队列最小堆也可以用小根堆只保留前 k 个但注意自定义比较器的写法优先队列默认大堆比较函数与 sort 相反。这里不再展开。四、总结与进阶建议4.1 核心知识点回顾容器是否有序是否允许重复 key是否允许修改 key是否允许修改 valueoperator[]set是升序/降序否否const迭代器—无multiset是是否—无map是按key升序否否是通过迭代器或[]有多功能multimap是是否是无4.2 使用建议需要集合元素唯一且有序→set。需要字典映射key 唯一value 可变→map。需要一对多映射或允许重复 key→multimap或multiset。只关心存在性不关心顺序→unordered_set/unordered_map哈希实现O(1) 平均。不要再自己手写二叉搜索树除非学习目的。工程上直接用 STL 容器。4.3 性能与注意事项红黑树的插入、删除、查找都是 O(log n)但常数较大。对于小数据量 1000vector 线性查找可能更快。避免在循环中频繁使用operator[]进行查找因为它会在缺失时插入改变容器大小。erase在迭代器失效方面map的erase(iterator)只使被删迭代器失效其他迭代器包括end()仍然有效。这是与vector的重要区别。尽量使用const_iterator如果你不打算修改元素以表明意图。4.4 延伸学习无序关联容器unordered_set、unordered_map。它们基于哈希表查找平均 O(1)但元素无序且需要提供哈希函数。红黑树原理理解旋转、颜色规则对理解map的平衡机制有帮助。自定义比较函数当你的 key 类型不支持operator或者你需要特殊比较逻辑时可以传入仿函数或 lambda。结语map和set是 C STL 中最常用、最强大的容器之一。掌握它们不仅能让你的代码更加简洁高效还能在算法竞赛和日常开发中如虎添翼。本文从基本概念到进阶实战涵盖了所有常用接口和典型场景。希望你能够亲自敲一遍示例代码并尝试解决文中的力扣题目。如果遇到问题欢迎在评论区交流讨论。
 揪出CUDA程序里的‘摸鱼’内存操作)
