Ben Chuanlong Du's Blog

It is never too late to learn.

Summary of Collections in Rust

Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!

The module std::collections has a good summary on popular collection data structures in Rust and when to use them.

  • Sequences: Vec, VecDeque (double-ended queue), LinkedList (doubly-linked list)
  • Maps: HashMap, BTreeMap (sorted map)
  • Sets: HashSet, BTreeSet (sorted set)
  • Misc: BinaryHeap (priority queue)

rust-collection-summary

elsa

Elsa provides append-only collections for Rust where borrows to entries can outlive insertions

itertools

itertools provides extra iterator adaptors, iterator methods, free functions, and macros.

Heapless / Stack / Array

heapless / arrayvec: stores on the stack only. Limited capacity, capacity set at creation.

  • heapless provides static friendly data structures that don't require dynamic memory allocation.

  • arrayvec arrayvec provides a vector with fixed capacity, backed by an array (which is stored on the stack). Notice that you cannot collect an iterator into an Array. However, you can collect an iterator into an ArrayVec. For more discussions, please refer to How do I collect into an array? .

smallvec
https://crates.io/crates/smallvec

stores some elements on the stack, falls back to the heap if the stack capacity is exceeded.

tinyvec: provides both, implemented in 100% safe code. For example, smallvec had 5 memory safety bugs to date; they are guaranteed to never happen with tinyvec. The drawback is that the stack storage is zero-initialized on creation, which incurs some cost; for small capacities it's usually negligible, but adds up if you want to store thousands of elements.

ndarray https://crates.io/crates/ndarray

An n-dimensional array for general elements and for numerics. Lightweight array views and slicing; views support chunking and splitting.

Array in Rust has discussions on ways to make it easy to construct arrays.

Hash / Set / Map

Hash code and Hash Maps

  • fnv is an implementation of the Fowler–Noll–Vo hash function.

  • hashbrown is a Rust port of Google's high-performance SwissTable hash map, adapted to make it a drop-in replacement for Rust's standard HashMap and HashSet types.

  • phf provides runtime support for perfect hash function data structures

  • indexmap A hash table with consistent order and fast iteration. The indexmap is a hash table where the iteration order of the key-value pairs is independent of the hash values of the keys. It has the usual hash table functionality, it preserves insertion order except after removals, and it allows lookup of its elements by either hash table key or numerical index.

  • dashmap is a blazing fast concurrent HashMap for Rust.

  • TinySet provides a few collections that are optimized to scale in size well for small numbers of elements, while still scaling well in time (and size) for numbers of elements.

  • schnellru is a fast and flexible LRU map.

Graph

References

Contiguous Data in Rust https://github.com/paulkernfeld/contiguous-data-in-rust

Comments