【C 面试真题】聊聊 C 的关联容器关联容器是按 key 找值的一族也是标准库面试的分水岭。背得出map 是红黑树、unordered_map 是哈希表只是及格真考你的是为什么选红黑树不选 AVL、operator[] 有什么坑、负载因子和 rehash 怎么回事、两族的迭代器失效规则差在哪、自定义类型怎么当 key。本文把有序、无序两族一次讲透。一、开场关联容器有哪些❓ 介绍一下标准库的关联容器✅ 按 key 找值的两族共八个族成员底层查找有序map / set / multimap / multiset红黑树O(log n)无序[C11]unordered_map / set / multimap / multiset哈希表均摊 O(1)map / multimap存pairconst Key, Valuemultimap 允许 key 重复set / multiset只有 keyvalue 就是 key 本身带multi的允许重复 key不带则互斥。回答思路先按有序红黑树/ 无序哈希“两族报成员再点一句带 multi 的允许重复 key”——最后落到选型口诀上面试官自然会顺着追问底层实现。选型口诀要有序遍历或范围查询用有序族纯查找、追求速度用无序族。二、有序族底层红黑树❓ map 为什么用红黑树✅ 红黑树是近似平衡的二叉搜索树——节点着红/黑色靠五条性质约束保证最长路径不超过最短路径的两倍。效果增、删、查全部稳定在O(log n)且中序遍历恰好有序——这正是 map按 key 排序的来源。为什么不是 AVL 树AVL 是严格平衡左右子树高度差 ≤ 1查询略快但插入删除后维持平衡要做的旋转更多。红黑树松一点插入最多 2 次旋转、删除最多 3 次维护便宜。容器场景增删频繁综合下来红黑树赢——所以工业界容器C 标准库、Java TreeMap清一色选它。红黑树的另一个好处节点地址稳定。插入删除只改指针链接、不搬节点这直接决定了有序族宽松的迭代器失效规则第六节细讲。三、map 使用考点operator[] 与范围查询❓ map 的 operator[] 和 at 有什么区别✅ 一张表看清操作key 不存在时备注m[k]插入默认值再返回读操作有写入副作用m.at(k)抛out_of_range只读安全m.find(k)返回end()只读最稳mapstring,intm;m[tom]18;// 插入或覆盖intam[bob];// ⚠ 没有 bob// 也会插入 {bob, 0}再返回 0intbm.at(bob);// 没有则抛异常⚠️ 典型翻车判断分支里随手写if (m[k] 0)——本想查询却把 {“k”,0} 塞进了 map。只读场景一律find或contains[C20]if(m.count(k)){/* 存在 */}if(m.contains(k)){/* C20 */}⚠️ 另外multimap 没有 operator[]——key 可重复下标取值语义根本无法定义。查询之外有序还给 map/set 留了独门功夫——lower_bound/upper_bound/equal_range范围操作setints{1,3,5,7,9};// 第一个 4 的元素autolos.lower_bound(4);// → 5// 第一个 5 的元素autoups.upper_bound(5);// → 7// [lo, up) 就是值为 5 的区间lower_bound(k)第一个≥ kupper_bound(k)第一个 k遍历某时间段的日志、找某分数段的用户、前缀匹配——这类范围型需求无序族做不了哈希只支持点查。四、无序族底层哈希表❓ unordered_map 的底层长什么样✅桶数组 拉链key 先过哈希函数得出桶下标落进同一个桶的元素串成链表。桶数组: [0]→cat [1]→(空) [2]→dog→owl ← 哈希碰撞 [3]→(空)查找 算哈希O(1) 桶内比对桶越长越慢。衡量拥挤程度的指标是负载因子// load_factor size / bucket_countunordered_mapstring,intm;m.max_load_factor(0.7f);// 阈值默认 1.0m.reserve(1000);// 预开足够桶避免 rehash负载因子超阈值触发rehash开更大的桶数组所有元素重新分桶——一次性 O(n)。这就是均摊 O(1)的来由n 次插入的总代价摊到每次是常数。⚠️最坏 O(n)哈希函数选得差或被恶意构造碰撞攻击所有 key 挤进同一个桶查找退化成链表扫描。所以无序族的 O(1) 是平均不是保证。五、两族对比性能与迭代器失效❓ 有序和无序到底怎么权衡✅ 四个维度对比维度map/setunordered_*查找O(log n) 稳定均摊 O(1)最坏 O(n)有序遍历/范围查✅❌插入使迭代器失效否不失效rehash 时全失效key 需要提供operator严格弱序hash 函数 operator迭代器失效高频考点规则不对称有序族插入不失效任何迭代器删除只失效被删的那个无序族rehash 后迭代器全部失效——但指针和引用仍然有效节点没搬只是重新挂桶。这是个反直觉的高分点。unordered_mapint,stringm;stringrm[1];// 拿到引用m[2];m[3];/* ... */// 中途可能 rehashcoutr;// ✅ 引用仍有效// 但旧迭代器已失效六、自定义类型做 key❓ 自己写的类型想当 key要提供什么✅ 看你用哪族——要求完全不同structKey{inta;string b;};// 有序族只要一个小于比较booloperator(constKeyx,constKeyy){if(x.a!y.a)returnx.ay.a;returnx.by.b;// 必须严格弱序}无序族则要两样哈希函数和相等比较// 无序族hash structKeyHash{size_toperator()(constKeyk)const{returnhashint()(k.a)^hashstring()(k.b);}};structKeyEq{booloperator()(constKeyx,constKeyy)const{returnx.ay.ax.by.b;}};unordered_mapKey,int,KeyHash,KeyEqm;⚠️ 无序族的隐性契约两个相等的 key 必须哈希出同一个值否则同一个 key 会落进两个桶find 永远找不到。相等比较和哈希必须配套写。七、怎么选实践建议❓ 实际项目怎么选✅ 三问定案要按序遍历、范围查询、找最大最小→ map/set纯点查、量大、追求吞吐→ unordered_map/set快一个量级不是梦key 没法定义小于比较只有 → 只能用无序族。// 词频统计无序更快unordered_mapstring,intfreq;// 排行榜按名次输出有序更省事mapstring,intscore;默认倾向纯查找场景 unordered_map 是现代默认一旦涉及顺序、范围、前缀别犹豫选 map——为排序额外付 O(log n) 比事后 sort 一遍 vector 便宜。八、面试高频追问❓ Q1为什么标准库选红黑树而不是 AVL、跳表、B 树✅ AVL 严格平衡、查询略快但增删旋转多、维护贵跳表实现简单但空间开销和缓存表现不占优B 树为磁盘页设计内存场景节点太小浪费。红黑树在增删查综合 内存布局上最均衡是容器场景的工程最优解。❓ Q2unordered_map 的最坏情况是什么✅ 所有 key 哈希碰撞挤进同一个桶查找退化成链表扫描 O(n)。哈希函数质量差或遭遇构造碰撞的恶意输入时会发生。❓ Q3rehash 之后指向元素的指针还有效吗✅有效。rehash 只重建桶数组、把节点重新挂链节点本身不搬家所以指针和引用不断——失效的只是迭代器。这是 unordered 失效规则里最反直觉、也最常考的一条。❓ Q4map 插入会使已有迭代器失效吗✅ 不会。红黑树插入只链接新节点、不改老节点地址所有已有迭代器继续有效删除也只失效被删元素那一个。❓ Q5unordered_map 为什么需要 operator哈希不是已经分桶了吗✅ 哈希只负责粗分到桶桶内可能有碰撞还要用 做精确认——判断到底是不是同一个 key。这也是为什么相等比较必须和哈希函数配套。九、总结速查表考点一句话结论有序族红黑树O(log n)中序即有序为什么红黑树插删旋转少综合维护最便宜无序族桶拉链均摊 O(1)最坏 O(n)operator[]不存在则插入默认值读带写副作用范围查询lower/upper_bound有序族独有负载因子size / bucket_count超阈值 rehash无序失效rehash 后迭代器失效指针引用不失效自定义 key有序要 无序要 hash 一句话回顾有序族红黑树稳定 O(log n)、中序有序、插入不失效迭代器、吃operator无序族哈希表均摊 O(1)、怕碰撞、rehash 只废迭代器不废指针、吃 hash 。要顺序和范围选 map纯点查选 unordered——operator[] 有坑只读用 find。如果您觉得本篇内容对你有帮助欢迎点赞 、收藏 ⭐、转发 。下期我们继续标准库篇聊迭代器——它的分类体系、和指针的关系以及那张容器失效规则表敬请关注