vec.h — Contiguous Growable Array

Introduction

vec.h provides Vec<T, Alloc>, a heap-allocated contiguous growable array. It replaces std::vector<T> in all xpp-owned code paths and closely mirrors Rust's std::vec::Vec in both API design and ownership semantics.

Key differences from std::vector:

• Dual API for every growth path. push() / reserve() / resize() assert on OOM; try_push() / try_reserve() / try_resize() return Result<void, AllocError> for explicit error handling.
• first() / last() return Option<T&>. No undefined behavior on empty containers — None is a first-class answer.
• pop() returns Option<T>. Moving the last element out, not just destroying it. The value is consumed, not lost.
• Allocator-aware. Accepts an optional Alloc template parameter using xpp's allocator protocol (allocate / deallocate / grow / shrink). EBO via CompressedPair means sizeof(Vec<T, GlobalAllocator>) = 24 bytes (3 words).

Design Philosophy

1. Explicit OOM, no exceptions. Every growth path has two forms: a convenience form that XPP_ASSERTs on failure (push, reserve, resize, shrink_to_fit, append), and an explicit try_* form that returns Result<void, AllocError>. Callers choose their trust level — crash-fast in debug, or handle gracefully in production paths.

2. Option for nullable access. get(i), first(), last(), and pop() all return Option. The type system encodes the possibility of "nothing there" without runtime assertions or undefined behavior. operator[] remains unchecked (debug-assert only) for hot-loop performance, use get() when index validity is uncertain.

3. Growth: double, minimum 4. On push-without-capacity, the buffer grows by max(capacity * 2, 4). The minimum ensures small Vecs don't thrash on reallocation (0 → 4 → 8 → 16 → ...). Growth uses default_grow() (allocate + memcpy + deallocate) which the allocator may override with an in-place realloc.

4. Move semantics with cleanup. Move constructor and move assignment steal the buffer and leave the source in a valid empty state (ptr = nullptr, len = 0, cap = 0). The moved-from Vec is safely destructible and reusable.

5. C++11 compatible, header-only. No requires, consteval, or if constexpr. Template parameter defaults and CompressedPair enable zero-overhead allocator storage without C++17 features.

Architecture

classDiagram
    class Vec {
        -CompressedPair~RawStorage, Alloc~ m_data
        +Vec()
        +Vec(size_t capacity, Alloc alloc)
        +Vec(const Vec&)
        +Vec(Vec&&)
        +~Vec()
        +push(T) void
        +try_push(T) Result
        +push_unchecked(T) void
        +pop() Option~T~
        +clear() void
        +truncate(size_t) void
        +get(size_t) Option~T&~
        +first() Option~T&~
        +last() Option~T&~
        +operator[]() T&
        +reserve(size_t) void
        +try_reserve(size_t) Result
        +shrink_to_fit() void
        +try_shrink_to_fit() Result
        +resize(size_t, T) void
        +try_resize(size_t, T) Result
        +append(Vec&) void
        +try_append(Vec&) Result
        +split_off(size_t) Vec
        +swap_remove(size_t) T
        +retain(Pred) void
        +begin() T*
        +end() T*
        +as_span() Span~T~
        +data() T*
        +len() size_t
        +capacity() size_t
        +empty() bool
    }
    class RawStorage {
        +T* ptr
        +size_t len
        +size_t cap
    }
    class CompressedPair {
        +first() RawStorage&
        +second() Alloc&
    }
    class Alloc {
        <<template param>>
        +allocate(Layout) Result~Span, AllocError~
        +deallocate(void*, Layout) void
        +grow / shrink (optional)
    }
    Vec *-- CompressedPair
    CompressedPair *-- RawStorage
    CompressedPair *-- Alloc

The buffer at a glance:

┌──────────────────────┬──────────────────────────────┐
│     initialized      │       uninitialized          │
│     [0 .. len)       │     [len .. capacity)        │
├──────────────────────┼──────────────────────────────┤
│ T, T, T, T, T        │ ????????????????????????????  │
└──────────────────────┴──────────────────────────────┘
        ptr                                              ptr + capacity

Elements in [0, len) are live objects with properly constructed T values. Elements in [len, capacity) are raw uninitialized memory — no constructors have run, no destructors will run. push() placement-news into the gap; pop() destructs the last element and decrements len.

API Reference

Construction

Capacity

Element Access

Mutation

Bulk Operations

Iteration

Iterators are raw pointers — compatible with C++11 range-for and STL algorithms.

Allocator Access

Usage Examples

Basic push / pop

xpp::Vec<int> v;
v.push(42);
v.push(7);
v.push(99);

// Access
int a = v[0];                    // 42
auto first = v.first();          // Option<int&>: Some(42)
auto last  = v.last();           // Option<int&>: Some(99)
auto oob   = v.get(100);         // Option<int&>: None

// Pop
auto x = v.pop();                // Option<int>: Some(99)
// v is now {42, 7}

Empty container safety

xpp::Vec<int> empty;
assert(empty.pop().is_none());   // None, not UB
assert(empty.first().is_none()); // None, not UB
assert(empty.last().is_none());  // None, not UB
assert(empty.get(0).is_none());  // None, not UB

Explicit error handling

