课时

我们讲解为什么相同的渐进复杂度（ O(N)）并不保证相同的速度：CPU 缓存和缓存行如何“偏好”相邻的元素，为什么使用连续内存的 std::vector 往往优于使用节点并有内存跳转的 std::list， std::deque 在何处折中，以及如何在实践中感受局部性（打印地址、线性遍历、谨慎的迭代风格）。最后——典型的优化错误：盲目相信 O(1)、根据一次试验下结论以及忽略 vector 的引用失效规则。

我们来讨论为什么在 std::set 和 std::map 中比较器是容器正确性的一部分，而不是“排序选项”：如何通过 comp 定义键的等价性，什么是 strict weak ordering，为什么不能用 <= 代替 <，为什么需要 tie-breaker，以及为什么比较器必须是“纯粹的”（不能有外部可变状态和副作用）。

解析 C++ 哈希容器的内部：查找路径 key → hash → bucket → 通过 == 进行相等性检查，什么是 bucket_count() 和 load_factor()，为什么负载密度影响速度以及增长如何触发 rehash 并使迭代器失效。展示工程实践技巧： reserve()、 max_load_factor()、简单诊断以及基于 std::unordered_map 按 id 的实用索引。

解析如何为关联容器设计“身份键”： 在通过比较器实现唯一性约定的 std::map/std::set 与通过 hash + == 实现的 std::unordered_map/std::unordered_set 之间有何不同，为什么复合键需要 tie-breaker，字符串归一化如何影响正确性和性能，以及哪些错误最常破坏查找和插入。

分析 C++ 中容器的工程选择：何时应坚持使用 std::vector（包括“已排序的 vector”+ 二分查找的变体），何时更适合使用 std::map。在教学案例“联系人名录”中比较按键查找、插入/删除、遍历顺序、缓存局部性影响和内存开销，并给出帮助根据需求选择容器的实用问题。