Diving Into Rust’s Built-in Collections

Rust, known for its focus on safety, performance, and ergonomics, provides a rich set of built-in collections to manage groups of data. Collections are essential for tasks like storing dynamic lists, mapping keys to values, or handling ordered sequences. Unlike primitive types (e.g., i32, bool), collections are heap-allocated (storing data on the heap rather than the stack) and can dynamically grow or shrink.

In this blog, we’ll explore Rust’s core collections, their use cases, APIs, and best practices. Whether you’re a beginner or looking to deepen your Rust knowledge, this guide will help you navigate the world of Rust collections with confidence.

Table of Contents

1. Introduction to Rust Collections
2. Core Collections
   • Vectors (Vec<T>): Dynamic Arrays
   • Strings (String and &str): UTF-8 Text
   • Hash Maps (HashMap<K, V>): Key-Value Storage
3. Other Notable Collections
   • BTreeMap and BTreeSet: Sorted Data
   • VecDeque: Double-Ended Queues
   • HashSet: Unordered Unique Elements
4. Choosing the Right Collection
5. Best Practices
6. Conclusion
7. References

Core Collections

Vectors (Vec<T>): Dynamic Arrays

A Vec<T> (pronounced “vector”) is Rust’s most basic sequence collection. It stores a contiguous, growable array of elements on the heap, making it ideal for dynamic lists where the size may change.

Key Features:

• Dynamic sizing: Grows/shrinks as elements are added/removed.
• Contiguous memory: Fast random access (O(1) time complexity).
• Amortized growth: Resizes efficiently by doubling capacity when full (minimizing reallocations).

Creating a Vector

Use Vec::new() for an empty vector, or the vec! macro for initialization with values:

// Empty vector
let mut numbers: Vec<i32> = Vec::new();

// Vector with initial values (type inferred)
let fruits = vec!["apple", "banana", "cherry"]; // Vec<&str>

Modifying a Vector

Add elements with push(), remove the last element with pop() (returns Option<T>), or insert/remove at arbitrary indices with insert()/remove() (O(n) time for non-end indices):

let mut numbers = vec![1, 2, 3];
numbers.push(4); // numbers = [1, 2, 3, 4]

let last = numbers.pop(); // last = Some(4), numbers = [1, 2, 3]

numbers.insert(1, 10); // numbers = [1, 10, 2, 3] (inserts at index 1)
numbers.remove(2); // numbers = [1, 10, 3] (removes element at index 2)

Accessing Elements

Access elements with:

• []: Panics if the index is out of bounds (use for known-valid indices).
• get(index): Returns Option<&T> (safer for dynamic indices).

let numbers = vec![10, 20, 30];

// Unsafe (panics if index is invalid)
let first = numbers[0]; // first = 10

// Safe (returns None if index is invalid)
let second = numbers.get(1); // second = Some(20)
let tenth = numbers.get(9); // tenth = None

Iterating Over Elements

Iterate over elements with for loops. Use mutable iterators (iter_mut()) to modify elements:

let mut numbers = vec![1, 2, 3];

// Immutable iteration
for num in &numbers {
    println!("{}", num); // 1, 2, 3
}

// Mutable iteration (modify elements)
for num in numbers.iter_mut() {
    *num *= 2; // Double each element
}
println!("{:?}", numbers); // [2, 4, 6]

Strings: String and &str

Rust has two primary string types:

• &str: A borrowed string slice (view into a UTF-8 encoded string, stack-allocated metadata, heap-allocated data).
• String: An owned, growable UTF-8 string (heap-allocated, managed by Rust’s ownership system).

Key Features:

• UTF-8 Encoding: All Rust strings are valid UTF-8, ensuring compatibility with global text.
• Ownership: String is owned (you control its lifetime), while &str is borrowed (depends on another owner).

Creating Strings

Create Strings with String::new(), to_string(), or String::from():

// Empty string
let mut hello = String::new();
hello.push_str("Hello"); // hello = "Hello"

// From a string literal (&str)
let world = "world".to_string(); // world = "world"
let rust = String::from("Rust"); // rust = "Rust"

Modifying Strings

Use push() (add a single char), push_str() (add a &str), or the + operator (concatenate, takes ownership of the left operand):

let mut message = String::from("Hello");
message.push(' '); // Add a space: "Hello "
message.push_str("World!"); // "Hello World!"

// Concatenation with + (left operand is consumed)
let part1 = String::from("Hello");
let part2 = String::from(" World");
let full = part1 + &part2; // full = "Hello World", part1 is now invalid

Accessing Characters

Rust strings cannot be indexed directly (e.g., s[0]) because UTF-8 characters can span multiple bytes. Instead, use:

• chars(): Iterate over Unicode scalar values (e.g., 'A', 'ñ', '😀').
• bytes(): Iterate over raw bytes (useful for low-level operations).

let s = String::from("café"); // "café" is 4 characters, 5 bytes (é = 2 bytes)

// Iterate over Unicode scalar values (chars)
for c in s.chars() {
    println!("{}", c); // c, a, f, é
}

