Collections

Rust's standard library provides several collection types for storing multiple values. Each collection has different performance characteristics and use cases. Understanding these collections is essential for writing efficient Rust programs.

Vec<T> - Dynamic Arrays

Vec<T> is a growable array that stores elements of the same type in contiguous memory.

Creating and Initializing Vectors

fn main() {
    // Creating empty vectors
    let mut vec1: Vec<i32> = Vec::new();
    let mut vec2 = Vec::<i32>::new();
    let mut vec3 = vec![]; // Type will be inferred
    
    // Creating with initial values
    let vec4 = vec![1, 2, 3, 4, 5];
    let vec5 = vec![0; 5]; // [0, 0, 0, 0, 0]
    
    // Creating with capacity
    let mut vec6 = Vec::with_capacity(10);
    
    println!("vec4: {:?}", vec4);
    println!("vec5: {:?}", vec5);
    println!("vec6 capacity: {}", vec6.capacity());
}

Adding and Removing Elements

fn main() {
    let mut numbers = Vec::new();
    
    // Adding elements
    numbers.push(1);
    numbers.push(2);
    numbers.push(3);
    
    // Extending with another vector
    numbers.extend(vec![4, 5, 6]);
    
    // Inserting at specific position
    numbers.insert(0, 0); // Insert 0 at beginning
    
    println!("After additions: {:?}", numbers);
    
    // Removing elements
    let last = numbers.pop(); // Removes and returns last element
    println!("Popped: {:?}", last);
    
    let removed = numbers.remove(0); // Remove element at index 0
    println!("Removed: {}", removed);
    
    // Remove all elements matching a condition
    numbers.retain(|&x| x % 2 == 0);
    println!("After retaining even numbers: {:?}", numbers);
    
    // Clear all elements
    numbers.clear();
    println!("After clear: {:?}", numbers);
}

Accessing Elements

fn main() {
    let numbers = vec![10, 20, 30, 40, 50];
    
    // Indexing (can panic)
    println!("First element: {}", numbers[0]);
    
    // Safe access with get()
    match numbers.get(10) {
        Some(value) => println!("Element at index 10: {}", value),
        None => println!("No element at index 10"),
    }
    
    // First and last elements
    if let Some(first) = numbers.first() {
        println!("First: {}", first);
    }
    
    if let Some(last) = numbers.last() {
        println!("Last: {}", last);
    }
    
    // Slicing
    let slice = &numbers[1..4]; // Elements at indices 1, 2, 3
    println!("Slice: {:?}", slice);
}

Iterating Over Vectors

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    
    // Iterate by reference
    for num in &numbers {
        println!("Number: {}", num);
    }
    
    // Iterate by value (consumes the vector)
    for num in numbers.clone() {
        println!("Owned number: {}", num);
    }
    
    // Iterate with index
    for (index, value) in numbers.iter().enumerate() {
        println!("Index {}: {}", index, value);
    }
    
    // Iterate mutably
    let mut mutable_numbers = vec![1, 2, 3, 4, 5];
    for num in &mut mutable_numbers {
        *num *= 2;
    }
    println!("Doubled: {:?}", mutable_numbers);
}

HashMap<K, V> - Key-Value Storage

HashMap<K, V> stores key-value pairs and provides O(1) average-case lookup.

Creating and Using HashMaps

use std::collections::HashMap;

fn main() {
    // Creating empty HashMap
    let mut scores: HashMap<String, i32> = HashMap::new();
    
    // Inserting values
    scores.insert("Blue".to_string(), 10);
    scores.insert("Red".to_string(), 50);
    
    // Creating from vectors
    let teams = vec!["Blue".to_string(), "Red".to_string()];
    let initial_scores = vec![10, 50];
    let scores_from_vecs: HashMap<_, _> = teams.into_iter()
        .zip(initial_scores.into_iter())
        .collect();
    
    println!("Scores: {:?}", scores_from_vecs);
    
    // Accessing values
    match scores.get("Blue") {
        Some(score) => println!("Blue team score: {}", score),
        None => println!("Blue team not found"),
    }
    
    // Iterating over key-value pairs
    for (team, score) in &scores {
        println!("{}: {}", team, score);
    }
}

Updating Values

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    
    // Insert or update
    scores.insert("Blue", 10);
    scores.insert("Blue", 25); // Overwrites previous value
    
    // Insert only if key doesn't exist
    scores.entry("Yellow").or_insert(50);
    scores.entry("Blue").or_insert(100); // Won't change Blue's value
    
    // Update based on old value
    let counter = scores.entry("Red").or_insert(0);
    *counter += 10;
    
    // Update with a closure
    scores.entry("Green").and_modify(|score| *score += 10).or_insert(5);
    
    println!("Final scores: {:?}", scores);
}

