You can't even explain how doing something as simple as a binary tree with parent pointer is possible in rust, so my assumption is that it isn't possible and I'd have to make work arounds. I can make work arounds just fine in C++, you don't have to teach me those, but I don't see why I'd learn a language where I'd be forced to make those work arounds rather than use the version that fits my problem best.
It might be possible that you can write nice versions etc, if so I'd like to see them, but it seems everyone is hell bent on just saying "You shouldn't do it!".
You are definitely (one of) the intended audiences of rust, just to dispense with any confusion there.
I don't at all think that there are not "any scenarios where the battle tested standard libraries wouldn't be sufficient". I spent a number of words on exactly that in another comment below. My point in that comment was that the use case I don't believe actually exists in production code is "I'm just gonna knock out a simple bespoke implementation of a binary tree". I'm not saying people don't do that, but they shouldn't. If what you need is simple, there is a good library for it. And if the library for it is not sufficient, then it is important enough to invest time into writing a good implementation.
Maybe here's a way to put it: simple bespoke implementations of linked data structures are easy in both c++ and rust using ref counting, slightly better but low-investment implementations are still pretty easy in c++ but are not really possible in rust, and really good implementations are possible in both languages if the investment is worthwhile for the use case. It is true that you would have to learn how to write such a thing in rust and that it would be non trivial to do so, but that is just part of learning a new programming language to an expert level.
I think one misconception in here is that the rust "wouldn't look so pretty". You could do a line for line port of your c++ code using raw pointers and declare it safe, and the two implementations would have similar aesthetics. If your c++ implementation were memory safe to begin with, your rust implementation will be as well. The same process of thinking through the invariants and implementing them correctly is necessary in both languages.
I think the pushback you get that you find off-putting is against the sometimes expressed idea that it is a big knock against rust that you can't do linked data structures with zero cost abstractions in safe rust. This is why people say either "yeah but you can do minimal cost implementations in safe rust and zero cost implementations in unsafe rust". The pushback is against the idea that this isn't a good enough solution. But it totally is, it's certainly no worse than the situation in c++ where the division between a safe and unsafe subset of the language does not exist. Unsafe rust is no different than generic c++ code.
To your last point, there's a great book / reference called The Rustonomicon that is all about writing unsafe rust code well.
Well, if you want to write a tree using indices in a local array instead of pointers for better locality and memory footprint (which is ideal for many situations), you run into the difference between language pointers and computer science pointers. That's not even something that Rust will be smart enough to help you do properly.
It's the lack of backlinks to parents that gets you. Rust can do hierarchies where an A owns a B which owns a C, but if you have a reference to C, you can't get back to A. (Yes, weak pointers, reference counts, unsafe hacks, etc. can work around that. But the language really doesn't like links to parents.)
So there's no direct translation from a C++ object hierarchy to Rust structs.
This is a little difficult on Windows or POSIX systems.
Also, as others have pointed out, you can smart-pointerise everything, but still have problems with common tree and graph structures. Rust is rigorous. C++ isn't; I'm not aware of any mainstream compilers which even have the option to make use of bare pointers or unsafe casting or undefined behaviour into compiler warnings/errors.
I mean, you haven't actually pointed at a trivial tree implementation. The requirement that children be able to navigate to siblings is the issue here (complicating unique ownership by parents).
which your link even says. You would need a handle to the parent to surf around through siblings, is the limitation.
It's not really clear (to me) that the rctree is really all that complicated; the Rc stuff is there to clarify ownership: for how long should allocated memory stick around. It might just read weirdly due to familiarity, in the same way that D might weird me out.
There aren't really simple data structures that involve pointers. Pointers are just hard (where hard means they require programmers to hold state in their head), and rust makes that explicit.
The reality is that implementing data structures that require pointers is not a typical task, and they're ideally provided by the stdlib or crates.
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.
Does rust have something like shared pointers? In c++ that's usually a quite easy way to bail out of the cognitive burden of understanding complex lifetimes.
But in my example this is not hard to get right in C. The tree is constructed (on the stack would be fine), then used for a while without mutating it, then freed all at once.
The thing that makes this hard in rust is destructors. If there's a cycle between A and B, and you destruct A first, then B, then B's destructor would see a dangling reference to A. And vice versa if you destruct B first.
But I don't need destructors, or at least ones that can see these references, so it's frustrating.
Rust really doesn't like pointers; and as such modeling graph data structures besides something like a DAG is a huge pain in the ass: there barely is any idiomatic way to make a mutable self-referential, undirected graph in std-only.
I think he mentioned this briefly in the article. In C it's common to use intrusive data structures like linked lists and AVL trees because that's how the language works, you can embed data structures easily. This wouldn't work with a B tree because it's allocation pattern is very specific. Rust on the other hand is very pro-generics where you can write a B-tree and painlessly have it store whatever anybody wants it to. It's more about what the language makes easy and idiomatic than anything.
It's an oft-quoted fact that Rust is meant to take stuff that good C/C++ programmers already do and build it into the language. If you weren't convinced of this before reading this post, then pay close attention to how important the author considers pointer ownership to be.
Those trivial examples seem to be mostly to not scare off C++ programmers. It's more interesting, though, to see how far you can push single ownership. You can build a single-ownership tree. Rust lacks a "nil", but has discriminated variant records (called "enums") to handle has/doesn't have semantics. You can also grow a <Vec> of owning references, so you can have an array which owns a variable number of children. Using all those features together, you can build a tree. Take a look at the XML library for Rust to see how this all works.
But it can't have backpointers. That would violate single-ownership. Weak pointers for backpointers are available, but that's an unstable feature and introduces reference counting overhead. Rust needs some construct which includes a single-ownership forward pointer and a dependent back pointer, updated together so that they're always in sync.
Thanks for the explanation, this really piques my interest in Rust. BTW, now I have a follow-up to my question whether Rust's references are the analogue to C++ weak pointers. C++ weak pointers can be dangling, but in a controlled manner, that is, one can ask them whether they're dangling or not. Am I correct in assuming that Rust will never allow anything like a dangling pointer, not even the "controlled dangling" of a C++ weak pointer?
Of course, since anything that can be written in C can be written in unsafe Rust.
Though, reading the post above yours, I was thinking more about the use of data structures than the implementation of them. In C++, when faced by the need to efficiently iterate through a data structure in different, incompatible orders, the tool of choice is often just to make intrusive linked lists with multiple next pointers per element. I think I've even once implemented something that was a priority queue (heap), two different lists and a tree at a same time.
While doing that in Rust is by no means impossible, it seems to me that the use of such a structure would be much more clumsy in Rust, to the point where I would try hard to solve the problem in some different way.
The languages are all turing-compatible anyway, so it's not about what can be done, it's about what approaches does the language make easy and promote. Overall I really like the kind of code idiomatic Rust tends to end up like.
Rust's ownership rules make it hard to implement data structures composed of nodes that own references to other nodes. (This includes linked lists, binary trees, and naive implementations of graphs.) There is a reason for this - it's rather tricky to implement such data structures truly safely in any language without introducing hidden assumptions, that's why they are so frequently seen in interview questions for java and c++ coders.
It might be possible that you can write nice versions etc, if so I'd like to see them, but it seems everyone is hell bent on just saying "You shouldn't do it!".
reply