2

I'm trying to implement a rather specific data structure in Rust, and I'm having trouble with the lifetimes and ownership of the data elements.

The structure has two parts: an R-tree and a Vec. Both need to store the same set of elements. The R-tree allows me to query the elements by location and the Vec maintains the order of the elements. Elements need to be able to be added and removed.

I'm not sure how to implement ownership here. If the Vec owns the elements, how would I borrow them to the R-tree only until they're removed, and not for the lifetime of the Vec? And vice versa.

The elements have interior mutable state, so I can't just clone them.

For example:

struct MyDataStructure {
    rtree: RTree,
    vec: Vec<Element>,
}

struct RTree { /* ... */ }

impl MyDataStructure {
    pub fn add_element(&mut self, element: Element) {
        // How do I add the element to both the RTree and the Vec?
    }

    pub fn remove_element(&mut self, element: &Element) {
        // And how do I remove it?
    }
}

impl RTree {
    pub fn add_element(&mut self, element: /* ??? */) {
    }

    pub fn remove_element(&mut self, element: /* ??? */) {
    }
}

Is there a standard pattern for solving this sort of situation?

James Westman
  • 2,680
  • 1
  • 15
  • 20
  • 2
    In contrast to most GC-based languages, Rust values aren't automatically placed behind a pointer. So a value can only live in one place, and it can't live in two locations at once. The standard pattern is to either put the value in one container and a reference (or more likely index, to avoid self-referential data) in the other. A more general alternative is to use the `Rc` smart pointer and put that in both places. If you know the object will be exactly in two places, you might want to look into [static `Rc`](https://github.com/matthieu-m/ghost-collections), but that's still work in progress. – user4815162342 May 25 '21 at 16:06
  • 1
    Also note, if you're still learning Rust, writing a data structure can be a daunting task. I advise you to take a look at [this tutorial](https://rust-unofficial.github.io/too-many-lists/) before proceeding; it might not help you directly, but it will give you a feeling for the interactions between Rust's ownership model and common data structures. – user4815162342 May 25 '21 at 16:10
  • 2
    To add to @user4815162342 comment: Here is an example of how you could use smart pointers to sync two variables / data structures, which comes from a question i asked a while ago. Check out the solution in the comments : https://stackoverflow.com/questions/66974494/how-can-i-modify-a-reference-to-a-field-within-the-same-struct-using-rc-and-refc –  May 25 '21 at 16:42
  • Thanks for the links! I'll have to benchmark it but I think `Rc` will work fine for me. – James Westman May 25 '21 at 18:20
  • Going off of what @user4815162342 said, you can use the `Vec` as the container of the elements and store the references (which will be indices into the `Vec`) in the `RTree`. Whenever you need to look up the actual value of an element in the `RTree`, simply look up that index in the `Vec`. The `Rc` approach, while more inefficient, will be easier to write and understand. – EvilTak May 25 '21 at 18:57

0 Answers0