If you want something where the Nodes have references (&, &mut) into a Vec, and the either
- the
Nodes themselves are in the Vec, or
- the
Vec and the Nodes are in the same containing data structure
then you're talking about a self-referencial struct, which isn't going to be useful.
For example.
#[derive(Default, Copy, Clone)]
struct Node<'a> {
// `&'a Node<'a>` is already a red flag. It's shared-borrowed
// forever so you can never get a `&mut Node<'_>`.
left: Option<&'a Node<'a>>,
right: Option<&'a Node<'a>>,
}
struct Tree<'a> {
nodes: Vec<Node<'a>>,
}
fn example() {
// This works on its own, but...
let mut nodes = vec![Node::default(); 2];
let (root, child) = nodes.split_at_mut(1);
root[0].left = Some(&child[0]);
// ...now the `Vec` is exclusively borrowed forever
let _ = &nodes[0];
// error[E0502]: cannot borrow `nodes` as immutable
// because it is also borrowed as mutable
}
You can work around some issues by keeping the data structures separate, but it still has downsides -- your owning data structure would still be borrowed for as long as the tree exists, which also pins it to the stack. (You generally can't move borrowed things, so if you have a reference-based data structure, all work has to happen before the owning structure gets destructed or moved -- including returning it from a function.)
Using references for this use case in general has a lot of downsides because the language has strong invariants they must uphold and really wants to check all those invariants at compile time.
So perhaps what you want is shared ownership in place of references, and interior mutability to so you can still mutate things. (Shared ownership types can only offer & access directly, or they would violate &muts exclusivity requirements.) Two common patterns are Rc<RefCell<_>> for single-threaded and Arc<Mutex<_>> for multi-threaded.
Example.
Or just indices...
#[derive(Default, Clone, Debug, Copy)]
struct Node {
left: Option<usize>,
right: Option<usize>,
}
fn example() {
let nodes = vec![Node { left: Some(1), right: None }, Node::default()];
}
Or atomic indices and perhaps interior mutability for actual data...
use atomic::Ordering::Release;
use std::sync::atomic::AtomicUsize;
// n.b. 0 represents `None` (there is sadly no `NonZeroAtomicUsize`)
#[derive(Default, Debug)]
struct Node {
left: AtomicUsize,
right: AtomicUsize,
}
fn main() {
let nodes = vec![Node::default(), Node::default()];
nodes[0].left.store(1, Release);
let _ = &nodes;
}
Or maybe you have a completely owned tree and only the data payload lives in a Vec somewhere, and you use indices for that.
Or perhaps something else, depending on your use case.
You may want to read this book about implementing linked lists in Rust. There's a number of overlapping considerations with implementing a tree.
Sorry there's no good simple answer (or maybe I'm just bad at answering very high-level design questions).