Advanced HashMap Operations

use std::collections::HashMap;

fn word_count(text: &str) -> HashMap<String, usize> {
    let mut map = HashMap::new();
    
    for word in text.split_whitespace() {
        let count = map.entry(word.to_string()).or_insert(0);
        *count += 1;
    }
    
    map
}

fn group_by_length(words: Vec<&str>) -> HashMap<usize, Vec<&str>> {
    let mut groups: HashMap<usize, Vec<&str>> = HashMap::new();
    
    for word in words {
        groups.entry(word.len()).or_insert_with(Vec::new).push(word);
    }
    
    groups
}

fn main() {
    let text = "hello world hello rust world";
    let counts = word_count(text);
    println!("Word counts: {:?}", counts);
    
    let words = vec!["rust", "is", "awesome", "and", "fast"];
    let grouped = group_by_length(words);
    println!("Grouped by length: {:?}", grouped);
}

HashSet<T> - Unique Values

HashSet<T> stores unique values and provides fast membership testing.

Basic HashSet Operations

use std::collections::HashSet;

fn main() {
    let mut set = HashSet::new();
    
    // Adding elements
    set.insert("apple");
    set.insert("banana");
    set.insert("apple"); // Duplicate, won't be added
    
    println!("Set: {:?}", set);
    println!("Contains 'apple': {}", set.contains("apple"));
    println!("Set length: {}", set.len());
    
    // Removing elements
    if set.remove("banana") {
        println!("Removed banana");
    }
    
    // Creating from iterator
    let numbers: HashSet<i32> = (1..=5).collect();
    println!("Numbers: {:?}", numbers);
}

Set Operations

use std::collections::HashSet;

fn main() {
    let set1: HashSet<i32> = [1, 2, 3, 4].iter().cloned().collect();
    let set2: HashSet<i32> = [3, 4, 5, 6].iter().cloned().collect();
    
    // Union: elements in either set
    let union: HashSet<_> = set1.union(&set2).cloned().collect();
    println!("Union: {:?}", union);
    
    // Intersection: elements in both sets
    let intersection: HashSet<_> = set1.intersection(&set2).cloned().collect();
    println!("Intersection: {:?}", intersection);
    
    // Difference: elements in set1 but not in set2
    let difference: HashSet<_> = set1.difference(&set2).cloned().collect();
    println!("Difference: {:?}", difference);
    
    // Symmetric difference: elements in either set but not in both
    let sym_diff: HashSet<_> = set1.symmetric_difference(&set2).cloned().collect();
    println!("Symmetric difference: {:?}", sym_diff);
    
    // Subset checking
    let subset: HashSet<i32> = [1, 2].iter().cloned().collect();
    println!("Is {:?} a subset of {:?}? {}", subset, set1, subset.is_subset(&set1));
}

VecDeque<T> - Double-Ended Queue

VecDeque<T> allows efficient insertion and removal at both ends.

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    
    // Adding to both ends
    deque.push_back(1);
    deque.push_back(2);
    deque.push_front(0);
    deque.push_front(-1);
    
    println!("Deque: {:?}", deque); // [-1, 0, 1, 2]
    
    // Removing from both ends
    while let Some(value) = deque.pop_front() {
        println!("Popped from front: {}", value);
    }
    
    // Using as a ring buffer
    let mut ring_buffer = VecDeque::with_capacity(3);
    for i in 0..5 {
        if ring_buffer.len() == 3 {
            ring_buffer.pop_front();
        }
        ring_buffer.push_back(i);
        println!("Ring buffer: {:?}", ring_buffer);
    }
}

BTreeMap<K, V> and BTreeSet<T> - Sorted Collections

B-tree collections maintain elements in sorted order.

BTreeMap

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    
    map.insert(3, "three");
    map.insert(1, "one");
    map.insert(4, "four");
    map.insert(2, "two");
    
    // Iteration is in sorted order by key
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
    
    // Range queries
    for (key, value) in map.range(2..=3) {
        println!("In range [2,3]: {}: {}", key, value);
    }
    
    // First and last entries
    if let Some((key, value)) = map.first_key_value() {
        println!("First: {}: {}", key, value);
    }
    
    if let Some((key, value)) = map.last_key_value() {
        println!("Last: {}: {}", key, value);
    }
}

BTreeSet

use std::collections::BTreeSet;

fn main() {
    let mut set = BTreeSet::new();
    
    set.insert(3);
    set.insert(1);
    set.insert(4);
    set.insert(2);
    
    // Iteration is in sorted order
    for value in &set {
        println!("Value: {}", value);
    }
    
    // Range operations
    let subset: BTreeSet<_> = set.range(2..=3).cloned().collect();
    println!("Subset [2,3]: {:?}", subset);
    
    // Split operations
    let split_set = set.split_off(&3);
    println!("Original (< 3): {:?}", set);
    println!("Split off (>= 3): {:?}", split_set);
}

