Rust Data Structures Guide: Vectors, HashMaps, Sets, and More

The Rust standard library provides fundamental data structures such as Vectors (Vec<T>), Hash Maps (HashMap<K, V>), and Hash Sets (HashSet<T>). These three data structures are the most commonly used and useful in most programming scenarios. Their design aligns with Rust’s goals of offering a safe, concurrent, and practical programming language. These structures cover most data storage and access needs while maintaining the lightweight and efficient nature of Rust’s standard library.

Vectors (Vec<T>)

A vector is Rust’s most commonly used dynamic array implementation. It provides fast indexed access, dynamic resizing, and efficient traversal due to its contiguous memory storage, which leverages modern CPU caching mechanisms.

fn main() {
    // Create an empty vector
    let mut numbers: Vec<i32> = Vec::new();

    // Create and initialize a vector using a macro
    let mut names = vec!["Alice", "Bob", "Carol"];

    // Add elements to the vector
    numbers.push(1);
    numbers.push(2);
    numbers.push(3);

    // Remove elements from the vector
    numbers.pop(); // Removes and returns the last element

    // Access elements in the vector
    if let Some(first_name) = names.get(0) {
        println!("The first name is: {}", first_name);
    }

    // Iterate through vector elements
    for name in &names {
        println!("{}", name);
    }

    // Modify elements in the vector
    if let Some(first_name) = names.get_mut(0) {
        *first_name = "Dave";
    }

    // Use an iterator to process vector elements
    let numbers_squared: Vec<i32> = numbers.iter().map(|&x| x * x).collect();
    println!("Squared numbers: {:?}", numbers_squared);

    // Extend the vector with additional elements
    numbers.extend([4, 5, 6].iter().copied());

    // Directly access elements using an index
    println!("Second name: {}", names[1]); // Note: Direct indexing may panic
}

Vectors are ideal for handling sequences of elements of the same type, whether they are strings, integers, or custom types. They allow easy element addition, removal, and random access.

Hash Maps (HashMap<K, V>)

A hash map provides key-value storage implemented using a hash table. It supports fast lookup, insertion, and deletion, making it a critical data structure for efficient data retrieval and management.

use std::collections::HashMap;

fn main() {
    // Create an empty hash map
    let mut book_reviews: HashMap<String, String> = HashMap::new();

    // Add elements to the hash map
    book_reviews.insert("The Hobbit".to_string(), "Excellent fantasy book".to_string());
    book_reviews.insert("The Catcher in the Rye".to_string(), "Classic novel".to_string());

    // Access elements in the hash map
    if let Some(review) = book_reviews.get("The Hobbit") {
        println!("Review of The Hobbit: {}", review);
    }

    // Remove elements from the hash map
    book_reviews.remove("The Catcher in the Rye");

    // Iterate over the hash map
    for (book, review) in &book_reviews {
        println!("{}: {}", book, review);
    }

    // Update elements in the hash map
    book_reviews.entry("The Hobbit".to_string()).or_insert("No review found".to_string());
    book_reviews.entry("1984".to_string()).or_insert("Dystopian science fiction".to_string());

    let mut scores = HashMap::new();

    // Insert directly using `insert`
    scores.insert("Blue", 10);
    scores.insert("Blue", 25); // Overwrites the previous value

    // Use `entry` to update or insert
    scores.entry("Yellow").or_insert(50); // Inserts because "Yellow" does not exist
    scores.entry("Blue").or_insert(50);   // Does nothing because "Blue" already exists

    // Result: {"Blue": 25, "Yellow": 50}

    // Check if a key exists
    if book_reviews.contains_key("1984") {
        println!("Review for 1984 is available.");
    }
}

Hash maps are useful when you need to access data quickly using keys, such as in database indexing and cache implementations. They offer flexible key-value associations, making data organization and retrieval simple and efficient.

Hash Sets (HashSet<T>)

A hash set is an unordered collection that stores unique elements. It is implemented using a hash table, providing fast lookup, insertion, and deletion operations.

use std::collections::HashSet;

