> I know Rust!
> Good! But could you implement a tree traversal in Rust?
This kills rustfags.
> I know Rust! > Good!
Falling into your wing while paragliding is called 'gift wrapping' and turns you into a dirt torpedo pic.twitter.com/oQFKsVISkI
— Mental Videos (@MentalVids) March 15, 2023
fn main() {
use std::collections::BTreeMap;
let mut map = BTreeMap::new();
map.insert(3, "c");
map.insert(2, "b");
map.insert(1, "a");
for (key, value) in map.iter() {
println!("{key}: {value}");
}
Cry, cnile bitch.
holy retard, batman
kek Rust broke LULZ so hard because it exposed that the majority of LULZ can't code for shit. You homosexuals just hide the denial behind the tranny obsession
>the majority of LULZ can't code for shit
>imports a library for tree traversal
Is Rust just the new Python?
Yes. That's why it will only continue to get more popular.
The new Pajeet lang™
>Is Rust just the new Python?
Nim is the new Python
https://nim-lang.org/
>he doesn't write his own c standard library for every program
ngmi
rustrannies win yet again
OP BTFO
>Cry, cnile bitch.
Good. Now let's do preorder, postorder and inorder traversals.
You don't seem to understand what a Map type is for. Also nice moving goalposts
> Currently, our implementation simply performs naive linear search. This provides excellent performance on small nodes of elements which are cheap to compare.
> https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
No, I understand it.
>https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
>In particular, every element is stored in its own individually heap-allocated node. This means that every single insertion triggers a heap-allocation, and every single comparison should be a cache-miss.
bullshit. there's absolutely nothing stopping you from implementing a tree (or a linked list for that matter of fact) with an array as the backing and indexes as "pointers".
and even if you don't want to use an array there's nothing stopping you from using an arena allocator which guarantees spatial locality to allocate the nodes.
confusing the concept of a binary tree with one particular implementation and then using that particular implementation's weakness as an argument against the concept itself is such an amateur thing to do.
If you use an array with indices then it's not much different from a raw pointer. It's _literally_ the same thing and has the same issues.
I think Rus[low]t bounds check every array index
>It's _literally_ the same thing and has the same issues.
One can break the type system. The other can't. That's the whole point of memory safety.
>One can break the type system. The other can't. That's the whole point of memory safety.
Because your type system sucks ass
>your type system
Without memory safety you don't have ANY type system, and then all of your data structures are fucked. No heap. No call stack. It's all fucked. Like your mom.
Unfortunately no meds for retards, consider the rope
I accept your surrender
>Java, golang, C++, C# don't have a type system!!! NO LANGUAGE HAS A TYPE SYSTEM EXCEPT RUST!!!
KYS troll
>NO LANGUAGE HAS A TYPE SYSTEM EXCEPT RUST
Not my argument, smoothbrain
In most languages, even C and C++, your code is memory safe unless you do certain stupid things, like using an allocation after freeing it
The whole idea of memory safety is as old as C
Obviously it was invented to talk about languages that don't enforce it in any way
Guess what? Even if it's not being enforced it's still a property you want if your program is supposed to do anything useful
>Rust's type system gets broken by pointers
>Rust's type system sucks
>You start chimping out at the previous fact
Explain more
Tell me which type system doesn't suck.
They all have trade-offs
>It's _literally_ the same thing and has the same issues.
do you happen to be insanely braindead? an array guarantees spatial locality retard, which makes this claim:
>This means that every single insertion triggers a heap-allocation, and every single comparison should be a cache-miss.
completely retarded.
You completely miss the point. If you have a memory allocator that uses an array as the memory space then it's literally the same thing and you setting an array index as free is the same as doing free(). You have the same issues, array bounds check has nothing to do with it. You still have the possible issue of "use after free", less type safety, etc. Im not talking about it from a performance standpoint, im completely aware of spacial locality; so maybe you shouldn't be retarded and also think about the "safety" aspect if you claim to use a safe language.
In other words, using an array is a hack to get around the "safety" of rust, throwing it in the trash to write faster code while making your code less safe than c++.
>use after free
How? After freeing it you just set its index to None or whatever
> You still have the possible issue of "use after free"
not if you don't free any nodes (which is fairly common use-case in practice for search data structures).
>Im not talking about it from a performance standpoint
except that the rust doc is. it's making bullshit claims about performance of BST without considering that malloc-ing each node isn't the only way to implement a BST.
not to mention, generation handles practically solve the "use after free" issue.
just look up arena allocators, or region based allocators.
https://en.wikipedia.org/wiki/Region-based_memory_management
the core idea is that instead of malloc-ing every single element and then managing them individually. you put them all into a single bucket and then when you're done, you free the entire bucket at once.
look up danging pointers. dangling indexes aren't a memory safety issue, but it's still a logic bug.
>look up danging pointers. dangling indexes aren't a memory safety issue, but it's still a logic bug.
How can you have a dangling index in Rust? There's no free() is Rust, the compiler adds that stuff based on RAII. I don't get it
>dude A stores an index (let's say 5) to a node
>someone else marks that node as "freed"
>another node is added to the list, the index 5 is reused for it, since it got "freed"
>dude A now uses his previously stored index, without realizing that the node at that index now is a completely different node
OhhhhhhhhhhhHHhhHhHHHHhhhH
This makes a lot of sense, and would be a hell to debug
it's exactly the same issue you face using malloc and free in C. rust is so advanced and so safe that the troons had to reinvent c in order to do anything useful with it.
except that one of them neatly avoids the worst feature of Rust - the borrow checker.
>moving goalposts
those are all tree traversals retard
>Also nice moving goalposts
nagger, do you even know what tree traversal is? Lmao. Rustroons are just Pythonshitters
>do this
>done
>o-ok b-but can you do this!
😐
It *krashed*
Wow this looks so polished. What DE are you using? Is this gnome?
that is literally windows with linux subsystem
are you proper retarded?
OP said "implement"
>ex-webdev rustnagger doesn't know how to make anything, only knows how to glue libraries together, doesn't even understand the prompt because of it
LOL
That's pretty must all of industry programming these days, so it's realistic.
*much
he didn't even use any libraries outside of the standard ones, are you losing your mind might i ask?
>standard library isn't a library
ishygddt
implement fucking retard
unsafe is referenced 35 times in BTreeMap alone
Total rustroon death
and?
ok now do that in a systems programming context. oh wait that's not an option...
>words words words
the left cant meme
oof thread killed in the very first post
>import solution
>ahah, yeah, i totally "implemented" it myself
>imports std::vector
>ahah, yeah, i totally "implemented" it myself
OP ARE YOU OK?
ARE YOU OKAY, OP??
I implemented a Tree structure with Vec of children and a back reference to its parent. Transversal was straightforward as well for it to impl Display. This was all using Rc<RefCell> for children and Weak<Refcell> for parent lookup. I've seen easier, more cache efficient solutions done with generational arenas as well.
What exactly is the issue here OP?
I guess the point OP is trying to make is that it's much simpler to do in C/C++. Moreover, Rc<RefCell> and areanas create reference cycle which can potentially leak memory.
>Rc<RefCell> and areanas create reference cycle which can potentially leak memory
Hence the Weak<Refcell>s
Yes, but a tree in C/C++ does not need to implement parent lookup and works fine. And certainly simple pointer is much simpler, than Rc<RefCell>. I am not saying that you can't implement in Rust, just saying that it's difficult to do in Rust. Keep in mind that a tree a basic data structure and by default a node only keeps references to its children, not to its parent.
what's the problem? memory leaks are safe (TM).
>Moreover, Rc<RefCell> and areanas create reference cycle which can potentially leak memory.
Trees have no cycles by definition.
>he doesn't know about the pseudo-cyclic ternary search tree
Why not just use Java sirs?
slow and bloated and UGLY
What the fuck is an "i32"? Why do people write in this bullshit language?
>What the fuck is an "i32"?
Seeing as you don't know how to code i'll refer you to HolyC which should be gospel to any LULZ programmers that was given to us by Terry himself.
https://harrison.totty.dev/p/a-lang-design-analysis-of-holyc
It's an int32_t.
Rust benefits from not having to be backwards compatible with a language that has retarded builtin types like unsigned long long int
>int32_t
Look more familiar retard
>What the fuck is an "i32"?
Are you retarded?
Confirmed for never having written code in your life and posting in language war meme threads like a total homosexual.
why do nocoders keep coming to programming threads whenever Rust is mentioned?
Nobody would write a tree like this. Not even C++ programmers would write a pointer-based tree like this.
C++ programmers don't have to, that's the point. Rust requires unholy amounts of gyrations to get the most basic shit done.
>that's the point
You don't get it, even his C++ implementation would be shit. I'm trying to say OP is a shitty programmer.
t. writes rust and c++
Show me your C++ and Rust tree implementations.
>even his
Retard, "his" implementation is literally a Leetcode default implementation,
https://leetcode.com/problems/binary-tree-inorder-traversal/
In the drop-down menu choose Rust. It's literally what just OP posted.
>cites a toy implementation of a tree on fucking leetcode as a "good" code
Fucking lmao.
Post your code then.
pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ret: Vec<i32> = vec![];
root.map(|node| {
let node = &node.borrow();
node.left.as_ref()
.map(|left| ret.append(&mut Solution::inorder_traversal(Some(Rc::clone(left*~~));
ret.push(node.val);
node.right.as_ref()
.map(|right| ret.append(&mut Solution::inorder_traversal(Some(Rc::clone(right*~~));
});
return ret;
}
ugliest thing i've written yet in Rust, do I win anything?
disgusting
Rust was a mistake.
>do I win anything?
A dildo to complete your transition
Rent free closet homosexual
All the closet homosexuals came out and started learning Rust. Idk what you're even talking about
I really wish Ada had received the attention that Rust garners. Even no-coders can read what Ada is doing, because it's direct and to the point.
no-coders would still have a fit with Ada because of its type system requiring explicit casts anytime you want to go between anything, and in general it's very verbose for someone who thinks C is bible.
>In the drop-down menu choose Rust.
Oh God it's hideous!
>"Rust is bad! Look, you can't even do a doubly linked list!"
>"I've literally never once needed a doubly linked list"
every day we have this discussion
You can implement one with Rc & RefCell. Anything else you wish to complain about no coder?
> can you solve this {trivial, obscenely common problem taught on first semester uni} in {random general purpose programming language}
if you're asking this seriously you should probably kill yourself op, you probably have a window close by, maybe jump out and remember to go head first retard
if you're asking this seriously, it either means you're retarded or the language in question is VERY retarded
I am employed as a Python dev and shit like this is one of the reasons I am hesitant about Rust. I am making a side project in it just to get the hang of it for future potential job offers, but maybe it isn't worth the effort. I already know C++ from university, maybe I should go with that instead. What I fear in C++ is that it feels jobs related to it value experience in it more than general knowledge in CS. Also I am a dropout and most C++ job posts I see require a degree.
Don't use systems programming languages unless you need a systems programming language.
>I already know C++ from university
Trust me, you don't know C++.
What I meant by "know"ing C++ is that I'm not a pure rookie who never had to deal with memory leaks or never made a multithreaded program in C++. C++ will come much more naturally to me since you have classes and inheritance unlike Rust where you need traits or some shit.
Just stop talking about things you don't understand.
pls stop bro
OK I will stick to Rust.
Kek bruv you don't know C++ until you've been shat on by some retarded C++ codebase and you think you're going insane. The C++ you touch at uni is the most basic of basic shit.
Option<Rc<RefCell<TreeNode>>>
What does all this stuff mean?
In modern C++ this would be just std::unique_ptr<TreeNode>
No
In modern C++ it would be std::optional<std::shared_ptr<TreeNode>
The only thing missing in C++ is RefCell which works kind of like thread-local Mutex but panics instead of blocking when locked.
Also no one implements Trees this way in Rust, just like no one does that in C++. But OP is only trying to get free (You)s and you fell for his bait.
He's right, tree is a single owner data structure, there is no need for refcounting
And in rust it would be Option<Box<T>> as Box has stronger guarantees than unique_ptr (has to have an object)
Yes, retards in this exact threads are taking leetcode trash as good
Every time you see someone writing Rc<RefCell<T>> in Rust, they're trying to implement some other language's design patterns in Rust. Anyways, Rust has its own equivalent to unique_ptr, and it's called Box. This is what OP should be using for a tree.
They're Java programmers. Lots of object oriented languages strongly encourage maintaining lots of references to other objects everywhere in a giant tangled mess. Rust encourages you to have single ownership of objects as much as possible. Java programmers refuse to learn to program any way other than what they're used to in Java, so when they're given access to Rust, they use its ugliest design patterns possible.
>Rust encourages you
No, it just prevents you from writing anything useful.
They only rust design pattern is to replace heap memory with arrays. Rust is such dumb language.
Yeah, just dump your data structure over as many pages as possible. Seriously if Rust encourages greater locality then I might even put on my high heels and learn it. Maybe I'll even pen a "NEW considered harmful" essay.
>if Rust encourages greater locality
how exactly do you think rust Vec works under the hood? If you have a whole bunch of arrays are keep reallocating them then you're going to get memory fragmentation. this isn't rocket science.
Unless your application is a toy with only 1 or 2 data structures, then you have to consider global locality and your access patterns as well. Stuffing everything into it's own array won't magically give your locality. https://youtube.com/watch?v=rX0ItVEVjHc
>Rc stands for “reference counted” (in std::rc)
>RefCell stands for “reference cell” (in std::cell)
>Box is just a smart heap pointer (in std::boxed)
>And “regular”, manual pointers are in std::ptr
So it’s pretty clear that Rust has all of the tools needed to implement common data structures, and it has all the stuff in the modern C++ std lib. It’s just that Rust’s tools are strewn about the std lib with absolutely fucking retarded names, and similar concepts are being in completely different sub packages of std. So to build ANYTHING, you have to study all the retarded tranny nomenclature of Rust’s standard library, and trying to grope around even with deep knowledge of other languages won’t help at all, because a lot of the nomenclature is cryptic and/or brand new.
How fucking stupid and gay. Why not just go with something like std::ptr::refcounted, std::ptr::unmanaged, std::ptr::shared — you know, a logical taxonomy with non-cryptic naming. Instead they came up with all new bullshit to learn, so new rust trannies can’t even implement a fucking tree. Reminds me of trying get started with web programming in Java where you have to learn like 30 custom Spring annotations just to serve some HTML. Too gay for me, fellas
>std::ptr::refcounted, std::ptr::unmanaged, std::ptr::shared
Please go back to C++
How is boxed, rc, boxed, and refcell any better?
>why is “referenced counted” reduced down to just Rc? Is is 1985? I thought we got away from cryptic 2-3 letter nonsense naming conventions?
>why is “Reference Cell” reduced down to “RefCell”? How is that consistent with “Rc”
>what the fuck is a Box? “Boxed types” in other languages have a different connotation. Why did they choose this langauge
Rust trannies are retarded. Organization and consistency of the std lib is important. Say what you want about Java verbosity: at least the standard lib naming is good and the conventions are consistent. There’s no confusion about what a FileInputStream is.
Go back
>It’s just that Rust’s tools are strewn about the std lib with absolutely fucking retarded names
The names are literally taken from other languages. Not everything is C++.
>similar concepts are being in completely different sub packages of std.
They all do completely different things.
>So to build ANYTHING, you have to study all the retarded tranny nomenclature of Rust’s standard library, and trying to grope around even with deep knowledge of other languages won’t help at all, because a lot of the nomenclature is cryptic and/or brand new.
If just having to read the rust book is enough to filter you, you probably shouldn't bother with programming in the first place.
>Why not just go with something like std::ptr::refcounted, std::ptr::unmanaged, std::ptr::shared
You just came up with 3 names for Rc<T>.
>Instead they came up with all new bullshit to learn, so new rust trannies can’t even implement a fucking tree. Reminds me of trying get started with web programming in Java where you have to learn like 30 custom Spring annotations just to serve some HTML.
Skill issue
>j-j-just read our gay book!
>j-j-just cut your dick off and take estrogen!
No, homosexual. I should be able to feel around your standard lib without your gay little crab book and figure out how to implement a fucking tree just with the package and class names alone. I know C, C++, multiple JVM langs, Python, JS/TS, and others. I’m already a production software engineer. Why the fuck would I read your faggy book and learn your gay little nomenclature? Why bother with the headache? To work with you? Some homosexual who can’t bench 225? No.
You offer no defense of the inconsistency between “Rc” and “RefCell” because it’s indefensible and bad. It takes us all back to 1985 with cryptic naming and gay little code names. Fuck your tranny language and enjoy being unemployed and SLOW.
>I’m already a production software engineer.
why would anyone choose to use anything but C for this? I just don't understand, what is the appeal?
>LULZ filtered by strongly static typed languages
What a shocker lmao
> Payload 32 bits,
> 2x64bit pointers
> Unclear amount of Option and Rc overhead
Option is not overhead retard. Unlike shit languages like C#, Java Option can be entirely optimized out.
> Option<Rc<RefCell<...>>>
Stop. Fucking quit. If you really want to implement a tree on your own, it is going to be 1 million times better to store the nodes in a Vec and make the tree nodes index into the Vec internally. Pretty much uses the vec as an arena.
That makes a safe tree pretty much trivial (and a faster tree that isn't provably safe just as trivial) and all of the algorithms will just make sense.
What's genuinely hard is a linked list, but that'd be dumb to implement on your own. It's in the standard lib.
Just use pointers nigga, fuck rust
You can do that in either C or Rust, it's just unsafe in both.
>But I don't care
don't use rust. Fixed
That works but it is troublesome with references.
Nocoders really don't understand why doubly linked lists are hard to prove the correctness of.
>Nocoders really don't understand why doubly linked lists are hard to prove the correctness of.
Nocoders can't code doubly linked lists correctly so they had to make a language that bans you from creating this data structure without using le special magic keyword. FTFY
>t. can't implement doubly linked list in Rust without unsafe
Filtered
really don't understand why doubly linked lists are hard to prove the correctness of.
>he doesn't know that you can bind the entire linked list's lifetime to an arena
>he doesn't know about generational handles to reuse slots in the arena
please, have mercy on my sides.
>>he doesn't know that you can bind the entire linked list's lifetime to an arena
>>he doesn't know about generational handles to reuse slots in the arena
Not OP. What the heck is an arena?
>That works but it is troublesome with references.
It isn't any different from Vecs or other standard containers. There is absolutely no need to use RefCells for a tree.
>What's genuinely hard is a linked list
lol, lmao even.
Why the fuck is anyone even using Rc/RefCell?
Is this board really nocoder shills vs other nocoder shills?
FFS
This looks like utter shit. Why would anyone want to program in this lang?
Can't wait for ML models to do this shit for me.
What exactly is wrong with it?
I'm a braindead zoomer and it is not easy to understand the code, especially the insert function/method in ""impl""
Have never looked at Rust before, it was just my first impression, nothing to be taken seriously.
insert is a function that operates on the node for which it was called, we know this because the self parameter is mutable, and a reference. it also accepts a value of generic type T as defined by the Node definition.
the first line in the insert function is a match block, this performs pattern matching on its operands, in this case it does the less than binary expression (implemented by PartialOrd on T) and compares it with the value of this node's value, the two other operands are references to the optional left and right vertices of the tree, wrapped in a tuple.
the first pattern that is matched is if value T is less than the value of this node, and if the left optional is None, with no preference for the right branch as the value is less and therefore will go down the left branch of the tree. if this case matches, the left optional reference in the tree is passed ownership of the value T parameter, wrapped in a box and a some type.
the second pattern the match block matches is if the value is smaller, and there is a node in the left branch in which case ownership of value T is passed to the insert function of the left node.
the third pattern is the right version of the first pattern, operating on the right branch, and the fourth pattern is the right version of the second patter, passing the value T into the right subtree.
this function returns no values, side effects are the current node, or some node in a subtree of this tree will be mutated and have a node added to it as a leaf.
Quite simple really, and a very expressive way to implement the branching of insertions. in C this would be if (node->left == NULL) checks, but pattern matching on the node's state by capturing its stateful members is more explicit as to what you intend as a programmer.
filtered
Because 1% of people on LULZ program, and 1% of programmers on LULZ have actually used Rust.
>Carbon
>iToddler image
YWNBAW homosexual troon
Is this a troon?
https://www.twitch.tv/krisnova
Sounds like a woman, but looks like Mr. Incredible from the Incredibles
Sorry sirs, but traversal of trees with depth > 1 is not Rustonic so you should store your data more properly. Thank you for understanding sirs
I've started storing my data firmly up my bussy. keeps it warm and its good for memory locality tbh.
But how would you implement immutable AVL tree?
This is a clear case when GC is better than manual pointer juggling.
don't use C++, don't use Rust, simple as.