How can I create a structure with internal links?
I'm trying to create a graph with adjacency lists, but I can't figure out how to specify an appropriate lifetime for links in an adjacency list.
What I am trying to understand is the following:
struct Graph<T> {
nodes : Vec<T>,
adjacencies : Vec<Vec<&T>>
}
This won't work because there is no lifetime specifier for the reference type. I suppose I could use indexes for adjacency, but I am really interested in the internal reference problem, and this is just a means of expressing this problem.
As I see it, it should be possible to do this safely, since the nodes belong to the object. It should be allowed to save links to these nodes.
I'm right? How can this be done in rust? Or if I am wrong, what am I missing?
source to share
It is impossible to represent this concept in Rust using only references because of Rusts memory safety - such an object cannot be built without an existing one. As long as nodes
and adjacencies
are kept separate, its OK, but once you try to combine them within the same structure, it can't work that way.
Alternatives use reference counting ( Rc<T>
if immutable is OK or Rc<RefCell<T>>
with internal mutability) or using unsafe pointers ( *const T
or *mut T
).
source to share
I think there is a problem here. If we port this to C ++:
template <typename T>
struct Graph {
std::vector<T> nodes;
std::vector<std::vector<T*>> adjacencies;
};
where adjacencies
points to nodes
, then one can understand that there is a problem: an operation on nodes
that invalidates references (for example, redistribution) will leave dangling pointers to adjacencies
.
I see at least two ways to fix this:
- Use indexes in
adjacencies
as they are stable - Use a level of indirection in
nodes
to keep the memory pinned
In Rust, this gives:
struct Graph<T> {
nodes: Vec<T>,
adjacencies: Vec<Vec<uint>>,
};
struct Graph<T> {
nodes: Vec<Rc<RefCell<T>>>,
adjacencies: Vec<Vec<Rc<RefCell<T>>>>,
};
Note. RefCell
- resolve the mutation T
, even though it was an alias, by introducing a runtime check.
source to share