Crust of Rust: std::collections

In this video we go over the various collection types in the Rust
standard library (effectively `std::collections`), and discuss a bit
about how they work, when you might use each one, and what their
respective trade-offs are.

0:00:00 Introduction
0:03:57 Vec
0:29:57 VecDeque
0:49:54 LinkedList
0:59:21 *Set types
1:07:51 HashMap
1:43:42 BTreeMap
2:10:22 BinaryHeap
2:30:31 Option and Result maybe(?)
2:37:35 Is () a collection?

[karljohannisson]

Dude this video is so good. It's Rust, but these concepts feel deeper and applicable to many languages. Thanks for sharing your knowledge to the world.

[lordmelbury]

"I think I wrote part of this"
~ Legend!

[driedurchin]

Would love a Crust of Rust on alternate allocators, when you might actually need one (i.e. you benchmarked and determined the default allocator is insufficient), and how you would employ them in practice.

[wesleychaffin]

The best Rust channel on YouTube strikes again 😄

[zanisxeroxhou]

Still waiting for your decrusting Tokio, Rayon, Axum, rust-gpu or wgpu!

[jdiehl]

Nice haircut, Jon! Always stoked to see you've released new Rust content.

[joffreybluthe]

Thoroughly enjoyed this video! Your videos are usually too advanced for me but this was perfect for where I'm at :)

[VivekYadav-dsoz]

Never seen a binary heap explained as a glass with different densities of liquids. Pretty brilliant if you ask me.

[SimonBuchanNz]

One note is that the implementation of vec![] that just pushes is only a book example, the actual implementation is basically just

This lets the compiler place the item construction directly into the allocated memory (though unfortunately not guaranteed, and currently isn't in debug), and the into_vec call just adds a capacity equal to the array length.

Also IIRC my CS lecturer said Deque is pronounced "deck", but he was German, so who knows!

[lorink]

note to self:
vec has retain filter. allocates on heap only (unlike smallvec). no iter because no index state.
set is just map with empty keys. stdlib hashmap is DoS resistant by using OSs random seed. usually does linear probing ie fills stuff into other bucket by hasing stuff again.
btree is like binarytree but with a sorted list in each node.

[CyborusYT]

*Vec::new does not allocate.* It has a capacity of 0 and a dangling pointer, the minimum size doesn't kick in until you push an item. If it did allocate, it couldn't be const.

[drip]

Another bing bong banger from your boy Jon. Can't wait to fully consume this piece of content.

[juchemz]

1:33:31 The std version of HashMap (hash brown) actually does not shuffle entries around like you suggest. When an entry is removed the slot is filled with a so-called "tombstone" value to indicate that something was there in the past

[vader]

28:00 Actually, the lifetime is also required bc custom allocators can be non-static, in which case leak would only be allowed to leak for the lifetime of the allocator.

[papydoctor]

About the VecDeque collection. A nice feature to add is to be able to reserve a capacity in a power of 2 and have the underlying process working with binary and logical operator instead of mod operator. :)

[KohuGaly]

There is in fact a heap analog to the radix sort. It's called radix heap and it's amazing. Basically, you store a chain of Vecs, where Nth vec has items which differ form the last popped item in first N digits. It only works if the inserted priorities are always larger than the last popped priority. But the performance boost is quite substantial.

[actr]

Would be very nice Jon, if you reviewing tokio and other stuff with async programming in rust, last video was 3 years ago, after that many things change, so, would be nice

[darthmoomoo]

The Foundation (R)(TM) is going to have an aneurysm when they discover the name of Jon's series. Jk (or maybe not).
Anyway, your videos are always comprehensive. Love it!

[Dygear]

This was excellent, I learned a lot in a very short time. Realized I didn't need the Bytes Crate's `.put` method to extend a Vec with a Vec I can just use `.extend`.

[jestarray]

I didn't know about hashmaps and "entry, so thanks!