Data Structures

cat-data-structures

Common data structures include arrays and vectors, which are contiguous block of memory that stores elements of the same data type; linked lists (sequences of nodes, where each node contains data and a pointer to the next node); stacks ("last-in, first-out" (LIFO) data structures); queues ("first-in, first-out" (FIFO) data structures); trees (hierarchical data structures consisting of nodes with parent-child relationships); sets (collections of unique elements); and maps (aka dictionaries, which store key-value pairs).

Standard library collections (in std::collections) include:

  • Vec<T> (Vector) is a dynamic array that can grow or shrink as needed. It's the most commonly used collection in Rust and is similar to a dynamic array or list in other languages. Provides fast access by index.
  • String is a growable, UTF-8 encoded string. It's a fundamental data structure for working with text.
  • HashMap<K, V> (Hash Map) stores key-value pairs, allowing for efficient lookup of values based on their keys. Uses a hash function for fast average-case access.
  • BTreeMap<K, V> (B-Tree Map) is similar to HashMap, but it keeps the keys sorted. Provides ordered access to key-value pairs.
  • HashSet<T> (Hash Set) stores a collection of unique elements. Used for efficiently checking membership and ensuring uniqueness.
  • BTreeSet<T> (B-Tree Set) is similar to HashSet, but it keeps the elements sorted.
  • LinkedList<T> is a doubly linked list. Useful for frequent insertions and deletions at arbitrary positions, but less efficient for random access.
  • VecDeque<T> (Vector Deque) is a double-ended queue. Allows efficient insertion and deletion at both ends.
  • BinaryHeap<T> is a binary heap, often used to implement a priority queue.

Vectors and Arrays

See Vectors.

Stack-allocated Arrays

RecipeCratesCategories
arrayvecarrayveccat-data-structures
smallvecsmallveccat-data-structures
tinyvectinyveccat-data-structures

Strings

See Strings.

Hashmaps and Friends

See Hashmaps.

RecipeCratesCategories
Store Data in an Insertion-ordered Mapindexmapcat-data-structures
Store Data in a multimapmultimapcat-data-structures
Store Collections of Objects that Need Stable, Safe Referencesslotmapcat-data-structures

BTreeMap and BTreeSet

RecipeCratesCategories
BTreeMap<K, V>stdcat-data-structures
BTreeSet<T>stdcat-data-structures

Stacks and Queues

RecipeCratesCategories
Implement a Queue Using VecDequecat-data-structures
Implement a Stack Using Veccat-data-structures

Bitflags

RecipeCratesCategories
Define and Operate on a Type Represented as a Bitfieldbitflagscat-data-structures cat-no-std
flagsetflagsetcat-data-structures
bitvecbitveccat-data-structures

Binary Heaps / Priority Queues

RecipeCratesCategories
priority-queuestdcat-data-structures

UUIDs

RecipeCratesCategories
Generate and Parse UUIDsuuidcat-data-structures

Heapless Data Structures

RecipeCratesCategories
Heaplessstdcat-data-structures

Additional Data Structures

  • Simple Data Types.
  • Smart Pointers.
  • Immutable Data Structures: im⮳, rpds⮳.
  • Specialized Data Structures:
    • Graphs: petgraph⮳, graph_rs⮳.
    • Trees and Tries: indextree⮳, rayon-trie.
    • Bloom Filters: bloomfilter⮳.
    • Skip Lists: skiplist⮳.
    • Ranges as keys: rangemap⮳ stores key-value pairs where keys are ranges.
    • Matrices and Tensors: ndarray⮳ provides an n-dimensional array for numerical computation.
    • Dataframes.
    • Concurrent Data Structures.
    • Bitsets: roaring⮳ implements compressed bitsets.
  • Serialization / Deserialization.