> and, most importantly, safe

https://github.com/TheAlgorithms/Rust/search?q=unsafe

Almost there...

Depends whether by "safe" you mean "not using unsafe" or "the implementation is safe". Many core data structures in Rust use unsafe, but I think most people would consider them safe implementations.

In the same way my c++ code is safe, yeah, the 'unsafe' code in this random-looking repo very well may be safe.

Unsafe rust has numerous safety checks above and beyond C++...

I’m very surprised that the rbtree needs to be unsafe at all.

It feels like a very early attempt. Skip the parent pointers and use Option rather than raw null pointers. Should get rid of the unsafe.

Linked list strikes again.

Is there not a way to do safe linked lists in Rust?

You can do a singly linked list just fine.

But with a doubly linked list, who owns the memory to each node?

In reality, you can do a doubly linked list with something like `RefCell`.

See the famous blog post on linked lists in rust here: https://rust-unofficial.github.io/too-many-lists/fourth-buil...

The borrow checker makes a doublily linked list difficult, from my understanding.

They're almost always a bad data structure to pick though, as the speed difference between being able to iterate a contiguous list, and even completely rebuild it, vs having to follow arbitrary pointers mean that the 'complexity' improvements of a linked list often become irrelevant.

------ Open Question)

I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level.

Is there any credence to that, and if so, is it happenstance, or is there some more fundamental reason?

> I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level.

No, I think you are reading too much into it. One is free to Box-allocate/pointer-chase on every line in Rust without any trouble. Sure, as other low level languages, rust also prefers/makes stack-allocation more ergonomic/the default, which is a quite cache-friendly way of operation but not even the stack is “native” in and of itself - it is just a frequently and extensively used part of the “heap”.

Because of cache locality issues, linked lists are a bad data structure for almost all purposes. A plain old vector, or maybe a VecDeque, wins for almost all workloads.

For the few times they are useful (e.g. if you're writing lock-free algorithms, you want a hard upper bound O(1) append rather than just amortized O(1) append, or you don't have malloc available), Rust is a fine language to write them in. But also there are plenty of high-quality libraries on crates.io, so you probably won't have to write your own.

Seems like all source code files I checked lacked comments, or had too little of them, so not so sure what is the reusability of this code.

It uses unsafe though

Code that uses the `unsafe` keyword can be safe, though.

Yes, but you are on your own, and future maintainers will also be on their own.

The exact same way all other parts of the code is. You are also on your own in case of any logic bugs, which may well be likely even worse to debug.

Yes, but an important reason to migrate a solution to Rust are the guarantees that it offers with respect to safety.

Those guarantees go away if you use "unsafe". In that case, you may just use C or C++.

Small, encapsulated uses of unsafe wrapped in a safe wrapper are entirely different than thousands of lines of unsafe.

Also - many of the borrow checker’s guarantees are enforced inside unsafe as well.