I want to create multiple objects link them together and return one from a function, how can I accomplish this in Rust?

This is a nice reference for what to do when you are returning one reference from a function to appease the borrow checker: https://bryce.fisher-fleig.org/strategies-for-returning-references-in-rust/

However, I would like to find a generic solution for creating a bunch of objects say within a loop so you can't know at compile time how many there will be. I then want to link them together by reference and return them.

For example, I create a bunch of linked list nodes, link them together then want to return the head. I'm guessing boxing is the only solution that really works?

You probably want Rc or Arc for this. Thet act like references in a garbage-collected language: You can keep the reference as long as you want, and the target will remain as long as any Rc exists that targets it.

Alternatively, you can return something like a Vec or a HashMap that contains all of the objects. If you do this, they’ll all need to refer to each other by key instead of a reference type.

1 Like

Rc and Arc are susceptible to reference loops leading to them not being removed and leaking memory right?

Other idea is quite interesting.. requires manually adding and removing the objects to the Vec and essentially tracking ownership yourself to prevent memory leaks, correct? Might work nicely for what I'm doing though. Referring to each other by key would be tricky in Vec to do at high performance if you are adding and removing objects.

That’s correct. You can break the cycles with Weak, but determining which references should be Rc and which should be Weak isn’t always an easy problem.

You could use something like slab to help with this; it keeps all of the keys unchanged, and reuses the slots of deleted items for future inserts.

1 Like

Slab does indeed look very interesting, thanks!

Seems a little unfair to call Rust memory safe when done manual memory management is needed in cases like this :frowning:

While undesirable, memory leaks don’t cause the kind of heisenbugs you get from use-after-free, thread races, or buffer overruns. It’s these latter problems that Rust tries to make impossible in safe code.

That's not really true. A linked list is all about shared mutation, which goes directly against the premise of the borrow checker and so there is a bit of extra friction.

It definitely is memory safe, and that safety is a lot more ergonomic than similar languages like C++, you just happened to hit a bad edge case.

The canonical example of implementing a linked list, and a really good resource to help understand what problems we are trying to solve, is Learn Rust With Entirely Too Many Linked Lists

3 Likes

That's fair. Upon further reflection, I suppose garbage collected languages have these too. Have to explicitly delete say a node in a linked list or else it'll 'leak' memory too.