BinaryHeap<T> - Priority Queue

BinaryHeap<T> is a max-heap that always keeps the largest element at the top.

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    
    // Adding elements
    heap.push(4);
    heap.push(1);
    heap.push(9);
    heap.push(3);
    heap.push(16);
    
    println!("Heap: {:?}", heap);
    
    // Peek at the largest element
    if let Some(&largest) = heap.peek() {
        println!("Largest element: {}", largest);
    }
    
    // Remove elements in descending order
    while let Some(value) = heap.pop() {
        println!("Popped: {}", value);
    }
    
    // Creating from vector
    let numbers = vec![2, 1, 5, 3, 4];
    let heap_from_vec = BinaryHeap::from(numbers);
    println!("Heap from vector: {:?}", heap_from_vec);
}

Custom Priority Queue

use std::collections::BinaryHeap;
use std::cmp::Reverse;

#[derive(Eq, PartialEq)]
struct Task {
    priority: u32,
    description: String,
}

impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&other.priority)
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut task_queue = BinaryHeap::new();
    
    task_queue.push(Task {
        priority: 1,
        description: "Low priority task".to_string(),
    });
    
    task_queue.push(Task {
        priority: 5,
        description: "High priority task".to_string(),
    });
    
    task_queue.push(Task {
        priority: 3,
        description: "Medium priority task".to_string(),
    });
    
    // Process tasks in priority order (highest first)
    while let Some(task) = task_queue.pop() {
        println!("Processing: {} (priority: {})", task.description, task.priority);
    }
    
    // Min-heap using Reverse
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    min_heap.push(Reverse(3));
    min_heap.push(Reverse(1));
    min_heap.push(Reverse(4));
    
    while let Some(Reverse(value)) = min_heap.pop() {
        println!("Min value: {}", value);
    }
}

Performance Characteristics

*Amortized time complexity

Choosing the Right Collection

When to Use Vec<T>

// Good for: Sequential access, known size, cache-friendly operations
fn process_numbers(numbers: Vec<i32>) -> Vec<i32> {
    numbers.into_iter()
        .map(|x| x * 2)
        .filter(|&x| x > 10)
        .collect()
}

// Good for: Stack-like operations
fn reverse_polish_calculator(tokens: Vec<&str>) -> Option<i32> {
    let mut stack = Vec::new();
    
    for token in tokens {
        match token {
            "+" => {
                let b = stack.pop()?;
                let a = stack.pop()?;
                stack.push(a + b);
            }
            "-" => {
                let b = stack.pop()?;
                let a = stack.pop()?;
                stack.push(a - b);
            }
            num => {
                if let Ok(n) = num.parse::<i32>() {
                    stack.push(n);
                } else {
                    return None;
                }
            }
        }
    }
    
    stack.pop()
}

When to Use HashMap<K, V>

use std::collections::HashMap;

// Good for: Fast lookups, caching, frequency counting
fn build_index(words: Vec<String>) -> HashMap<String, Vec<usize>> {
    let mut index = HashMap::new();
    
    for (pos, word) in words.into_iter().enumerate() {
        index.entry(word).or_insert_with(Vec::new).push(pos);
    }
    
    index
}

// Good for: Configuration storage
fn load_config() -> HashMap<String, String> {
    let mut config = HashMap::new();
    config.insert("host".to_string(), "localhost".to_string());
    config.insert("port".to_string(), "8080".to_string());
    config.insert("debug".to_string(), "true".to_string());
    config
}

When to Use BTreeMap<K, V>

use std::collections::BTreeMap;

// Good for: Ordered iteration, range queries
fn analyze_grades(grades: Vec<(String, u32)>) -> BTreeMap<u32, Vec<String>> {
    let mut grade_groups = BTreeMap::new();
    
    for (student, grade) in grades {
        grade_groups.entry(grade).or_insert_with(Vec::new).push(student);
    }
    
    grade_groups
}

// Good for: Time-series data
fn record_temperature(readings: &mut BTreeMap<u64, f64>, timestamp: u64, temp: f64) {
    readings.insert(timestamp, temp);
}

fn get_temperature_range(readings: &BTreeMap<u64, f64>, start: u64, end: u64) -> Vec<f64> {
    readings.range(start..=end).map(|(_, &temp)| temp).collect()
}

Common Patterns

Builder Pattern with Collections

struct Report {
    title: String,
    sections: Vec<String>,
    metadata: std::collections::HashMap<String, String>,
}

