目录
1）关联容器有哪些？各自底层是什么？
2）为什么 map/set 查找是 O(logN)？红黑树有什么性质？
3）map vs unordered_map 选型：什么时候用哪个？
4）map 的 operator[] 有什么副作用？
5）unordered_map 的 operator[] 也会插入吗？
6）count / find / equal_range 在 set/map 中怎么用？
7）lower_bound / upper_bound 在 map/set 的意义？
8）multimap/multiset 和 map/set 区别？
9）erase 的几种重载与迭代器失效规则
10）unordered_map 的 rehash、load_factor、reserve：会问很频繁
11）为什么 unordered_* 最坏 O(N)？如何缓解？
12）自定义排序：map/set 如何按自定义规则排序？
13）自定义 hash：unordered_map 如何支持自定义 key（如 pair/struct）？
14）map 的迭代器为什么是“稳定”的？能指向元素后长期使用吗？
15）map 的元素是 const key，为什么？
16）如何高效“更新或插入”？try_emplace / emplace / insert_or_assign
17）如何用 map 做“按 value 排序”？
18）时间复杂度对比常考表
额外：面试官最喜欢追问的“实战题型”（关联容器常用套路）
1）关联容器有哪些？各自底层是什么？
Q：STL 的关联容器有哪些？map/set和unordered_map/unordered_set区别是什么？
A：
有序关联容器：
set / multiset / map / multimap底层：红黑树（平衡二叉搜索树）
按 key 有序（
std::less<Key>默认）典型复杂度：查找/插入/删除O(log N)
无序关联容器：
unordered_set / unordered_multiset / unordered_map / unordered_multimap底层：哈希表（bucket + 链/开放寻址实现）
不保证遍历顺序
平均复杂度：查找/插入/删除O(1)，最坏O(N)（哈希冲突退化）
常见坑：
面试官常追问：*为什么 map 是 O(logN)？为什么 unordered_最坏会 O(N)？**（见后续题）
2）为什么 map/set 查找是 O(logN)？红黑树有什么性质？
Q：map/set为什么查找插入删除是 O(logN)？红黑树核心性质是什么？
A：
因为红黑树是一种近似平衡 BST，树高是O(logN)，所以基于树高的操作都是O(logN)。
红黑树典型性质（说出 3~5 条就够）：
节点是红或黑
根是黑
叶子 NIL 节点（空节点）是黑
红节点的孩子必须是黑（不能连红）
从任一节点到其所有后代 NIL 的路径，黑节点数相同（黑高一致）
常见坑：
不需要背“证明”，但要能说：通过限制红节点分布与黑高一致，让树不会退化成链表。
3）map vs unordered_map 选型：什么时候用哪个？
Q：什么时候用map，什么时候用unordered_map？
A：
用map的场景：
需要有序（比如按 key 范围遍历、找 lower_bound/upper_bound）
需要稳定的 O(logN) 最坏保证
key 类型不适合/不好写 hash（或者想减少哈希攻击风险）
用unordered_map的场景：
只关心 key->value 的快速访问，不需要排序
平均性能优先（大量查询/插入）
key 哈希分布良好
常见坑：
unordered_map遍历顺序不稳定，rehash 后顺序也可能变。最坏 O(N) 在安全场景/对抗输入（哈希冲突）可能是问题。
4）map 的 operator[] 有什么副作用？
Q：map[key]做了什么？与find区别？
A：
operator[]：若 key 不存在，会插入一个新元素，value 用默认构造生成，然后返回 value 引用。find：不插入，只查找。
示例：
std::map<std::string,int> m; m["a"]++; // 插入 {"a",0} 再自增 => 1 auto it = m.find("b"); // 不会插入常见坑：
面试常考：统计频次时
m[x]++可以；但“只想判断存在”就别用[]，会污染容器。
5）unordered_map 的 operator[] 也会插入吗？
Q：unordered_map[key]会插入吗？
A：
会。规则与map一样：key 不存在就插入默认值。
坑：
频繁
[]可能导致不断增长、触发 rehash，性能抖动。
6）count / find / equal_range 在 set/map 中怎么用？
Q：count、find、equal_range分别适合什么？
A：
find(k)：找一个 key 的迭代器（不存在返回 end）count(k)：对
set/map结果只可能是0 或 1对
multiset/multimap可能大于 1
equal_range(k)：返回
[lower_bound(k), upper_bound(k))对 multi 容器尤其好用（一次拿到某个 key 的所有元素范围）
7）lower_bound / upper_bound 在 map/set 的意义？
Q：lower_bound/upper_bound返回什么？复杂度？
A：
lower_bound(k)：第一个>= k的位置upper_bound(k)：第一个> k的位置在
map/set上复杂度O(logN)（树查找）
常见用法：
范围查询、区间删除、统计区间元素数量（结合 distance/迭代）
8）multimap/multiset 和 map/set 区别？
Q：multi 版本与非 multi 版本区别？如何删除某个 key 的一个元素 vs 全部？
A：
map/set：key 唯一multimap/multiset：key 可重复
删除：
删除全部：
ms.erase(key)（返回删掉的数量）删除一个：先
auto it = ms.find(key); if(it!=end) ms.erase(it);
坑：
erase(key)在 multi 容器会删一堆；面试经常考你是否知道差异。
9）erase 的几种重载与迭代器失效规则
Q：erase有哪些用法？迭代器会不会失效？
A：
erase(it)删除迭代器所指元素erase(key)删除 key 匹配的元素erase(first, last)删除区间
迭代器失效：
map/set：删除某个元素只会使被删元素的迭代器失效，其他迭代器仍有效。unordered_*：erase 会让被删元素迭代器失效；
rehash会让所有迭代器可能失效（这是大坑）
安全遍历删除写法（通用）：
for(auto it = m.begin(); it != m.end(); ){ if(cond) it = m.erase(it); else ++it; }10）unordered_map 的 rehash、load_factor、reserve：会问很频繁
Q：rehash 什么时候发生？load_factor、max_load_factor、reserve有什么用？
A：
哈希表维护：
load_factor = size / bucket_count当
load_factor > max_load_factor时，触发rehash（扩 bucket 并重新分布元素）reserve(n)：让容器至少能容纳 n 个元素而不频繁 rehash（典型优化手段）rehash(b)：直接设置 bucket 数下限为 b
面试加分点：
大量插入前
reserve能减少 rehash 次数，显著优化性能稳定性。
11）为什么 unordered_* 最坏 O(N)？如何缓解？
Q：unordered_map 为什么可能退化到 O(N)？怎么解决？
A：
原因：大量 key 哈希到同一个桶，桶内查找退化成线性链（或冲突处理退化）。
缓解：
选择更好的 hash（自定义
hash）提前
reserve控制
max_load_factor对抗场景下选
map（避免哈希攻击导致退化）
12）自定义排序：map/set 如何按自定义规则排序？
Q：如何让set按自定义规则排序？比较器要满足什么？
A：
传入比较器类型：
std::set<T, Cmp>比较器必须满足严格弱序（strict weak ordering）：
不能出现自相矛盾：
cmp(a,b)与cmp(b,a)不能同时为 true等价关系要稳定，否则会导致容器行为未定义/丢元素
常见坑：
用“<=”写比较器会炸（必须是严格
<语义）比较器依赖可变外部状态也容易出事故
13）自定义 hash：unordered_map 如何支持自定义 key（如 pair/struct）？
Q：unordered_map<pair<int,int>, int>怎么写？
A：
需要提供hash（以及必要时==）：
struct PairHash { size_t operator()(const std::pair<int,int>& p) const noexcept { return std::hash<int>{}(p.first) ^ (std::hash<int>{}(p.second) << 1); } }; std::unordered_map<std::pair<int,int>, int, PairHash> mp;加分点：
提到
noexcept、hash 混合方式、以及 pair/struct 要保证==与 hash 一致。
14）map 的迭代器为什么是“稳定”的？能指向元素后长期使用吗？
Q：map插入/删除后，已有迭代器会失效吗？
A：
map/set插入不会让已有迭代器失效（节点式结构）删除只让被删元素迭代器失效
因此很多场景下迭代器更“稳定”。
对比：
vector插入/扩容会让大量迭代器失效unordered_*rehash 会让迭代器大面积失效
15）map 的元素是 const key，为什么？
Q：为什么map的value_type是pair<const Key, T>？
A：
因为 key 决定在红黑树中的位置。
如果允许修改 key，会破坏有序性和树结构不变量，所以 key 必须是 const。
坑：
不能
it->first = newKey;（编译失败），要改只能 erase + insert。
16）如何高效“更新或插入”？try_emplace / emplace / insert_or_assign
Q：C++17 里 map/unordered_map 如何避免不必要构造？
A：
try_emplace(k, args...)：key 不存在才构造 value（更省）insert_or_assign(k, v)：存在就赋值，不存在就插入emplace：原地构造（但如果你传了 value 对象，仍可能先构造再移动）
常见坑：
面试官会让你解释：
emplace不是“永远零拷贝”，取决于参数传递方式。
17）如何用 map 做“按 value 排序”？
Q：map 只能按 key 排序，如果要按 value 排序怎么办？
A：
常规做法：把
map拷贝到vector<pair<...>>，然后sort按 value 排序或者使用
multimap<value, key>反转存储（注意 value 重复）
坑：
直接写比较器按 value 排序会破坏 key 唯一/查找语义（不建议）。
18）时间复杂度对比常考表
Q：map/set、unordered_map/unordered_set 的复杂度表？
A（口述版即可）：
map/set：查找/插入/删除O(logN)（最坏也保证）unordered_*：平均O(1)，最坏O(N)；rehash 会导致阶段性抖动
额外：面试官最喜欢追问的“实战题型”（关联容器常用套路）
词频统计/TopK：
unordered_map计数 +priority_queue或 sort去重：
set/unordered_set区间查询：必须用
map/set的lower_bound/upper_boundLRU/缓存：
unordered_map+list（关联容器当索引用）自定义 key：struct/pair 的 hash 与比较器
 开发实战：常见迁移挑战与技术解析)
