Dynamic array (your own vector)

std::vector is the default container in C++, and building one teaches more about the language than almost any other exercise: object lifetimes, ownership, the rule of five, move semantics, exception safety and amortized analysis all show up in about 150 lines. This lesson builds Vec<T> piece by piece.

1. Memory is not objects

A Vec with capacity 8 and size 3 holds 3 objects and 5 slots of raw memory. The difference matters: an object has a lifetime (its constructor ran; its destructor must run), raw memory doesn't.

So new T[8] is the wrong tool: it constructs eight objects you don't have (and doesn't compile at all if T has no default constructor). Instead, separate the two jobs:

#include <memory>
#include <print>
#include <string>

int main() {
    std::allocator<std::string> alloc;
    std::string* p = alloc.allocate(4);          // memory for 4 strings, no strings yet

    std::construct_at(p + 0, "hello");           // two live objects
    std::construct_at(p + 1, 5, '!');
    std::println("{} {}", p[0], p[1]);

    std::destroy(p, p + 2);                      // end exactly the lifetimes we started
    alloc.deallocate(p, 4);                      // then return the memory
}

The class invariant for Vec: slots [0, size_) hold live objects; slots [size_, cap_) are raw memory. Every member function must keep that true.

2. Growth: why doubling

When size_ == cap_, push_back needs a bigger buffer, and every existing element has to be moved into it. How much bigger?

Grow by a constant k. Reallocations happen at sizes k, 2k, 3k, …, and each moves all current elements: k + 2k + 3k + … + n ≈ n²/(2k) moves for n push_backs. Quadratic — a bigger k only shrinks the constant.

Grow by a factor (×2). Reallocations happen at sizes 1, 2, 4, …, n, and the total number of moves is 1 + 2 + 4 + … + n/2 < n. So n push_backs cost fewer than n constructions plus n moves: amortized O(1) per push_back, even though an individual push_back occasionally costs O(n).

#include <cstddef>
#include <print>

int main() {
    for (std::size_t n : {1'000, 1'000'000}) {
        std::size_t doubling = 0, plus16 = 0;
        for (std::size_t cap = 1; cap < n; cap *= 2) doubling += cap;   // moves at each growth
        for (std::size_t cap = 16; cap < n; cap += 16) plus16 += cap;
        std::println("n={:>9}: ×2 moves {:>9}, +16 moves {:>13}", n, doubling, plus16);
    }
}

3. Reallocation, step by step

Growing to capacity n:

1. allocate raw storage for n elements;
2. move-construct each element into the new storage;
3. destroy the old elements (moved-from objects still have lifetimes!);
4. deallocate the old storage;
5. point data_ at the new storage and set cap_ = n.

void reserve(std::size_t n) {
    if (n <= cap_) return;
    T* p = std::allocator<T>{}.allocate(n);
    for (std::size_t i = 0; i < size_; ++i)
        std::construct_at(p + i, std::move_if_noexcept(data_[i]));
    std::destroy(data_, data_ + size_);
    if (data_) std::allocator<T>{}.deallocate(data_, cap_);
    data_ = p;
    cap_ = n;
}

Why move_if_noexcept

Suppose moving element 3 throws, halfway through step 2. Elements 0–2 have already been moved out of the old buffer, so the old buffer is damaged and you can't go back. If instead you copy, the originals are untouched: on failure, destroy what you built, free the new buffer, rethrow, and the vector is exactly as before. That's the strong exception guarantee.

std::move_if_noexcept(x) returns an rvalue (so the move constructor is used) if T's move constructor is noexcept — or if T can't be copied at all — and an lvalue (so the copy constructor is used) otherwise. Moves that can't throw are safe to use; moves that might throw aren't.

Practical consequence: mark your move constructors noexcept. A type with a potentially-throwing move constructor is copied every time a std::vector of it grows.

#include <print>
#include <vector>

struct Loud {
    Loud() = default;
    Loud(const Loud&) { std::println("  copy"); }
    Loud(Loud&&) noexcept { std::println("  move"); }   // try removing noexcept
};

int main() {
    std::vector<Loud> v(2);
    std::println("growing:");
    v.reserve(v.capacity() + 1);   // forces a reallocation
}

4. The aliasing trap: v.push_back(v[0])

push_back(const T& value) takes a reference. If the vector is full and value refers to one of its own elements, then a naïve implementation — reallocate first, then construct the new element from value — reads from the old buffer after freeing it.

// Wrong when value aliases an element:
if (size_ == cap_) reserve(2 * cap_);           // frees the buffer value lives in
std::construct_at(data_ + size_, value);        // reads freed memory

The fix is ordering: when growing, construct the new element in the new buffer first, then move the old elements across, then free the old buffer. std::vector is required to get this right, so your Vec should too.

5. Iterator invalidation

Pointers, references and iterators into the buffer die with it. After any operation that reallocates — push_back / emplace_back when size() == capacity(), reserve(n) with n > capacity(), shrink_to_fit — every pointer into the vector dangles. reserve up front is how you keep them valid:

#include <print>
#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(10);                 // capacity >= 10: no reallocation below
    v.push_back(1);
    int* first = &v[0];
    for (int i = 2; i <= 10; ++i) v.push_back(i);
    std::println("{}", *first);    // still valid
}

