[Rust Guide] 15.1 Using `Box<T>` to Point to Data on the Heap

15.1.1 Box<T>

Box<T> can be understood simply as a box. It is the simplest smart pointer and allows you to store data on the heap instead of the stack.

The implementation is that Box<T> has a small amount of memory on the stack that stores a pointer to the data living on the heap. In other words, the actual data is stored on the heap. Aside from storing the data on the heap, it has no other overhead, and the tradeoff is that it has no additional features.

At first glance, Box<T> does not seem very different from an ordinary pointer, but the real difference is that Box<T> implements the Deref and Drop traits.

15.1.2 Common Use Cases for Box<T>

When the size of a type cannot be determined at compile time, but the context that uses it needs to know its exact size, Box<T> is a good choice.

When you have a large amount of data and want to transfer ownership, but you need to ensure that it is not copied during the operation.

When you use a value and only care whether it implements a specific trait, not what its concrete type is.

15.1.3 Storing Data on the Heap with Box<T>

Take a look at an example:

fn main() {
    let b = Box::new(5);
    println!("b = {b}");
}

We define the variable b as a value containing a Box pointing to the value 5, which is allocated on the heap. This program will print b = 5.

Like any other owned value, when b goes out of scope, it will free memory just like any other owned value—the memory on both the heap and the stack will be released when the scope ends.

15.1.4 Enabling Recursive Types with Box<T>

At compile time, Rust needs to know how much space a type takes up. However, there is a type called a recursive type whose size cannot be determined at compile time.

Using this diagram as an example, the Cons type has two fields: one field is i32, and the other field is the Cons type itself.

At compile time, Rust needs to know the size of the type. The size of i32 is fixed, but the size of the second Cons field, which is the Cons type itself, cannot be determined.

In this situation, Box<T> can be used. For recursive types, Box<T> makes it possible to determine their size.

This kind of thing exists in functional languages and is called a Cons List.

15.1.5 About Cons List

Cons List is a data structure from the Lisp language. In this structure, each member consists of two elements: one is the value of the current item, such as the i32 in the diagram above; the other is the next element.

This data structure keeps recursing all the way down until the last element. The last member contains only a Nil value and no next element, and the Nil value serves as a terminating marker.

The concepts of Nil and None are not the same. None means an invalid or missing value, while Nil is a terminating marker.

From the diagram, you can see that a Cons List is a kind of linked list.

15.1.6 The Rust Alternative to Cons List

Cons List is not a commonly used collection in Rust. In general, Vec<T> is a better choice.

The following List definition matches the structure of the Cons List above:

enum List {
    Cons(i32, List),
    Nil,
}

The List enum has two variants: Cons and Nil. The Cons variant carries two pieces of data: one of type i32 and one of type List.

There is nothing logically wrong with this definition, but it will fail at compile time:

$ cargo run
   Compiling cons-list v0.1.0 (/tmp/ch15-refresh/cons-list)
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>),
  |               ++++    +

For more information about this error, try `rustc --explain E0072`.
error: could not compile `cons-list` (bin "cons-list") due to 1 previous error

This happens because Rust needs to know the size of the type, but it cannot calculate the size of a recursive type.

15.1.7 How Rust Calculates Type Size

First, let’s look at how Rust determines the size of a type. For example:

enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(i32, i32, i32),
}

To determine how much space to allocate for a Message value, Rust walks through each variant to see which one requires the most space.

Rust considers Message::Quit to need no space, Message::Move to need enough space to store two i32 values, and so on. Because only one variant exists at a time, the space required by a Message value is the space required by its largest variant—typically Write(String), whose String is larger than three i32 values on common 64-bit platforms.

15.1.8 Using Box to Obtain a Sized Recursive Type

As mentioned earlier, Rust needs to know the size of a type, but it cannot calculate the size of a recursive type. So we can use a type with a known size instead, and Box<T> fits the requirement perfectly: it does not store the data itself, but rather a pointer to the data, and the size of a pointer is the fixed usize.

Rust knows the size of Box<T> because Box<T> is essentially a pointer. A pointer does not directly store the value, so no matter how the data it points to changes, the size of the pointer itself does not change. In other words, the size of the pointer does not vary based on the size of the data it points to.

With that in mind, we can modify the original code. Specifically, we replace the unknown-sized part—the nested List type—with Box<List>:

enum List {
    Cons(i32, Box<List>),
    Nil,
}

This is still recursive, but it no longer stores List directly. Instead, it points indirectly to the List value on the heap, which solves the problem in a roundabout way.

15.1.9 Summary of the Box Type

• It only provides indirect storage and heap allocation.
• It has no extra features.
• It has no performance overhead.
• It is suitable for situations that require indirect storage, such as Cons List.
• It implements the Deref and Drop traits.