From Vectors to HashSets: Navigating Rust's Data Structures

Explore Rust's core data structures, including Vectors, HashSets, and more, to write efficient and safe code.

The Rust standard library provides fundamental data structures such as Vectors ( Vec ), Hash Maps ( HashMap ), and Hash Sets ( HashSet ). 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 )

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 = 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 = 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 )

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 = 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 )

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 

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

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

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

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

 let symmetric_difference = numbers.symmetric_difference(&other_numbers).cloned().collect::>();
 println!("Symmetric Difference: {:?}", symmetric_difference);
 // Symmetric Difference: `` (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 )

LinkedList is a doubly linked list provided by Rust’s standard library. Compared to vectors ( Vec ), 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 = 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 )

BTreeMap is a key-value collection implemented using a B-tree. It maintains keys in a sorted order. Compared to hash maps ( HashMap ), 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 = 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 )

BTreeSet is a set implemented based on a B-tree. It stores unique elements and maintains them in a sorted order. Compared to HashSet , 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 = 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 )

BinaryHeap 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.