Rust § data-structures

Data structures

Rust admits structs (product types — fields aggregated together), enums (sum types — one of several variants), and tuples (anonymous product types). The standard library provides a substantial collection surface: Vec<T> (growable array), String (owned UTF-8 string), HashMap<K,V> and BTreeMap<K,V> (key-value maps), HashSet<T> and BTreeSet<T> (sets), VecDeque<T> (double-ended queue), LinkedList<T> (doubly-linked list — rarely used), and BinaryHeap<T> (priority queue). The combination — value types with no inheritance, sum types as primary discriminating mechanism, owned-vs-borrowed string distinction, hash-and-tree map alternatives — covers the data-structure surface.

Structs

The struct keyword introduces a record type:

struct Point {
    x: f64,
    y: f64,
}

struct Person {
    name: String,
    age: u32,
    email: String,
}

Construction and access:

let p = Point { x: 3.0, y: 4.0 };
let q = Person {
    name: String::from("Alice"),
    age: 30,
    email: String::from("alice@example.com"),
};

println!("{}, {}", p.x, p.y);
println!("{}", q.name);

The struct keyword introduces the type; field accesses use the dot notation.

Tuple structs

Structs may also have positional (unnamed) fields:

struct Pair(i32, i32);
struct Color(u8, u8, u8);

let p = Pair(1, 2);
let c = Color(255, 128, 0);

println!("{}, {}", p.0, p.1);                   // tuple-struct field access

The tuple-struct form is conventionally for newtype patterns — wrapping a single type to give it semantic meaning:

struct UserId(u64);                              // distinguishes from raw u64
struct Inches(f64);
struct Centimeters(f64);

fn distance(d: Inches) -> Centimeters {
    Centimeters(d.0 * 2.54)
}

The newtype admits the compiler distinguishing semantically distinct types that share a representation.

Unit structs

A struct with no fields:

struct Marker;

let m = Marker;

Unit structs are conventionally markers for trait implementations (e.g., type-level state machines).

Update syntax

The .. admits constructing a struct with most fields from another:

let alice = Person {
    name: String::from("Alice"),
    age: 30,
    email: String::from("alice@example.com"),
};

let bob = Person {
    name: String::from("Bob"),
    ..alice                                     // copies remaining fields from alice
};

The mechanism admits “modify a few fields, keep the rest”; useful for builders and configurations.

Methods on structs

The impl block admits attaching methods:

impl Point {
    fn new(x: f64, y: f64) -> Self {
        Point { x, y }
    }

    fn distance(&self, other: &Point) -> f64 {
        ((self.x - other.x).powi(2) + (self.y - other.y).powi(2)).sqrt()
    }
}

let p = Point::new(3.0, 4.0);
let q = Point::new(0.0, 0.0);
println!("{}", p.distance(&q));                  // 5.0

Treated in Functions and closures and Traits.

Enums

The enum keyword introduces a sum type — one of several variants:

enum Shape {
    Circle(f64),
    Rectangle { width: f64, height: f64 },
    Square(f64),
}

let s1 = Shape::Circle(5.0);
let s2 = Shape::Rectangle { width: 3.0, height: 4.0 };
let s3 = Shape::Square(2.0);

Each variant may carry data — positional (tuple-style), named (struct-style), or no data:

enum Status {
    Active,                                     // no data
    Pending(String),                            // tuple variant
    Failed { reason: String, code: i32 },        // struct variant
}

Pattern matching on enums

The conventional dispatch is match:

fn area(s: &Shape) -> f64 {
    match s {
        Shape::Circle(r) => std::f64::consts::PI * r * r,
        Shape::Rectangle { width, height } => width * height,
        Shape::Square(side) => side * side,
    }
}

Treated in Pattern matching.

`Option<T>` and `Result<T, E>`

The standard library’s Option<T> and Result<T, E> are enums:

enum Option<T> {
    Some(T),
    None,
}

enum Result<T, E> {
    Ok(T),
    Err(E),
}

The conventional uses:

Option<T> — for “may or may not have a value”; replaces null.
Result<T, E> — for fallible operations; replaces exceptions.

The ? operator admits compact propagation; treated in Error handling.

Methods on enums

The impl block applies to enums:

impl Shape {
    fn area(&self) -> f64 {
        match self {
            Shape::Circle(r) => std::f64::consts::PI * r * r,
            Shape::Rectangle { width, height } => width * height,
            Shape::Square(side) => side * side,
        }
    }
}

let s = Shape::Circle(5.0);
println!("{}", s.area());

Tuples

Tuples admit anonymous fixed-size product types:

let pair: (i32, &str) = (42, "hello");
let triple = (1, 2.0, "three");

