[rustacean]

Thank you. But it seems not finished? I am trying to implement some basic data structures and algorithms in Rust, but the compiler nearly kills me. Is there any data structure & algorithms implementation tutorials for Rust newbies, like Learning_ Rust_With_Entirely_Too_Many_Linked_Lists[1]?

[1]:http://cglab.ca/~abeinges/blah/too-many-lists/book/README.ht...

[kazagistar]

Data structures and algorithms are possibly the hardest part of Rust to dive into unless you have a really good reason. The best advice for newbies is to learn with other stuff and use existing algorithms. Of course, if you are trying to implement stuff for a class or something similar then you might be out of luck, and might consider trying the Rust IRC and such to work through the errors as they come up.

[EbTech]

I made this cookbook specifically to show it doesn't have to be so hard. While designing an industrial-strength data structure library is an advanced skill, there are easier ways to implement the core ideas that should suffice for contest and coursework purposes. Very few people have to build actual libraries.

[lgas]

> Data structures and algorithms are possibly the hardest part of Rust to dive into

What else is there?

[Paul-ish]

I think it was too much for the. to say "Data structures AND algorithms". It is mostly data structures that can be difficult.

[jeeyoungk]

Agreed. It's very unnatural to represent data structures with circular references, or pointers in general. I had to re-think how I approach certain problems to make it more Rust-friendly.

[geodel]

CRUD webapps. It can get venture funding too if one can design a login page.

[freeordead]

So what is the point of a language in which things are hard to implement?

[derefr]

Algorithms and data structures are inherently hard to implement correctly and safely given low-overhead, bare-metal designs.

Rust tries to guarantee that you've implemented things correctly and safely, and therefore makes all the formal verification of such into a requirement.

Other low-overhead-bare-metal languages, meanwhile, trust you to have done the formal verification yourself using non-compiler-toolchain tools like linters and static analyzers.

The people who use these other languages who do ensure correctness+safety, will have done all the same work they do in Rust—just using third-party tools instead.

The people who use these other languages but who do not ensure correctness+safety, might seem to have an "easier time", but they will almost always end up with algorithms/data structures that—while seeming to work in most cases—have fatal flaws or vulnerabilities.

To use Rust is simply to sign up for "doing the work" of formally verifying your code up-front, rather than brushing it off as something to think about in some vague, undefined "later."

[tomjakubowski]

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.

[wuch]

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.

[baq]

Agreed but don't you have to do all this in C/C++ too if you want your data structure to be really safe? Except perhaps zero sized types.

[wuch]

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.

[whyever]

> Cyclic data structures (without additional layer of indirection) require unsafe, or reference counting and dynamic borrow checking.

Doesn't this apply to any language?

[Groxx]

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™".

[TuringTest]

Efficiency, predictability, increased security.