4 ms·

Why would you write your own basic data structures when the standard library provides them for you? I haven't written an implementation of a doubly-linked list

Why would you write your own basic data structures when the standard library provides them for you? I haven't written an implementation of a doubly-linked list by hand in a very long time. If your point was about explicit ownership being a little more tricky with self-referential structures, that's true, though the existence of std::collections::LinkedList shows that it's entirely possible to manage these structures and at least you still get the benefits of explicit ownership for the structure and the data within it.

amelius 6y ago
> Why would you write your own basic data structures when the standard library provides them for you? I think the problem with this view is that Rust is not being used as a true programming language (like for implementing algorithms), but more as a "glue language". If all the interesting stuff has to be done in libraries in "unsafe" mode, and all the uninteresting stuff (gluing) is done with borrow checking, then Rust is more a glue language. Which is fine. But don't call it a general purpose programming language.
- Silhouette 6y ago
  I respectfully disagree. Using tools provided by the standard library is common practice in any general purpose programming language. It just means that the algorithms you're implementing can concentrate on the novel aspects that provide additional value and not get bogged down with reinventing wheels for the basic implementation details. Also, you seem to be suggesting that it's necessary to use unsafe code to implement these data structures in Rust. For something like the doubly-linked lists that were mentioned in an earlier comment, it usually suffices to use tools like Option and Rc for the links and to encapsulate the logic that manages those links inside functions like push_back and pop_back that you are surely defining to mutate your data structure anyway. Is there something specific you have in mind where this kind of strategy doesn't work and unsafe code is the only solution?
- steveklabnik 6y ago
  Someone above suggests boot::intrusive. Do you also think that means C++ is a "glue language"?
- xigoi 6y ago
  So any language that doesn't force you to constantly reinvent the wheel is a “glue language”?
j16sdiz 6y ago
I write my own basic structure when I need specific implementation for performance. Most of time its about memory layout or caching a specific internal pointer for some hot code.
- Silhouette 6y ago
  Sure, but unless the high performance code you work with is very different in nature to the high performance code I've worked with, you probably have a small set of carefully implemented and probably very well optimised structures in your toolbox and write everything else using them. You do need to deal with the explicit ownership semantics in Rust when you're first implementing those tools, but that's a probably minor inconvenience up front and afterwards things mostly just work like the equivalent data structures in any other programming language, but with the added safety guarantees from the ownership system and borrow checker.
bluecalm 6y ago
Double linked list is just an example. There are other both more useful and harder to generalize structures like various kinds of trees for example. Anyway, if your question is why implement your own data structures then it's very likely C/C++ isn't a proper tool for your job anyway.
- Silhouette 6y ago
  There are other both more useful and harder to generalize structures like various kinds of trees for example. Trees are usually easy because each node has a single parent all the way up to the root and ownership can follow the same hierarchy. More general graphs are a little more tricky, but the same techniques that you can use to implement a specific case like a DLL generalise. For example, in Rust, you can combine Option and Rc to handle, respectively, the intermediate states while the structure is being manipulated and the shared ownership semantics.

amelius 6y ago

> Why would you write your own basic data structures when the standard library provides them for you? I think the problem with this view is that Rust is not being used as a true programming language (like for implementing algorithms), but more as a "glue language". If all the interesting stuff has to be done in libraries in "unsafe" mode, and all the uninteresting stuff (gluing) is done with borrow checking, then Rust is more a glue language. Which is fine. But don't call it a general purpose programming language.

Silhouette 6y ago
I respectfully disagree. Using tools provided by the standard library is common practice in any general purpose programming language. It just means that the algorithms you're implementing can concentrate on the novel aspects that provide additional value and not get bogged down with reinventing wheels for the basic implementation details. Also, you seem to be suggesting that it's necessary to use unsafe code to implement these data structures in Rust. For something like the doubly-linked lists that were mentioned in an earlier comment, it usually suffices to use tools like Option and Rc for the links and to encapsulate the logic that manages those links inside functions like push_back and pop_back that you are surely defining to mutate your data structure anyway. Is there something specific you have in mind where this kind of strategy doesn't work and unsafe code is the only solution?
steveklabnik 6y ago
Someone above suggests boot::intrusive. Do you also think that means C++ is a "glue language"?
xigoi 6y ago
So any language that doesn't force you to constantly reinvent the wheel is a “glue language”?

j16sdiz 6y ago

I write my own basic structure when I need specific implementation for performance. Most of time its about memory layout or caching a specific internal pointer for some hot code.

Silhouette 6y ago
Sure, but unless the high performance code you work with is very different in nature to the high performance code I've worked with, you probably have a small set of carefully implemented and probably very well optimised structures in your toolbox and write everything else using them. You do need to deal with the explicit ownership semantics in Rust when you're first implementing those tools, but that's a probably minor inconvenience up front and afterwards things mostly just work like the equivalent data structures in any other programming language, but with the added safety guarantees from the ownership system and borrow checker.

bluecalm 6y ago

Double linked list is just an example. There are other both more useful and harder to generalize structures like various kinds of trees for example. Anyway, if your question is why implement your own data structures then it's very likely C/C++ isn't a proper tool for your job anyway.

Silhouette 6y ago
There are other both more useful and harder to generalize structures like various kinds of trees for example. Trees are usually easy because each node has a single parent all the way up to the root and ownership can follow the same hierarchy. More general graphs are a little more tricky, but the same techniques that you can use to implement a specific case like a DLL generalise. For example, in Rust, you can combine Option and Rc to handle, respectively, the intermediate states while the structure is being manipulated and the shared ownership semantics.