容器与哈希表

常见容器（卷 I 6.3）

• 原书问题：① 书中把 std::hash_map 列为标准库字典，但它从未进入 C++ 标准，只是 SGI STL / MSVC 等的非标准扩展（MSVC 中已弃用）；标准的哈希表容器是 C++11 的 std::unordered_map（cppreference「std::unordered_map」，since C++11）。② 书中说二叉堆「像二叉搜索树一样保持排序」并不准确：堆只保证父节点与子节点之间的偏序（堆性质），兄弟之间、左右子树之间无序，因此不能按序遍历或 $O(\log n)$ 查找任意元素，只能 $O(1)$ 取堆顶（Wikipedia「Binary heap」）。

常见操作：插入、删除（可能需要先查找；有迭代器时直接用迭代器删更高效）、顺序访问（迭代）、随机访问、查找、排序。

迭代器（卷 I 6.3.2）

• 迭代器是「知道」如何高效遍历某种容器的小类，像数组索引或指针：指向一个元素、可前进、可判断是否遍历完。
• 好处：不破坏封装（通常是容器的友元，好的容器只能通过迭代器遍历）；简化遍历——即使是中序深度优先遍历树，也能写得像遍历数组一样简单。
• 前置还是后置自增（卷 I 6.3.2.1）：GEA 认为在值被使用的表达式中，++p 会引入数据依赖（CPU 要等自增完成才能用值），在深流水线 CPU 上造成停顿，而 p++ 的值可以立即使用、自增可稍后或并行进行，所以对内置类型偏好后置自增；在 for 的更新表达式中两者没有区别，好的编译器能看出值没被使用。例外：重载了自增运算符的类（如迭代器），后置版本按定义必须返回未修改的副本，复制成本可能让前置自增更划算。（这是 GEA 的观点；流水线与数据依赖见 并发与并行基础。）

算法复杂度与内存布局（卷 I 6.3.3）

• 用大 O 只保留增长最快的项：$5n^2+17$、$102n^2+50n+12$、$\tfrac12n^2$ 都是 $O(n^2)$。与元素个数无关为 $O(1)$；遍历一次为 $O(n)$；两重循环为 $O(n^2)$；二分查找最坏访问 $\lfloor\log_2 n+1\rfloor$ 个元素，为 $O(\log n)$；执行 n 次 $O(\log n)$ 子算法为 $O(n\log n)$。从快到慢：$O(1)$、$O(\log n)$、$O(n)$、$O(n\log n)$、$O(n^2)$、$O(n^k)\ (k>2)$。
• 选容器时看最常用的操作，再选这些操作性能最好的容器。
• 还要考虑内存布局：数组连续、除元素外几乎无额外开销（动态数组有很小的固定开销）；链表每个元素包在含 next（可能还有 prev）指针的节点里，64 位机上每元素最多 16 字节开销，且节点往往不连续。连续内存对缓存友好得多，所以高速算法通常用数组（除非链表节点本身从小块连续内存分配）；频繁插入删除时链表更好。

自研还是用现成库（卷 I 6.3.4）

引擎（尤其主机和移动平台）常自研容器，理由：

• 完全控制内存需求、算法、何时如何分配；
• 优化机会：针对目标主机硬件或引擎中的特定用途调优；
• 可定制：提供标准库或 Boost 没有的算法（如查找最相关的 n 个元素）；
• 去除外部依赖：问题能立即调试修复，不必等库的下一个版本（可能在游戏发售之后）；
• 控制并发：Naughty Dog 在 PS4 上多数并发数据结构使用轻量的自旋锁互斥体，因为它们与基于纤程的任务调度系统配合良好，第三方库可能不给这种灵活性（见 线程同步原语）。

• 补充（与书中观点并列）：书中关于分配器的批评主要针对 C++11 之前的模板分配器模型。C++17 引入了多态内存资源 std::pmr：std::pmr::monotonic_buffer_resource 可以用一块预先提供的缓冲（甚至栈上数组）做只增不减、整体释放的分配，本质上就是栈/线性分配器，std::pmr::vector、std::pmr::list 等容器都能直接使用（cppreference「std::pmr::monotonic_buffer_resource」，since C++17）。是否在运行时代码中使用 STL 仍是工程取舍。
• 原书问题：书中说更多 Boost 组件已进入「标准委员会的库技术报告 TR2」并将成为未来标准。实际上 TR2 从未发布：征集提案后 ISO 流程改变，不会有 TR2，改为以多份技术规范 (Technical Specification，如 Filesystem TS) 发布扩展（Wikipedia「C++ Technical Report 1」中的 Technical Report 2 一节）。
• 实例：PC 版《荣誉勋章：太平洋突袭》大量使用 STL，通过谨慎限制和控制其使用解决了由此引起的性能问题；OGRE 也大量使用 STL 风格容器；Naughty Dog 禁止在运行时游戏代码中使用 STL 容器（离线工具代码允许）。GEA 结论：可行，但要谨慎。
• GEA 还提醒智能指针复杂且可能很耗性能，通常句柄更好（详见卷 II 17.5 节）；句柄见 自定义内存分配器。
• Loki 的基于策略的编程 (policy-based programming) 等概念可用于任何 C++ 项目，作者推荐 Alexandrescu 的《Modern C++ Design》。

