🧩 Reinventing from Scratch: Building Vec<T> the Hard Way

Chapter 1 — “What Even Is a Vector?”

“The only way to truly understand Rust’s safety is to tear it apart and rebuild it — piece by unsafe piece.”

🧭 1.1. The Big Picture

Everyone uses Vec<T>. Few understand how it’s built. Fewer still have looked into the raw memory arena where it’s born.

In this chapter, we’ll peel away the abstractions until we’re left with three naked truths:

1. A Vec<T> is just a contiguous block of memory (the heap playground).
2. It keeps track of two numbers: how much it owns (capacity) and how much it’s using (length).
3. It manages ownership of that memory — allocating, resizing, freeing — safely (most of the time).

Let’s reconstruct this idea from zero.

🧠 A Thought Experiment

Imagine you want to collect i32s dynamically:

let mut numbers = Vec::new();
numbers.push(1);
numbers.push(2);
numbers.push(3);

From the outside: clean, safe, fast.

Under the hood:

• The first push() allocates space for a few integers.
• The second and third go into that space.
• When you exceed capacity, Rust reallocates — copying old data into a bigger box.
• When numbers goes out of scope, it drops all elements and frees the heap memory.

That’s all Vec does — but each step involves sharp knives:

Allocation, pointer arithmetic, and lifetimes. Welcome to the Unsafe Zone.

⚙️ 1.2. Memory: The Stack vs. The Heap

Rust stores data in two places:

• Stack → fast, fixed-size, automatically freed.
• Heap → slower, flexible-size, manually managed.

A Vec<T> always lives on the stack, but its contents live on the heap.

Let’s visualize it:

Stack:
+-------------------------+
|   Vec<T>               |
|   +------------------+ |
|   | ptr → 0x7ff3... | |
|   | len = 3         | |
|   | cap = 4         | |
+-------------------------+

Heap:
0x7ff3... → [1, 2, 3, _]

So the Vec struct itself is only three words: ptr, len, cap.

⚠️ Sidenote: “Why Not Just a Linked List?”

Because CPUs love contiguous memory. Sequential memory = cache-friendly = blazing fast. Linked lists are jumpy — each node could be anywhere.

That’s why Rust’s Vec<T> is the default choice for almost everything: you can traverse, slice, and borrow it efficiently.

🧩 1.3. Let’s Build the Skeleton

We’ll start our own version — let’s call it “MyVec” — a minimal imitation of Vec<T>.

struct MyVec<T> {
    ptr: *mut T,
    len: usize,
    cap: usize,
}

Looks innocent, right? But this struct is like holding a live wire. That *mut T (a raw pointer) has no guarantees — not even that it’s valid!

So before we can push anything, we need to learn how to allocate memory manually.

That’s our next step.

🚧 1.4. Setting the Stage for Allocation

To play with heap memory, we need Rust’s low-level allocator API from std::alloc.

use std::alloc::{alloc, dealloc, Layout};

Let’s make a constructor:

impl<T> MyVec<T> {
    fn new() -> Self {
        MyVec {
            ptr: std::ptr::null_mut(),
            len: 0,
            cap: 0,
        }
    }
}

This null_mut() pointer means:

“I have no memory yet — don’t touch me.”

But soon, we’ll use alloc() to get a slice of the heap.

💡 Sidenote: What’s Layout?

Layout describes how much space to allocate and how to align it.

let layout = Layout::array::<T>(n).unwrap();

This ensures:

• T is correctly aligned (e.g., 4 bytes for u32, 8 bytes for f64),
• The total size = n * size_of::<T>().

Misalignment = Undefined Behavior (UB). That’s Rustonomicon Rule #1:

If you think you’re safe but haven’t checked alignment — you’re already unsafe.

⚠️ 1.5. Unsafe Zone Ahead

To actually allocate memory:

unsafe {
    let layout = Layout::array::<T>(10).unwrap();
    let ptr = alloc(layout) as *mut T;
}

Here:

• alloc() gives you raw, uninitialized memory.
• Writing to it without initialization → UB.
• Forgetting to free it → memory leak.
• Freeing it twice → double free (UB again).

🔥 Warning: Once you enter unsafe, you become the compiler’s brain. You must manually enforce all the guarantees it normally protects.

🧠 1.6. What We’ve Learned So Far

We now understand the anatomy of a Vec:

• It’s a small struct on the stack.
• It holds a raw pointer to heap memory.
• It tracks how many elements are used and how much space it owns.
• It needs explicit allocation, initialization, and cleanup.

The next chapter — “Manual Memory Management 101” — will be our first dive into std::alloc:

We’ll actually create, write to, and free heap memory safely (or almost safely).

🧭 Chapter Summary

🧩 Next Up → Chapter 2: Manual Memory Management 101

We’ll summon the heap, allocate raw space for T, and handle alloc() / dealloc() by hand.

Would you like me to continue writing Chapter 2 (Manual Memory Management 101) next — with full examples, visual diagrams, and “unsafe” callouts like this?