codeloopback
Guide contents

Lesson 56 of 94

Box: Heap Allocation

Values live wherever their owner is: on the stack, inside another struct, or inside a collection's buffer. A smart pointer is a type that owns a value stored somewhere else and acts like a reference to it. This section covers the four you'll use:

Smart pointer Owns
Box<T> one value on the heap, single owner
Rc<T> / Arc<T> one value, shared by several owners (reference counted)
RefCell<T> / Cell<T> a value you can change through a shared reference
Cow<T> either borrowed or owned data

Box<T> is the simplest: it puts a value on the heap and owns it. When the Box is dropped, the value is freed. You don't need it often, but three situations require it: recursive types, trait objects, and very large values you want to move cheaply.

1. Putting a value on the heap

Box::new(value) moves the value to the heap. The Box itself is just a pointer on the stack.

Rust
fn main() {
    let on_stack = 42;
    let on_heap = Box::new(42);
    println!("{on_stack} {on_heap}");
    println!("sum: {}", on_stack + *on_heap);
    println!("Box<i32> is {} bytes (a pointer)", std::mem::size_of::<Box<i32>>());
}
Output
42 42
sum: 84
Box<i32> is 8 bytes (a pointer)

*on_heap dereferences the box to get the value, exactly like a reference. println! dereferences automatically.

2. A Box owns its value

Moving a Box moves the pointer, not the value. When the owner goes out of scope, the heap memory is freed.

Rust
fn make_config() -> Box<String> {
    Box::new(String::from("mode=production"))
}

fn main() {
    let config = make_config();
    let moved = config; // moves the pointer; the String stays where it is
    println!("{moved}");
    // println!("{config}"); // error: value moved
} // `moved` is dropped: the String and the box's heap allocation are freed
Output
mode=production

3. Methods work through a Box

A Box<T> derefs to T, so you call T's methods directly.

Rust
fn main() {
    let names: Box<Vec<&str>> = Box::new(vec!["ana", "ben"]);
    println!("{} names, first {:?}", names.len(), names.first());

    let mut counter = Box::new(0);
    *counter += 5;
    println!("{counter}");
}
Output
2 names, first Some("ana")
5

4. You rarely need Box for ordinary values

It's tempting to box everything. Don't: a Vec, String, or HashMap already keeps its contents on the heap, and plain structs are cheap to move. Box<Vec<T>> just adds an extra pointer hop.

Rust
struct Order {
    id: u32,
    items: Vec<String>, // already heap-allocated inside; no Box needed
}

fn main() {
    let o = Order { id: 1, items: vec![String::from("lamp")] };
    println!("Order is {} bytes on the stack; its items live on the heap", std::mem::size_of::<Order>());
    println!("{} {:?}", o.id, o.items);
}
Output
Order is 32 bytes on the stack; its items live on the heap
1 ["lamp"]

5. Recursive types need a Box

A type that contains itself directly would have infinite size. A Box has a fixed size (one pointer), which breaks the recursion. You saw this with Expr in Enums.

Rust✗ does not compile · E0072
enum List {
    Cons(i32, List),
    Nil,
}

fn main() {}
Output
error[E0072]: recursive type `List` has infinite size
 --> src/main.rs:1:1
  |
1 | enum List {
  | ^^^^^^^^^
2 |     Cons(i32, List),
  |               ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 |     Cons(i32, Box<List>),
  |               ++++    +

6. A singly linked list

Rust
#[derive(Debug)]
enum List {
    Cons(i32, Box<List>),
    Nil,
}

use List::{Cons, Nil};

impl List {
    fn sum(&self) -> i32 {
        match self {
            Cons(value, rest) => value + rest.sum(),
            Nil => 0,
        }
    }
}

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));
    println!("{:?}", list);
    println!("sum = {}", list.sum());
}
Output
Cons(1, Cons(2, Cons(3, Nil)))
sum = 6

Linked lists are mostly a teaching example; a Vec or VecDeque is faster for almost every real workload.

7. A binary search tree

Each node owns its children through Option<Box<Node>>: None for no child. Option<Box<T>> is the same size as a plain pointer, thanks to the null-pointer optimization from Option.

Rust
#[derive(Debug)]
struct Node {
    key: u32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(key: u32) -> Self {
        Node { key, left: None, right: None }
    }