let (a, b) = pair;                              // destructure
println!("{}", pair.0);                          // .0, .1, .2 access

The conventional uses are returning multiple values, grouping related items, and intermediate computations. For long-lived structures, named structs are conventionally clearer.

Arrays

Fixed-size array (size known at compile time):

let arr: [i32; 5] = [1, 2, 3, 4, 5];
let zeros: [i32; 10] = [0; 10];                 // ten zeros

println!("{}", arr[0]);                          // index access
println!("{}", arr.len());                       // 5

for x in &arr {
    println!("{}", x);
}

The size is part of the type; arrays of different sizes have different types. Index access is bounds-checked at runtime; out-of-bounds panics.

For dynamic-sized data, Vec<T> is conventional.

Slices

A slice is a borrowed view into an array or vector:

let v = vec![1, 2, 3, 4, 5];
let s: &[i32] = &v[1..4];                        // slice [2, 3, 4]

println!("{:?}", s);

Slices admit substantial flexibility: a function can accept a slice and work with arrays, vectors, or sub-ranges:

fn sum(s: &[i32]) -> i32 {
    s.iter().sum()
}

let v = vec![1, 2, 3];
let arr = [4, 5, 6];

println!("{}", sum(&v));                         // 6
println!("{}", sum(&arr));                       // 15
println!("{}", sum(&v[1..]));                    // 5 (just 2, 3)

The conventional Rust function takes &[T] rather than &Vec<T> for substantial flexibility.

`Vec<T>`

The conventional growable array:

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

let v2 = vec![1, 2, 3, 4, 5];                   // macro form

let v3: Vec<i32> = (1..=10).collect();          // from iterator

println!("{}", v[0]);                            // index access (panics on OOB)
println!("{:?}", v.get(0));                      // Option<&i32>; safe access

v.pop();                                         // remove last
v.insert(0, 100);                                // insert at index
v.remove(0);                                     // remove at index
v.contains(&5);                                  // membership
v.len();                                         // length
v.is_empty();                                    // emptiness

Vec<T> is the conventional contiguous-memory growable container; O(1) push/pop at end, O(n) insert/remove in middle.

Iterating

let v = vec![1, 2, 3, 4, 5];

for x in &v {                                   // borrow
    println!("{}", x);
}

for x in &mut v {                               // mutable borrow
    *x *= 2;
}

for x in v {                                    // consume
    println!("{}", x);
}
// v no longer accessible

Capacity

Vec admits pre-allocating capacity:

let mut v: Vec<i32> = Vec::with_capacity(100);
for i in 0..100 {
    v.push(i);
}
// no reallocations during the loop

The with_capacity is conventional when the size is known or estimated.

`String` and `&str`

String is the owned, growable UTF-8 string; &str is a borrowed string slice. Treated in Strings.

let s: String = String::from("hello");
let slice: &str = &s;                            // borrow as &str
let owned: String = slice.to_string();           // copy as String

`HashMap<K, V>`

The conventional hash-based key-value map:

use std::collections::HashMap;

let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Alice"), 95);
scores.insert(String::from("Bob"), 87);

println!("{:?}", scores.get("Alice"));           // Some(&95)
println!("{:?}", scores.get("Charlie"));         // None

if scores.contains_key("Alice") {
    println!("Alice is in");
}

scores.remove("Alice");
println!("{}", scores.len());                    // 1

for (key, value) in &scores {
    println!("{}: {}", key, value);
}

Insert-or-update

let mut counts: HashMap<&str, i32> = HashMap::new();

for word in &["a", "b", "a", "c", "b", "a"] {
    *counts.entry(word).or_insert(0) += 1;
}
// counts: {"a": 3, "b": 2, "c": 1}

The entry API admits substantial conciseness for the conventional patterns:

map.entry(key).or_insert(default);
map.entry(key).or_insert_with(|| compute_default());
map.entry(key).and_modify(|v| *v += 1).or_insert(0);

Hashing

HashMap requires keys to implement Hash and Eq:

#[derive(Hash, Eq, PartialEq)]
struct Coord { x: i32, y: i32 }

let mut grid: HashMap<Coord, &str> = HashMap::new();
grid.insert(Coord { x: 0, y: 0 }, "origin");

The #[derive(Hash, Eq, PartialEq)] produces a structural hash; for custom hash, implement Hash manually.

`BTreeMap<K, V>`

A tree-based ordered map:

use std::collections::BTreeMap;

let mut map: BTreeMap<i32, &str> = BTreeMap::new();
map.insert(3, "three");
map.insert(1, "one");
map.insert(2, "two");

for (key, value) in &map {                       // iterates in key order
    println!("{}: {}", key, value);
}

The principal differences from HashMap:

