Implement m:n relationship between structs

Hello,
I’m new to Rust and I’d like to ask for advice on how to implement the following situation properly: Let say I have some structs A and B. Instances of A need to reference some instances of B. Some instances of B might be referenced by multiple A instances. Furthermore, the B instances need to know in which A instances they are referenced in. So it would be some kind of m:n relationship. I’ve tried to implement it the way I would do it in other languages, so something along the lines of:
struct A<'a> { b_elements: Vec<&'a B<'a>> }
struct B<'b> { a_elements: Vec<&'b A<'b>> }

However, I’m not sure if this makes sense as I don’t know how Rust could tell when an instance of A or B is no longer referenced by any instance of the other and thus can be freed. Do I need to use an Rc or something else for this? As I’m still learning, I tried to implement it as above but quickly ran into issues when e.g. trying to implement a function that would add an instance of B to some instance of A as this:

impl<'c> A<'c> {
    fn add_b(&'c mut self, b: &'c mut B<'c>) {
        self.b_elements.push(b);
        b.a_elements.push(self);
    }
}

Yes, I think you should use Rc or Arc in this case. The corresponding Weak pointers will work well for this part:

Example type definitions based on your description:

use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct A {
    children: Vec<Rc<RefCell<B>>>,
}

struct B {
    parents: Vec<Weak<A>>,
}

The RefCell will be needed to mutate the Bs when you access them through an A (e.g. to push a new Weak onto the parents field).

For completeness, I should also mention that you could do this by keeping all the As in one big Vec, all the Bs in another Vec, and using indices instead of pointers to describe the relationships between the two. If you don't like messing around with RefCell then you might prefer that approach.

1 Like

I like the parent/child constructs.

1 Like

@AlexLogical since your model is essentially a bipartite graph, you might also be able to implement it using a graph-processing library like petgraph.

1 Like