| Contents |

18 Common collection types

In C programming, managing groups of data elements whose size is unknown at compile time typically requires manual memory management using functions like malloc, realloc, and free. While flexible, this approach is notoriously prone to errors, including memory leaks, double frees, use-after-free bugs, and buffer overflows, which can lead to crashes or security vulnerabilities.

Rust provides built-in collection types to handle dynamic data safely and efficiently. These are data structures capable of storing multiple values. Unlike fixed-size arrays or tuples, standard collections such as Vec<T>, String, and HashMap<K, V> store their data on the heap and can grow or shrink as needed during program execution. They abstract away the complexities of manual memory management, leveraging Rust’s ownership and borrowing system to guarantee memory safety without sacrificing performance.

This chapter introduces the most frequently used collection types in Rust. We will explore their characteristics, compare them with C idioms and fixed-size Rust types, and demonstrate how they facilitate dynamic data management safely.

18.1 Overview of Collections and Comparison with C

For developers coming from C, the most significant advantage of Rust’s collections is their automatic resource management. Instead of manually orchestrating malloc, realloc, and free, and meticulously tracking allocation sizes and capacities, you utilize Rust’s standard library types that handle these details internally.

Rust’s collections offer safety and convenience through:

  1. Automated Memory Management: Allocation and deallocation are handled automatically via Rust’s ownership system. When a collection variable goes out of scope, its destructor is called, freeing the associated heap memory and preventing leaks.
  2. Type Safety: Collections are generic (e.g., Vec<T>), ensuring they hold elements of only one specific type T at compile time. This prevents type confusion errors common in C when using void* or untagged unions without careful management.
  3. Compile-Time Safety Checks: Rust’s ownership and borrowing rules prevent common C errors like dangling pointers or data races when accessing collection elements, catching potential issues before runtime.

While providing these safety guarantees, Rust collections are designed for performance. Techniques like amortized constant-time appending to Vec<T> mean performance is often comparable to well-written C code using dynamic arrays, but with a substantially lower risk of memory-related bugs.

The primary collection types we will cover are:

Rust also provides specialized collections like BTreeMap, HashSet, BTreeSet, and VecDeque for specific requirements such as sorted data or double-ended queue operations. All standard collections adhere to Rust’s ownership rules, ensuring predictable and safe memory management.

18.2 The Vec<T> Vector Type

Vec<T>, commonly referred to as a “vector,” is Rust’s primary dynamic array type. The Vec<T> struct itself is a small object on the stack containing a pointer to its heap-allocated data, a length, and a capacity. This contiguous heap-based layout allows for efficient indexing (O(1) complexity) and iteration. A Vec<T> automatically manages its underlying buffer, resizing it as necessary when elements are added.

18.2.1 Creating a Vector

Vectors can be created in several ways:

  1. Empty Vector with Vec::new():

    let mut v: Vec<i32> = Vec::new();
v.push(1);

    Vec::new() creates an empty vector on the stack and does not allocate any memory on the heap until the first element is pushed. Type annotation is often needed if the vector is initially empty and its type cannot be inferred from later usage.

  2. Using the vec! Macro: A convenient shorthand for creating vectors with initial elements.

    let v_empty: Vec<i32> = vec![];      // Creates an empty vector
let v_nums = vec![1, 2, 3];          // Infers Vec<i32>
let v_zeros = vec![0; 5];            // Creates vec![0, 0, 0, 0, 0]

  3. From Iterators using collect(): Many iterators can be gathered into a vector.

    // Creates vec![1, 2, 3, 4, 5]
let v_range: Vec<i32> = (1..=5).collect();

  4. Converting from Slices or Arrays:

    let slice: &[i32] = &[10, 20, 30];
// Creates an owned Vec<T> by cloning elements from the slice
let v_from_slice: Vec<i32> = slice.to_vec();
// Vec::from(slice) is equivalent to slice.to_vec()
let v_also_from_slice: Vec<i32> = Vec::from(slice);

