Summary

The Rust standard library features a great collections part, providing a few highly optimized implementations of basic data structures.

We started with Vec<T> and VecDeque<T>, both based on a heap-allocated array and wrapped in the RawVec<T> structure. They show excellent performance while memory efficiency remains high, thanks to the array base and unsafe operations based on pointers.

 

 

LinkedList<T> is a doubly-linked list that performs really well, thanks to direct data manipulation and the lack of runtime checking. While it excels at splitting and merging, most other operations are slower than Vec<T> and it lacks some useful features.

HashSet and HashMap are based on the same implementation (HashMap) and—unless specified differently—use DefaultHasher to generate a hashed key of an object. This key is stored (and later retrieved) using the Robin Hood hashing method, which provides major performance benefits over a naive implementation.

Alternatively,...