Optional Recursive Types

Question

I have a structure with a parent property I want to add to a queue. The parent is the same type as itself, so I need to wrap it in a Box.

use std::collections::vec_deque::VecDeque;

struct GraphNode {
    value: u32,
    parent: Option<Box<&GraphNode>>,
}

fn main() {
    let mut queue: VecDeque<GraphNode> = VecDeque::new();

    let parent = GraphNode {
        value: 23,
        parent: Option::None,
    };

    let second = GraphNode { value: 42, parent };

    let third = GraphNode {
        value: 19,
        parent: Option::Some(Box::from(&parent)),
    };

    queue.push_front(parent);
    queue.push_front(second);
    queue.push_front(third);
}

Playground

error[E0106]: missing lifetime specifier
 --> src/main.rs:5:24
  |
5 |     parent: Option<Box<&GraphNode>>,
  |                        ^ expected lifetime paramete

The parent can be null, so I get that it needs to be Box<Option<&GraphNode>>, but I get the error expected lifetime parameter, however what's in the docs isn't really making sense to me.

There's also the issue that when I create a Box, to save to the parent, the value is moved. I don't want to move the value, I just want to save a reference in the box.

score 2 · Answer 1 · edited Feb 24 '19 at 18:36

I think you are looking for std::rc::Rc, not Box.

use std::collections::vec_deque::VecDeque;
use std::rc::Rc;

struct GraphNode {
    value: u32,
    parent: Option<Rc<GraphNode>>,
}

fn main() {
    let mut queue: VecDeque<Rc<GraphNode>> = VecDeque::new();

    let parent = Rc::new(GraphNode {
        value: 23,
        parent: None,
    });

    let second = Rc::new(GraphNode {
        value: 42,
        parent: None,
    });

    let third = Rc::new(GraphNode {
        value: 19,
        parent: Some(parent.clone()), // Clones the reference, still point to the same thing.
    });

    queue.push_front(parent);
    queue.push_front(second);
    queue.push_front(third);
}

Playground

Rc (reference counted), is a way to have multiple "owners" to the same object. When cloning, you are just cloning the reference, so changes made to either one will affect the other.

The lifetime problems you encountered is because you are storing a direct reference (don't actually know what it's suppose to be called) made with &.

If you want to know more about lifetimes, here's the entry from the book.

Optional Recursive Types

1 Answers1