let array: [i32; 3] = [4, 5, 6];
// For arrays [T; N] where T implements Copy, Vec::from(array) copies elements.
// This creates a Vec<T> from the array by copying.
let v_from_array: Vec<i32> = Vec::from(array);
// If T is not Copy, use iterators: `array.into_iter().collect()`

  5. Pre-allocating Capacity with Vec::with_capacity(): If you have an estimate of the number of elements, pre-allocating can improve performance by reducing the frequency of reallocations.

    // Allocate space for at least 10 elements upfront
let mut v_cap = Vec::with_capacity(10);
for i in 0..10 {
    v_cap.push(i); // No reallocations occur in this loop
}
// Pushing the 11th element might trigger a reallocation
v_cap.push(10);

18.2.2 Internal Structure and Memory Management

A Vec<T> internally consists of three components, typically stored on the stack:

  1. A pointer to the heap-allocated buffer where the elements are stored contiguously.
  2. length: The number of elements currently stored in the vector.
  3. capacity: The total number of elements the allocated buffer can hold before needing to resize.

The invariant length <= capacity always holds. When adding an element (push) while length == capacity, the vector usually allocates a new, larger buffer (often doubling the capacity), copies the existing elements to the new buffer, frees the old buffer, and then adds the new element. This strategy results in an amortized O(1) time complexity for appending elements.

Removing elements decreases length but does not automatically shrink the capacity. You can call v.shrink_to_fit() to request that the vector release unused capacity, although the allocator might not always free the memory immediately.

When a Vec<T> goes out of scope, its destructor runs automatically. This destructor drops (cleans up) all elements contained within the vector and then frees the heap-allocated buffer, ensuring no memory leaks occur.

18.2.3 Common Methods and Operations

18.2.4 Accessing Elements Safely

Rust offers two primary ways to access vector elements, prioritizing safety:

  1. Indexing ([]): Provides direct access (&T or &mut T) but panics the current thread if the index is out of bounds. If the panicked thread is the main thread (and the panic is not caught), the program typically terminates. Use indexing when the index is guaranteed to be valid (e.g., within a loop 0..v.len()).

    let v = vec![10, 20, 30];
let first: &i32 = &v[0]; // Ok, borrows the first element
// let fourth = v[3]; // This would panic the current thread at runtime

  2. .get() method: Returns an Option<&T> (or Option<&mut T> for .get_mut()). This is the idiomatic way to handle potentially invalid indices without causing a panic.

    let v = vec![10, 20, 30];
if let Some(second) = v.get(1) {
    println!("Second element: {}", second);
} else {
    // This branch is unreachable in this specific example
    println!("Index 1 is out of bounds.");
}

match v.get(3) {
    Some(_) => unreachable!(), // Should not happen -- index 3 on a 3-element vec
    None => println!("Index 3 is safely handled as out of bounds."),
}

Using .get() is generally preferred when the validity of an index isn’t absolutely certain at compile time or when a panic is unacceptable.

18.2.5 Iterating Over Vectors

Vectors support several common iteration patterns:

18.2.6 Storing Elements of Different Types

A Vec<T> requires all its elements to be of the exact same type T. If you need to store items of different types within a single collection, common approaches in Rust include:

  1. Enums: Define an enum where each variant can hold one of the possible types. This is the most common and often most efficient method when the set of types is known at compile time.

    enum DataItem {
    Integer(i32),
    Float(f64),
    Text(String),
}

let mut data_vec: Vec<DataItem> = Vec::new();
data_vec.push(DataItem::Integer(42));
data_vec.push(DataItem::Float(3.14));
data_vec.push(DataItem::Text("Hello".to_string()));

for item in &data_vec {
    match item {
        DataItem::Integer(i) => println!("Got an integer: {}", i),
        DataItem::Float(f) => println!("Got a float: {}", f),
        DataItem::Text(s) => println!("Got text: {}", s),
    }
}

  2. Trait Objects: Use Box<dyn Trait> if the elements share a common behavior defined by a trait. This involves dynamic dispatch (runtime lookup of method calls) and requires heap allocation for each element via Box. It’s more flexible if the exact types aren’t known upfront but incurs runtime overhead.

    // Example concept:
// trait Displayable { fn display(&self); }
// // ... implementations for different concrete types ...
//
// let mut items: Vec<Box<dyn Displayable>> = Vec::new();
// items.push(Box::new(MyType1 { /* ... */ }));
// items.push(Box::new(MyType2 { /* ... */ }));
// for item in &items { item.display(); } // Dynamic dispatch

    Generally, prefer enums when the set of types is fixed and known.

18.2.7 Summary: Vec<T> vs. Manual C Dynamic Arrays

Compared to manually managing dynamic arrays in C using malloc/realloc/free:

Vec<T> is the idiomatic, safe, and efficient way to handle growable sequences of homogeneous data in Rust.

18.3 The String Type

Rust’s String type represents a growable, mutable, owned sequence of UTF-8 encoded text. Like Vec<T>, the String struct itself is a small object on the stack, containing a pointer to its heap-allocated text data, a length, and a capacity. This design ensures that only the text data is stored on the heap, with the stack-based struct managing the heap-allocated memory. A call to String::new() does not allocate memory on the heap; it creates an empty String struct on the stack. The heap allocation happens only when data is first added to the string. This automatic and lazy memory management is a key advantage over manual C-style string handling.

18.3.1 Understanding String vs. &str

This distinction is fundamental in Rust and often a point of confusion for newcomers:

You can get an immutable &str slice from a String easily (e.g., &my_string[..], or often implicitly via deref coercion), but converting a &str to an owned String usually involves allocating memory and copying the data (e.g., using .to_string() or String::from()).

18.3.2 String vs. Vec<u8>

While a String is internally backed by a buffer of bytes (like Vec<u8>), its primary difference is the UTF-8 guarantee. String methods ensure that the byte sequence remains valid UTF-8. If you need to handle arbitrary binary data, raw byte streams, or text in an encoding other than UTF-8, you should use Vec<u8> instead. Attempting to create a String from invalid UTF-8 byte sequences will result in an error or panic.

18.3.3 Creating and Modifying Strings

// Create an empty String
let mut s1 = String::new();

// Create from a string literal (&str)
let s2 = String::from("initial content");
let s3 = "initial content".to_string(); // Equivalent, often preferred style

// Appending content
let mut s = String::from("foo");
s.push_str("bar"); // Appends a &str slice. s is now "foobar"
s.push('!');       // Appends a single char. s is now "foobar!"

Appending uses similar reallocation strategies as Vec for amortized O(1) performance.

18.3.4 Concatenation

There are several ways to combine strings:

  1. Using the + operator (via the add trait method): This operation consumes ownership of the left-hand String and requires a borrowed &str on the right.

    let s1 = String::from("Hello, ");
let s2 = String::from("world!");
// s1 is moved here and can no longer be used directly.
// &s2 works because String derefs to &str.
let s3 = s1 + &s2;
println!("{}", s3); // Prints "Hello, world!"
// println!("{}", s1); // Compile Error: value used after move

    Because + moves the left operand, chaining multiple additions can be inefficient and verbose (s1 + &s2 + &s3 + ...).

  2. Using the format! macro: This is generally the most flexible and readable approach, especially for combining multiple pieces or non-string data. It does not take ownership of its arguments (it borrows them via references) and returns a newly allocated, owned String.

    let name = "Rustacean";
let level = 99;
let s1 = String::from("Status: ");
let greeting = format!("{}{}! Your level is {}.", s1, name, level);
println!("{}", greeting); // Prints "Status: Rustacean! Your level is 99."
// s1, name, and level are still usable here because format! borrowed them.
println!("{} still exists.", s1);

18.3.5 UTF-8, Characters, and Indexing

Because String guarantees UTF-8, where characters can span multiple bytes (1 to 4), direct indexing by byte position (s[i]) to get a char is disallowed. This is a safety feature: a byte index might fall in the middle of a multi-byte character, leading to an invalid character boundary.

Instead, Rust provides methods to work with strings correctly:

18.3.6 Common String Methods

18.3.7 Summary: String vs. C Strings

Traditional C strings (char*, usually null-terminated) present several challenges that Rust’s String and &str system addresses:

String and &str provide a robust, safe, and Unicode-aware system for handling text data, significantly improving upon the limitations and unsafety of traditional C strings, while offering specific mechanisms for safe C interoperability when needed.