`HashMap`	`BTreeMap`
`O(1)` lookup average	`O(log n)` lookup
Unordered iteration	Ordered by key
Requires `Hash + Eq`	Requires `Ord`

The conventional choice: HashMap when order does not matter; BTreeMap when iterating in sorted order or doing range queries.

`HashSet<T>` and `BTreeSet<T>`

Sets are maps without values:

use std::collections::HashSet;

let mut set: HashSet<i32> = HashSet::new();
set.insert(1);
set.insert(2);
set.insert(1);                                  // duplicate; no effect

println!("{}", set.len());                       // 2
println!("{}", set.contains(&1));                // true

// Set operations:
let a: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
let b: HashSet<i32> = [2, 3, 4].iter().cloned().collect();

let intersection: HashSet<i32> = a.intersection(&b).cloned().collect();
let union: HashSet<i32> = a.union(&b).cloned().collect();
let difference: HashSet<i32> = a.difference(&b).cloned().collect();
let symmetric_difference: HashSet<i32> = a.symmetric_difference(&b).cloned().collect();

BTreeSet<T> admits ordered iteration; same trade-offs as BTreeMap vs HashMap.

`VecDeque<T>`

A double-ended queue (ring buffer):

use std::collections::VecDeque;

let mut q: VecDeque<i32> = VecDeque::new();
q.push_back(1);
q.push_back(2);
q.push_front(0);

println!("{:?}", q.pop_front());                  // Some(0)
println!("{:?}", q.pop_back());                   // Some(2)

O(1) push/pop at both ends; conventionally for queues and double-ended workflows. For pure stacks, Vec (push/pop at the end) is conventional.

`BinaryHeap<T>`

A priority queue (max-heap):

use std::collections::BinaryHeap;

let mut heap: BinaryHeap<i32> = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);
heap.push(1);
heap.push(5);

while let Some(top) = heap.pop() {
    println!("{}", top);                          // 5, 4, 3, 1, 1
}

The standard library admits a max-heap; for a min-heap, wrap values in std::cmp::Reverse:

use std::cmp::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(top)) = min_heap.pop() {
    println!("{}", top);                          // 1, 3, 4
}

`LinkedList<T>`

A doubly-linked list. Rarely used in idiomatic Rust:

use std::collections::LinkedList;

let mut list: LinkedList<i32> = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_front(0);

The conventional Rust default is Vec<T> for almost all sequence-like uses; VecDeque<T> for queues; LinkedList<T> only for the rare cases requiring constant-time splice operations.

Choosing a collection

The conventional Rust advice:

Need	Collection
Growable list, indexed access	`Vec<T>`
Queue, double-ended	`VecDeque<T>`
Hash-based key-value	`HashMap<K, V>`
Ordered key-value	`BTreeMap<K, V>`
Hash-based set	`HashSet<T>`
Ordered set	`BTreeSet<T>`
Priority queue	`BinaryHeap<T>`
Fixed-size array	`[T; N]`

Common patterns

Building a vec from an iterator

let squares: Vec<i32> = (1..=10).map(|n| n * n).collect();
let evens: Vec<i32> = (1..=20).filter(|&n| n % 2 == 0).collect();

The .collect() admits substantial conciseness for vector construction.

Counting occurrences

use std::collections::HashMap;

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

Group by

use std::collections::HashMap;

fn group_by_length(words: &[&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
}

Tuple-struct newtype

struct UserId(u64);
struct GroupId(u64);

fn assign_to_group(user: UserId, group: GroupId) {
    // can't accidentally swap the arguments
}

The newtype pattern admits compile-time distinction between semantically distinct types.

Using `#[derive]`

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Point { x: i32, y: i32 }

let p1 = Point { x: 0, y: 0 };
let p2 = p1.clone();                             // Clone
let p3 = Point { x: 0, y: 0 };
println!("{:?}", p1);                            // Debug
println!("{}", p1 == p3);                        // PartialEq

use std::collections::HashSet;
let mut set: HashSet<Point> = HashSet::new();    // Hash, Eq
set.insert(p1);

The #[derive] admits auto-implementing common traits; treated in Traits.

A note on the conventional discipline

The contemporary Rust data-structure advice:

Use Vec<T> by default — for almost all sequence needs.
Use String for owned strings, &str for borrowed.
Use HashMap by default for key-value; BTreeMap only when order matters.
Use newtypes for semantic distinction.
Derive Debug, Clone, PartialEq on most data types.
Implement methods in impl blocks; group related operations.
Prefer enums over flag-based representations — sum types prevent invalid states.

The combination — value-typed structs, sum-typed enums, ownership-aware collections, hash-and-tree map alternatives — is the substance of Rust’s data-structure surface. The conventional discipline is to choose the type that admits expressing the data’s invariants directly.