容器选择 — Wu Chenfeng

链表插入是常数时间，找到那个节点却可能遍历整表。容器选择先列出主要操作与引用稳定性，再比较数组、哈希和有序树。实际缓存和分配常常决定理论复杂度能否兑现。

操作决定容器

工作负载

选择结构前列出：

插入、删除、查找、遍历哪个最频繁；
是否需要稳定顺序；
键是否唯一；
数据量和峰值；
是否多线程/GPU；
是否需要序列化、差异和确定性；
查询是精确、范围还是最近邻。

没有工作负载，“HashMap 比列表快”没有意义。

数组、列表与双端队列

连续数组或vector：

按下标访问为 $O(1)$ ；
尾部追加摊还 $O(1)$ ；
中间插删 $O(N)$ ；
缓存局部性好；
重新分配会使指针/迭代器失效。

链表已知节点时插删 $O(1)$ ，但查找是 $O(N)$ ，每节点分配与指针跳转对缓存不友好。现代实时代码中，它往往没有理论图上看起来那么便宜。

双端队列适合两端插删和队列。具体块布局与迭代性能取决于实现。

`std::vector` 的容量与失效

std::vector 保存一段连续元素，通常区分 size 与 capacity。size 是已经构造的元素数量，capacity 是当前存储可容纳的元素数量。尾部插入超出容量时会申请更大连续空间，把旧元素移动或复制过去，再释放旧空间。

扩容倍率由标准库实现决定，标准只要求尾部追加具有摊还常数复杂度。常用操作的区别：

reserve(n) 只保证容量至少为 n，不创建元素；
resize(n) 改变元素数量，可能构造或销毁元素；
push_back 加入已有对象，emplace_back 用参数在尾部构造对象；
clear 销毁元素但通常保留容量；
shrink_to_fit 是非强制请求，不能依赖它一定释放内存。

重新分配会使指向元素的指针、引用和迭代器全部失效。未扩容的尾部插入也会使末尾迭代器失效。需要长期身份时，应保存稳定 ID、索引加版本号，或选择具有相应稳定性保证的结构。

vector 的连续性通常让它成为默认顺序容器。频繁中间插入并不自动意味着 list 更快；还要计算查找节点、每节点分配和缓存未命中。

栈、队列与优先队列

栈是 LIFO，适合 DFS、解析和撤销层级；队列是 FIFO，适合 BFS、任务和事件顺序。

优先队列通常由二叉堆实现：

查看最小/最大： $O(1)$ ；
插入： $O(\log N)$ ；
弹出： $O(\log N)$ 。

A*、Dijkstra 和调度器会用它选择当前代价最小节点。若需要更新已有节点 Priority，要保存句柄/Index 或允许重复插入并在弹出时跳过旧记录。

哈希表

哈希表平均查找/插入 $O(1)$ ，但碰撞、扩容和恶意键可退化。

关键：

哈希与相等性判断必须一致；
可变键放入后不能改变参与哈希的字段；
装载因子影响内存与碰撞；
重新哈希会产生峰值；
普通哈希遍历顺序不应作为确定性输出顺序。

资产构建需要稳定结果时，输出前按规范键排序，或使用有序结构。不要依赖某次运行的 Dictionary 枚举顺序。

std::unordered_map 常由桶数组加冲突链或等价结构实现。哈希先定位桶，再在桶内通过相等性判断找键。load_factor = size / bucket_count，超过阈值时重新哈希会重建桶分布，并产生时间和内存峰值。

平均 $O(1)$ 依赖哈希分布和装载因子。键集中到少量桶时会退化到线性查找。自定义键必须让相等对象得到相同哈希；哈希相同的对象仍可不相等。

设桶数为4、哈希函数为整数键本身，键1和5都进入桶1。查找5时先定位桶1，再逐个比较键；找到1不代表已经命中。若键对象从1改成2却仍留在桶1，随后查找2会进入桶2而找不到它，即使对象还在容器中。扩容到8桶时又要重算位置，5会移到桶5。这三个步骤分别说明相等比较、不可变键与重新哈希的必要性。

开放寻址表把元素直接放在桶数组中，缓存局部性较好，但删除、探测序列和高装载率更敏感。链式或节点式实现更容易保持节点地址，却增加指针和分配成本。标准只规定接口、复杂度与失效规则，不固定 unordered_map 的内部冲突策略。

树结构

树表达层级：场景图、Skeleton、UI、文件目录和 BVH。

深度优先搜索（DFS）适合递归处理子树、序列化和后序删除。广度优先搜索（BFS）适合按层级处理和找最少边数路径。

递归DFS 简洁，但极深树可能栈溢出。大型/不可信数据使用显式栈，并检测环。场景“应该是树”也可能因损坏引用形成环。

平衡二叉搜索树保持查询、插入、删除 $O(\log N)$ ，并支持有序遍历。若只需要键查找，哈希往往更直接；若需要范围/顺序，树更合适。

红黑树与有序关联容器

红黑树用颜色约束限制最长路径：根通常视为黑色，空叶为黑色，红节点不能有红孩子，从任一节点到后代空叶的黑节点数量相同。由此树高保持在 $O(\log N)$ 。

插入或删除破坏约束后，通过重新着色和左旋、右旋恢复平衡。红黑树追求的是较宽松的高度界，不像 AVL 树那样严格平衡，因此更新时通常需要较少旋转。

std::map、std::set 的标准保证有序遍历和对数级查找、插入、删除。很多标准库用红黑树实现，但具体结构不是 C++ 标准的一部分。节点式有序容器通常保持未删除元素的迭代器/引用稳定，代价是每节点分配、指针开销和较差的空间局部性。

需要范围查询和有序遍历时，选择有序容器。只按键精确查找时，可以考虑哈希表。数据量较小或更新少时，排序后的 vector 加二分查找也值得测试，它通常更紧凑且有较好的访问局部性。

容器工作负载

以下为诊断数据定义，用来比较候选实现的真实操作，不是固定最优答案。

text

Workload { count, lookups, orderedRanges, insertions, erasures,
           stableReferenceRequired, iterationBytes }

操作序列与引用稳定性

假设编辑器每次载入一万条资产，随后执行一千次按名称查找和十次有序范围显示，更新很少。排序数组先付一次排序成本，查找用二分，范围结果连续读取；哈希表精确查找方便，但范围显示还需排序副本。有序树把排序成本分摊到插入，却增加节点与指针访问。三个候选都应回放同一条操作序列。

引用稳定性会直接排除部分实现。对象指针交给异步任务后，vector扩容会使旧指针失效；提前reserve只能覆盖已知容量以内的追加，不能解决中间删除和生命周期问题。长期身份保存ID，再在受保护阶段解析对象，通常更容易维护。

复杂度表中的平均与摊还表示不同前提：哈希平均依赖分布，数组摊还追加依赖扩容策略对整段序列的成本分摊。测试同时记录最慢一次操作与总耗时，才能看见扩容尖峰。

验证方法

固定同一操作序列比较时间、分配峰值和迭代失效。哈希键变化、rehash和vector扩容专门测试；有序范围查询与精确查找分别测量。

实现与证据

正文选择依据与工作负载结构已复读。vector容量语义核对标准草案；未运行容器性能基准，文中没有实际平台速度排名。

参考资料

C++标准草案 vector.capacity：reserve、capacity、shrink_to_fit及引用失效；2026-10-22核读。
C++标准草案 associative.reqmts：有序关联容器的操作与复杂度。