一个Cactus Stack or Parent Pointer Tree是一个堆栈,其中堆栈中的节点具有指向其父级的指针,因此堆栈可以通过多种方式进行攀爬。
我正在尝试在 Rust 中实现一个基于 this immutable implementation 的可变仙人掌堆栈使用Rc<RefCell<T>>
传递共享内存的模式:
use std::rc::Rc;
use std::cell::RefCell;
#[derive(Clone, Default)]
pub struct Cactus<T> {
node: Option<Rc<RefCell<Node<T>>>>,
}
#[derive(Clone)]
pub struct Node<T> {
val: Rc<RefCell<T>>,
parent: Option<Rc<RefCell<Node<T>>>>,
len: usize,
}
impl<T> Cactus<T> {
pub fn new() -> Cactus<T> {
Cactus { node: None }
}
pub fn is_empty(&self) -> bool {
self.node.is_none()
}
pub fn len(&self) -> usize {
self.node.as_ref().map_or(0, |x| x.borrow().len)
}
pub fn child(&self, val: T) -> Cactus<T> {
Cactus {
node: Some(Rc::new(RefCell::new(Node {
val: Rc::new(RefCell::new(val)),
parent: self.node.clone(),
len: self.node.as_ref().map_or(1, |x| x.borrow().len + 1),
}))),
}
}
pub fn parent(&self) -> Option<Cactus<T>> {
self.node.as_ref().map(|n| Cactus {
node: n.borrow().parent.clone(),
})
}
pub fn val(&mut self) -> Option<Rc<RefCell<T>>> {
self.node.map(|n| n.borrow_mut().val.clone())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_simple() {
let r = Cactus::new();
assert!(r.is_empty());
assert_eq!(r.len(), 0);
assert!(r.val().is_none());
assert!(r.parent().is_none());
let r2 = r.child(2);
assert!(!r2.is_empty());
assert_eq!(r2.len(), 1);
assert_eq!(*r2.val().unwrap(), 2);
let r3 = r2.parent().unwrap();
assert_eq!(r3.is_empty(), true);
assert_eq!(r3.len(), 0);
let r4 = r.child(3);
assert_eq!(r4.len(), 1);
assert_eq!(*r4.val().unwrap(), 3);
let r5 = r4.parent().unwrap();
assert!(r5.is_empty());
let r6 = r4.child(4);
assert_eq!(r6.len(), 2);
assert_eq!(*r6.val().unwrap(), 4);
assert_eq!(*r6.parent().unwrap().val().unwrap(), 3);
}
}
我的问题是获取val
来自节点:
error[E0308]: mismatched types
--> src/main.rs:64:9
|
64 | assert_eq!(*r2.val().unwrap(), 2);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
|
= note: expected type `std::cell::RefCell<{integer}>`
found type `{integer}`
= note: this error originates in a macro outside of the current crate
error[E0308]: mismatched types
--> src/main.rs:70:9
|
70 | assert_eq!(*r4.val().unwrap(), 3);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
|
= note: expected type `std::cell::RefCell<{integer}>`
found type `{integer}`
= note: this error originates in a macro outside of the current crate
error[E0308]: mismatched types
--> src/main.rs:75:9
|
75 | assert_eq!(*r6.val().unwrap(), 4);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
|
= note: expected type `std::cell::RefCell<{integer}>`
found type `{integer}`
= note: this error originates in a macro outside of the current crate
error[E0308]: mismatched types
--> src/main.rs:76:9
|
76 | assert_eq!(*r6.parent().unwrap().val().unwrap(), 3);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
|
= note: expected type `std::cell::RefCell<{integer}>`
found type `{integer}`
= note: this error originates in a macro outside of the current crate
最佳答案
我担心您只是试图在这个问题上抛出 Option
、Rc
和 RefCell
,从而迷失了自己。
这些并不是包治百病的 Elixir ,您需要了解它们何时有意义,何时没有意义。
这是我修改后的定义:
pub struct Cactus<T>(Option<Rc<Node<T>>>);
struct Node<T> {
value: RefCell<T>,
parent: Cactus<T>,
len: usize,
}
免责声明:我试图推断你在哪里真正需要可变性,在哪里不需要,因为你从未真正解释过它。我的推断可能有些地方是错误的;例如,我认为没有必要更换 parent 。
让我们分析一下Node
:
Node
唯一拥有它的值,它从不共享它,因此这里的Rc
没有意义。Node
可能有别名,但您仍然想修改其值,这需要将值包装在RefCell
中。Node
总是有一个父节点,因为Cactus
已经嵌入了无效的概念。
和仙人掌
:
Cactus
可能为 null,因此它是一个Option
。Cactus
与其他节点共享其节点,因此需要Rc
。Cactus
永远不需要切换到另一个Node
,它可以直接改变共享节点,因此不需要RefCell
。
从那里,我们可以为 Cactus
实现 Clone
( the automatic derivation fails hard ):
impl<T> Clone for Cactus<T> {
fn clone(&self) -> Self { Cactus(self.0.clone()) }
}
注意在 lambda 中使用 as_ref
获取 &Rc
;如果没有它,map_or
调用将尝试将 Rc
移出 self.0
,这是被禁止的,因为 self
是借来的。
其他功能自然如下:
impl<T> Cactus<T> {
pub fn new() -> Cactus<T> { Cactus(None) }
pub fn is_empty(&self) -> bool { self.0.is_none() }
pub fn len(&self) -> usize { self.0.as_ref().map_or(0, |n| n.len) }
pub fn child(&self, val: T) -> Cactus<T> {
let node = Node {
value: RefCell::new(val),
parent: self.clone(),
len: self.len() + 1,
};
Cactus(Some(Rc::new(node)))
}
pub fn parent(&self) -> Cactus<T> {
self.0.as_ref().map_or(Cactus(None), |n| n.parent.clone())
}
pub fn value(&self) -> Option<&RefCell<T>> {
self.0.as_ref().map(|n| &n.value)
}
}
请注意,我更改了一些签名:
parent
返回Cactus
,它可能为 null。我不区分拥有空 parent 和空 parent 之间的区别。这是有问题的,我只是觉得将可能为空的Cactus
包裹在Option
中很奇怪。value
返回对RefCell
的引用(封装在Option
中),以便调用者可以调用borrow_mut
并改变实际值。
这需要对测试进行一些调整:
#[test]
fn test_simple() {
let r = Cactus::new();
assert!(r.is_empty());
assert_eq!(r.len(), 0);
assert!(r.value().is_none());
assert!(r.parent().is_empty());
let r2 = r.child(2);
assert!(!r2.is_empty());
assert_eq!(r2.len(), 1);
assert_eq!(*r2.value().unwrap().borrow(), 2);
let r3 = r2.parent();
assert_eq!(r3.is_empty(), true);
assert_eq!(r3.len(), 0);
let r4 = r.child(3);
assert_eq!(r4.len(), 1);
assert_eq!(*r4.value().unwrap().borrow(), 3);
let r5 = r4.parent();
assert!(r5.is_empty());
let r6 = r4.child(4);
assert_eq!(r6.len(), 2);
assert_eq!(*r6.value().unwrap().borrow(), 4);
assert_eq!(*r6.parent().value().unwrap().borrow(), 3);
}
正如您所看到的,大多数情况下,在 .unwrap()
之后调用 .borrow()
。
值得注意的是,最新一行无法编译:r6.parent()
返回一个临时值,我们尝试从中获取引用;编译器提示在删除临时文件后使用此引用,可能是作为 assert_eq
实现方式的详细信息。
| 74 | assert_eq!(*r6.parent().value().unwrap().borrow(), 3); | ^^^^^^^^^^^^-----------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | | | | | temporary value created here | temporary value dropped here while still borrowed | = note: values in a scope are dropped in the opposite order they are created = note: consider using a `let` binding to increase its lifetime = note: this error originates in a macro outside of the current crate
只需将 r6.parent()
替换为 r4
即可修复此问题。
关于tree - 如何在 Rust 中实现可变的仙人掌堆栈?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48293875/