# Box\<T>

## What is the `Box<T>` Smart Pointer?

{% hint style="success" %}
💡 `Box<T>` is a smart pointer which allows you to allocate memory in the **heap** rather than the **stack** for data of type `T` and ensures automatic deallocation when it goes out of scope.
{% endhint %}

It’s used most often for these situations:

* When the size of your data is unknown at compile time, and you can not allocate it on the stack.
* When building recursive data structures like trees requires nodes that hold references to themselves.
* When you need to transfer ownership of data allocated on the heap. By moving a `Box<T>`, you transfer ownership of the underlying data as well.
* When working with trait objects (***dynamically sized types***), you might need to allocate them on the heap.

## Storing Data On The Heap with `Box<T>`

```rust
fn main() {
    // Allocate memory on the heap for an i32 and store the value 10
    let x = Box::new(10);
    println!("Value in the box: {}", x);
}
```

We define the variable `x` to have the value of a `Box` that points to the value `10`, which is allocated on the heap. This program will print `Value in the box: 10` .

When a box goes out of scope, `x` will be deallocated, and this will happen for both the box which is stored on the **stack,** and its data which is stored in the **heap** as well.

<figure><img src="https://2930324358-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MCVzu45Bb9LVrMqjdY6%2Fuploads%2FMpOfCJVxBPdWvyCy6Dwf%2Fimage.png?alt=media&#x26;token=d8d674cb-6773-482e-9d22-fd17ebda453d" alt=""><figcaption><p>Store data in heap with Box&#x3C;T></p></figcaption></figure>

## Recursive Types with `Box<T>`

As we all know Rust requires knowing the size of a type at compile time. This can be a challenge when dealing with recursive data structures, where a value can contain a reference to itself. Here's how `Box<T>` comes into play to enable recursive types:

```rust
// This won't work!
enum List {
  Cons(i32, List), // Error: Recursive type with List itself
  Nil,
}
```

This code defines a `List` enum with two variants: `Cons` and `Nil`.

`Cons` holds an `i32` value and a reference to another `List` element. However, this creates a problem. The compiler cannot determine the size of `List` at compile time because it depends on itself!

Instead, we're going to use `Box<T>` to rewrite the List enum.

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

impl List {
    fn new() -> List {
        List::Nil
    }

    fn push(self, element: i32) -> List {
        List::Cons(element, Box::new(self))
    }
}

fn main() {
    // Create an empty list
    let list = List::new();

    // Prepend some elements
    let list = list.push(1);
    let list = list.push(2);
    let list = list.push(3);

    // Print the list
    println!("List: {:?}", list);
}

// Output
List: Cons(3, Cons(2, Cons(1, Nil)))

// Structure Visualization
List::Cons(3, Box ->
    List::Cons(2, Box ->
        List::Cons(1, Box ->
            List::Nil)))
```

In this code, `Cons` now holds an `i32` value and a `Box<List>`. This `Box<List>` acts as a pointer to a `List` element on the heap.

The compiler now knows the size of `Cons` which holds `i32`, and a `pointer`, both with **fixed sizes.** Rust always knows how much space a `Box<T>` needs because the size of the pointer doesn’t change based on the amount of data it’s pointing to.

<figure><img src="https://2930324358-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MCVzu45Bb9LVrMqjdY6%2Fuploads%2FwVMBWq3Rb211fofji5pP%2Fimage.png?alt=media&#x26;token=d8c57ca5-d685-4a3a-94d9-ad211ec19f3b" alt=""><figcaption></figcaption></figure>