Vectors - Rust for C-Programmers

18.2 The `Vec<T>` Vector Type

Vec<T>, commonly referred to as a “vector,” is Rust’s primary dynamic array type. It stores elements of type T contiguously in memory on the heap. This contiguous 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:

Empty Vector with Vec::new():

#![allow(unused)]
fn main() {
// Type annotation is often needed if the vector is initially empty
// and its type cannot be inferred from later usage.
let mut v: Vec<i32> = Vec::new();
v.push(1); // Add an element
}

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

#![allow(unused)]
fn main() {
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]
}

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

#![allow(unused)]
fn main() {
// Creates vec![1, 2, 3, 4, 5]
let v_range: Vec<i32> = (1..=5).collect();
}

Converting from Slices or Arrays:

#![allow(unused)]
fn main() {
let slice: &[i32] = &[10, 20, 30];
let v_from_slice: Vec<i32> = slice.to_vec(); // Creates an owned Vec<T> by cloning elements

let array: [i32; 3] = [4, 5, 6];
// Vec::from consumes the array if possible (e.g., array is not Copy),
// otherwise it copies the elements. For basic types like i32, it copies.
let v_from_array: Vec<i32> = Vec::from(array);
}

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.

#![allow(unused)]
fn main() {
// 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:

A pointer to the heap-allocated buffer where the elements are stored contiguously.
length: The number of elements currently stored in the vector.
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

push(element: T): Appends an element to the end. Amortized O(1).
pop() -> Option<T>: Removes and returns the last element as an Option, or None if the vector is empty. O(1).
insert(index: usize, element: T): Inserts an element at index, shifting subsequent elements to the right. O(n). Panics if index > len.
remove(index: usize) -> T: Removes and returns the element at index, shifting subsequent elements to the left. O(n). Panics if index >= len.
get(index: usize) -> Option<&T>: Returns an immutable reference (&T) to the element at index wrapped in Some, or None if the index is out of bounds. Performs bounds checking. O(1).
get_mut(index: usize) -> Option<&mut T>: Returns a mutable reference (&mut T). Performs bounds checking. O(1).
Indexing (v[index]) : Provides direct access to elements using square brackets. Returns &T or &mut T. Panics if index is out of bounds. Use this only when you are certain the index is valid. O(1).
len() -> usize: Returns the current number of elements (length). O(1).
is_empty() -> bool: Checks if the vector contains zero elements (length == 0). O(1).
clear(): Removes all elements, setting length to 0 but retaining the allocated capacity. O(n) because it must drop each element.

18.2.4 Accessing Elements Safely

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

Indexing ([]): Provides direct access but panics (terminates the program) if the index is out of bounds. Suitable when the index is guaranteed to be valid (e.g., within a loop 0..v.len()).

#![allow(unused)]
fn main() {
let v = vec![10, 20, 30];
let first: &i32 = &v[0]; // Ok, borrows the first element
// let fourth = v[3]; // This would panic at runtime
}

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

#![allow(unused)]
fn main() {
let v = vec![10, 20, 30];
if let Some(second) = v.get(1) {
    println!("Second element: {}", second);
} else {
    println!("Index 1 is out of bounds."); // Won't happen here
}

match v.get(3) {
    Some(_) => unreachable!(), // Should not happen
    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.

18.2.5 Iterating Over Vectors

Vectors support several common iteration patterns:

Immutable iteration (&v or v.iter()): Borrows the vector immutably, yielding immutable references (&T) to each element.

#![allow(unused)]
fn main() {
let v = vec![1, 2, 3];
for item in &v { // or v.iter()
    println!("{}", item);
}
// v is still usable here
}

Mutable iteration (&mut v or v.iter_mut()): Borrows the vector mutably, yielding mutable references (&mut T) allowing modification of elements.

#![allow(unused)]
fn main() {
let mut v = vec![10, 20, 30];
for item in &mut v { // or v.iter_mut()
    *item += 5; // Dereference to modify the value
}
// v is now vec![15, 25, 35]
}

Consuming iteration (v or v.into_iter()): Takes ownership of the vector and yields owned elements (T). The vector itself cannot be used after the iteration begins.

#![allow(unused)]
fn main() {
let v = vec![100, 200, 300];
for item in v { // v is moved here, equivalent to v.into_iter()
    println!("{}", item);
}
// Compile error: cannot use v anymore here, as it was moved
// println!("{:?}", v);
}

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:

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),
}

fn main() {
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),
    }
}
}

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.
```
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(); }
```
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> provides automatic memory management, preventing leaks and double frees.
It guarantees memory safety, eliminating buffer overflows via bounds checking (panic or Option return).
It offers convenient, built-in methods for common operations (push, pop, insert, etc.).
Appending elements has amortized O(1) complexity, similar to optimized C implementations.
It gives control over allocation strategy via with_capacity and shrink_to_fit.

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