Rust持久数据结构

Rust持久数据结构提供具有结构共享的完全持久数据结构。

设置

要使用rpds，请将以下内容添加到您的 Cargo.toml

[dependencies]
rpds = "<version>"

数据结构

此crate提供以下数据结构

1. 列表
2. 向量
3. 栈
4. 队列
5. 哈希TrieMap
6. 哈希TrieSet
7. 红黑树Map
8. 红黑树Set

列表

您经典的函数式列表。

示例

use rpds::List;

let list = List::new().push_front("list");

assert_eq!(list.first(), Some(&"list"));

let a_list = list.push_front("a");

assert_eq!(a_list.first(), Some(&"a"));

let list_dropped = a_list.drop_first().unwrap();

assert_eq!(list_dropped, list);

向量

一个可索引的序列。其实现在理解持久向量第1部分和理解持久向量第2部分中描述。

示例

use rpds::Vector;

let vector = Vector::new()
    .push_back("I’m")
    .push_back("a")
    .push_back("vector");

assert_eq!(vector[1], "a");

let screaming_vector = vector
    .drop_last().unwrap()
    .push_back("VECTOR!!!");

assert_eq!(screaming_vector[2], "VECTOR!!!");

栈

一个后进先出（LIFO）数据结构。这只是伪装成List的列表。

示例

use rpds::Stack;

let stack = Stack::new().push("stack");

assert_eq!(stack.peek(), Some(&"stack"));

let a_stack = stack.push("a");

assert_eq!(a_stack.peek(), Some(&"a"));

let stack_popped = a_stack.pop().unwrap();

assert_eq!(stack_popped, stack);

队列

一个先进先出（FIFO）数据结构。

示例

use rpds::Queue;

let queue = Queue::new()
    .enqueue("um")
    .enqueue("dois")
    .enqueue("tres");

assert_eq!(queue.peek(), Some(&"um"));

let queue_dequeued = queue.dequeue().unwrap();

assert_eq!(queue_dequeued.peek(), Some(&"dois"));

哈希TrieMap

一个使用哈希数组映射 trie实现的映射。有关详细信息，请参阅理想哈希树。

示例

use rpds::HashTrieMap;

let map_en = HashTrieMap::new()
    .insert(0, "zero")
    .insert(1, "one");

assert_eq!(map_en.get(&1), Some(&"one"));

let map_pt = map_en
    .insert(1, "um")
    .insert(2, "dois");

assert_eq!(map_pt.get(&2), Some(&"dois"));

let map_pt_binary = map_pt.remove(&2);

assert_eq!(map_pt_binary.get(&2), None);

哈希TrieSet

一个使用HashTrieMap实现的集合。

示例

use rpds::HashTrieSet;

let set = HashTrieSet::new()
    .insert("zero")
    .insert("one");

assert!(set.contains(&"one"));

let set_extended = set.insert("two");

assert!(set_extended.contains(&"two"));

let set_positive = set_extended.remove(&"zero");

assert!(!set_positive.contains(&"zero"));

红黑树Map

一个使用红黑树实现的映射。

示例

use rpds::RedBlackTreeMap;

let map_en = RedBlackTreeMap::new()
    .insert(0, "zero")
    .insert(1, "one");

assert_eq!(map_en.get(&1), Some(&"one"));

let map_pt = map_en
    .insert(1, "um")
    .insert(2, "dois");

assert_eq!(map_pt.get(&2), Some(&"dois"));

let map_pt_binary = map_pt.remove(&2);

assert_eq!(map_pt_binary.get(&2), None);

assert_eq!(map_pt_binary.first(), Some((&0, &"zero")));

红黑树Set

一个使用RedBlackTreeMap实现的集合。

示例

use rpds::RedBlackTreeSet;

let set = RedBlackTreeSet::new()
    .insert("zero")
    .insert("one");

assert!(set.contains(&"one"));

let set_extended = set.insert("two");

assert!(set_extended.contains(&"two"));

let set_positive = set_extended.remove(&"zero");

assert!(!set_positive.contains(&"zero"));

assert_eq!(set_positive.first(), Some(&"one"));

其他功能

可变方法

当您更改数据结构时，您通常不需要它的先前版本。对于这些情况，rpds为您提供了可变方法，这些方法通常更快。

use rpds::HashTrieSet;

let mut set = HashTrieSet::new();

set.insert_mut("zero");
set.insert_mut("one");

let set_0_1 = set.clone();
let set_0_1_2 = set.insert("two");

初始化宏

所有数据结构都有方便的初始化宏。

use rpds::*;

let vector = vector![3, 1, 4, 1, 5];
let map = ht_map!["orange" => "orange", "banana" => "yellow"];

请参阅其他数据结构的初始化宏文档。

线程安全

此crate中的所有数据结构都可以在线程之间共享，但这是一种可选功能。这是因为使数据结构线程安全会有性能开销。当您实际上不在线程之间共享数据结构时，避免这种开销是值得的。

当然，如果您尝试在不同的线程间共享 rpds 数据结构，您有理由相信 Rust 编译器会确保这样做是安全的。如果您使用的是不线程安全的版本，您将在编译时遇到错误。

要创建任何数据结构的线程安全版本，请使用 new_sync()

let vec = Vector::new_sync()
    .push_back(42);

或者使用初始化宏的 _sync 变体

let vec = vector_sync!(42);

更多详细信息

在这个 crate 中，数据结构内部维护了大量引用计数指针。这些指针不仅用于数据结构内部节点之间的链接，还用于存储的值。

标准库中有两种引用计数指针的实现：Rc 和 Arc。它们的行为方式相同，但 Arc 允许您在多个线程间共享它指向的数据。缺点是，与 Rc 相比，它的克隆和释放速度要慢得多，而持久数据结构会执行大量此类操作。在一些使用 rpds 数据结构的微基准测试中，我们可以看到使用 Rc 而不是 Arc 可以使某些操作的速度提高两倍！您可以通过运行 cargo bench 来亲自看到这一点。

为了实现这一点，我们将引用计数指针的类型（Rc 或 Arc）作为数据结构类型参数进行参数化。我们使用 archery crate 来以方便的方式完成此操作。

let vec: Vector<u32, archery::ArcTK> = Vector::new_with_ptr_kind();
//                              ↖
//                                This will use `Arc` pointers.
//                                Change it to `archery::RcK` to use a `Rc` pointer.

[dependencies]
rpds = { version = "<version>", default-features = false }

[dependencies]
rpds = { version = "<version>", features = ["serde"] }