vector<T>.cpp — Custom Implementation

A from-scratch implementation of std::vector focusing on Manual Memory Management, RAII principles, and Strong Exception Guarantees.

Geometric Growth

Uses a 2x growth factor to achieve amortized O(1) push_back performance, minimizing reallocation frequency.

Move Semantics

Optimized for efficient transfer of resources via Move semantics, significantly reducing expensive deep copies.

Custom Allocator

Utilizes ::operator new to separate memory allocation from object construction.

The Implementation

vector.hpp

cpp

#include <iostream>
#include <memory>
#include <algorithm>
#include <utility>

template <typename T>
class Vector {
private:
    T* data = nullptr;
    size_t sz = 0;
    size_t cap = 0;

    void reallocate(size_t new_cap) {
        T* new_data = static_cast<T*>(::operator new(new_cap * sizeof(T)));
        
        for (size_t i = 0; i < sz; ++i) {
            new(&new_data[i]) T(std::move_if_noexcept(data[i]));
        }

        for (size_t i = 0; i < sz; ++i) {
            data[i].~T();
        }
        
        ::operator delete(data);
        data = new_data;
        cap = new_cap;
    }

public:
    Vector() = default;
    
    void push_back(const T& value) {
        if (sz >= cap) {
            reallocate(cap == 0 ? 1 : cap * 2);
        }
        new(&data[sz]) T(value);
        sz++;
    }

    void push_back(T&& value) {
        if (sz >= cap) {
            reallocate(cap == 0 ? 1 : cap * 2);
        }
        new(&data[sz]) T(std::move(value));
        sz++;
    }

    ~Vector() {
        for (size_t i = 0; i < sz; ++i) {
            data[i].~T();
        }
        ::operator delete(data);
    }
    
    size_t size() const { return sz; }
    size_t capacity() const { return cap; }
    T& operator[](size_t index) { return data[index]; }
};

Performance Considerations

One of the critical sections of a vector is the Reallocation Logic. When the capacity is reached, we must allocate a new chunk of memory and move the existing elements. By using std::move_if_noexcept, I ensure that if the move constructor might throw, we fallback to a copy to maintain the Strong Exception Guarantee (the original vector remains unchanged if reallocation fails).