Common Collections in Rust

In Rust, standard collections allow developers to store multiple values within a single data structure. Unlike primitive arrays ([T; N]) or tuples ((T, U)), which are stored on the stack with fixed sizes determined at compile time, collections are allocated on the heap. This allows their contents to dynamically grow or shrink at runtime.

This guide covers Rust's three primary collections: Vectors (Vec<T>), Strings (String), and Hash Maps (HashMap<K, V>), detailing their internal memory architectures, ownership semantics, and safe access patterns.

1. Introduction to Collections: Heap Allocation vs. Stack

Primitive types like arrays and tuples have fixed lengths known at compile time, allowing Rust to place them directly onto the call stack. Collections, however, manage dynamic amounts of data. To support runtime resizing, collections allocate memory on the heap.

Key Differences:

• Arrays ([T; N]): Fixed size, stack-allocated, compile-time size check.
• Collections (Vec<T>, String, HashMap<K, V>): Dynamic size, heap-allocated, runtime reallocations.

2. Vectors (Vec<T>): Initialization and Memory Layout

A vector (Vec<T>) stores items of the same type T in contiguous heap memory.

Creating Vectors

You can construct a vector using explicit type annotations with Vec::new(), or through Rust's inferencing via the vec! macro:

fn main() {
    // Creating an empty vector requires type annotations because no elements exist to infer type T
    let mut v: Vec<i32> = Vec::new();

    // Appending elements
    v.push(1);
    v.push(2);
    v.push(3);

    // Initializing a vector with starting values using the vec! macro
    let v2 = vec![1, 2, 3, 4, 5]; // Rust infers type Vec<i32>
}

Vector Scope and Deallocation

Like any heap-allocated resource in Rust, a vector owns its elements. When a vector variable goes out of scope, Rust automatically calls its cleanup logic (Drop), freeing both the vector metadata and all elements stored within it.

{
    let v2 = vec![1, 2, 3, 4, 5];
    // Perform operations with v2
} 
// <- v2 goes out of scope here.
//    v2 and all contained elements are dropped and heap memory is freed immediately.

3. Element Access: Direct Indexing vs. Safe Get Operations

Rust provides two methods for reading elements inside a vector: Direct Indexing (&v[index]) and the Get Method (v.get(index)).

fn main() {
    let v = vec![10, 20, 30, 40, 50];

    // Method 1: Direct Indexing (Panics on out-of-bounds)
    let third: &i32 = &v[2];
    println!("The third element is {}", third);

    // Method 2: Safe Access with .get() (Returns Option<&T>)
    match v.get(2) {
        Some(third_element) => println!("The third element is {}", third_element),
        None => println!("There is no third element."),
    }
}

Direct Indexing vs. get() Method

Note: Arrays produce compile-time errors for out-of-bounds access with literal indices because their size is fixed in the type system. Vectors, being dynamic heap arrays, can only perform index checks at runtime.

4. Borrow Checker & Memory Reallocation Pitfalls

Rust’s ownership rules strictly enforce that you cannot have a mutable reference and an immutable reference to the same data in the same scope. This safety guarantee is crucial for vectors due to heap reallocation.

The Reallocation Hazard

When a new element is appended to a vector using .push(), the vector may exceed its current allocation capacity. To accommodate new elements, the vector must:

1. Request a larger block of memory from the heap allocator.
2. Copy/move existing elements to the new heap address.
3. Deallocate the old memory block.

Preventing Dangling Pointers with the Borrow Checker

If Rust permitted an immutable reference (&v[0]) to coexist with a call to v.push(), reallocation could leave that immutable reference pointing to deallocated memory.

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];

    let first = &v[0]; // Immutable borrow created here

    v.push(6); // ERROR: Cannot borrow `v` as mutable because it is already borrowed as immutable!

    println!("The first element is: {}", first); // Immutable borrow used here
}

To fix this issue, ensure the immutable reference's scope ends before mutating the vector:

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];

    let first = v[0]; // Copy the primitive value rather than holding a reference
    v.push(6);        // Mutating v is now safe
    println!("First: {}", first);
}

5. Iterating and Mutating Vector Elements

To sequentially process elements, use a for loop to borrow the vector immutably or mutably.

Immutable Iteration

To read every element without modifying the vector:

fn main() {
    let v = vec![100, 32, 57];
    for element in &v {
        println!("{}", element); // element is of type &i32
    }
}

Mutable Iteration and Dereferencing

To modify elements in place, iterate over mutable references (&mut v). You must explicitly use the dereference operator (*) to access and modify the value underlying the reference:

fn main() {
    let mut v = vec![100, 32, 57];

    for element in &mut v {
        // *element unwraps the reference to allow direct mutation of the heap value
        *element += 50; 
    }

    for element in &v {
        println!("{}", element); // Prints: 150, 82, 107
    }
}

