rust 如何创建递归队列?

odopli94  于 2023-02-08  发布在  其他
关注(0)|答案(2)|浏览(126)

我尝试使用trait Element<T>作为队列不同节点的所有函数的容器,并使用两个名为Node<T>End的结构体来实现递归队列。
Node<T>结构体应该处理队列本身中的所有功能,而End结构体的目的是处理最后一个节点的情况。
我得到了下面的代码:

trait Element<T> {
    fn append_item(self, item: T) -> Node<T>;
}

struct Node<T> {
    data: T,
    successor: Box<dyn Element<T>>
}

impl<T> Element<T> for Node<T> {
    fn append_item(mut self, item: T) -> Node<T> {
        self.successor = Box::new(self.successor.append_item(item));
        self
    }
}

struct End;

impl<T> Element<T> for End {
    fn append_item(self, item: T) -> Node<T> {
        Node { data: item, successor: Box::new(self) }
    }
}

问题是,我得到了两个错误:
1.* 无法移动dyn Element<T>类型的值 *
1.* 参数类型T可能生存时间不够长 *
两者都在Node::append_item中的同一行上。
现在,我知道为什么会出现第一个错误了(因为dyn Element<T>的大小无法静态确定),但我不知道如何解决它,也不知道为什么会出现第二个错误。

wfveoks0

wfveoks01#

error[E0161]: cannot move a value of type `dyn Element<T>`
  --> src/lib.rs:12:35
   |
12 |         self.successor = Box::new(self.successor.append_item(item));
   |                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the size of `dyn Element<T>` cannot be statically determined

这里的问题是fn append_item(self, item: T)通过值接受self,但是在本例中self具有类型dyn Element<T>,该类型没有大小限制,因此永远不能通过值传递。
这里最简单的解决方案是只使用self: Box<Self>,这意味着这个方法是在Box<E>而不是directl上定义的。这对于像dyn Element<T>这样的trait对象来说非常好用,而且它不需要调整类型的大小。
(另外,在下面更新的代码中,为了方便起见,我将返回类型更改为Box<Node<T>>,但这本身并不是必需的,只是更方便一点。)

trait Element<T> {
    fn append_item(self: Box<Self>, item: T) -> Box<Node<T>>;
}

impl<T> Element<T> for Node<T> {
    fn append_item(mut self: Box<Self>, item: T) -> Box<Node<T>> {
        self.successor = self.successor.append_item(item);
        self
    }
}

impl<T> Element<T> for End {
    fn append_item(self: Box<Self>, item: T) -> Box<Node<T>> {
        Box::new(Node { data: item, successor: self })
    }
}

[一个月一次]

error[E0310]: the parameter type `T` may not live long enough
  --> src/lib.rs:12:26
   |
12 |         self.successor = Box::new(self.successor.append_item(item));
   |                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...so that the type `T` will meet its required lifetime bounds
   |

这里的问题是dyn Trait有一个隐式的生存期,实际上是dyn '_ + Trait,具体的生存期取决于上下文,你可以在Rust参考中读到确切的规则,但是如果包含的类型和trait本身都没有任何引用,那么生存期总是'static
Box<dyn Element<T>>就是这种情况,它实际上是Box<dyn 'static + Element<T>>。换句话说,Box包含的任何类型都必须具有'static生存期。要使Node<T>也是这种情况,还必须使T具有'static生存期。
不过,这很容易解决:只需按照编译器的建议添加一个T: 'static边界:

impl<T: 'static> Element<T> for Node<T> {
//    ^^^^^^^^^
    // ...
}

[ Playground link

8cdiaqws

8cdiaqws2#

Frxstrem already elaborated如何通过使用Box<Self>作为接收方来避免移动的需要如果您需要参数类型的更大灵活性(例如,能够保持引用以及拥有的类型),而不需要使用T: 'static,您可以引入一个命名的生存期:

trait Element<'a, T: 'a> {
    fn append_item(self: Box<Self>, item: T) -> Node<'a, T>;
}

struct Node<'a, T: 'a> {
    data: T,
    successor: Box<dyn Element<'a, T> + 'a>,
}

impl<'a, T: 'a> Element<'a, T> for Node<'a, T> {
    fn append_item(self: Box<Self>, new_data: T) -> Node<'a, T> {
        Node {
            successor: Box::new(self.successor.append_item(new_data)),
            ..*self
        }
    }
}

struct End;

impl<'a, T: 'a> Element<'a, T> for End {
    fn append_item(self: Box<Self>, data: T) -> Node<'a, T> {
        Node {
            data,
            successor: self,
        }
    }
}

相关问题