Without the reserve, the same code reads a freed buffer — undefined behaviour that AddressSanitizer reports as heap-use-after-free.

6. Owning resources: the rule of five

Vec owns a buffer and the objects in it, so the compiler-generated copy operations (which copy the pointer) are wrong, and you need all five:

Vec(Vec&& other) noexcept
    : data_(std::exchange(other.data_, nullptr)),
      size_(std::exchange(other.size_, 0)),
      cap_(std::exchange(other.cap_, 0)) {}

Vec& operator=(const Vec& other) {
    Vec copy(other);    // may throw — *this untouched so far
    swap(copy);         // noexcept
    return *this;       // old contents destroyed with `copy`
}

Copy-and-swap handles self-assignment for free and gives the strong guarantee.

7. Worked example: emplace_back

Putting sections 2–4 together:

#include <cstddef>
#include <memory>
#include <print>
#include <string>
#include <utility>

template <class T>
struct MiniVec {
    T* data_ = nullptr;
    std::size_t size_ = 0, cap_ = 0;

    template <class... Args>
    T& emplace_back(Args&&... args) {
        if (size_ == cap_) {
            std::size_t n = cap_ == 0 ? 1 : 2 * cap_;              // geometric growth
            T* p = std::allocator<T>{}.allocate(n);
            std::construct_at(p + size_, std::forward<Args>(args)...);  // new element first
            for (std::size_t i = 0; i < size_; ++i)
                std::construct_at(p + i, std::move_if_noexcept(data_[i]));
            std::destroy(data_, data_ + size_);
            if (data_) std::allocator<T>{}.deallocate(data_, cap_);
            data_ = p;
            cap_ = n;
        } else {
            std::construct_at(data_ + size_, std::forward<Args>(args)...);
        }
        return data_[size_++];
    }

    ~MiniVec() {
        std::destroy(data_, data_ + size_);
        if (data_) std::allocator<T>{}.deallocate(data_, cap_);
    }
};

int main() {
    MiniVec<std::string> v;
    v.emplace_back("alpha");
    for (int i = 0; i < 5; ++i) v.emplace_back(v.data_[0]);   // aliasing, across growth
    std::println("size {}, capacity {}, last {}", v.size_, v.cap_, v.data_[v.size_ - 1]);
}

(For brevity this version leaks the new buffer if a copy throws mid-growth; the build task asks you to handle that too.)

Faded example — your turn

Write pop_back and clear for MiniVec. Then answer: does either change cap_? Does either need to touch the allocator?

void pop_back() { /* ??? */ }
void clear() noexcept { /* ??? */ }

void pop_back() { --size_; std::destroy_at(data_ + size_); }
void clear() noexcept { std::destroy(data_, data_ + size_); size_ = 0; }

Summary

• Keep raw storage and live objects separate: allocate / construct_at / destroy / deallocate. Never new T[n].
• Grow by a factor, not a constant: amortized O(1) push_back.
• Reallocate in order: allocate, construct the new element, move the old ones (move_if_noexcept), destroy, deallocate.
• Mark move operations noexcept, or vectors of your type will copy.
• Reallocation invalidates every pointer and iterator; reserve prevents it.
• An owning type needs the rule of five; copy-and-swap makes assignment easy.