4 ms·
> One of the major reasons why is “needs a lot of unsafe to implement” is a historical criteria for “this belongs in the standard library” Custom data structur
by Const-me 7y ago
> One of the major reasons why is “needs a lot of unsafe to implement” is a historical criteria for “this belongs in the standard library”
Custom data structures often need a lot of unsafe code. Graphs, trees and linked lists are everywhere in system programming.
You can’t add everything to standard library, too many variations.
For trees, in C++ and/or C# I’ve used red-black, B-tree, unordered, and multi-dimensional ones like BSP, k-d, and PK. Graphs are all different, depending on what you need to store (just the topology, per-node data, per-edge data), and which operations need to work fast on them. Even linked lists are different, sometimes you want single link, other times you want them to be circular instead of linear.
And there’re other pointer-based structures useful for some applications, like skip lists and tries.
- steveklabnik 7y agoThanks to generics and the ease of publishing packages, those aren’t usually “custom” in Rust programs; you import a package that has them implemented for you. Just like you import ones from the standard library. Even then, that’s still a very small amount of the overall code in a given project.
- Const-me 7y ago> those aren’t usually “custom” in Rust programs On modern hardware, RAM latency is often the main reason why CPU-bound code is slow. The fix is often changing RAM layout, i.e. modifying data structures. And when the code uses SIMD to process the payload portion of these structures, alignment requirements cause them to become really custom pretty soon. > that’s still a very small amount of the overall code in a given project That’s not universal across all software. Lately, I’m working in the area of CAD/CAM/CAE. Before that I worked on videogames, HPC, multimedia. In many of these projects, data structures were not a small amount, even relatively speaking.