Lib.rs

PRust: (P)ersistent & Immutable Data Structures in (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）
• 栈（也称为连续列表）
• 双端队列

线程安全

出于性能原因，线程安全是可选的。要启用thread_safe功能，请在您的Cargo.toml中添加以下内容

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

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

Prust是如何工作的？

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

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

颜色数组是指克隆这些结构是高效的，因为它们通常只需要几个指针来表示。