# Smart Pointers
Pointers do that, point to address in memory. 0 Overhead
`&` References are a kind of pointer

`Smart Pointers` are data structe that act like a pointer + metadata and methods.
They may `own` data they point to

Ex: `String` `Vec<T>` -> THey own memory and allow its manipulation.
Basically a `struct` that implements `Deref` and `Drop` traits.
    - `Deref` : Allows to behave like a reference
    - `Drop` : Customize what happens when variable goes out of scope

===

# Using `Box<T>` to Point to Data on the Heap
Basically a pointer to heap allocation of the type. Why use them?
 - Unknown size at compile time, but need to use it in stack (requires exact time when using it)?
 - Move ownership of large amount of data (MAKE SURE ITS NOT COPIED)
 - Own any type that implements a trait, rather than a specific type

## Storing data in Heap with `Box<T>`
```rust
fn main() {
    let b = Box::new(5);
    println!("b = {}", b);
}
```
Box allow access to the type directly, like it was in the stack it will be slower tho. When it goes out of scope both the `Box` and the `Type` are deallocated form stack and heap respectively.

## Recursive Types with Boxes
Type that hold a value of the same type -> Recursive Type
These can't be known at compile time (when does the recursion stop?)

### Cons List
Data Structure that comes from Lisp's `cons` function.
 - `cons` -> Constructs a new pair from 2 arguments, the pair contains the pair forming a list.

 - Colloquially `to cons x into y` -> Construct a container instance by puttin `x` at the start of the new container followed by `y`

An item in a `cons list` contains the item and the next one (`Nil` if it is non-existant, but not invalid)
```rust
enum List<T> {
    Cons(T, List),
    Nil,
}

fn main() {
    let list: List<i32> = Cons(1, Cons(2, Cons(3,Nil)));
}
```
This will not compile: `List` is an infinite type, can't be constructed in stack
How does Rust check the size of a variable?
 - Compute stack size of an type first, ex:
```rust
// Correct Struct
enum Message {
    Quit, // enum size
    Move { x: i32, y: i32 }, // enum size + sizeof(i32 * 2)
    Write(String), // enum size + sizeof(String) -> Only the struct with the pointer, not the actual string in heap
    ChangeColor(i32, i32, i32), // enum size + sizeof(i32 * 3)
}
// Incorrect Struct
enum List<T> {
    Cons(T, List), // sizeof(T) + sizeof(List(sizeof(T) + sizeof(List(...
    Nil,
}
// It will infinetely go through List to compute size!
```

#### Allowing Recursion with Box
`Box` is a pointer to heap, we have fixed stack size, we don't care about heap size.
```rust
enum List<T> {
    Cons(i32, Box<List>), // sizeof(i32) + sizeof(Box)
    Nil
}
```
Box size is known and does not need to check further, data pointing is later redirected to heap.