When and how to use a vector of references

Question

This code correctly compiles. It has a few unused code warnings, but that's okay for now.

use std::collections::BTreeMap;

enum Object<'a> {
    Str(String),
    Int(i32),
    Float(f32),
    Vector(Vec<&'a Object<'a>>),
    Prim(fn(State) -> State)
}

struct State<'a> {
    named: BTreeMap<String, &'a Object<'a>>,
    stack: Vec<Object<'a>>

}

impl<'a> State<'a> {
    fn push_int(&mut self, x: i32) {
        self.stack.push(Object::Int(x));
    }
}


fn main() {
    println!("Hello, world!");
    let obj = Object::Str("this is a test".to_string());
}

The important part of this code is push_int and stack: Vec<Object<'a>>.

I'm sort of trying to make a stack-based VM. I want to pass the state to functions, which can take stuff off the stack, manipulate the stuff, and then put some stuff back on the stack; the named field is going to hold named objects.

I have a hunch that it would be better to have the stack represented as a Vec<&'a Object<'a>> instead. The way I have it now, I fear I'm committing some inefficiency error. Is my hunch correct?

The second part of the problem is that I don't know how to get the vector of references version to work. Creating new value with the right lifetimes to push onto the stack is not working for me.

I'm a bit vague about this issue, so if I've been unclear, ask me questions to clear stuff up.

You'd want `Vec>>` for an owned pointer. You do have inefficiency, in that `Object::Int` takes as much space as `Object::String`, but boxing it is just going to make it worse (even if boxing allowed more compact representations). I would just change `Str(String)` to `Str(Box)` and `Vector>` to `Vector>>` and leave it at that, since that removes the only things keeping `Object` *too* large. It's still possible the extra indirection is worse than the inefficiency for smaller (probably more common) values, though. — Veedrac, Nov 09 '15 at 02:51
what do you mean with "inefficiency"? Are you asking how to save memory or how to be more performant? Also I think this question belongs on http://codereview.stackexchange.com/ — oli_obk, Nov 09 '15 at 09:08
@ker I think I meant both; I was vague because I didn't know enough to be more specific. Yes, it could have gone to codereview; I wasn't sure. — phil, Nov 10 '15 at 20:08

score 14 · Accepted Answer · edited May 23 '17 at 12:09

The reason you could not get it to work is that structs cannot have fields that refer to other fields. (See supporting links at the bottom.)

What you can do, is put all the Objects into your Vec, and have the HashMap contain the indices of the named elements it references.

struct State {
    named: BTreeMap<String, usize>,
    stack: Vec<Object>
}

I'd also remove all lifetimes from your example, as this can be done completely with owned objects.

enum Object {
    Str(String),
    Int(i32),
    Float(f32),
    Vector(Vec<Object>),
    Prim(fn(State) -> State)
}

You can try out a working implementation in the Playground

Supporting links:

A style point regarding "(yes, every word is a different link)". A bulleted list of links to other Stack Overflow questions is clearer to browse, because SO will automatically look up the titles and show them. — David J., Oct 05 '16 at 18:58

When and how to use a vector of references

1 Answers1