    fn insert(&mut self, key: u32) {
        let child = if key < self.key { &mut self.left } else { &mut self.right };
        match child {
            Some(node) => node.insert(key),
            None => *child = Some(Box::new(Node::new(key))),
        }
    }

    fn contains(&self, key: u32) -> bool {
        if key == self.key {
            return true;
        }
        let child = if key < self.key { &self.left } else { &self.right };
        child.as_ref().is_some_and(|n| n.contains(key))
    }

    fn in_order(&self, out: &mut Vec<u32>) {
        if let Some(l) = &self.left {
            l.in_order(out);
        }
        out.push(self.key);
        if let Some(r) = &self.right {
            r.in_order(out);
        }
    }
}

fn main() {
    let mut root = Node::new(50);
    for k in [30, 70, 20, 40, 60, 80] {
        root.insert(k);
    }
    let mut sorted = Vec::new();
    root.in_order(&mut sorted);
    println!("{:?}", sorted);
    println!("contains 60: {}, contains 65: {}", root.contains(60), root.contains(65));
}
Output
[20, 30, 40, 50, 60, 70, 80]
contains 60: true, contains 65: false

8. Trait objects: Box<dyn Trait>

Box<dyn Trait> is the most common use of Box, covered in Trait Objects. The box gives every implementation the same size, so they fit in one collection.

Rust
trait Notifier {
    fn send(&self, msg: &str) -> String;
}

