Custom Vector-Like Collection

A custom dynamic array (RawVec<T> / MiniVec<T>) is a heap-allocated, contiguous, growable buffer implemented directly on top of std::alloc::Layout, std::ptr::NonNull<T>, and pointer arithmetic. Implementing a vector from first principles requires managing raw memory allocation, geometric capacity doubling, uninitialized memory safety, ownership transfer via Deref<Target = [T]>, and deterministic destruction of initialized elements alongside buffer deallocation in Drop.

Memory Layout and Invariants

MiniVec<T> on stack (24 bytes on 64-bit)
+------------------+------------------+------------------+
| ptr: NonNull<T>  | len: usize (3)   | cap: usize (4)   |
+--------+---------+------------------+------------------+
         |
         v  Heap allocation: Layout::array::<T>(cap)
         +---------+---------+---------+-----------------+
         | Elem 0  | Elem 1  | Elem 2  | Uninitialized   |
         +---------+---------+---------+-----------------+
         |<------- initialized ------->|<-- spare cap -->|

Complete Implementation

use std::alloc::{self, Layout};
use std::fmt;
use std::marker::PhantomData;
use std::ops::{Deref, DerefMut, Index, IndexMut};
use std::ptr::{self, NonNull};

pub struct MiniVec<T> {
    ptr: NonNull<T>,
    len: usize,
    cap: usize,
    _marker: PhantomData<T>,
}

unsafe impl<T: Send> Send for MiniVec<T> {}
unsafe impl<T: Sync> Sync for MiniVec<T> {}

impl<T> MiniVec<T> {
    pub const fn new() -> Self {
        assert!(
            std::mem::size_of::<T>() != 0,
            "ZSTs are not supported in MiniVec"
        );
        Self {
            ptr: NonNull::dangling(),
            len: 0,
            cap: 0,
            _marker: PhantomData,
        }
    }

    pub fn with_capacity(capacity: usize) -> Self {
        let mut vec = Self::new();
        if capacity > 0 {
            vec.reserve_exact(capacity);
        }
        vec
    }

    pub const fn len(&self) -> usize {
        self.len
    }

    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub const fn capacity(&self) -> usize {
        self.cap
    }

    pub fn push(&mut self, value: T) {
        if self.len == self.cap {
            self.grow();
        }
        // SAFETY: `self.len < self.cap` is guaranteed after `grow()`,
        // and `self.ptr.as_ptr().add(self.len)` points to valid uninitialized memory.
        unsafe {
            ptr::write(self.ptr.as_ptr().add(self.len), value);
        }
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            self.len -= 1;
            // SAFETY: The element at `self.len` was initialized and is now logically removed.
            unsafe { Some(ptr::read(self.ptr.as_ptr().add(self.len))) }
        }
    }

    pub fn insert(&mut self, index: usize, element: T) {
        assert!(index <= self.len, "insert index out of bounds");
        if self.len == self.cap {
            self.grow();
        }
        // SAFETY: Shifting `self.len - index` elements right by 1 stays within `self.cap`.
        unsafe {
            let p = self.ptr.as_ptr().add(index);
            if index < self.len {
                ptr::copy(p, p.add(1), self.len - index);
            }
            ptr::write(p, element);
        }
        self.len += 1;
    }

    pub fn remove(&mut self, index: usize) -> T {
        assert!(index < self.len, "remove index out of bounds");
        self.len -= 1;
        // SAFETY: `index` is within initialized bounds; trailing elements shift left by 1.
        unsafe {
            let p = self.ptr.as_ptr().add(index);
            let result = ptr::read(p);
            ptr::copy(p.add(1), p, self.len - index);
            result
        }
    }

    fn reserve_exact(&mut self, new_cap: usize) {
        assert!(new_cap > self.cap);
        let new_layout = Layout::array::<T>(new_cap).expect("allocation capacity overflow");
        assert!(
            new_layout.size() <= isize::MAX as usize,
            "allocation too large"
        );

        let new_ptr = if self.cap == 0 {
            // SAFETY: `new_layout.size() > 0` because `size_of::<T>() > 0` and `new_cap > 0`.
            unsafe { alloc::alloc(new_layout) }
        } else {
            let old_layout = Layout::array::<T>(self.cap).unwrap();
            // SAFETY: `self.ptr` was allocated with `old_layout`, and `new_layout.size() > 0`.
            unsafe { alloc::realloc(self.ptr.as_ptr() as *mut u8, old_layout, new_layout.size()) }
        };

        self.ptr = match NonNull::new(new_ptr as *mut T) {
            Some(p) => p,
            None => alloc::handle_alloc_error(new_layout),
        };
        self.cap = new_cap;
    }

    fn grow(&mut self) {
        let new_cap = if self.cap == 0 { 4 } else { self.cap * 2 };
        self.reserve_exact(new_cap);
    }
}