xpp::Vec<LargeObject> v;
auto r = v.try_push(LargeObject{...});
if (r.is_err()) {
    // OOM — degrade gracefully
    return xpp::err(AllocError{});
}

Reserve + unchecked push (hot path)

xpp::Vec<int> v;
v.reserve(1000);  // one allocation
for (int i = 0; i < 1000; i++) {
    v.push_unchecked(i);  // no capacity check, no grow
}

split_off

xpp::Vec<int> v;
v.push(1); v.push(2); v.push(3); v.push(4);

auto tail = v.split_off(2);
// v    == {1, 2}
// tail == {3, 4}

swap_remove (fast unordered removal)

xpp::Vec<std::string> v;
v.push("a"); v.push("b"); v.push("c");

auto removed = v.swap_remove(0);  // removes "a", swaps "c" to position 0
// v == {"c", "b"}   (order not preserved!)

retain (in-place filter)

xpp::Vec<int> v;
v.push(1); v.push(2); v.push(3); v.push(4);

v.retain([](int x) { return x % 2 == 0; });
// v == {2, 4}

Range-for iteration

xpp::Vec<int> v;
v.push(1); v.push(2); v.push(3);

for (auto& x : v) {
    x *= 2;
}
// v == {2, 4, 6}

// Const iteration:
const auto& cv = v;
for (const auto& x : cv) {
    printf("%d\n", x);
}

Copy and move

xpp::Vec<int> a;
a.push(1); a.push(2);

xpp::Vec<int> b(a);              // deep copy
xpp::Vec<int> c(std::move(a));   // move: a is now empty, c owns the buffer

a = b;                            // copy assignment
a = std::move(b);                 // move assignment

Custom allocator

struct CountingAlloc {
    size_t allocs = 0;
    size_t frees  = 0;

    xpp::Result<xpp::Span<uint8_t>, xpp::AllocError>
    allocate(xpp::Layout layout) const {
        void* p = ::operator new(layout.size);
        if (!p) return xpp::err(xpp::AllocError{});
        const_cast<CountingAlloc*>(this)->allocs++;
        return xpp::ok(xpp::Span<uint8_t>(static_cast<uint8_t*>(p), layout.size));
    }

    void deallocate(void* ptr, xpp::Layout) const noexcept {
        const_cast<CountingAlloc*>(this)->frees++;
        ::operator delete(ptr);
    }
};

CountingAlloc ca;
{
    xpp::Vec<int, CountingAlloc> v(ca);
    v.push(1);
    v.push(2);
    assert(v.allocator().allocs >= 1);
}
// ca.frees reflects deallocation

Comparison

Implementation Notes

Storage: CompressedPair

template <class T, class Alloc>
class Vec {
    _::CompressedPair<RawStorage, Alloc> m_data;

    struct RawStorage {
        T*     ptr;   // heap buffer
        size_t len;   // initialized elements
        size_t cap;   // allocated slots
    };
};

CompressedPair applies EBO: when Alloc is empty (like GlobalAllocator), m_data is exactly RawStorage (24 bytes). When Alloc is stateful, it grows by sizeof(Alloc).

Accessor methods for CompressedPair fields

Rather than storing m_len and m_cap as reference members (which would bloat sizeof(Vec)), the implementation uses private accessor methods that return references into m_data.first():

size_t& len_() { return m_data.first().len; }
size_t& cap_() { return m_data.first().cap; }

These are inlined by the compiler — zero runtime cost, clean sizeof.

Growth: default_grow and default_shrink

grow_to() delegates to default_grow(allocator, ptr, old_layout, new_layout), which is:

1. Allocate new buffer (allocator.allocate(new_layout))
2. memcpy old elements to new buffer
3. Deallocate old buffer (allocator.deallocate(ptr, old_layout))

try_shrink_to_fit() uses default_shrink() instead of grow_to() because grow_to() short-circuits when new_cap <= capacity() — which is always true for a shrink operation. default_shrink() unconditionally reallocates to the smaller size.

For allocators with native realloc (e.g. jemalloc, tcmalloc), overriding grow() and shrink() avoids the intermediate copy.

Placement-new construction and explicit destruction

All element construction uses placement-new:

::new (ptr() + len()) T(value);   // push
::new (ptr() + len()) T(std::move(value));  // push (rvalue)

Destruction is explicit (never delete):

ptr()[i].~T();   // individual
destroy_range(begin_idx, end_idx);  // batch

dealloc_buffer() calls allocator.deallocate() on the raw memory — it does NOT call destructors. The caller must have already destroyed all live elements.

No const T

A static_assert(!std::is_const<T>::value, ...) prevents Vec<const int> — a vector of immutable elements is semantically nonsensical (you can't move out of const, can't grow by copying const, etc.).

Omitted methods

• into_raw_parts() / from_raw_parts() — data() + len() + capacity() already expose the same information. The consuming/reconstruction semantics add no capability in C++ (no FFI boundary to cross).
• first_mut() / last_mut() — C++ distinguishes mutable vs const access via const-qualification on the member function, not via separate method names.
• get_many_mut([i, j]) — Requires compile-time proof that the two indices are distinct. C++ cannot express this safely without runtime checks.