// Iterate over bytes
for b in s.bytes() {
    println!("{}", b); // 99, 97, 102, 195, 169 (é is 0xC3 0xA9 in UTF-8)
}

Hash Maps (HashMap<K, V>): Key-Value Storage

HashMap<K, V> (from std::collections) stores key-value pairs with O(1) average time complexity for insertions, deletions, and lookups. It uses hashing to map keys to indices, making it ideal for unordered data.

Key Features:

• Unordered: Keys are not stored in insertion order (use BTreeMap for ordered data).
• Hashing Requirements: Keys must implement Hash and Eq (or PartialEq with caution).
• Entry API: Safely insert/update values with minimal overhead.

Creating Hash Maps

Import HashMap first, then initialize with HashMap::new() or collect() from an iterator:

use std::collections::HashMap;

// Empty hash map
let mut scores = HashMap::new();

// Insert key-value pairs
scores.insert(String::from("Alice"), 95);
scores.insert(String::from("Bob"), 85);

// Collect from an iterator of tuples
let teams = vec![String::from("Blue"), String::from("Yellow")];
let initial_scores = vec![10, 50];
let mut team_scores: HashMap<_, _> = teams.into_iter().zip(initial_scores.into_iter()).collect();
// team_scores = {"Blue": 10, "Yellow": 50} (order not guaranteed)

Accessing Values

Use get(&key) to retrieve an Option<&V>, or the entry API to insert/update values conditionally:

let scores = HashMap::from([("Alice", 95), ("Bob", 85)]);

// Get a value (returns Option<&V>)
let alice_score = scores.get("Alice"); // Some(95)
let charlie_score = scores.get("Charlie"); // None

// Entry API: Insert if key doesn't exist
let mut counts = HashMap::new();
let word = "hello";
*counts.entry(word).or_insert(0) += 1; // counts = {"hello": 1}

Updating Values

Overwrite existing keys with insert(), or update in-place with mutable references:

let mut scores = HashMap::from([("Alice", 95)]);
scores.insert("Alice", 100); // Overwrites: {"Alice": 100}

// Update based on current value
let mut points = HashMap::from([("Game", 0)]);
if let Some(val) = points.get_mut("Game") {
    *val += 10; // points = {"Game": 10}
}

Other Notable Collections

BTreeMap and BTreeSet: Sorted Data

• BTreeMap<K, V>: A sorted key-value map (ordered by key). Uses a B-tree under the hood, enabling O(log n) operations and ordered iteration. Ideal for range queries (e.g., “find all keys between 10 and 20”).

  use std::collections::BTreeMap;
  let mut map = BTreeMap::new();
  map.insert(3, "three");
  map.insert(1, "one");
  map.insert(2, "two");
  // Iteration is sorted: (1, "one"), (2, "two"), (3, "three")

• BTreeSet<T>: A sorted set (unique elements, ordered by value). Useful for maintaining a sorted collection with O(log n) insertions/lookups.

VecDeque: Double-Ended Queues

VecDeque<T> (from std::collections) is a double-ended queue optimized for fast insertions/deletions at both ends (O(1) time). Use it for queues, stacks, or sliding windows:

use std::collections::VecDeque;
let mut deque = VecDeque::new();
deque.push_back(1); // [1]
deque.push_front(0); // [0, 1]
deque.pop_back(); // [0]

HashSet: Unordered Unique Elements

HashSet<T> (from std::collections) is an unordered set of unique elements (no duplicates). It uses the same hashing logic as HashMap and is ideal for membership checks (e.g., “is this value in the set?“):

use std::collections::HashSet;
let mut fruits = HashSet::new();
fruits.insert("apple");
fruits.insert("banana");
fruits.insert("apple"); // Duplicate, ignored
assert!(fruits.contains("banana")); // true

Choosing the Right Collection

Best Practices

1. Prefer Vec Over LinkedList: LinkedList<T> has poor cache performance due to non-contiguous memory. Use VecDeque for queue-like behavior instead.
2. Use entry API for Hash Maps: Avoid redundant lookups when inserting/updating values (e.g., map.entry(key).or_insert(default)).
3. Borrow When Possible: Use &str instead of String for read-only text to avoid unnecessary allocations.
4. Handle UTF-8 Carefully: Use chars() or unicode-segmentation crate for grapheme cluster iteration (e.g., emojis, accented characters).
5. Avoid Over-Engineering: Start with Vec, String, or HashMap—they solve most problems. Only switch to specialized collections (e.g., BTreeMap) when needed.

Conclusion

Rust’s built-in collections are powerful tools for managing data efficiently and safely. By understanding their tradeoffs—contiguous memory for Vec, UTF-8 safety for String, and fast lookups for HashMap—you can write idiomatic, performant Rust code.

Whether you’re building a simple app or a complex system, choosing the right collection is critical. Refer to the Rust standard library docs for deeper dives into methods and edge cases.

References

• Rust Standard Library: Collections
• The Rust Programming Language Book: Collections
• Rust by Example: Collections
• Rust Performance Guide: Collections