Well, if you want to write a tree using indices in a local array instead of pointers for better locality and memory footprint (which is ideal for many situations), you run into the difference between language pointers and computer science pointers. That's not even something that Rust will be smart enough to help you do properly.
In fact (unless something has changed dramatically without my getting the memo), that's how you would write many data structures in Rust---either for better memory behavior or you have cycles and Rc won't cut it. You have to use a vector of nodes and indices as pointers; if you try using references, the borrow checker comes and kicks sand in your face.
It's doable to keep using pointers instead of indices- they just all have the lifetime of the vector and you can freely follow them around.
This does prevent resizing the vector, but you can get around that by using a different arena that allocates in chunks rather than reallocating (and thus doesn't require a unique reference for .insert).
Rust can totally help you do that properly. You can wrap the indices in a struct parameterized by a lifetime and regain all the same tools you would have with language pointers.
reply