Lib.rs

PRust: (P)持久化 & (R)不可变数据结构在 (Rust) 中

该库包含一系列不可变和持久化数据结构，灵感来源于 Haskell、OCaml、Closure 以及 Okasaki 的《纯函数数据结构》一书。

它不包含

• 不安全的内存访问（没有使用 unsafe）
• 接受可变引用的方法
• 外部依赖

Prust 有何用途？

持久化数据结构：是否想要在数据结构上撤销操作？使用持久化数据结构，您可以访问之前的版本，基本上维护了所需的更改历史。

// Insert words
let mut trie = Trie::empty().insert("apple").insert("app").insert("banana");

// Snapshot the current trie. This operation is lightweight, allocating only a couple of bytes long.
let snapshot = trie.clone();

// Insert more words
trie = trie.insert("grape").insert("banana-split");

// Check for words in current trie
assert_eq!(trie.search("grape"), true);

// Restore trie to a previous of moment in time
trie = snapshot;

// Word was not present at snapshop moment
assert_eq!(trie.search("grape"), false);

不可变数据结构：一旦创建，数据结构就不会改变。而不是修改，会创建一个新的“视图”。

// deque: [2, 1]
let deque: Deque<i32> = Deque::empty().push_front(1).push_front(2);

// Even with pop_back, deque is still unaltered, since it's immutable
let (value, _) = deque.pop_back().unwrap();
assert_eq!(*value, 1);
assert_eq!(deque.length(), 2);

// The "new" deque with pop_back is returned as part of the call
let (value, deque_updated) = deque.pop_front().unwrap();
assert_eq!(*value, 2);
assert_eq!(deque_updated.length(), 1);

多线程友好性：得益于其不可变性，Prust 的数据结构本质上是无缝的线程安全的。更多内容请参见下面的部分。

可用的数据结构

• 字典树（又称前缀树）
• 哈希表/哈希集（基于字典树）
• AVL 树
• 有序映射/有序集（基于 AVL）
• 栈（又称 Cons 列表）
• 双端队列

线程安全

出于性能考虑，线程安全是可选的。要启用 thread_safe 功能，请将以下内容添加到您的 Cargo.toml

[dependencies.prust_lib]
version = "version"
features = ["thread_safe"]

这将把引用计数从 std::rc::Rc 转换为 std::sync::Arc。

Prust 是如何工作的？

Prust 不进行原地更新，每当调用类似可变的操作时（例如，向集合中添加值），Prust 返回一个新的更新后的结构体的“副本”，保持原始结构不变。这确保了持久性（通过保留先前版本）和不可变性（因为原始结构保持不变）。

这是通过重用原始结构的绝大部分，仅构建与更新版本相关的新的部分来实现的。

一个有趣的事实是，这些结构的克隆效率很高，因为它们通常只由几个指针表示。