如果你在阅读过程中有任何疑问或想要进一步探讨的内容欢迎在评论区畅所欲言我们一起学习、共同成长~ 如果你觉得这篇文章还不错不妨顺手点个赞、加入收藏并分享给更多的朋友噢~1. 关联式容器 vs 序列式容器STL容器分为序列式容器和关联式容器核心区别序列式容器vector、list、deque 等底层是线性结构存储元素本身检索需遍历效率较低O (N)关联式容器底层基于平衡树红黑树实现存储key, value键值对检索通过key定位效率高达 O (log₂N)是面试 / 笔试高频考查模块。2. 关联式容器核心知识点2.1 键值对pair2.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) {} };核心考点first 存键second 存值支持两种访问方式①普通对象访问pair对象.first 、pair对象.second②map 迭代器访问it-first 、it-second用struct默认为public成员可直接 .first / .second 访问。带参构造是 map 插入元素最常用方式手写代码必须熟练①手动构造 pair 插入 mapm.insert(pairint, string(100, 张三));②make_pair 简写插入 mapm.insert(make_pair(100, 张三));2.1.2 make_pair笔试高频作用make_pair是模板函数自动推导模板参数简化pair创建不用手动指定T1、T2。源码背template class T1, class T2 pairT1, T2 make_pair(T1 a, T2 b) { return pairT1, T2(a, b); } // map.insert(make_pair(1,one))常用于 map 插入简写m.insert(make_pair(100, 张三));2.2 set 容器自动去重升序2.2.1 核心特点面试必背只存单个keykey必须唯一天然去重无 valueset底层是红黑树一种自平衡的二叉搜索树默认升序排列元素禁止直接修改元素值红黑树节点位置由元素值决定修改元素值破坏红黑树的有序性“删除旧元素插入新元素”可间接修改find/ insert/ erase的平均与最坏时间复杂度均为 O (logN)。2.2.2 三种构造笔试默写1空构造set元素类型 容器名;2列表构造自动去重升序setint s5 {3, 1, 4, 1, 5}; // 初始化后自动变为{1,3,4,5}3区间构造笔试数组去重首选int arr[] {2, 2, 1, 3}; setint s6(arr, arr sizeof(arr)/sizeof(int)); // {1,2,3} vectorint vec {5, 3, 5, 7}; setint s7(vec.begin(), vec.end()); // {3,5,7}2.2.3 核心接口 全套必掌握代码接口考点begin()/end()正向遍历升序rbegin()/rend()反向遍历降序insert(val)返回pair迭代器,bool.secondtrue则插入成功find(val)找到返回迭代器没找到返回end()判断存在标准写法erase(val)按值删除返回删除个数 0/1count(val)仅 0 或 1等价判断是否存在使用 set 包含头文件setusing namespace std; 或 std 前缀#include iostream #include set using namespace std; int main() { // 数组去重 int arr[] { 1,3,2,3,4,2,5 }; setint 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 核心特点面试高频存储键值对 pairconst key, value key 唯一且不可修改红黑树节点位置由key决定修改key破坏有序性value 可通过 it-second 修改map 底层红黑树按 key 默认升序find/ insert/ erase的平均与最坏时间复杂度均为 O (logN)map 重载 []支持 [] 访问 value笔试高频需理解底层逻辑set、multimap 无 [] 重载。2.3.2 三种构造1空构造mapint, string m;2列表构造mapint, string m { {1,A},{2,B} };3区间构造vectorpairint, string v { {3,C},{1,A},{1,A} }; // vectorpair 转 map自动去重 key mapint, string m(v.begin(), v.end()); // {1:A,3:C}2.3.3 核心接口 全套必掌握代码接口考点insert(pair)存在相同 key 不会覆盖返回pairit,booloperator[]可读可写key 不存在会插入默认 valuekey 存在会覆盖原 value。find(key)查找 key不存在返回end()erase(key)按 key 删除返回删除数量 0/1使用 map 包含头文件mapusing namespace std; 或 std 前缀#include iostream #include map #include string using namespace std; int main() { mapstring, string m; // 3种插入方式 m.insert(pairstring, 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]的底层逻辑必须理解构造键值对key, V()value 为默认值如 int 为 0string 为空执行insert若 key 已存在返回原元素的迭代器若 key 不存在返回新元素的迭代器最终返回该节点的value引用。坑哪怕只读取key 不存在也会插入默认空值污染容器。所以查询优先用find。mapint, string m; cout m[2]; // 不存在key2插入2, 输出空串对比 m.at(key) key 不存在直接抛异常不新增元素。2.4 multiset 与 multimap允许重复 key2.4.1 multiset / multimap 与 set / map 的核心区别面试高频特性set/mapmultiset/multimapkey必须唯一可重复count() 返回值0 或 1≥0返回重复次数[]map 支持multimap 不支持key 重复无法确定返回哪个 value2.4.2 头文件multiset#include setmultimap#include map2.4.3 equal_range笔试必考函数equal_range(key)返回pairiterator, iteratorrange.first首个匹配 key 的迭代器range.second最后一个匹配 key 的下一位迭代器默写#include iostream #include map using namespace std; int main() { multimapstring, 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) 坑点set/maperase (val) 删除一个匹配元素返回 0/1multiset/multimaperase (val) 删除全部匹配元素返回删除总数multisetint ms {2,2,2}; int num ms.erase(2); // num 32.5 set/map 迭代器特性与迭代器失效问题高频2.5.1 迭代器类型区分set/map/multiset/multimap双向迭代器仅支持it / --it不支持it n随机访问vector/deque随机访问迭代器支持itn2.5.2 红黑树容器迭代器失效规则必背底层红黑树节点内存地址固定仅删除节点会失效insert 插入仅旋转树结构所有迭代器均不失效erase 删除被删除节点对应的迭代器失效其余迭代器完全有效2.5.3 erase 两种重载返回值笔试erase(迭代器pos)无论 set/map/multiset/multimap返回下一个有效迭代器遍历删除专用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)迭代器双向迭代器 /--前向迭代器 仅支持 空间开销小哈希桶数组空间开销更大适用场景需要有序、区间范围查询、性能稳定只做增删查、不需要排序、追求极致速度高频面试问答什么时候用 map什么时候用 unordered_map答需要有序、范围遍历选 map无需排序、仅高频查找选 unordered_map。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左右先左旋后右旋触发依据AVL 树|平衡因子| 1失衡节点是祖父节点红黑树出现连续红节点3.4 红黑树近似平衡set/map 底层重点3.4.1 核心性质面试必背每个节点非红即黑根节点、叶子节点都为黑分支方向上无连续红节点当前节点向下到任意叶子节点所有分支的黑节点总数相同性质 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 祖父黑分三种场景场景 1u 红调整p 和 u 改黑g 改红cur 跳到 g 向上递归检查场景 2u 黑且 cur 与 p 同侧调整p 改黑g 改红左左➡右单旋 / 右右➡左单旋场景 3u 黑且 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核心思路由示例输入知两个数组都可能含重复元素而交集要求唯一则利用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) it2; else if (*it1 *it2) it1; else { ret.push_back(*it1); it1; it2; } } return ret; } };4.2 两数之和map简单LeetCode 1核心思路暴力解法的缺陷双重循环时间复杂度 O (N²)效率低map 优化思路用 map 存储 “元素值 - 下标” 键值对遍历数组时对当前元素nums[i]计算互补值target - nums[i]在 map 中查找该互补值class Solution { public: vectorint twoSum(vectorint nums, int target) { mapint, 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核心思路“前K个”显然属于 Top K 问题。C初阶(11)/STL(四)stack和queue总结了 Top K 问题经验。输出结果要求有序排除快速选择法堆优先队列法是 Top K 问题最通用解法可用。确认数据量1 words.length 500数据量小简洁解法 sort 全排序可用。需要先统计每个单词频次哈希表可 O (1) 快速完成单词计数映射。哈希 堆优先队列#include iostream #include unordered_map #include queue #include vector #include string using namespace std; // 存储pairstring,int为自定义复合类型无法用内置比较器必须手写比较规则 struct cmp { bool operator()(const pairstring, int a, const pairstring, int b) const { // 输出结果频次大、字典序小在前则频次大、字典序小更不易被删所以优先级低远堆顶 if (a.second b.second) // 频次相同 return a.first b.first; // a(字典序小)更低级下沉远堆顶 return a.second b.second; // 频次不同a(频次大)更低级下沉远堆顶 } }; class Solution { public: vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring, int cnt; for (auto word : words) { cnt[word]; } priority_queuepairstring, int, vectorpairstring, int, cmp q; for (auto c : cnt) { q.push(c); if (q.size() k) q.pop(); // 删堆顶频次小字典序大单词最终剩下前k高频词 } vectorstring 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: vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring, int cnt; for (auto word : words) { cnt[word]; } vectorstring 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_mapstring, 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(); // 准备收集下一单词的字母 } } } vectorstring 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; }