18.4 The HashMap<K, V> Type

HashMap<K, V> is Rust’s primary implementation of a hash map (also known as a hash table, dictionary, or associative array). It stores mappings from unique keys of type K to associated values of type V. It provides efficient average-case time complexity for insertion, retrieval, and removal operations, typically O(1).

To use HashMap, you first need to bring it into scope:

use std::collections::HashMap;

18.4.1 Key Characteristics

18.4.2 Creating and Populating a HashMap

use std::collections::HashMap; // Required import

// Create an empty HashMap
let mut scores: HashMap<String, i32> = HashMap::new();

// Insert key-value pairs using .insert()
// Note: .to_string() creates an owned String from the &str literal
scores.insert("Alice".to_string(), 95);
scores.insert(String::from("Bob"), 88); // String::from also works

// Create with initial capacity estimate
let mut map_cap: HashMap<u64, i32> = HashMap::with_capacity(50);

// Create from an iterator of tuples (K, V)
let teams = vec![String::from("Blue"), String::from("Red")];
let initial_scores = vec![10, 50];
// zip combines the two iterators into an iterator of pairs
// collect consumes the iterator and creates the HashMap
let team_scores: HashMap<String, i32> =
    teams.into_iter().zip(initial_scores.into_iter()).collect();

18.4.3 Accessing Values

// Using .get(&key) for safe access (returns Option<&V>)
// Note: .get() takes a reference to the key type.
// If K is String, you can often pass &str due to borrowing rules.
let alice_score: Option<&i32> = scores.get("Alice");
match alice_score {
    Some(score_ref) => println!("Alice's score: {}", score_ref),
    None => println!("Alice not found."),
}

// Using indexing map[key] -> &V or &mut V
// Panics the current thread if the key is not found!
// Use only when absolutely sure the key exists.
// The Index trait implementation returns an immutable reference &V.
let alice_ref: &i32 = &scores["Alice"];
println!("Alice's score via index: {}", alice_ref);

// let charlie_ref = &scores["Charlie"]; // This would panic the current thread

// Checking for key existence
if scores.contains_key("Bob") {
    println!("Bob is in the map.");
}

Unlike Vec, HashMap indexing (map[key]) does not return the value directly even if V is Copy. It always returns a reference (&V for immutable indexing, &mut V for mutable indexing). Dereferencing this reference (*map[key]) will copy the value if V is Copy. The panic occurs if the key is absent, preventing access to non-existent data.

18.4.4 Updating and Removing Values

18.4.5 Iteration

You can iterate over keys, values, or key-value pairs. Remember that the iteration order is not guaranteed.

// Iterate over key-value pairs (yields immutable references: (&K, &V))
println!("Scores:");
for (name, score) in &scores { // or scores.iter()
    println!("- {}: {}", name, score);
}

// Iterate over keys only (yields immutable references: &K)
println!("\nNames:");
for name in scores.keys() {
    println!("- {}", name);
}

// Iterate over values only (yields immutable references: &V)
println!("\nValues:");
for score in scores.values() {
    println!("- {}", score);
}

// Iterate with mutable references to values:
// let mut mutable_scores = scores; // Need mutable binding
// for score in mutable_scores.values_mut() { *score += 1; }
// for (key, value) in mutable_scores.iter_mut() { *value += 1; }

18.4.6 Internal Details: Hashing, Collisions, and Resizing

Internally, HashMap typically uses an array (often a Vec) of buckets or slots. When inserting a key-value pair:

  1. The key is hashed to produce an integer.
  2. This hash is used to calculate an index (a bucket or slot) into the internal array.
  3. If the calculated slot is empty, the key-value pair (or information pointing to them) is stored there.
  4. If the calculated slot is already occupied by a different key (a hash collision, where multiple keys hash to the same initial slot index), the map must employ a collision resolution strategy. The two primary approaches are:

Rust’s std::collections::HashMap uses a highly optimized implementation of open addressing (specifically, a variation of Robin Hood probing adapted from the hashbrown crate). This strategy tends to have better cache performance compared to separate chaining because elements are stored directly within the contiguous array, reducing pointer indirections.