struct Email(&'static str);
struct Sms(&'static str);

impl Notifier for Email {
    fn send(&self, msg: &str) -> String {
        format!("email to {}: {msg}", self.0)
    }
}

impl Notifier for Sms {
    fn send(&self, msg: &str) -> String {
        format!("sms to {}: {msg}", self.0)
    }
}

fn main() {
    let channels: Vec<Box<dyn Notifier>> = vec![Box::new(Email("ops@x.com")), Box::new(Sms("+1555"))];
    for c in &channels {
        println!("{}", c.send("deploy finished"));
    }
}
Output
email to ops@x.com: deploy finished
sms to +1555: deploy finished

9. Boxing closures and errors

Closures and errors of different types are also stored as Box<dyn Fn...> and Box<dyn Error>, which you've already used.

Rust
use std::error::Error;

fn pick(op: &str) -> Box<dyn Fn(i64, i64) -> i64> {
    match op {
        "+" => Box::new(|a, b| a + b),
        "*" => Box::new(|a, b| a * b),
        _ => Box::new(|a, _| a),
    }
}

fn parse(s: &str) -> Result<i64, Box<dyn Error>> {
    Ok(s.parse()?)
}

fn main() {
    println!("{} {}", pick("+")(2, 3), pick("*")(2, 3));
    println!("{:?}", parse("x").map_err(|e| e.to_string()));
}
Output
5 6
Err("invalid digit found in string")

10. Moving a large value cheaply

Moving a value copies its bytes. For a very large struct, boxing it means only an 8-byte pointer is copied on each move. It can also prevent stack overflows from huge local arrays.

Rust
struct Frame {
    pixels: [u8; 1_000_000], // 1 MB, stored inline
}

fn render(frame: Box<Frame>) -> Box<Frame> {
    frame // moving the Box copies 8 bytes, not 1 MB
}

fn main() {
    let frame = Box::new(Frame { pixels: [7; 1_000_000] });
    let frame = render(frame);
    println!("{} bytes of pixels, first = {}", frame.pixels.len(), frame.pixels[0]);
    println!("size of Frame: {} bytes, size of Box<Frame>: {} bytes", std::mem::size_of::<Frame>(), std::mem::size_of::<Box<Frame>>());
}
Output
1000000 bytes of pixels, first = 7
size of Frame: 1000000 bytes, size of Box<Frame>: 8 bytes

In practice a Vec<u8> is the more common choice for large buffers; Box<[u8; N]> is useful when the size is fixed.

11. Shrinking an enum by boxing a large variant

An enum is as big as its largest variant. Boxing a rarely used large variant makes every value of the enum smaller.

Rust
#[allow(dead_code)]
enum Message {
    Ping,
    Text(String),
    Snapshot([u64; 64]), // 512 bytes
}

#[allow(dead_code)]
enum SmallMessage {
    Ping,
    Text(String),
    Snapshot(Box<[u64; 64]>), // 8 bytes
}

fn main() {
    println!("Message:      {} bytes", std::mem::size_of::<Message>());
    println!("SmallMessage: {} bytes", std::mem::size_of::<SmallMessage>());
}
Output
Message:      520 bytes
SmallMessage: 24 bytes

#[allow(dead_code)] silences warnings about variants this example never constructs.

12. Box<[T]> and Box<str>: fixed-size owned buffers

A Vec<T> stores a pointer, length, and capacity (24 bytes). When a buffer will never grow again, into_boxed_slice() drops the capacity (16 bytes) and any spare memory. The same goes for String and Box<str>.

Rust
fn main() {
    let mut v = Vec::with_capacity(100);
    v.extend([1, 2, 3]);
    let frozen: Box<[i32]> = v.into_boxed_slice();
    println!("{:?} len {}", frozen, frozen.len());

    let name: Box<str> = String::from("ferris").into_boxed_str();
    println!("{name} ({} bytes)", name.len());

    println!("Vec<i32> {} bytes, Box<[i32]> {} bytes", std::mem::size_of::<Vec<i32>>(), std::mem::size_of::<Box<[i32]>>());
}
Output
[1, 2, 3] len 3
ferris (6 bytes)
Vec<i32> 24 bytes, Box<[i32]> 16 bytes

13. Deref coercion: &Box<T> works as &T

A function that takes &T accepts a &Box<T> automatically. This is deref coercion, explained fully in Drop, Deref & Cow.

Rust
fn shout(s: &str) -> String {
    s.to_uppercase()
}

fn total(values: &[u32]) -> u32 {
    values.iter().sum()
}

fn main() {
    let boxed_text: Box<String> = Box::new(String::from("hello"));
    let boxed_values: Box<Vec<u32>> = Box::new(vec![1, 2, 3]);
    println!("{} {}", shout(&boxed_text), total(&boxed_values));
}
Output
HELLO 6

14. Moving a value out of a Box

Dereferencing a Box with * moves the value out and frees the box's allocation.

Rust
fn main() {
    let boxed = Box::new(String::from("unboxed now"));
    let plain: String = *boxed;
    println!("{plain}");
}
Output
unboxed now

15. Box implements the traits of what it holds

Box<T> is Debug, Clone, PartialEq, Ord, Display, and so on whenever T is.

Rust
fn main() {
    let a = Box::new(vec![3, 1, 2]);
    let mut b = a.clone();
    b.sort();
    println!("{:?} {:?} equal: {}", a, b, a == b);
    println!("{}", Box::new(3.5) > Box::new(1.0));
}
Output
[3, 1, 2] [1, 2, 3] equal: false
true

16. Realistic example: an expression evaluator

A small calculator whose syntax tree uses Box for its recursive nodes, with evaluation and pretty printing.

Rust
enum Expr {
    Num(f64),
    Var(&'static str),
    Bin(Box<Expr>, char, Box<Expr>),
}

use Expr::*;

fn bin(l: Expr, op: char, r: Expr) -> Expr {
    Bin(Box::new(l), op, Box::new(r))
}

impl Expr {
    fn eval(&self, vars: &[(&str, f64)]) -> Result<f64, String> {
        match self {
            Num(n) => Ok(*n),
            Var(name) => vars.iter().find(|(v, _)| v == name).map(|(_, x)| *x).ok_or(format!("unknown variable {name}")),
            Bin(l, op, r) => {
                let (a, b) = (l.eval(vars)?, r.eval(vars)?);
                match op {
                    '+' => Ok(a + b),
                    '-' => Ok(a - b),
                    '*' => Ok(a * b),
                    '/' if b == 0.0 => Err(String::from("division by zero")),
                    '/' => Ok(a / b),
                    _ => Err(format!("unknown operator {op}")),
                }
            }
        }
    }

    fn show(&self) -> String {
        match self {
            Num(n) => n.to_string(),
            Var(v) => v.to_string(),
            Bin(l, op, r) => format!("({} {op} {})", l.show(), r.show()),
        }
    }
}

fn main() {
    // price * (1 + tax) - discount
    let e = bin(bin(Var("price"), '*', bin(Num(1.0), '+', Var("tax"))), '-', Var("discount"));
    println!("{}", e.show());
    println!("{:?}", e.eval(&[("price", 100.0), ("tax", 0.2), ("discount", 15.0)]));
    println!("{:?}", e.eval(&[("price", 100.0)]));
    println!("{:?}", bin(Num(1.0), '/', Num(0.0)).eval(&[]));
}
Output
((price * (1 + tax)) - discount)
Ok(105.0)
Err("unknown variable tax")
Err("division by zero")

17. Realistic example: a file-system tree

Directories own their children; Vec<Node> already provides the indirection, so no Box is needed here, which is worth recognizing.

Rust
enum Node {
    File { name: String, bytes: u64 },
    Dir { name: String, children: Vec<Node> },
}

impl Node {
    fn size(&self) -> u64 {
        match self {
            Node::File { bytes, .. } => *bytes,
            Node::Dir { children, .. } => children.iter().map(Node::size).sum(),
        }
    }

    fn print(&self, depth: usize) {
        match self {
            Node::File { name, bytes } => println!("{}{name} ({bytes} B)", "  ".repeat(depth)),
            Node::Dir { name, children } => {
                println!("{}{name}/ ({} B)", "  ".repeat(depth), self.size());
                for c in children {
                    c.print(depth + 1);
                }
            }
        }
    }
}

fn main() {
    let tree = Node::Dir {
        name: String::from("project"),
        children: vec![
            Node::File { name: String::from("Cargo.toml"), bytes: 220 },
            Node::Dir {
                name: String::from("src"),
                children: vec![Node::File { name: String::from("main.rs"), bytes: 1_450 }, Node::File { name: String::from("lib.rs"), bytes: 3_100 }],
            },
        ],
    };
    tree.print(0);
}
Output
project/ (4770 B)
  Cargo.toml (220 B)
  src/ (4550 B)
    main.rs (1450 B)
    lib.rs (3100 B)

18. Realistic example: a plugin registry

Plugins are created from names at runtime and stored as Box<dyn Plugin>.

Rust
trait Plugin {
    fn name(&self) -> &str;
    fn transform(&self, input: &str) -> String;
}

struct Upper;
struct Reverse;
struct Censor(Vec<&'static str>);

impl Plugin for Upper {
    fn name(&self) -> &str {
        "upper"
    }
    fn transform(&self, input: &str) -> String {
        input.to_uppercase()
    }
}

impl Plugin for Reverse {
    fn name(&self) -> &str {
        "reverse"
    }
    fn transform(&self, input: &str) -> String {
        input.chars().rev().collect()
    }
}

impl Plugin for Censor {
    fn name(&self) -> &str {
        "censor"
    }
    fn transform(&self, input: &str) -> String {
        self.0.iter().fold(input.to_string(), |acc, w| acc.replace(w, &"*".repeat(w.len())))
    }
}

fn create(name: &str) -> Option<Box<dyn Plugin>> {
    match name {
        "upper" => Some(Box::new(Upper)),
        "reverse" => Some(Box::new(Reverse)),
        "censor" => Some(Box::new(Censor(vec!["darn", "heck"]))),
        _ => None,
    }
}

fn main() {
    let configured = ["censor", "upper", "unknown"];
    let pipeline: Vec<Box<dyn Plugin>> = configured.iter().filter_map(|n| create(n)).collect();
    let names: Vec<&str> = pipeline.iter().map(|p| p.name()).collect();
    let out = pipeline.iter().fold(String::from("well darn it"), |text, p| p.transform(&text));
    println!("{:?}: {out}", names);
}
Output
["censor", "upper"]: WELL **** IT

19. Realistic example: a state machine with boxed states

Each state is its own type implementing a State trait, and a transition returns the next state as Box<dyn State>. This is the classic GoF State pattern.

Rust
trait State {
    fn name(&self) -> &'static str;
    fn next(self: Box<Self>, event: &str) -> Box<dyn State>;
}

struct Draft;
struct Review {
    approvals: u8,
}
struct Published;

impl State for Draft {
    fn name(&self) -> &'static str {
        "draft"
    }
    fn next(self: Box<Self>, event: &str) -> Box<dyn State> {
        if event == "submit" { Box::new(Review { approvals: 0 }) } else { self }
    }
}

impl State for Review {
    fn name(&self) -> &'static str {
        "review"
    }
    fn next(self: Box<Self>, event: &str) -> Box<dyn State> {
        match event {
            "approve" if self.approvals + 1 >= 2 => Box::new(Published),
            "approve" => Box::new(Review { approvals: self.approvals + 1 }),
            "reject" => Box::new(Draft),
            _ => self,
        }
    }
}

impl State for Published {
    fn name(&self) -> &'static str {
        "published"
    }
    fn next(self: Box<Self>, _event: &str) -> Box<dyn State> {
        self
    }
}

fn main() {
    let mut state: Box<dyn State> = Box::new(Draft);
    for event in ["approve", "submit", "approve", "reject", "submit", "approve", "approve", "submit"] {
        state = state.next(event);
        println!("{event:<8} -> {}", state.name());
    }
}
Output
approve  -> draft
submit   -> review
approve  -> review
reject   -> draft
submit   -> review
approve  -> review
approve  -> published
submit   -> published

self: Box<Self> means the method consumes the boxed state, so a transition can reuse the same allocation (self) or return a new one.

20. Realistic example: a recursive JSON-like pretty printer

Rust
enum Value {
    Num(f64),
    Str(String),
    List(Vec<Value>),
    Pair(Box<Value>, Box<Value>),
}

fn render(v: &Value, indent: usize) -> String {
    let pad = "  ".repeat(indent);
    match v {
        Value::Num(n) => format!("{pad}{n}"),
        Value::Str(s) => format!("{pad}\"{s}\""),
        Value::List(items) => {
            let inner: Vec<String> = items.iter().map(|i| render(i, indent + 1)).collect();
            format!("{pad}[\n{}\n{pad}]", inner.join(",\n"))
        }
        Value::Pair(k, v) => format!("{pad}{} => {}", render(k, 0), render(v, 0)),
    }
}

fn main() {
    let v = Value::List(vec![
        Value::Num(1.5),
        Value::Str(String::from("rust")),
        Value::Pair(Box::new(Value::Str(String::from("key"))), Box::new(Value::Num(42.0))),
        Value::List(vec![Value::Num(1.0), Value::Num(2.0)]),
    ]);
    println!("{}", render(&v, 0));
}
Output
[
  1.5,
  "rust",
  "key" => 42,
  [
    1,
    2
  ]
]

21. Realistic example: building a list with a cursor

Walking a Box-linked list with a mutable cursor is a classic exercise in borrowing. The cursor is a &mut Option<Box<Node>> that always points at the next empty slot.

Rust
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn from_slice(values: &[i32]) -> Option<Box<Node>> {
    let mut head: Option<Box<Node>> = None;
    let mut cursor = &mut head;
    for &v in values {
        let node = cursor.insert(Box::new(Node { value: v, next: None }));
        cursor = &mut node.next;
    }
    head
}

fn to_vec(mut node: &Option<Box<Node>>) -> Vec<i32> {
    let mut out = Vec::new();
    while let Some(n) = node {
        out.push(n.value);
        node = &n.next;
    }
    out
}

fn main() {
    let list = from_slice(&[4, 8, 15, 16, 23, 42]);
    println!("{:?}", to_vec(&list));
}
Output
[4, 8, 15, 16, 23, 42]

Option::insert stores a value in the Option and returns a &mut to it, which is exactly what the cursor needs.

22. When to use Box

Situation Use Box?
A recursive enum or struct Yes, for the recursive field (or use a Vec)
A collection of different types implementing a trait Yes: Vec<Box<dyn Trait>>
Returning different closure or error types Yes: Box<dyn Fn...>, Box<dyn Error>
A very large value moved around often Sometimes
An ordinary struct, String, or Vec No: they're already cheap to move
Rust
fn main() {
    let should_box = |recursive: bool, dyn_trait: bool, huge: bool| recursive || dyn_trait || huge;
    println!("recursive tree: {}", should_box(true, false, false));
    println!("plain config struct: {}", should_box(false, false, false));
}
Output
recursive tree: true
plain config struct: false

Summary

  • Box<T> owns a single value on the heap. It's a pointer-sized value that frees its contents when dropped.
  • Use it for recursive types, trait objects (Box<dyn Trait>), boxed closures and errors, and large values you move often.
  • Box<T> derefs to T: methods work directly, *b gets the value, and &Box<T> coerces to &T.
  • Box<[T]> and Box<str> are compact owned buffers that never grow.
  • Don't box ordinary values; Rust values don't need to be on the heap.

Next: Rc & Weak, for values with more than one owner.