如何在结构体中存储递归引用

Question

让我们假设下面的结构

struct Item<'a> {
    items: Vec<&'a Item<'a>>
}

假设下面的变量包含许多Item对象，items字段为空。

let mut items: Vec<Item<'a>> = get_items();

让我们假设我的任务是在每个Item的items字段中添加对items向量中所有其他Item对象的引用。

我当前的实现是

struct Item<'a> {
    items: Vec<&'a Item<'a>>,
}
impl<'a> Item<'a> {
    fn new() -> Item<'a> {
        Item { items: vec![] }
    }   
}
fn main() {
    let mut items = vec![Item::new(), Item::new()];
    while let Some(item) = items.pop() {
        for another_item in &mut items {
            item.items.push(another_item); 
        }   
        items.push(item);
    }   
}`

它失败了，因为我执行了item.items.push(another_item);

Answer 1

你想做的是不合理的。如果不知道你的用例，你的问题就没有好的解决方案。

有几个与可变性有关的错误。这些问题解决后，您的代码变成:

struct Item<'a> {
    items: Vec<&'a Item<'a>>,
}
impl<'a> Item<'a> {
    fn new() -> Item<'a> {
        Item { items: vec![] }
    }   
}
fn main() {
    let mut items = vec![Item::new(), Item::new()];
    while let Some(mut item) = items.pop() {
        for another_item in items {
            item.items.push(&another_item); 
        }   
        items.push(item);
    }   
}

编译器现在抱怨another_item的生存期:

错误:another_item不存在足够长的时间

for循环拥有another_item，它不能把所有权交还给引用的Vec。

无论你做什么，你都无法回避这个基本问题。这些规则背后的一个原因是引用实际上就是指针。当您将元素移入和移出items时，每个item将改变其位置，使先前创建的指向它的指针无效。(这不是Python，它有神奇的垃圾收集引用。)当然，Rust的规则阻止了这种情况的发生。

Answer 2

我以这段代码结束

use std::rc::Rc;
use std::cell::RefCell;
struct Item {
    items: Vec<Rc<RefCell<Item>>>,
}
fn main() {
    let items = vec![Item { items: Vec::new() }, Item { items: Vec::new() }];
    let iter = items.into_iter();
    let items = iter.map(|item| Rc::new(RefCell::new(item)));
    let items = items.collect::<Vec<_>>();
    for item_index in 0..items.len() {
        let item = items[item_index].clone();
        let mut item = item.borrow_mut();
        for another_item_index in 0..items.len() {
            if another_item_index == item_index {
                continue;
            }
            let another_item = items[another_item_index].clone();
            (*item).items.push(another_item);
        }
    }
}