To maintain efficient average O(1) lookups, the HashMap monitors its load factor (number of elements / number of slots). When the load factor exceeds a certain threshold (meaning the table is becoming too full, increasing collision probability), the map allocates a larger array of slots (resizing) and re-inserts all existing elements into the new, larger table using their hash values. This resizing operation takes O(n) time but happens infrequently enough that the average (amortized) insertion time remains O(1).

18.4.7 Summary: HashMap vs. C Hash Tables

Implementing hash tables manually in C requires significant effort: choosing or implementing a suitable hash function, designing an effective collision resolution strategy (like chaining or open addressing), writing the logic for resizing the table, and managing memory for the table structure, keys, and values. Using a third-party C library can help, but integration and ensuring type safety and memory safety still rely heavily on the programmer.

Rust’s HashMap<K, V> provides:

18.5 Other Standard Collection Types

Beyond the three main types, Rust’s standard library (std::collections) offers several other useful collections:

All these standard collections manage their memory automatically and uphold Rust’s safety guarantees through the ownership and borrowing system.

18.6 Performance Characteristics Summary

Choosing the right collection type often involves considering the time complexity of common operations. The table below summarizes typical complexities (average or amortized where applicable):

Collection Access (Index/Key) Insert (End/Any) Remove (End/Any) Iteration Order Key Notes
Vec<T> O(1) / N/A O(1)* / O(n) O(1) / O(n) Insertion Contiguous memory, cache-friendly. *Amortized.
String N/A (Byte Slice) O(1)* / N/A N/A UTF-8 Bytes Vec<u8> + UTF-8 guarantee. Append is O(1)*.
HashMap<K, V> O(1)** O(1)** O(1)** Arbitrary Requires Hash+Eq keys. **Average case.
BTreeMap<K, V> O(log n) O(log n) O(log n) Sorted by Key Requires Ord+Eq keys. Slower than HashMap.
HashSet<T> O(1)** (contains) O(1)** O(1)** Arbitrary Unique elements, hashed. **Average case.
BTreeSet<T> O(log n) (contains) O(log n) O(log n) Sorted Unique elements, ordered. Requires Ord+Eq.
VecDeque<T> O(1) (ends) / O(n) O(1)* (ends) / O(n) O(1)* (ends) / O(n) Insertion Ring buffer. *Amortized O(1) at ends.
LinkedList<T> O(n) O(1)*** O(1)*** Insertion Poor cache locality. ***Requires known node/cursor.
BinaryHeap<T> O(1) (peek) O(log n) O(log n) N/A O(log n) push/pop. Useful for priority queues.

Notes: * Amortized O(1): The operation is very fast on average, but occasional calls might be slower (O(n)) due to internal resizing. ** Average case O(1): Assumes a good hash function and few collisions. Worst-case can be O(n). *** O(1) if you already have direct access (e.g., a cursor) to the node or its neighbor involved in the operation. Finding the node first is O(n).

18.7 Selecting the Appropriate Collection

Here’s a quick guide based on common needs:

When in doubt for sequences, start with Vec<T>. For key-value lookups, start with HashMap<K, V>. Choose other collections when their specific properties (ordering, double-ended access, uniqueness) are required.

18.8 Summary

Rust’s standard library provides a versatile suite of collection types, with Vec<T>, String, and HashMap<K, V> being the most commonly used. These types offer essential capabilities for managing dynamic data whose size isn’t known at compile time.

For C programmers, the paramount advantage is that Rust collections manage their own memory safely and automatically, governed by the ownership and borrowing system. This design fundamentally eliminates entire categories of memory management errors prevalent in C, such as memory leaks, use-after-free, double frees, and buffer overflows associated with manual malloc/realloc/free usage.

These collections provide not only safety but also efficiency, often matching the performance of carefully tuned C implementations while drastically reducing the risk of memory corruption bugs. By understanding the characteristics, performance trade-offs, and typical use cases of Rust’s collections, you can write more expressive, robust, and maintainable code that effectively handles dynamic data, liberating you from the considerable burden and risks of manual memory management in C.

| Contents |