Lots of these comments seem confused about the purpose of this. It's not about using linked lists (that's easy, they're in std::collections), it's about implementing them. So the common non-kernel/embedded use cases are well supported, just use std::collections::LinkedList! But if you're in a no-std context then you might need this.
Learn Rust with entirely too many linked lists (2019)
101–110 of 179 posts
Re: Learn Rust with entirely too many linked lists (2019)
#102>You're doing some awesome lock-free concurrent thing. I can confirm lists are pretty rarely used. The four times I've used a linked list in 10 years of professional programming were: -quick&dirty hashmap in C -threadsafe queue -keeping track of a set of objects that can't be copied ( threads) -LRU cache In C++ at least, the nice thing about a list is you can push/pop in the front/back without a reallocattion or inva…
Linked lists are used a lot in game programming where the worst-case behaviour of std::vector and similar structures is undesirable. Linked lists may be slow for a variety of reasons but they're simple and predictable which is very nice when you're trying not to miss the 16.67ms per-frame window.
Used, yes, butbnot implemented. std::collections::LinkedList is a doubly-linked list suitable for games. It's basically just the no-std crowd that might need to implement their own.
Re: Learn Rust with entirely too many linked lists (2019)
#103Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that. If you have safe b…
As a non-Ruster, any particular reason they didn't include this? A lot of the code I've done over the years involve graphs, which have a lot of circular pointer and/or backpointers. I find it kinda weird they'd make such a common thing a PITA in a new language.
Rust has a concept of ownership and borrowing. (I think) everything is fine when you just have immutable references everywhere. But as soon as you start taking mutable references (of which only one can exist at a time) or ownership (stronger than mutable references), then cycles break things.
You can get around it with Interior Mutability, it's just slightly more verbose.
Also, it isn't really that they made an easy thing hard. Properly maintaining the invariants with cyclical references is hard and unsafe. Rust exposes that difficulty in a very literal way
Re: Learn Rust with entirely too many linked lists (2019)
#104Earlier quoted context omitted.
A hash table is vulnerable to collision attacks, if keys are derived from any kind of untrusted external input. Trees might be slow, but they're consistently slow.
non sequitur. No one mentioned security, nor do any elementary data structures concern themselves with such higher level things. If you're allowing unlimited untrusted data to control internal data structures, you're going to have a bad time regardless of which data structure you're using.
And rusts default hashing implementation is hardened against these attacks
Re: Learn Rust with entirely too many linked lists (2019)
#105Earlier quoted context omitted.
Linked lists are inherently niche on modern hardware.
Yes. Lists were fine when memory was random-access. Today, if you're linking all over memory, cache misses dominate performance. So contiguous data structures are preferred.
This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.
Re: Learn Rust with entirely too many linked lists (2019)
#106Earlier quoted context omitted.
As a non-Ruster, any particular reason they didn't include this? A lot of the code I've done over the years involve graphs, which have a lot of circular pointer and/or backpointers. I find it kinda weird they'd make such a common thing a PITA in a new language.
It might actually be possible now with Pin. Could anyone actually knowledgeable about this comment?
I don't know much about Rust (and nearly nothing about Pin) but if this was true, don't you think someone would already have written a library providing doubly linked list without using unsafe?
Re: Learn Rust with entirely too many linked lists (2019)
#107Re: Learn Rust with entirely too many linked lists (2019)
#108Earlier quoted context omitted.
Thanks! Why does everything look like a multi-dimensional array for you in rust?
An array (an ADT) can be arbitrary dimensional, with one-dimensional case often called vector (and two-dimensional called matrix). An array can also be adjustable, both in one and multi-dimension variants. So a vector can be both adjustable and non adjustable, and some language do have both versions. Some language have adjustable one-dimensional array/vector as the only dynamic aggregate/ordered datatype. And to answ…
Thanks for clarifying.
I think we're just using different definitions. The only real definition of an array I've encountered in work and school is that it's just a one dimensional collection of elements, usually of static size. A vector depending on context is usually the same thing as an array but you conveniently change the size dynamically. Lists can whatever you need it to be given the context, just needs to be sequential.
Of course you can represent higher dimension structures by linearizing indices (x + row_size * y, etc).
I think people are getting confused as most don't consider arrays to be arbitrarily dimensional without some scheme.
Completely off topic but you've reminded me of this great article: https://hypirion.com/musings/understanding-persistent-vector...
Re: Learn Rust with entirely too many linked lists (2019)
#109Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that. If you have safe b…
You can somewhat emulate this with Weak pointers:
https://doc.rust-lang.org/std/rc/struct.Weak.html
They don't count against ownership, but do bring some extra headaches of their own (referencing counting overhead, etc).
Re: Learn Rust with entirely too many linked lists (2019)
#110Earlier quoted context omitted.
Yes. Lists were fine when memory was random-access. Today, if you're linking all over memory, cache misses dominate performance. So contiguous data structures are preferred.
This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.
That's no longer a linked list, it's a vector.