game-engine-design-exercises/Vector.h

#ifndef VECTOR_H
#define VECTOR_H

#include <cassert>
#include <new>
#include <utility>

template<typename T>
class Vector {
    T* data;
    int capacity;
    int elements;

public:
    Vector() : data(nullptr), capacity(0), elements(0) {
    }

    explicit Vector(int n, const T& t) : Vector() {
        for(int i = 0; i < n; i++) {
            push_back(t);
        }
    }

    explicit Vector(int n) : Vector() {
        // calling Vector(n, T()) would break structures which can be
        // default constructed but not copied e.g. unique pointers elements
        for(int i = 0; i < n; i++) {
            push_back(T());
        }
    }

    ~Vector() {
        // placement new needs explicit destructor calling
        for(int i = 0; i < elements; i++) {
            data[i].~T();
        }
        // casting this pointer not back to its origin type yields a crash
        delete[] reinterpret_cast<char*>(data);
    }

    // allocate new storage for copies
    Vector(const Vector& other)
        : data(allocate(other.capacity)), capacity(other.capacity),
          elements(other.elements) {
        // copy data into new storage
        for(int i = 0; i < elements; i++) {
            new(data + i) T(other.data[i]);
        }
    }

    // this handles copy and move assigment
    // copy: replace current resources with other made by the copy constructor
    // move: replace current resources with other made by the move constructor
    // other gets the old data and is destroyed by the destructor after going
    // out of scope
    Vector& operator=(Vector other) {
        swap(*this, other);
        return *this;
    }

    // construct a default vector so the other vector gets valid values from the
    // swap
    Vector(Vector&& other) : Vector() {
        swap(*this, other);
    }

    void reserve(int size) {
        if(size <= capacity) {
            return;
        }
        Vector v;
        v.capacity = size;
        v.data = allocate(size);
        for(int i = 0; i < elements; i++) {
            v.push_back(std::move(data[i]));
        }
        swap(*this, v);
    }

    void resize(int size, const T& t) {
        // elements will be equal to size after this call but not the capacity
        if(size > elements) {
            // fill until the given size is reached
            for(int i = elements; i < size; i++) {
                push_back(t);
            }
        } else if(size < elements) {
            // remove objects until the size matches
            for(int i = size; i < elements; i++) {
                data[i].~T();
            }
            elements = size;
        }
    }

    void resize(int size) {
        // calling resize(size, T()); would break structures which can be
        // default constructed but not copied e.g. unique pointers elements
        // will be equal to size after this call but not the capacity
        if(size > elements) {
            // fill until the given size is reached
            for(int i = elements; i < size; i++) {
                push_back(T());
            }
        } else if(size < elements) {
            // remove objects until the size matches
            for(int i = size; i < elements; i++) {
                data[i].~T();
            }
            elements = size;
        }
    }

    void push_back(const T& t) {
        ensureCapacity();
        new(data + elements++) T(t);
    }

    void push_back(T&& t) {
        ensureCapacity();
        // && would be lost without std::move
        new(data + elements++) T(std::move(t));
    }

    T& operator[](int index) {
        return data[index];
    }

    const T& operator[](int index) const {
        return data[index];
    }

    T& at(int index) {
        // std states "at" is [] with range check
        assert(index >= 0 && index < elements);
        return (*this)[index];
    }

    const T& at(int index) const {
        // std states "at" is [] with range check
        assert(index >= 0 && index < elements);
        return (*this)[index];
    }

    int size() const {
        return elements;
    }

    T* begin() {
        return data;
    }

    T* end() {
        return data + elements;
    }

    const T* begin() const {
        return data;
    }

    const T* end() const {
        return data + elements;
    }

    void erase(T* from, T* to) {
        T* remove = from;
        T* move = to;
        T* stop = end();
        // fill the hole by moving following objects as long as possible
        while(move != stop) {
            *remove = std::move(*move);
            remove++;
            move++;
        }
        // remove left over objects
        while(remove != stop) {
            remove->~T();
            remove++;
            elements--;
        }
    }

    void erase(T* start) {
        erase(start, start + 1);
    }

    T* as_array() {
        return begin();
    }

    const T* as_array() const {
        return begin();
    }

    void erase_by_swap(int index) {
        elements--;
        if(index != elements) {
            data[index] = std::move(data[elements]);
        }
        data[elements].~T();
    }

    int length() const {
        return capacity;
    }

private:
    static T* allocate(int length) {
        return reinterpret_cast<T*>(new char[sizeof(T) * length]);
    }

    static void swap(Vector& a, Vector& b) {
        std::swap(a.data, b.data);
        std::swap(a.capacity, b.capacity);
        std::swap(a.elements, b.elements);
    }

    void ensureCapacity() {
        if(elements >= capacity) {
            // doubling the size amortizes costs
            reserve(capacity == 0 ? 1 : capacity * 2);
        }
    }
};

#endif