2

我经常想在 Rust 中定义递归数据类型。我们需要某种程度的间接性来避免具有无限大小的类型。经典的解决方案是使用Box（游乐场）：

enum IntList {
    Empty,
    Cons(i32, Box<IntList>),
}

我遇到的问题是它要求列表拥有自己的尾巴。这意味着您不能在共享尾部的两个列表之间共享空间，因为两者都想拥有它。您可以使用借来的参考（playground）：

enum IntList<'a> {
    Empty,
    Cons(i32, &'a IntList<'a>),
}

但是很难创建一个列表，因为它不允许拥有自己的尾巴。

有没有办法让列表不在乎它是否拥有尾巴？这样我就可以让一个列表拥有尾部，而另一个列表引用同一个列表作为它的尾部。

我的尝试

我的第一个想法是Cow用于此目的，但我无法让它发挥作用。这就是我尝试过的（游乐场）：

#[derive(Clone)]
enum IntList<'a> {
    Empty,
    Cons(i32, Cow<'a, IntList<'a>),
}

但它失败并出现错误

error[E0275]: overflow evaluating the requirement `IntList<'a>: std::marker::Sized`
 --> src/main.rs:8:13
  |
8 |   Cons(i32, Cow<'a, IntList<'a>>),
  |             ^^^^^^^^^^^^^^^^^^^^
  |
  = note: required because of the requirements on the impl of `std::borrow::ToOwned` for `IntList<'a>`
  = note: required because it appears within the type `std::borrow::Cow<'a, IntList<'a>>`
  = note: no field of an enum variant may have a dynamically sized type
4

2 回答 2

2

我制作了一种类似于Cow我所说的数据类型Cowish。如果那里已经有类似的东西，请告诉我！

pub enum Cowish<'a, T, O>
where
    T: 'a,
{
    Borrowed(&'a T),
    Owned(O),
}

impl<'a, T, O> Borrow<T> for Cowish<'a, T, O>
where
    T: 'a,
    O: Borrow<T>,
{
    fn borrow(&self) -> &T {
        match self {
            Borrowed(b) => b,
            Owned(o) => o.borrow(),
        }
    }
}

impl<'a, T, O> Cowish<'a, T, O>
where
    T: ToOwned<Owned=O> + 'a,
    O: Borrow<T>,
{
    pub fn into_owned(self) -> O {
        match self {
            Borrowed(b) => b.to_owned(),
            Owned(o) => o,
        }
    }
}

使用它，我可以做我想做的事：

enum IntList<'a> {
    Empty,
    Cons(i32, Cowish<'a, IntList<'a>, Box<IntList<'a>>>),
}

一个更大的例子可以在这里找到。

于 2018-08-03T20:05:46.803 回答
0

这可能太旧了，但只是为了记录，如果你想制作一个可以使用的链表std::rc::Rc。就像Box，但您可以对单个对象有多个引用。唯一需要注意的是，一旦列表包含在 Rc 中，您就不能改变它。这是rust book中的一个例子：

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
use std::rc::Rc;

fn main() {
    let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil))))); // [10, 5]
    let b = Cons(3, Rc::clone(&a)); // [10, 5, 3]
    let c = Cons(4, Rc::clone(&a)); // [10, 5, 4]
}
于 2020-12-13T17:35:57.717 回答