6. Heterogeneous Vectors via Enum Wrapping

By design, a Vec<T> can only hold elements of a single type T. When you need to store multiple types in a single vector, you can wrap those types in an enum.

Real-Life Analogy: Spreadsheet Cells

A single column in a spreadsheet can store distinct data formats—such as integers, floating-point numbers, or text strings—while still belonging to the same grid layout.

enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}

fn main() {
    // The vector type is Vec<SpreadsheetCell>, maintaining homomorphy for Rust
    let row = vec![
        SpreadsheetCell::Int(3),
        SpreadsheetCell::Float(10.12),
        SpreadsheetCell::Text(String::from("blue")),
    ];

    // Extracting heterogeneous values using pattern matching
    match &row[1] {
        SpreadsheetCell::Int(i) => println!("Integer: {}", i),
        SpreadsheetCell::Float(f) => println!("Float: {}", f),
        SpreadsheetCell::Text(s) => println!("Text: {}", s),
    }
}

7. Deep Dive into Strings: UTF-8 Encodings and Memory Representations

In high-level languages, strings are abstracted away as simple sequences of characters. In Rust, as a systems programming language, string internals are explicitly exposed.

A String in Rust is a wrapper around a byte vector (Vec<u8>) guaranteed to contain valid UTF-8 encoded data.

Historical Context & Character Encodings

1. ASCII: Uses 7 bits of a single byte to represent 128 unique symbols. It only supports basic English letters, numbers, and basic commands.
2. National Code Pages: Other regions created 8-bit encodings for foreign alphabets, causing byte parsing conflicts when sharing text globally.
3. Unicode: A universal character set standardizing over 140,000 characters (including modern scripts and emojis). Unicode is backward-compatible with ASCII (the first 128 symbols are identical).
4. UTF-8: The standard variable-width encoding for Unicode. A single character can be represented using 1, 2, 3, or 4 bytes.

8. String Manipulation: Appending and Concatenation Strategies

Rust provides several methods to construct, extend, and combine strings.

Creating Strings

fn main() {
    let mut s1 = String::new(); // Empty owned string
    
    let data = "initial contents"; // String slice (&str)
    let s2 = data.to_string();    // Converts &str to owned String
    
    let s3 = String::from("initial contents"); // Direct instantiation
}

Appending to Strings

• push_str(&str) appends a string slice without taking ownership.
• push(char) appends a single primitive char.

fn main() {
    let mut s = String::from("foo");
    s.push_str("bar"); // s is now "foobar"

    let suffix = "!";
    s.push_str(suffix); // suffix is borrowed, remaining valid afterward

    s.push('a'); // Appends a single char
    println!("{}", s); // Prints: foobar!a
}

Concatenation: + Operator vs. format! Macro

Combining strings with the + operator invokes Rust's add method, which transfers ownership of the left-hand operand:

// Trait signature implemented under the hood:
// fn add(self, s: &str) -> String

fn main() {
    let s1 = String::from("Hello, ");
    let s2 = String::from("world!");

    // s1 is moved here and can no longer be used!
    // s2 is coerced from &String into &str automatically via Deref coercion.
    let s3 = s1 + &s2; 

    // println!("{}", s1); // ERROR: Value used after move!
    println!("{}", s3);    // Hello, world!

    // Concatenating multiple strings safely without losing ownership using format!
    let st1 = String::from("tic");
    let st2 = String::from("tac");
    let st3 = String::from("toe");

    // format! borrows all parameters and returns a new owned String
    let s_all = format!("{}-{}-{}", st1, st2, st3);
    println!("{}", s_all); // tic-tac-toe
    println!("{}", st1);   // st1 remains valid!
}

9. String Indexing Breakdown: Bytes, Chars, and Grapheme Clusters

In Rust, direct indexing on a String (s[0]) is forbidden at compile time.

Why Direct Indexing Is Prohibited

Because UTF-8 is a variable-width encoding, direct integer indexing creates dangerous ambiguities.

Consider the Russian word "Здравствуйте":

• Number of visual characters: 12
• Byte size in UTF-8: 24 bytes

If s[0] were allowed, Rust would return the first raw byte (208), which is only half of the two-byte encoding for the first character 'З'. Returning half a character violates string safety invariants.

The Three Unicode Perspectives

To inspect strings accurately, you must choose the appropriate representation level:

Code Demonstration: Iterating String Representations

use unicode_segmentation::UnicodeSegmentation; // Added to Cargo.toml

fn main() {
    let hindi_word = "नमस्ते";

    // 1. Raw Bytes
    print!("Bytes: ");
    for b in hindi_word.bytes() {
        print!("{} ", b);
    }
    println!();

    // 2. Chars (Unicode Scalar Values)
    print!("Chars: ");
    for c in hindi_word.chars() {
        print!("'{}' ", c);
    }
    println!();

    // 3. Grapheme Clusters (Extended)
    print!("Graphemes: ");
    for g in hindi_word.graphemes(true) {
        print!("\"{}\" ", g);
    }
    println!();
}

