RUST: Data Structures

I. Primitive Types (Built-in)

These are the fundamental building blocks.

1. Integer Types:
   • Signed: i8, i16, i32, i64, i128 (fixed-size), isize (pointer-sized)
   • Unsigned: u8, u16, u32, u64, u128 (fixed-size), usize (pointer-sized, often used for indexing)
2. Floating-Point Types:
   • f32 (single-precision)
   • f64 (double-precision)
3. Boolean Type:
   • bool: Represents true or false.
4. Character Type:
   • char: Represents a single Unicode scalar value (4 bytes).

II. Compound Types (Built-in)

These group other values together.

1. Tuples:
   • (T1, T2, …): Fixed-size, ordered list where each element can have a different type. Accessed by index (e.g., my_tuple.0). Useful for returning multiple values from functions.
   • Example: (i32, f64, bool)
2. Arrays:
   • [T; N]: Fixed-size list where all elements must have the same type T. N is the size, known at compile time. Usually allocated on the stack. Accessed by index (e.g., my_array[0]).
   • Example: [i32; 5] (an array of 5 integers)

III. Standard Library Collections (std::collections)

These are more flexible, often heap-allocated structures.

1. Vectors:
   • Vec<T>: A growable, contiguous list (dynamic array) where all elements have the same type T. Heap-allocated. The most common list/array type.
   • Use case: When you need a list of items whose size might change.
2. String & String Slices:
   • String: A growable, heap-allocated, UTF-8 encoded text string. Owned.
   • &str (string slice): A borrowed, immutable view into a UTF-8 encoded string (often part of a String or a string literal). Fixed size (for the slice itself).
   • Use case: String for storing and manipulating text you own, &str for passing references to text efficiently.
3. Hash Maps:
   • HashMap<K, V>: A collection of key-value pairs implemented using a hash table. Keys must be unique. Provides fast average-time insertion, deletion, and lookup (O(1)). Unordered.
   • Use case: Associative arrays, dictionaries, lookups by key when order doesn’t matter.
4. B-Tree Maps:
   • BTreeMap<K, V>: A collection of key-value pairs implemented using a B-Tree. Keys must be unique. Keeps keys sorted. Slower than HashMap for lookups (O(log n)) but allows efficient iteration in sorted order.
   • Use case: When you need key-value storage and need to iterate over keys in sorted order.
5. Hash Sets:
   • HashSet<T>: A collection of unique values implemented using a hash table (like the keys of a HashMap). Fast average-time insertion, deletion, and checking for containment (O(1)). Unordered.
   • Use case: Storing unique items, efficiently checking if an item exists in the set.
6. B-Tree Sets:
   • BTreeSet<T>: A collection of unique values implemented using a B-Tree (like the keys of a BTreeMap). Keeps values sorted. Slower than HashSet (O(log n)) but allows efficient iteration in sorted order.
   • Use case: Storing unique items when you need to iterate over them in sorted order.
7. Double-Ended Queue:
   • VecDeque<T>: A growable, queue-like structure (implemented as a ring buffer) allowing efficient addition and removal from both the front and back (O(1)).
   • Use case: Implementing queues, stacks, or when frequent insertions/removals at both ends are needed.
8. Linked List:
   • LinkedList<T>: A doubly-linked list. Efficient insertion/removal in the middle (O(1) if you have a cursor), but requires traversing for lookups (O(n)). Generally less performant than Vec or VecDeque in practice due to poor cache locality.
   • Use case: Specific algorithms that benefit from linked list properties (less common now).
9. Binary Heap:
   • BinaryHeap<T>: A max-heap priority queue. Allows efficiently adding elements and removing/peeking at the largest element (O(log n)).
   • Use case: Priority queues, scheduling, certain graph algorithms (like Dijkstra’s).

IV. User-Defined Types

You define these yourself using keywords.

1. Structs:
   • struct Name { field1: T1, field2: T2, … }: Defines a custom data structure with named fields. Each field can have a different type. Fixed structure defined at compile time.
   • Use case: Grouping related data together, representing objects or records (like database results!).
2. Enums:
   • enum Name { Variant1, Variant2(T), Variant3 { field: T }, … }: Defines a type that can be one of several possible variants. Variants can optionally hold associated data.
   • Use case: Representing states, choices, optional values (Option<T>), results (Result<T, E>), different kinds of messages, etc.

V. Slices (Borrowed Views)

1. Slices:
   • &[T] (shared slice), &mut [T] (mutable slice): A dynamically sized view into a contiguous sequence (like an array or Vec). Doesn’t own the data, just borrows it. Very efficient for passing parts of collections without copying.
   • Use case: Passing parts of arrays/vectors to functions, implementing views on data.

This list covers the most commonly encountered data structures. The choice of which one to use depends heavily on your specific requirements regarding mutability, ownership, ordering, performance characteristics (lookup vs. insertion speed), and whether the size is fixed or dynamic. For database results, structs (often collected in a Vec<YourStruct>) are usually the most idiomatic and recommended approach when the structure is known.