impl<T> Deref for MiniVec<T> {
    type Target = [T];

    fn deref(&self) -> &[T] {
        // SAFETY: `0..self.len` is initialized and properly aligned.
        unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.len) }
    }
}

impl<T> DerefMut for MiniVec<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        // SAFETY: `0..self.len` is initialized and uniquely borrowed via `&mut self`.
        unsafe { std::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.len) }
    }
}

impl<T> Index<usize> for MiniVec<T> {
    type Output = T;
    fn index(&self, index: usize) -> &Self::Output {
        &(**self)[index]
    }
}

impl<T> IndexMut<usize> for MiniVec<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut (**self)[index]
    }
}

impl<T: fmt::Debug> fmt::Debug for MiniVec<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&**self, f)
    }
}

impl<T> Drop for MiniVec<T> {
    fn drop(&mut self) {
        if self.cap != 0 {
            // Drop all remaining initialized elements in place.
            unsafe {
                ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr.as_ptr(), self.len));
                let layout = Layout::array::<T>(self.cap).unwrap();
                alloc::dealloc(self.ptr.as_ptr() as *mut u8, layout);
            }
        }
    }
}

pub struct IntoIter<T> {
    buf: NonNull<T>,
    cap: usize,
    start: *const T,
    end: *const T,
}

impl<T> IntoIterator for MiniVec<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        let ptr = self.ptr;
        let cap = self.cap;
        let len = self.len;
        std::mem::forget(self);

        // SAFETY: `ptr.as_ptr().add(len)` stays within or one-past the allocation.
        let end = unsafe { ptr.as_ptr().add(len) };
        IntoIter {
            buf: ptr,
            cap,
            start: ptr.as_ptr(),
            end,
        }
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.start == self.end {
            None
        } else {
            // SAFETY: `self.start < self.end` points to an initialized element not yet yielded.
            unsafe {
                let item = ptr::read(self.start);
                self.start = self.start.add(1);
                Some(item)
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = (self.end as usize - self.start as usize) / std::mem::size_of::<T>();
        (remaining, Some(remaining))
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.start == self.end {
            None
        } else {
            // SAFETY: Decrementing `self.end` steps onto the last initialized element.
            unsafe {
                self.end = self.end.sub(1);
                Some(ptr::read(self.end))
            }
        }
    }
}

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        if self.cap != 0 {
            let remaining = (self.end as usize - self.start as usize) / std::mem::size_of::<T>();
            unsafe {
                ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
                    self.start as *mut T,
                    remaining,
                ));
                let layout = Layout::array::<T>(self.cap).unwrap();
                alloc::dealloc(self.buf.as_ptr() as *mut u8, layout);
            }
        }
    }
}

fn main() {
    let mut v = MiniVec::new();
    println!("Initial: len={}, cap={}", v.len(), v.capacity());

    for word in ["alpha", "beta", "gamma", "delta", "epsilon"] {
        v.push(String::from(word));
    }
    println!("After 5 pushes: {:?} (len={}, cap={})", v, v.len(), v.capacity());

    v.insert(2, String::from("inserted"));
    println!("After insert(2): {:?}", v);

    let removed = v.remove(1);
    println!("Removed index 1 ('{}'): {:?}", removed, v);

    // Slice methods work directly through Deref<Target = [T]>
    v.sort();
    println!("Sorted via slice DerefMut: {:?}", v);

    let mut iter = v.into_iter();
    println!("Front: {:?}, Back: {:?}", iter.next(), iter.next_back());
    let rest: Vec<String> = iter.collect();
    println!("Remaining collected: {:?}", rest);
}

Initial: len=0, cap=0
After 5 pushes: ["alpha", "beta", "gamma", "delta", "epsilon"] (len=5, cap=8)
After insert(2): ["alpha", "beta", "inserted", "gamma", "delta", "epsilon"]
Removed index 1 ('beta'): ["alpha", "inserted", "gamma", "delta", "epsilon"]
Sorted via slice DerefMut: ["alpha", "delta", "epsilon", "gamma", "inserted"]
Front: Some("alpha"), Back: Some("inserted")
Remaining collected: ["delta", "epsilon", "gamma"]