Cargo Dependencies Setup (Cargo.toml):

[dependencies]
unicode-segmentation = "1.10.0"

10. Hash Maps (HashMap<K, V>): Setup and Ownership Transfer

A HashMap<K, V> stores key-value pairs using a hashing function to map keys to memory slots.

Basic Initialization and Insertion

HashMap is not included in Rust's standard prelude, so it must be explicitly imported from std::collections:

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();

    // Inserting key-value pairs
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}

Ownership Transfer Semantics

Types that implement the Copy trait (like i32) are copied into the hash map. Types that own heap memory (like String) are moved, transferring ownership to the hash map.

use std::collections::HashMap;

fn main() {
    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");

    let mut map = HashMap::new();
    map.insert(field_name, field_value);

    // field_name and field_value are moved into the map here.
    // Calling println!("{}", field_name); will trigger a COMPILE ERROR!
}

Note: If you insert references into a hash map instead of owned values, those references must remain valid for the entire lifetime of the hash map (enforced via lifetime annotations).

11. Hash Map Insertion, Overwriting, and Entry API

Rust provides flexible control over how values are inserted or updated based on existing keys.

1. Overwriting Existing Keys

Calling .insert() with an existing key replaces its old value:

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25); // Overwrites 10 with 25

    println!("{:?}", scores); // Prints: {"Blue": 25}
}

2. Inserting Only If Key Is Absent (entry API)

The entry API checks if a key exists before inserting a value:

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    // Entry returns an enum representing the state of the key
    // .or_insert() appends the value ONLY if the key is vacant
    scores.entry(String::from("Yellow")).or_insert(50); // Inserts Yellow: 50
    scores.entry(String::from("Blue")).or_insert(50);   // Blue exists; ignored

    println!("{:?}", scores); // Prints: {"Blue": 10, "Yellow": 50}
}

Accessing Values Safely

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    let team_name = String::from("Blue");
    
    // .get() returns Option<&V>
    let score: Option<&i32> = scores.get(&team_name); 

    match score {
        Some(s) => println!("Score: {}", s),
        None => println!("Team not found"),
    }

    // Iterating over key-value pairs
    for (key, value) in &scores {
        println!("{}: {}", key, value);
    }
}

12. Advanced Hash Map Workflows: In-Place Frequency Counters

A common pattern is looking up a key, inserting a default value if missing, and updating the existing value based on its previous state.

Word Counter Workflow

The .or_insert() method returns a mutable reference (&mut V) to the value associated with the key. You can then dereference and modify this value in place.

use std::collections::HashMap;

fn main() {
    let text = "hello world wonderful world";
    let mut map = HashMap::new();

    for word in text.split_whitespace() {
        // 1. map.entry(word) inspects if the key exists
        // 2. .or_insert(0) returns a &mut i32 pointing to the existing or newly created value
        let count: &mut i32 = map.entry(word).or_insert(0);

        // 3. Dereference count to increment the value in place
        *count += 1;
    }

    println!("{:?}", map);
    // Prints: {"hello": 1, "world": 2, "wonderful": 1}
}

Entry Pipeline Execution

Summary and Key Takeaways

• Dynamic Heap Storage: Vectors, Strings, and Hash Maps store variable-length data on the heap and automatically clean up their memory via Drop when going out of scope.
• Vector Safety: Use v.get(index) instead of direct indexing (&v[index]) to safely handle out-of-bounds indices with an Option<&T> without crashing your application.
• Reallocation Borrow Rules: Modifying a vector (e.g., calling v.push()) can trigger heap reallocation, invalidating existing references. Rust prevents these memory safety errors at compile time.
• Heterogeneous Collections: Wrap different types within enum variants to store mixed data structures inside a single Vec<T>.
• String Encodings: Rust strings (String and &str) are strict UTF-8 encoded byte sequences (Vec<u8>). Characters can span anywhere from 1 to 4 bytes.
• Direct String Indexing Is Prohibited: Rust disallows integer indexing like s[0] on strings to prevent partial-byte corruption. Use .bytes(), .chars(), or the unicode-segmentation crate to inspect strings safely.
• String Concatenation Rules: The + operator moves ownership of the left-hand string operand, whereas the format! macro operates nondestructively by borrowing its arguments.
• Hash Map Ownership: Inserting owned values (like String) into a HashMap transfers ownership into the collection unless references with explicit lifetimes are used.
• The Entry API Pattern: Use map.entry(key).or_insert(default_value) to simplify inserting defaults or mutating values in place. This method returns a dereferencable mutable reference (&mut V).