3 ms·

Linked lists have a really important property: each node can be owned by a different allocator. You can have a node which is stack memory, linking to a node whi

Linked lists have a really important property: each node can be owned by a different allocator. You can have a node which is stack memory, linking to a node which is heap allocated with libc malloc, linking to a node which is arena-allocated per frame of a game engine, linking to a node which is global static memory. And you can set this up in a maintainable, sensible way. Linked lists are incredibly useful when an object can exist in a predetermined set of lists, and allocation failure must not be possible when adding the object to a list.

abetlen 8y ago
Your comment kind of reminds me of this implementation http://www.rosettacode.org/wiki/Power_set#C http://www.rosettacode.org/wiki/Power_set#C for generating a power set in C. The code recursively calls a function that permutes through the members of the power set and creatively constructs linked lists pointing up the call stack.
duneroadrunner 8y ago
Yes, and in C++, linked lists can retain this property and be implemented in a memory safe way using non-owning reference-counting smart pointers[1]. Many defend the use of unsafe Rust in cases like these, in part by asserting that C++ would have the same (un)safety issue. I don't think that's right. A C++ implementation would not have to use (unsafe) raw pointers, or (expensive, intrusive) owning pointers from the standard library. I think C++ has the advantage in cases like these because of the aforementioned non-owning reference-counting smart pointers. I don't think the same type of pointer/reference can be implemented in Rust (as it would need a constructor), but it's not immediately obvious to me that such a reference type couldn't be added to the language as an intrinsic element (like Rc). I think such an element is dearly missing from the Rust language. I suspect that adding it would make the language safer and easier to use. [1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus#norad-pointers https://github.com/duneroadrunner/SaferCPlusPlus#norad-point...
- foota 8y ago
  I'm not a Rust expert, but aren't you describing https://doc.rust-lang.org/std/rc/struct.Rc.html https://doc.rust-lang.org/std/rc/struct.Rc.html?

abetlen 8y ago

Your comment kind of reminds me of this implementation http://www.rosettacode.org/wiki/Power_set#C http://www.rosettacode.org/wiki/Power_set#C for generating a power set in C. The code recursively calls a function that permutes through the members of the power set and creatively constructs linked lists pointing up the call stack.

duneroadrunner 8y ago

Yes, and in C++, linked lists can retain this property and be implemented in a memory safe way using non-owning reference-counting smart pointers[1]. Many defend the use of unsafe Rust in cases like these, in part by asserting that C++ would have the same (un)safety issue. I don't think that's right. A C++ implementation would not have to use (unsafe) raw pointers, or (expensive, intrusive) owning pointers from the standard library. I think C++ has the advantage in cases like these because of the aforementioned non-owning reference-counting smart pointers. I don't think the same type of pointer/reference can be implemented in Rust (as it would need a constructor), but it's not immediately obvious to me that such a reference type couldn't be added to the language as an intrinsic element (like Rc). I think such an element is dearly missing from the Rust language. I suspect that adding it would make the language safer and easier to use. [1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus#norad-pointers https://github.com/duneroadrunner/SaferCPlusPlus#norad-point...

foota 8y ago
I'm not a Rust expert, but aren't you describing https://doc.rust-lang.org/std/rc/struct.Rc.html https://doc.rust-lang.org/std/rc/struct.Rc.html?