循环数据结构在稳定、安全、Rust 中的概念实现的证明。

循环数据结构在稳定、安全、Rust 中的概念实现的证明。这展示了static-rc crate 和ghost-cell crate 的综合能力。动机为什么要重视安全？关于数据结构的两个事实的简单组合：它们很普遍，经常用于存储用户控制的输入。它们非常容易出错，同时处理生命周期和混叠问题。这两个因素的结合意味着单个逻辑错误可能导致未定义行为，从而为多种攻击打开大门。如何编写安全的循环数据结构？如上所述，通常有两个障碍：生命周期和混叠。今天最先进的推荐是以下之一：带有索引而不是指针的Vec 。处理生命周期的竞技场，以及处理混叠的某种形式的单元格。Rc +RefCell 。这些方法有什么问题？基于Vec的解决方案将Vec拼接/拆分操作的算法复杂性。在链表中，拼接另一个链表，或者拆分链表的一部分，都是 O(1) 操作，但将 N 个元素从一个Vec转移到另一个Vec至少是一个 O(N) 操作。基于 Arena 的解决方案将允许以预期的算法复杂性实现所有操作，但这是以永远无法从 arena 回收内存为代价的，只要存在引用 arena 的单个数据结构。最后，Rc +RefCell会增加内存消耗和运行时