impl Report {
    fn new(title: &str) -> Self {
        Report {
            title: title.to_string(),
            sections: Vec::new(),
            metadata: std::collections::HashMap::new(),
        }
    }
    
    fn add_section(mut self, section: &str) -> Self {
        self.sections.push(section.to_string());
        self
    }
    
    fn add_metadata(mut self, key: &str, value: &str) -> Self {
        self.metadata.insert(key.to_string(), value.to_string());
        self
    }
    
    fn build(self) -> Self {
        self
    }
}

fn main() {
    let report = Report::new("Monthly Report")
        .add_section("Introduction")
        .add_section("Data Analysis")
        .add_section("Conclusion")
        .add_metadata("author", "Alice")
        .add_metadata("date", "2024-01-15")
        .build();
    
    println!("Report: {}", report.title);
    println!("Sections: {:?}", report.sections);
    println!("Metadata: {:?}", report.metadata);
}

Working with Multiple Collections

use std::collections::{HashMap, HashSet};

struct Library {
    books: HashMap<String, Book>,
    authors: HashMap<String, HashSet<String>>, // author -> book_ids
    genres: HashMap<String, HashSet<String>>,  // genre -> book_ids
}

struct Book {
    id: String,
    title: String,
    author: String,
    genre: String,
}

impl Library {
    fn new() -> Self {
        Library {
            books: HashMap::new(),
            authors: HashMap::new(),
            genres: HashMap::new(),
        }
    }
    
    fn add_book(&mut self, book: Book) {
        let book_id = book.id.clone();
        let author = book.author.clone();
        let genre = book.genre.clone();
        
        // Add to books collection
        self.books.insert(book_id.clone(), book);
        
        // Update author index
        self.authors.entry(author).or_insert_with(HashSet::new).insert(book_id.clone());
        
        // Update genre index
        self.genres.entry(genre).or_insert_with(HashSet::new).insert(book_id);
    }
    
    fn books_by_author(&self, author: &str) -> Vec<&Book> {
        self.authors.get(author)
            .map(|book_ids| {
                book_ids.iter()
                    .filter_map(|id| self.books.get(id))
                    .collect()
            })
            .unwrap_or_default()
    }
    
    fn books_by_genre(&self, genre: &str) -> Vec<&Book> {
        self.genres.get(genre)
            .map(|book_ids| {
                book_ids.iter()
                    .filter_map(|id| self.books.get(id))
                    .collect()
            })
            .unwrap_or_default()
    }
}

Best Practices

1. Choose Based on Use Case

// Use Vec for sequences and when order matters
let scores = vec![85, 92, 78, 96, 88];

// Use HashMap for key-value associations
use std::collections::HashMap;
let mut user_scores = HashMap::new();
user_scores.insert("alice", 85);

// Use HashSet for unique items
use std::collections::HashSet;
let unique_visitors: HashSet<String> = HashSet::new();

// Use BTreeMap when you need sorted order
use std::collections::BTreeMap;
let sorted_scores: BTreeMap<String, i32> = BTreeMap::new();

2. Preallocate When Size is Known

// Good: Allocate with known capacity
let mut vec = Vec::with_capacity(1000);
let mut map = std::collections::HashMap::with_capacity(100);

// Avoid: Multiple reallocations
let mut vec = Vec::new(); // Will reallocate as it grows

3. Use Entry API for HashMap Operations

use std::collections::HashMap;

// Good: Use entry API
fn count_words(text: &str) -> HashMap<String, usize> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word.to_string()).or_insert(0) += 1;
    }
    counts
}

// Avoid: Multiple lookups
fn count_words_inefficient(text: &str) -> HashMap<String, usize> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        let word = word.to_string();
        if counts.contains_key(&word) {
            let count = counts.get(&word).unwrap();
            counts.insert(word, count + 1);
        } else {
            counts.insert(word, 1);
        }
    }
    counts
}

4. Consider Iterator Chaining

use std::collections::HashMap;

// Good: Iterator chaining
fn process_data(data: Vec<(String, i32)>) -> HashMap<String, i32> {
    data.into_iter()
        .filter(|(_, value)| *value > 0)
        .map(|(key, value)| (key.to_uppercase(), value * 2))
        .collect()
}

// More explicit but verbose
fn process_data_verbose(data: Vec<(String, i32)>) -> HashMap<String, i32> {
    let mut result = HashMap::new();
    for (key, value) in data {
        if value > 0 {
            result.insert(key.to_uppercase(), value * 2);
        }
    }
    result
}

Collections are fundamental to most Rust programs. Choose the right collection based on your access patterns, performance requirements, and whether you need ordering. Understanding the characteristics of each collection will help you write more efficient and idiomatic Rust code.