C++ programmers usually prefer contiguous data layout as well. I mean std::vector is just a contiguous array that dynamically reallocates and copies/move-constructs everything as needed.
But many interesting data structures are hard to write in a memory-efficient manner without resorting to non-contiguous nodes. Even a hashtable often will use linked lists within each bucket for collision resolution. You can argue that an open-addressing scheme is more cache-friendly, but it also has downsides, i.e. performance degrades faster as the load factor gets higher.
Many other interesting data structures, especially some lock-free structures, are simply impractical to implement as single contiguous arrays.
Of course, any node-based structure can make use of a memory pool that allocates blocks from one or more larger contiguous buffers, but there will still be pointers interleaved throughout the structure.
All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures, and saying "don't ever write node-based data structures" is just pointless. Yes, Rust has some downsides and tradeoffs. Is it so bad to just say that out loud?
> All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures,
Yup! Rust does not fix all your problems, sadly. Maybe some of them. :-)
If you're working with graph-like structures in Rust, then you have two choices:
1. You can work with pointers using 'unsafe' blocks, and then wrap everything inside a nice, safe API. This is a good tradeoff if your data structure is only a tiny portion of your code, or if it's reusable. (Most of the data structures in Rust's 'std' crate are written like this.)
2. You can work with indices instead of pointers. This is the approach taken by petgraph (https://docs.rs/petgraph/0.4.3/petgraph/), which is currently one of the best graph libraries for Rust.
Not all Rust code needs to be safe. It's OK to write "unsafe" code and put it behind a "safe" API. If I can eliminate 98% of the opportunities for pointer bugs, I'm happy to eyeball the remaining 2% manually.
> All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures
Debatable. It certainly does for the consumers of these structures, and data structures are consumed a lot more often than they are rewritten.
> Yes, Rust has some downsides and tradeoffs. Is it so bad to just say that out loud?
Of course not. But that doesn't mean you shouldn't expect some pushback if you're incorrectly describing those tradeoffs.
Is it really so bad to say "at the end of the day, the difficulty of complex graphs in safe Rust is symptomatic not of a flaw in Rust but of how hard it is to build these things without memory errors even in C or C++" out loud?
How often do you really need those interesting structures(and the memory fragmentation that comes with them)? I've seen countless times where a developer reached for std::hash_map/linked_list when there will never be more than 10 values in their dataset. In that case an array would be at least as fast and much easier on your data layout.
Also if you're trying to implement lockfree data structures then safe/unsafe pointer access are going to be the least of your worries :).
When you need them you really need them. A Patricia Trie for example, which includes back pointers to ancestor nodes, is simply an ideal structure for prefix search.
How about a rephrasing: how many times do you really need to write these?
Rust will make it tricky to implement these, but then you can use the datastructure safely as much as you want. It's a "write once use everywhere" thing.
But many interesting data structures are hard to write in a memory-efficient manner without resorting to non-contiguous nodes. Even a hashtable often will use linked lists within each bucket for collision resolution. You can argue that an open-addressing scheme is more cache-friendly, but it also has downsides, i.e. performance degrades faster as the load factor gets higher.
Many other interesting data structures, especially some lock-free structures, are simply impractical to implement as single contiguous arrays.
Of course, any node-based structure can make use of a memory pool that allocates blocks from one or more larger contiguous buffers, but there will still be pointers interleaved throughout the structure.
All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures, and saying "don't ever write node-based data structures" is just pointless. Yes, Rust has some downsides and tradeoffs. Is it so bad to just say that out loud?