在Rust中实现动态类型的LinkedList

vwkv1x7d  于 2023-01-09  发布在  其他
关注(0)|答案(1)|浏览(125)

这是对此处所提问题的后续: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的方法声明及其实现,包含两个字段headtail,如下所示。

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));
h7wcgrx3

h7wcgrx31#

trait Next的定义中,没有任何地方提到Node类型的对象,因此,编译器怎么知道你可以在它上面调用borrow_data呢?这就是你通过Any trait做向下转换的地方。
更重要的是,编译器还想知道我们讨论的是哪种类型的节点。Node<i32>Node<String>还是什么?这是完全不可能的,因为列表是动态的,因此节点中包含的任何类型也是动态的。
让我们以您为例:

Node<String> -> Node<u32> -> Node<u64> -> Node<String> -> ...

如果这就是你的列表,那么,使用非常粗糙丑陋的伪代码,下面这个怎么样:

let x: String = my_list.head.borrow_data();
let y: u32 = my_list.head.next.borrow_data();
let z: u64 = my_list.head.next.next.borrow_data();

你看到这里的问题了吗?编译器在编译时怎么知道列表中的第三项是u64类型的?这不是泛型以你想要的方式工作的情况。

相关问题