fn main() {
    // Create an empty set
    let mut numbers = HashSet::new();

    // Add elements to the set
    numbers.insert(1);
    numbers.insert(2);
    numbers.insert(3);

    // Remove an element from the set
    numbers.remove(&3);

    // Check if an element exists in the set
    if numbers.contains(&1) {
        println!("1 is in the set");
    }

    // Iterate over the set
    for number in &numbers {
        println!("{}", number);
    }

    // Set operations: union, intersection, difference, symmetric difference

    // At this point, numbers contain {1, 2}

    let other_numbers = [2, 3, 4].iter().cloned().collect::<HashSet<_>>();
    // other_numbers contain {2, 3, 4}

    let union = numbers.union(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Union: {:?}", union);
    // Union: `{1, 2, 3, 4}` (all unique elements from both sets)

    let intersection = numbers.intersection(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Intersection: {:?}", intersection);
    // Intersection: `{2}` (common elements)

    let difference = numbers.difference(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Difference: {:?}", difference);
    // Difference: `{1}` (elements in `numbers` but not in `other_numbers`)

    let symmetric_difference = numbers.symmetric_difference(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Symmetric Difference: {:?}", symmetric_difference);
    // Symmetric Difference: `{1, 3, 4}` (elements unique to each set)
}

Hash sets are particularly useful for handling collections of unique elements, such as user ID lists and records under specific conditions. Set operations like union, intersection, and difference provide powerful tools for handling collection data efficiently.

Doubly Linked List (LinkedList<T>)

LinkedList<T> is a doubly linked list provided by Rust’s standard library. Compared to vectors (Vec<T>), linked lists allow efficient insertion and deletion of elements, especially at the beginning or end of the list. However, they perform poorly in random access.

use std::collections::LinkedList;

fn main() {
    // Create a new empty linked list
    let mut list: LinkedList<i32> = LinkedList::new();

    // Add elements to the back of the list
    list.push_back(1);
    list.push_back(2);

    // Add elements to the front of the list
    list.push_front(0);

    // Pop elements from the front and back of the list
    assert_eq!(list.pop_front(), Some(0));
    assert_eq!(list.pop_back(), Some(2));

    // Iterate over the list
    for elem in list.iter() {
        println!("{}", elem);
    }

    // Modify elements in the list (requires using an iterator)
    let mut iter_mut = list.iter_mut();
    if let Some(first_elem) = iter_mut.next() {
        *first_elem = 3;
    }

    // Print the modified list
    println!("Modified list: {:?}", list);
}

When frequent additions or deletions at the beginning or end of a list are required, LinkedList is a good choice, as these operations have a time complexity of O(1).

If your application rarely needs random access and focuses more on sequential traversal, a linked list might be a better option than a vector.

B-Tree Map (BTreeMap<K, V>)

BTreeMap<K, V> is a key-value collection implemented using a B-tree. It maintains keys in a sorted order. Compared to hash maps (HashMap<K, V>), BTreeMap excels when ordered keys, range lookups, or ordered traversals are needed.

use std::collections::BTreeMap;

fn main() {
    // Create a new empty BTreeMap
    let mut map: BTreeMap<String, i32> = BTreeMap::new();

    // Insert key-value pairs into the BTreeMap
    map.insert("apple".to_string(), 3);
    map.insert("banana".to_string(), 2);
    map.insert("pear".to_string(), 4);

    // Retrieve the value corresponding to a key
    if let Some(v) = map.get("apple") {
        println!("apple: {}", v);
    }

    // Remove a key-value pair
    map.remove("banana");

    // Iterate over the BTreeMap
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }

    // Range query: get all key-value pairs with keys between "apple" and "pear" (inclusive)
    let range = map.range("apple".to_string()..="pear".to_string());
    for (key, value) in range {
        println!("Range query: {}: {}", key, value);
    }
}

BTreeMap is a good option when an automatically sorted map is needed, especially useful for range queries and ordered traversal.

If your program frequently performs lookup, insertion, and deletion operations where keys are naturally ordered, BTreeMap can be more suitable than HashMap as it maintains the order of keys, facilitating range lookups and ordered traversal.

B-Tree Set (BTreeSet<T>)

BTreeSet<T> is a set implemented based on a B-tree. It stores unique elements and maintains them in a sorted order. Compared to HashSet<T>, BTreeSet supports ordered operations and range queries but may be slower for some operations.

use std::collections::BTreeSet;

fn main() {
    // Create a new empty BTreeSet
    let mut set: BTreeSet<i32> = BTreeSet::new();

    // Add elements to the set
    set.insert(12);
    set.insert(5);
    set.insert(18);

    // Check if an element exists
    if set.contains(&12) {
        println!("Set contains 12");
    }

    // Remove an element
    set.remove(&5);

    // Iterate over the set (elements will be in ascending order)
    for num in &set {
        println!("{}", num);
    }

    // Range query: retrieve all elements greater than or equal to 10 and less than 20
    for num in set.range(10..20) {
        println!("Range query: {}", num);
    }
}

BTreeSet is a good choice when you need an ordered set for quick lookups, range queries, or ordered traversal.

It is suitable for scenarios where unique elements need to be stored, and the elements have a comparable relationship.

Binary Heap (BinaryHeap<T>)

BinaryHeap<T> is an implementation of a priority queue based on a binary heap. It allows fast insertion of elements and removal of the maximum (or minimum) element, depending on whether it is a max-heap or min-heap. By default, Rust's BinaryHeap is a max-heap.

use std::collections::BinaryHeap;

fn main() {
    // Create a new empty BinaryHeap
    let mut heap = BinaryHeap::new();

    // Add elements to the heap
    heap.push(1);
    heap.push(5);
    heap.push(2);

    // Peek at the maximum element in the heap without removing it
    if let Some(max) = heap.peek() {
        println!("Max element: {}", max);
    }

    // Remove and return the maximum element
    println!("Removed max element: {}", heap.pop().unwrap());

    // Iterate over the heap (the order of iteration is not sorted)
    for num in &heap {
        println!("{}", num);
    }
}

When a data structure is needed for quick access to and removal of the maximum (or minimum) element, BinaryHeap is ideal. This is especially useful in algorithms like Dijkstra's shortest path.

BinaryHeap is suitable for task scheduling, greedy algorithms, or any scenario requiring a priority queue.

---

We are Leapcell, your top choice for hosting Rust projects.

Leapcell is the Next-Gen Serverless Platform for Web Hosting, Async Tasks, and Redis:

Multi-Language Support

• Develop with Node.js, Python, Go, or Rust.

Deploy unlimited projects for free

• pay only for usage — no requests, no charges.

Unbeatable Cost Efficiency

• Pay-as-you-go with no idle charges.
• Example: $25 supports 6.94M requests at a 60ms average response time.

Streamlined Developer Experience

• Intuitive UI for effortless setup.
• Fully automated CI/CD pipelines and GitOps integration.
• Real-time metrics and logging for actionable insights.

Effortless Scalability and High Performance

• Auto-scaling to handle high concurrency with ease.
• Zero operational overhead — just focus on building.

Explore more in the Documentation!

Follow us on X: @LeapcellHQ