C++进阶(04)：map和set

💬 ：如果你在阅读过程中有任何疑问或想要进一步探讨的内容，欢迎在评论区畅所欲言！我们一起学习、共同成长~！

👍 ：如果你觉得这篇文章还不错，不妨顺手点个赞、加入收藏，并分享给更多的朋友噢~！

---

1. 关联式容器 vs 序列式容器

STL容器分为序列式容器和关联式容器，核心区别：

• 序列式容器（vector、list、deque 等）：底层是线性结构，存储元素本身，检索需遍历，效率较低（O (N)）；
• 关联式容器：底层基于平衡树（红黑树）实现，存储<key, value>键值对，检索通过key定位，效率高达 O (log₂N)，是面试 / 笔试高频考查模块。

---

2. 关联式容器核心知识点

2.1 键值对（pair）

2.1.1 底层定义（面试手写）

本质：键值对是二元结构体模板，是关联式容器的底层存储单元，存储一组一一对应的 key-value 数据。

简易源码（背）：

template <class T1, class T2> struct pair { // 定义类型别名 typedef T1 first_type; typedef T2 second_type; T1 first; // 键key T2 second; // 值value // 无参构造 pair() : first(T1()), second(T2()) {} // 带参构造 pair(const T1& a, const T2& b) : first(a), second(b) {} };

核心考点：

1. first 存键，second 存值，支持两种访问方式：
   ①普通对象访问：pair对象.first 、pair对象.second
   ②map 迭代器访问：it->first 、it->second
2. 用struct：默认为public成员，可直接 .first / .second 访问。
3. 带参构造是 map 插入元素最常用方式，手写代码必须熟练，
   ①手动构造 pair 插入 map：m.insert(pair<int, string>(100, "张三"));
   ②make_pair 简写插入 map：m.insert(make_pair(100, "张三"));

2.1.2 make_pair（笔试高频）

作用：make_pair是模板函数，自动推导模板参数，简化pair创建，不用手动指定T1、T2。

源码（背）：

template <class T1, class T2> pair<T1, T2> make_pair(T1 a, T2 b) { return pair<T1, T2>(a, b); } // map.insert(make_pair(1,"one"))

常用于 map 插入简写：m.insert(make_pair(100, "张三"));

2.2 set 容器（自动去重，升序）

2.2.1 核心特点（面试必背）

1. 只存单个key，key必须唯一（天然去重），无 value；
2. set底层是红黑树（一种自平衡的二叉搜索树），默认升序排列元素；
3. 禁止直接修改元素值（红黑树节点位置由元素值决定，修改元素值破坏红黑树的有序性），“删除旧元素插入新元素”可间接修改；
4. find/ insert/ erase的平均与最坏时间复杂度均为 O (logN)。

2.2.2 三种构造（笔试默写）

（1）空构造

set<元素类型> 容器名;

（2）列表构造（自动去重升序）

set<int> s5 = {3, 1, 4, 1, 5}; // 初始化后自动变为{1,3,4,5}

（3）区间构造（笔试数组去重首选）

int arr[] = {2, 2, 1, 3}; set<int> s6(arr, arr + sizeof(arr)/sizeof(int)); // {1,2,3} vector<int> vec = {5, 3, 5, 7}; set<int> s7(vec.begin(), vec.end()); // {3,5,7}

2.2.3 核心接口 + 全套必掌握代码

接口	考点
begin()/end()	正向遍历升序
rbegin()/rend()	反向遍历降序
insert(val)	返回pair<迭代器,bool>；.second==true则插入成功
find(val)	找到返回迭代器，没找到返回end()，判断存在标准写法
erase(val)	按值删除，返回删除个数 0/1
count(val)	仅 0 或 1，等价判断是否存在

• 使用 set 包含头文件<set>
• using namespace std; 或 std 前缀

#include <iostream> #include <set> using namespace std; int main() { // 数组去重 int arr[] = { 1,3,2,3,4,2,5 }; set<int> s(arr, arr + sizeof(arr) / sizeof(int)); // 正向遍历 for (auto it = s.begin(); it != s.end(); ++it) cout << *it << " "; cout << endl; // 反向遍历 for (auto it = s.rbegin(); it != s.rend(); ++it) cout << *it << " "; cout << endl; auto ret = s.insert(6); if (ret.second) cout << "成功插入：" << *ret.first; // 查找元素 if (s.find(3) != s.end()) cout << "存在"; s.erase(2); return 0; }

2.3 map 容器（键值对，key唯一有序）

2.3.1 核心特点（面试高频）

1. 存储键值对 pair<const key, value> ，key 唯一且不可修改（红黑树节点位置由key决定，修改key破坏有序性），value 可通过 it->second 修改；
2. map 底层红黑树，按 key 默认升序；
3. find/ insert/ erase的平均与最坏时间复杂度均为 O (logN)；
4. map 重载 []，支持 [] 访问 value（笔试高频，需理解底层逻辑），set、multimap 无 [] 重载。

2.3.2 三种构造

（1）空构造

map<int, string> m;

（2）列表构造

map<int, string> m = { {1,"A"},{2,"B"} };

（3）区间构造

vector<pair<int, string>> v = { {3,"C"},{1,"A"},{1,"A+"} }; // vector<pair> 转 map，自动去重 key map<int, string> m(v.begin(), v.end()); // {1:"A",3:"C"}

2.3.3 核心接口 + 全套必掌握代码

接口	考点
insert(pair)	存在相同 key 不会覆盖，返回pair<it,bool>
operator[]	可读可写；key 不存在会插入默认 value，key 存在会覆盖原 value。
find(key)	查找 key，不存在返回end()
erase(key)	按 key 删除，返回删除数量 0/1

• 使用 map 包含头文件<map>
• using namespace std; 或 std 前缀

#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, string> m; // 3种插入方式 m.insert(pair<string, string>("apple", "苹果")); m.insert(make_pair("banana", "香蕉")); m["peach"] = "桃子"; // 遍历键值对 for (auto& e : m) { cout << e.first << "->" << e.second << endl; } // 查找，再修改value auto it = m.find("apple"); if (it != m.end()) { it->second = "红苹果"; } // 删除 m.erase("banana"); return 0; }

2.3.4 [] 底层原理（笔试挖坑点）

map容器名[key]的底层逻辑（必须理解）：

1. 构造键值对<key, V()>（value 为默认值，如 int 为 0，string 为空）；
2. 执行insert，若 key 已存在，返回原元素的迭代器；若 key 不存在，返回新元素的迭代器；
3. 最终返回该节点的value引用。

坑：哪怕只读取，key 不存在也会插入默认空值，污染容器。所以查询优先用find。

map<int, string> m; cout << m[2]; // 不存在key=2，插入<2, "">，输出空串

对比 m.at(key) ：key 不存在直接抛异常，不新增元素。

2.4 multiset 与 multimap（允许重复 key）

2.4.1 multiset / multimap 与 set / map 的核心区别（面试高频）

特性	set/map	multiset/multimap
key	必须唯一	可重复
count() 返回值	0 或 1	≥0（返回重复次数）
[]	map 支持	multimap 不支持（key 重复无法确定返回哪个 value）

2.4.2 头文件

• multiset：#include <set>
• multimap：#include <map>

2.4.3 equal_range（笔试必考）

1. 函数：equal_range(key)
2. 返回：pair<iterator, iterator>
   • range.first：首个匹配 key 的迭代器
   • range.second：最后一个匹配 key 的下一位迭代器
3. 默写：

#include <iostream> #include <map> using namespace std; int main() { multimap<string, string> mm; mm.insert(make_pair("fruit", "apple")); mm.insert(make_pair("fruit", "banana")); auto range = mm.equal_range("fruit"); for (auto it = range.first; it != range.second; ++it) { cout << it->first << " " << it->second; // 区分：it->first 是键值对的 key } return 0; }

2.4.4 erase (val) 坑点

1. set/map：erase (val) 删除一个匹配元素，返回 0/1
2. multiset/multimap：erase (val) 删除全部匹配元素，返回删除总数

multiset<int> ms = {2,2,2}; int num = ms.erase(2); // num = 3

2.5 set/map 迭代器特性与迭代器失效问题（高频）

2.5.1 迭代器类型区分

1. set/map/multiset/multimap：双向迭代器仅支持++it / --it，不支持it + n随机访问
2. vector/deque：随机访问迭代器，支持it+n

2.5.2 红黑树容器迭代器失效规则（必背）

底层红黑树，节点内存地址固定，仅删除节点会失效

1. insert 插入：仅旋转树结构，所有迭代器均不失效
2. erase 删除：
   • 被删除节点对应的迭代器失效
   • 其余迭代器完全有效

2.5.3 erase 两种重载返回值（笔试）

1. erase(迭代器pos)：无论 set/map/multiset/multimap，返回下一个有效迭代器（遍历删除专用）
2. erase(值val)：
   ①set/map：删除一个匹配元素，返回 0/1
   ②multiset/multimap：删除全部匹配元素，返回删除总数

循环删除安全模板（防失效）：

for (auto it = s.begin(); it != s.end();) { if (*it % 2 == 0) it = s.erase(it); // 返回下一有效迭代器 else ++it; }

2.6 set / map 与 unordered_set / unordered_map（面试问答）

对比项	set /map（有序）	unordered_set /unordered_map（无序）
底层	红黑树	哈希表（链地址法解决冲突）
顺序	自动按 key 升序	完全无序，存储由哈希值决定
时间复杂度	稳定 O (logN)	平均 O (1)；最坏冲突严重 O (N)
迭代器	双向迭代器 ++/--	前向迭代器 仅支持 ++
空间	开销小	哈希桶数组，空间开销更大
适用场景	需要有序、区间范围查询、性能稳定	只做增删查、不需要排序、追求极致速度

高频面试问答

1. 什么时候用 map？什么时候用 unordered_map？
   答：需要有序、范围遍历选 map；无需排序、仅高频查找选 unordered_map。
2. unordered_map 最坏 O (N) 原因？
   答：大量 key 哈希值冲突，链表退化成线性查找。

---

3. 平衡二叉树底层（面试高频）

3.1 平衡树的存在意义

普通二叉搜索树（O(logN)）有序插入时退化成单链表，增删查时间复杂度退化到O(N)；

平衡树通过旋转维持树高，稳定保证查询效率。

3.2 AVL 树（严格平衡）

3.2.1 核心性质

• 左右子树均为 AVL 树；
• 平衡因子 = 右子树高度 - 左子树高度，|平衡因子| ≤ 1；
• 查找效率 O (logN)；插入 / 删除需频繁旋转，维护成本高。

3.3 平衡树四种旋转操作

旋转目的：

左右子树高度差过大时，查询效率退化。在满足 BST “全部左 < 根 < 全部右”（平衡树是带自平衡约束的二叉搜索树）前提下，旋转缩短树高，保证O(logN)。

• （1）右右（父节点是祖父节点的右节点，新节点是父节点的右节点）：左单旋；

• （2）左左：右单旋；
• （3）右左：先父右旋（变直线，注意保持左<根<右）后祖父左旋。

更复杂的旋转，紧盯3个节点，其他节点保持整体左<根<右即可，

• （4）左右：先左旋后右旋；

触发依据

1. AVL 树：|平衡因子| > 1，失衡节点是祖父节点
2. 红黑树：出现连续红节点

3.4 红黑树（近似平衡，set/map 底层，重点）

3.4.1 核心性质（面试必背）

1. 每个节点非红即黑；
2. 根节点、叶子节点都为黑；
3. 分支方向上无连续红节点；
4. 当前节点向下到任意叶子节点，所有分支的黑节点总数相同；

性质 3. + 4. ➡ 推论：最长路径 ≤ 2× 最短路径（保证近似平衡）

3.4.2 红黑树节点结构

enum Color { RED, BLACK }; // 颜色枚举 template <class ValueType> struct RBTreeNode { RBTreeNode(const ValueType& data = ValueType(), Color color = RED) // 新节点默认红 : _pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_color(color) {} RBTreeNode* _pLeft; // 左孩子 RBTreeNode* _pRight; // 右孩子 RBTreeNode* _pParent; // 父节点（旋转必需） ValueType _data; Color _color; // 新节点 };

面试简答：新节点默认红色原因

插入红节点只会违反「无连续红」一条规则； 若插黑色，破坏路径黑节点数相等，触发大量调整，成本更高。

3.4.3 插入调整触发条件

插入新节点（默认红）后，只有父节点为红时需调整（违反「无连续红」）。

cur 新节点（红），p 父（红），u 叔，g 祖父（黑），分三种场景：

1. 场景 1：u 红

   • 调整：p 和 u 改黑，g 改红，cur 跳到 g 向上递归检查；
     

2. 场景 2：u 黑，且 cur 与 p 同侧

   • 调整：p 改黑，g 改红，左左➡右单旋 / 右右➡左单旋；
     

3. 场景 3：u 黑，且 cur 与 p 异侧

   • 调整：先旋转 p 转化为场景 2，再按场景 2 单旋处理。
     

3.5 红黑树与 AVL 树的区别（面试必答）

特性	AVL 树	红黑树
平衡条件	|平衡因子| ≤ 1（严格平衡）	最长路径 ≤ 2× 最短路径（近似平衡）
旋转开销	插入 / 删除频繁旋转	插入最多 2 次旋转，删除最多 3 次旋转
额外存储	每个节点存平衡因子（int）	仅 1 bit 存颜色
适用场景	查询多、增删少	频繁插入 / 删除（STL set/map 用）

---

4. 高频 OJ 题

4.1 两个数组的交集（set，简单）

LeetCode 349

核心思路：

1. 由示例输入知两个数组都可能含重复元素，而交集要求唯一，则利用set自动去重 + 升序；

2. 双指针查找交集。

class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1(nums1.begin(), nums1.end()); set<int> s2(nums2.begin(), nums2.end()); vector<int> ret; // auto it1 = s1.begin(), it2 = s2.begin(); while (it1 != s1.end() && it2 != s2.end()) { if (*it1 > *it2) it2++; else if (*it1 < *it2) it1++; else { ret.push_back(*it1); it1++; it2++; } } return ret; } };

4.2 两数之和（map，简单）

LeetCode 1

核心思路：

1. 暴力解法的缺陷：双重循环时间复杂度 O (N²)，效率低；

2. map 优化思路：用 map 存储 “元素值 - 下标” 键值对，遍历数组时，对当前元素nums[i]，计算互补值target - nums[i]，在 map 中查找该互补值

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int, int> Val_Idx; // <元素, 下标> for (int i = 0; i < nums.size(); i++) { int difference = target - nums[i]; auto it = Val_Idx.find(difference); if (it != Val_Idx.end()) // 有匹配差 return { it->second, i }; // 遍历到第2个差时map里才存在第1个差匹配，此时nums[i]=第2个差，difference=第1个差 Val_Idx[nums[i]] = i; } return {}; // 无匹配差，兜底返回匹配返回值，避免报错 } };

4.3 前 K 个高频单词（中等）

LeetCode 692

核心思路：

1. “前K个”显然属于 Top K 问题。C++初阶(11)/STL(四)：stack和queue总结了 Top K 问题经验。
2. 输出结果要求有序，排除快速选择法
3. 堆（优先队列）法是 Top K 问题最通用解法，可用。
4. 确认数据量：1 <= words.length <= 500，数据量小，简洁解法 sort 全排序可用。
5. 需要先统计每个单词频次，哈希表可 O (1) 快速完成单词计数映射。

哈希 + 堆（优先队列）

#include <iostream> #include <unordered_map> #include <queue> #include <vector> #include <string> using namespace std; // 存储pair<string,int>为自定义复合类型，无法用内置比较器，必须手写比较规则 struct cmp { bool operator()(const pair<string, int>& a, const pair<string, int>& b) const { // 输出结果频次大、字典序小在前，则频次大、字典序小更不易被删所以优先级低远堆顶 if (a.second == b.second) // 频次相同 return a.first < b.first; // a(字典序小)更低级，下沉远堆顶 return a.second > b.second; // 频次不同，a(频次大)更低级，下沉远堆顶 } }; class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> cnt; for (auto& word : words) { cnt[word]++; } priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> q; for (auto& c : cnt) { q.push(c); if (q.size() > k) q.pop(); // 删堆顶频次小字典序大单词，最终剩下前k高频词 } vector<string> ret(k); // 函数要求返回单词数组 for (int i = k - 1; i >= 0; i--) { // 堆顶小频次，而输出要求降序 ret[i] = q.top().first; q.pop(); } return ret; } };

哈希 + sort 全排序

#include <iostream> #include <unordered_map> #include <algorithm> #include <vector> #include <string> using namespace std; class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> cnt; for (auto& word : words) { cnt[word]++; } vector<string> ret; // 无序存单词 for (auto& p : cnt) { ret.push_back(p.first); } // 所有单词排序 // sort(起始迭代器，末尾后一位迭代器，自定义比较函数); sort(ret.begin(), ret.end(), [&](const string& a, const string& b)->bool { if (cnt[a] == cnt[b]) return a < b; return cnt[a] > cnt[b]; }); ret.erase(ret.begin() + k, ret.end()); // 删除前k后的单词 return ret; } };

4.4 单词识别（单词频次统计，中等）

BITKY120 单词识别

核心思路：属于无K限制的全局频次排序题，复用哈希统计+vector全排序模板，先分割清洗字符串统一小写计数，再按频次降、同频字典升序整体排序后全部输出。

#include <iostream> #include <unordered_map> #include <algorithm> #include <vector> #include <string> using namespace std; int main() { string s; getline(cin, s); // 整行输入，含空格、句号 unordered_map<string, int> cnt; string word; for (int i = 0; i < s.size(); i++) { if (s[i] >= 'A' && s[i] <= 'Z') word += s[i] + 32; // 大转小，字母拼单词 else if (s[i] >= 'a' && s[i] <= 'z') word += s[i]; // 小写字母拼单词 else { // 空格/句号 if (!word.empty()) { // 前面已收集完整单词 cnt[word]++; // 当前单词计数+1 word.clear(); // 准备收集下一单词的字母 } } } vector<string> ret; for (auto& p : cnt) { ret.push_back(p.first); } sort(ret.begin(), ret.end(), [&](const string& a, const string& b)->bool { if (cnt[a] == cnt[b]) return a < b; // 次数相同，小写字典序升序 return cnt[a] > cnt[b]; // 次数大的排在前面 }); for (string& r : ret) { cout << r << ":" << cnt[r] << endl; } return 0; }