这是对此处所提问题的后续:Possible to implement dynamically-typed linked list in safe Rust?
我使用std::any::Any
trait成功地实现了一个动态类型LinkedList。
然而,我想挑战自己,尝试用另一种方式实现它,例如使用泛型类型- Node,其中T可以是任何类型,u32,u64,String,...
示例
Node<String> -> Node<u32> -> Node<u64> -> Node<String> -> ...
我的方法是使用一个名为Next
的特征来给予Node<T>
“下一个”的能力。Node<T>
看起来像这样。
struct Node<T> {
data: T,
next: Option<Rc<RefCell<dyn Next>>>,
}
trait Next
看起来是这样的。
pub trait Next {
fn borrow_next(&self) -> Option<Ref<dyn Next>>;
fn set_next(&mut self, next: Rc<RefCell<dyn Next>>);
}
这些是任何节点的Next的实现。
impl<T> Next for Node<T> {
fn set_next(&mut self, next: Rc<RefCell<dyn Next>>) {
self.next = Some(next);
}
fn borrow_next(&self) -> Option<Ref<dyn Next>> {
match &self.next {
None => None,
Some(stmt) => Some(stmt.borrow()),
}
}
}
下面是实际结构体Node<T>
的实现。
impl<T> Node<T> {
pub fn new<P>(data: P) -> Node<P> {
Node::<P> { data, next: None }
}
pub fn new_wrapped<P>(data: P) -> Rc<RefCell<Node<P>>> {
Rc::new(RefCell::new(Node::<P>::new(data)))
}
pub fn into_wrapped(self) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(self))
}
pub fn borrow_data(&self) -> &T {
&self.data
}
pub fn set_data(&mut self, data: T) {
self.data = data;
}
}
最后,结构体DynLinkedList
的方法声明及其实现,包含两个字段head
和tail
,如下所示。
struct DynLinkedList {
head: Option<Rc<RefCell<dyn Next>>>,
tail: Option<Rc<RefCell<dyn Next>>>,
}
impl DynLinkedList {
pub fn new_empty() -> Self {
Self {
head: None,
tail: None,
}
}
pub fn new_with_node(node: Rc<RefCell<dyn Next>>) -> Self {
Self {
head: Some(node.clone()),
tail: Some(node),
}
}
pub fn append(&mut self, node: Rc<RefCell<dyn Next>>) {
self.tail.take().map_or_else(
|| self.head = Some(node.clone()),
|old_tail| old_tail.borrow_mut().set_next(node.clone()),
);
self.tail = Some(node);
}
}
问题来了:
我无法访问Node<T>
的data
字段,因为编译器将其视为trait对象dyn Next
。
例如,此测试将不起作用:
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_dynll_new_with_node() {
let node = Node::<u32>::new(77_u32);
let dynll = DynLinkedList::new_with_node(node.into_wrapped());
assert_eq!(&dynll.head.unwrap().borrow().borrow_data(), &77);
assert_eq!(&dynll.tail.unwrap().borrow().borrow_data(), &77)
}
}
编译器错误为:
error[E0599]: no method named `borrow_data` found for struct `Ref<'_, (dyn Next + 'static)>` in the current scope
--> src/dyn_ll_idea_five.rs:125:47
|
125 | assert_eq!(&*dynll.head.unwrap().borrow().borrow_data(), &77);
| ^^^^^^^^^^^ method not found in `Ref<'_, (dyn Next + 'static)>`
但是,当.unwrap()
之后的.borrow()
返回时,它应该返回一个Node类型的对象,该对象将具有方法.borrow_data()
,我如何让Rust知道这是一种情况呢?谢谢。
我实际上希望能够做到这一点:
let mut list = DynLinkedList::new();
list.push_front("hello".to_string());
list.push_back("world".to_string());
list.push_front(123);
list.push_back(456);
assert_eq!(list.pop_front(), Some("hello".to_string()));
assert_eq!(list.pop_back(), Some("world".to_string()));
assert_eq!(list.pop_front(), Some(123));
assert_eq!(list.pop_back(), Some(456));
1条答案
按热度按时间h7wcgrx31#
在
trait Next
的定义中,没有任何地方提到Node
类型的对象,因此,编译器怎么知道你可以在它上面调用borrow_data
呢?这就是你通过Any
trait做向下转换的地方。更重要的是,编译器还想知道我们讨论的是哪种类型的节点。
Node<i32>
或Node<String>
还是什么?这是完全不可能的,因为列表是动态的,因此节点中包含的任何类型也是动态的。让我们以您为例:
如果这就是你的列表,那么,使用非常粗糙丑陋的伪代码,下面这个怎么样:
你看到这里的问题了吗?编译器在编译时怎么知道列表中的第三项是
u64
类型的?这不是泛型以你想要的方式工作的情况。