A couple years ago I implemented a btree (technically order statistic tree) in a couple thousand lines of unsafe rust for a project. I wrote it more or less how I'd do it in C. Each internal node and leaf node was a separate heap allocation and internal nodes had an array of child pointers. It was surprisingly hard to program up. And complicated!
In my opinion, unsafe rust code is worse to use than C because rust is missing the arrow operator. And rust still requires strict aliasing to be followed even in unsafe code. This makes complex unsafe code very hard to implement correctly. Like, it’s easy for something to look right and work correctly but for MIR to still find subtle issues.
Eventually I rewrote my btree on top of Vecs. My node & leaf pointers are now array indices. The result? There is no longer any unsafe code. The code has become significantly simpler and it now runs ~10% faster than it did before, which is shocking to me. I guess bounds checks are cheaper than memory fragmentation on modern computers.
I have so many thoughts having done that. First, I think this is actually the right way to write rust. Yes, manually keeping track of which array slots are in use is inconvenient. But unsafe & pointers are also quite inconvenient in rust. Programming like this makes use after free bugs possible to write. But it’s still memory safe by rust’s definition. It’s impossible to get arbitrary heap corruption because there are no raw pointers. And the indexes are bounds checked.
I also don’t think the resulting code is any worse than the equivalent C++. Everyone talks about memory safety but IMO rust’s best features are enums, traits, cargo, match expressions and so on. Even when you do a run around the borrow checker, it’s these features which make me keep coming back to rust.
I agree better guidance would be nice, but so many words have been spilled on rust already. Would you find content talking about subtle stuff like this? Sometimes the only way to learn is by trying stuff out.