C++ 中如何对 map 按 value 排序
哪些公司问过
越疆机器人1
答案要点
- std::map 基于红黑树按 key 有序,比较器只作用于 key,不能直接按 value 排序
- 通用做法:拷贝到 vector<pair<K,V>>,std::sort 配合比较 second 的 lambda,O(n log n)
- value 相同时追加按 key 比较,保证排序结果确定
- 反转为 multimap<V,K> 或 set<pair<V,K>>,适合需要持续维护按 value 有序的场景
- 只需前 k 个时用 partial_sort 或大小为 k 的堆,复杂度 O(n log k)
易错点
- 试图给 std::map 写按 value 比较的比较器
- 反转键值时用 map 导致相同 value 的元素丢失
- 比较函数使用 <= 违反严格弱序,导致 std::sort 行为未定义
面试官常见追问
- 为什么反转时要用 multimap 而不是 map?
- 能不能给 map 传一个按 value 比较的比较器?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- vector 的扩容机制与性能174 场
- map 与 unordered_map 的区别167 场
- STL 的组成与常用容器151 场
- vector 与 list 的区别85 场
- STL 迭代器失效的场景47 场
- map 的底层实现:为什么用红黑树47 场
- STL 内存分配器12 场
- deque 的底层实现10 场
- unordered_map 底层实现、哈希冲突与 rehash9 场
- vector 和数组的区别8 场