动态数组与分块分配（卷 I 6.3.5）

• 定长 C 数组在游戏中很常用：无需分配、连续、缓存友好，追加和查找都高效。
• 动态数组：先分配 n 个元素的缓冲，超出时分配更大的新缓冲、复制、释放旧缓冲；按固定增量 n 或翻倍增长。作者见过的实现大多只增不减（清空为零可能释放也可能不释放），缓冲大小成为「高水位线」，std::vector 就是这样（标准规定 std::vector::clear() 不改变容量，需要 shrink_to_fit() 或与空 vector 交换才可能释放）。补充：按固定增量增长时，追加 $n$ 个元素的总复制量是 $O(n^2)$；按倍数（如翻倍）增长时追加的均摊成本为 $O(1)$，这也是 std::vector 要求 push_back 均摊常数时间的原因。
• 增长可能极其昂贵（重新分配和复制），释放旧缓冲还会造成碎片。若能确定高水位线，最好在引擎启动时一次分配好。GEA 建议开发期用动态数组，确定内存预算后改为定长数组。

字典与哈希表（卷 I 6.3.6）

• 字典通常用二叉搜索树（按键有序，查找 $O(\log n)$）或哈希表实现。
• 哈希表：把键哈希成整数，对表长取模得到槽位索引；无冲突时查找 $O(1)$。例：5 个槽时键 3 存于 3 号槽，键 6 存于 1 号槽。

冲突处理（卷 I 6.3.6.1）

名称容易混淆：「开放/封闭寻址」指元素地址是否完全由哈希值决定。

哈希函数（卷 I 6.3.6.2）

• $h=H(k)$，$i=h \bmod N$。键是唯一整数时可用恒等函数；32 位浮点可直接把位模式重新解释为 32 位整数（书中用 memcpy 做类型双关）；字符串则把所有字符的 ASCII/UTF 码合成一个 32 位整数。
• 好的哈希函数：把键均匀分布到整张表以减少冲突、计算足够快、确定性（同输入同输出）。
• GEA 表 6.1（吞吐量为粗略的相对等级，SMHasher 分数）：

密码学哈希故意做得慢，目标是极难碰撞、极难由哈希值反推输入。

封闭哈希表的探测（卷 I 6.3.6.3–6.3.6.4）

• 线性探测：槽 i 被占则试 i+1、i+2……（到表尾回绕）；变体是前后交替 i+1、i−1、i+2、i−2……。缺点是键值对容易「扎堆」。
• 二次探测：试 $i\pm j^2$，即 $i+1^2, i-1^2, i+2^2, i-2^2,\dots$（都要对表长取模），减少聚集。
• 封闭哈希宜用素数表长；素数表长配合二次探测，覆盖槽位最好、聚集最少。
  • 补充（书中未说明的前提）：单向二次探测 $i+j^2$ 在素数表长 $m$ 下只保证前约 $m/2$ 个探测位置互不相同，负载因子超过 1/2 时插入可能找不到空槽；若像书中那样正负交替 ($i\pm j^2$)，且表长是模 4 余 3 的素数（如 7、11、19、23、31），前 $m$ 个探测恰好覆盖全部槽位，只要有空槽就一定能找到（Wikipedia「Quadratic probing」）。
• Robin Hood 哈希：近年流行的封闭哈希探测方案，即使表接近满也能提升性能（GEA 未展开细节）。

与 UE5 的对照

容器与字符串 记录 UE5 的 TArray 是带可选分配器参数、默认堆分配并多分配余量的连续容器，TMap/TSet 基于哈希与稀疏数组、遍历顺序不保证、扩容可能使元素指针失效。这对应 GEA 所说的动态数组「增长需重新分配与复制」，以及自研容器可接入自定义分配器的理由。