[comex]

This seems like an unfortunate pathological case caused by the abstraction level Rust sits at. The kinds of tree- and graph-like data structures that garbage collected languages can represent in safe code (at the cost of performance) don't work as well in Rust; you can still implement them with various mechanisms (std::swap is very important for trees; Rc and Weak; replacing pointers with indices into a global Vec; etc.), but due to a desire to get optimal low-level performance, core data structures often end up using unsafe blocks in their implementations. The thing is, though, implementing data structures is something of a worst case: in most other code you can use the data structures to provide the pointer relationships you need, but when implementing them you have to do that yourself. Most other code is more naturally amenable to working with the borrow checker - which is not to say it's not difficult.

[pcwalton]

This isn't unique to Rust, in fact, as modern C++ presents the same dilemma. Here [1] is a Stack Overflow question where someone asks how to make a doubly-linked list out of smart pointers, and all the answers either involve shared_ptr or C pointers. Same pedagogical issue: you want to deemphasize the less-safe pointers (in Rust, the ones behind an "unsafe" gate; in C++, the raw C pointers) in favor of the safer abstractions, but you hit a wall when it comes to doubly-linked lists.

C++ has it easier in practical terms, I guess—few projects actually use smart pointers as pervasively as modern C++ guidelines stipulate (and they're hard-wired into the language in a couple places like operator new and this), so C pointers usually have to be taught pretty early anyway. In Rust, by contrast, unsafe pointers are considered evil things you touch only when you know you have to. But the problem is still there: it feels like something that comes with the territory of manual memory management in general.

[1]: http://stackoverflow.com/questions/15384443/doubly-linked-li...

[pjmlp]

I don't get why they just don't suggest using weak_ptr<>() for the backwards reference.

[Animats]

You need to use weak pointers for backpointers in Rust, because there's no GC. If you create a cycle with reference counted objects, objects are never released and the program will leak memory.

[pjmlp]

Of course, but my question was why it wasn't explained, I know very well the reason why weak pointers are required.

[pcwalton]

There's little benefit to doing so. Because weak_ptr points to a shared_ptr, you are still paying the overhead of the reference counting either way. You might as well just use shared_ptr and have a destructor that unlinks every element from the list.

weak_ptr is basically for managing leaks, not for avoiding reference count overhead. Leaks aren't the problem in a doubly-linked list, however.

[pjmlp]

Thanks for jumping in. Yeah I guess it makes sense.

It just got me thinking into having some kind of data structure examples in Rust as side project, after 1.0 availability.

Now just have to find time for it.

[static_noise]

I guess this would solve the problem but it would also be slow because traversing the list via weak_ptr requires a conversion from weak_ptr to shared_ptr for every item.

[pjmlp]

There isn't any choice in RC systems in presence of cycles, either weak pointers or a presence of cycle collector.

Anything else is unsafe, specially if the pointer is allowed to escape the RC object that contains it.

And this is one of the reasons why usually optimized GCs outperform RC solutions.

Unless approaches like affine types or counting elision are used, but those fail down in the presence of cycles, forcing the developers to use other approaches to represent cycles.