It's not any harder to correctly implement a data structure, even an "advanced" one, in Rust-with-unsafe than it is in C++-with-exceptions. I don't know where this meme comes from.
I don't think this claim is completely unfounded from perspective of people coming to Rust from other languages. Consider for example:
* Poor ergonomics of raw pointers. Lack of arrow syntax, verbose pointer arithmetic (at least now there is an experimental offset_to).
* Once you have pointers in data structures, properly specifying lifetimes is now your job. Compiler is no longer your friend, but an whisperer of evil (Compiler: Of course it safe. It has 'static lifetime, it must be safe. How do I know, you ask? I saw you dereferencing a pointer).
* Cyclic data structures (without additional layer of indirection) require unsafe, or reference counting and dynamic borrow checking.
* Need to account for zero-sized types when doing pointer arithmetic.
* Need to uphold Rust invariants in unsafe regions of code - forming non-unique mutable references to the same memory is hardly unusual when working with cyclic data structures, or in general (consider for example a swap without checking if memory locations are identical).
It seems to me that Rust moves part of required work from users of data structure to the designer / developer of data structure. You need to invest more work upfront, but once done users don't need to be on constant lookout for accidental API misuse that results in undefined behaviour.
No, those are Rust specific things.
For example, aliasing mutable references in C++ is potentially dangerous, but not undefined behaviour per se.
Regarding making a "really safe" data structure, this is quite tricky question.
Safety means quite different things in those communities.
Moreover those different concepts of safety are not readily transferable between languages, at least not in useful sense.
In Rust you would say that data structure is safe if it doesn't cause undefined behaviour when used without any unsafe user-code.
Essentially once you write a safe data structure the safety is enforced by a compiler, even in a presence of malicious user-code (as long as it avoids unsafe blocks of code).
In C++ on the other hand, a user would have only themselves to blame if they broke a precondition expressed somewhere in a documentation and caused undefined-behaviour.
This is exactly why I would postulate that writing correct data structure in Rust, as opposed to say C++, may require more effort.
For similar reasons using dependent types doesn't make programming any easier.
Of course, this may turn out to be a worthy investment in the long run.
Some of it is probably that you're not able to not-handle some categories of flaws, and the compiler yells at you for them instead of pushing it off to a runtime error you may never see. Instant pain on the ignorant implementer rather than "works on my machine™".
* Poor ergonomics of raw pointers. Lack of arrow syntax, verbose pointer arithmetic (at least now there is an experimental offset_to).
* Once you have pointers in data structures, properly specifying lifetimes is now your job. Compiler is no longer your friend, but an whisperer of evil (Compiler: Of course it safe. It has 'static lifetime, it must be safe. How do I know, you ask? I saw you dereferencing a pointer).
* Cyclic data structures (without additional layer of indirection) require unsafe, or reference counting and dynamic borrow checking.
* Need to account for zero-sized types when doing pointer arithmetic.
* Need to uphold Rust invariants in unsafe regions of code - forming non-unique mutable references to the same memory is hardly unusual when working with cyclic data structures, or in general (consider for example a swap without checking if memory locations are identical).
It seems to me that Rust moves part of required work from users of data structure to the designer / developer of data structure. You need to invest more work upfront, but once done users don't need to be on constant lookout for accidental API misuse that results in undefined behaviour.