main.cpp

#include <iostream>
#include <vector>

template <typename T>
class Arr {
public:
    Arr() : m_size { 0 }, m_capacity { 0 }, m_data{ nullptr } {};
    ~Arr() { ::operator delete(m_data); }

    [[nodiscard]] size_t size() const { return m_size; }
    [[nodiscard]] size_t capacity() const { return m_capacity; }
    [[nodiscard]] bool empty() const { return m_size == 0; }
    [[nodiscard]] bool full() const { return m_size == m_capacity; }

    void push_back(const T& value) {
        if (m_size == m_capacity)
            grow_capacity(m_size + 1);
        new (&m_data[m_size++]) T(value);
    }

    void push_back(T&& value) {
        if (m_size == m_capacity)
            grow_capacity(m_size + 1);
        new (&m_data[m_size++]) T(std::move(value));
    }

    void prepare_bulk(const size_t count) {
        if (m_capacity < m_size + count) {
            grow_capacity(m_size + count);
        }
    }

    void end_bulk(const bool shrink_to_fit = false) {
        if (shrink_to_fit && m_capacity > m_size) {
            T* new_data = static_cast<T*>(::operator new(sizeof(T) * m_size));

            if constexpr (std::is_trivially_copyable_v<T>)
                memcpy(new_data, m_data, m_size * sizeof(T));
            else {
                for (size_t i = 0; i < m_size; ++i)
                    new (&new_data[i]) T(std::move(m_data[i]));
            }

            for (size_t i = 0; i < m_size; ++i)
                m_data[i].~T();

            ::operator delete(m_data);
            m_data = new_data;
            m_capacity = m_size;
        }
    }

    void push_back_batch(const T* src, const size_t count) {
        if (m_size + count > m_capacity)
            grow_capacity(m_size + count);

        if constexpr (std::is_trivially_copyable_v<T>) {
            memcpy(&m_data[m_size], src, count * sizeof(T));
            m_size += count;
        }
        else {
            for (size_t i = 0; i < count; ++i)
                new (&m_data[m_size++]) T(src[i]);
        }
    }

    void remove(const T element) {
        const size_t count = count_element(element);
        if (count == 0)
            return;

        m_capacity -= count;
        T* new_data = static_cast<T*>(::operator new(sizeof(T) * m_capacity));

        size_t new_index = 0;
        for (size_t i = 0; i < m_size; ++i) {
            if (m_data[i] == element)
                continue;

            new (&new_data[new_index++]) T(std::move(m_data[i]));
        }

        for (size_t i = 0; i < m_size; ++i)
            m_data[i].~T();
        ::operator delete(m_data);

        m_data = new_data;
        m_size -= count;
    }


    void del(const size_t index) {
        if (index >= m_size)
            throw std::out_of_range("index out of range");

        T* new_data = static_cast<T*>(::operator new(sizeof(T) * --m_capacity));
        const size_t split = index;

        for (size_t i = 0; i < split; ++i) {
            new (&new_data[i]) T(std::move(m_data[i]));
        }
        for (size_t i = split+1; i < m_size; ++i) {
            new (&new_data[i-1]) T(std::move(m_data[i]));
        }

        for (size_t i = 0; i < m_size; ++i)
            m_data[i].~T();
        ::operator delete(m_data);

        m_data = new_data;
        m_size--;
    }

    T& operator[](size_t i) {
        if (i >= m_size)
            throw std::out_of_range("index out of range");
        return m_data[i];
    }

    const T& operator[](size_t i) const {
        if (i >= m_size)
            throw std::out_of_range("index out of range");
        return m_data[i];
    }

    void print() const {
        for (size_t i = 0; i < m_size; ++i) {
            std::cout << m_data[i] << " ";
        }
        std::cout << "\n";
        std::cout << "Size: " << m_size << "\n";
        std::cout << "Capacity: " << m_capacity << "\n";
    }

private:
    size_t m_size;
    size_t m_capacity;
    T* m_data;

    size_t count_element(const T& element) {
        size_t count = 0;
        for (size_t i = 0; i < m_size; ++i) {
            if (m_data[i] == element)
                count++;
        }
        return count;
    }

    void grow_capacity(size_t min_capacity) {
        size_t old_capacity = m_capacity;
        size_t new_capacity = m_capacity == 0 ? 1 : m_capacity * 2;
        new_capacity = min_capacity > new_capacity ? min_capacity : new_capacity;

        T* new_data = static_cast<T*>(::operator new(sizeof(T) * new_capacity));
        if constexpr (std::is_trivially_copyable_v<T>)
            memcpy(new_data, m_data, m_size * sizeof(T));
        else if (old_capacity > 0) {
            for (size_t i = 0; i < m_size; ++i)
                new (&new_data[i]) T(std::move(m_data[i]));
        }

        for (size_t i = 0; i < m_size; ++i)
            m_data[i].~T();
        ::operator delete(m_data);

        m_data = new_data;
        m_capacity = new_capacity;
    }
};

constexpr int BULK_SIZE = 100000;

void bulk_test_batch() {
    Arr<int> arr;
    auto temp = new int[BULK_SIZE];
    for (int i = 0; i < BULK_SIZE; i++)
        temp[i] = i;
    arr.push_back_batch(temp, BULK_SIZE);
    delete[] temp;
}

void bulk_test_single() {
    Arr<int> arr;
    arr.prepare_bulk(BULK_SIZE);
    for (int i = 0; i < BULK_SIZE; i++)
        arr.push_back(i);
    arr.end_bulk(true);
}

void bulk_test_vec() {
    std::vector<int> v;
    for (int i = 0; i < BULK_SIZE; i++)
        v.push_back(i);
}

void bulk_test_vec_reserve() {
    std::vector<int> v;
    v.reserve(BULK_SIZE);
    for (int i = 0; i < BULK_SIZE; i++)
        v.push_back(i);
}

//https://stackoverflow.com/questions/22387586/measuring-execution-time-of-a-function-in-c
#include <chrono>
auto timeFuncInvocation =
    [](auto&& func, auto&&... params) {
        // get time before function invocation
        auto start = std::chrono::high_resolution_clock::now();
        // function invocation using perfect forwarding
        std::forward<decltype(func)>(func)(std::forward<decltype(params)>(params)...);
        // get time after function invocation
        auto stop = std::chrono::high_resolution_clock::now();
        return stop - start;
};

int main() {
    constexpr int ITER = 1000;
    long long arr_total_bulk = 0, arr_total_single = 0, vec_total = 0, vec_res_total = 0;

    //Separate iterations of for loops gives more accurate results even though it is less efficient:
    for (size_t i = 0; i < ITER; ++i)
        vec_total += std::chrono::duration_cast<std::chrono::nanoseconds>(timeFuncInvocation(bulk_test_vec)).count();

    for (size_t i = 0; i < ITER; ++i)
        vec_res_total += std::chrono::duration_cast<std::chrono::nanoseconds>(timeFuncInvocation(bulk_test_vec_reserve)).count();

    for (size_t i = 0; i < ITER; ++i)
        arr_total_bulk += std::chrono::duration_cast<std::chrono::nanoseconds>(timeFuncInvocation(bulk_test_batch)).count();

    for (size_t i = 0; i < ITER; ++i)
        arr_total_single += std::chrono::duration_cast<std::chrono::nanoseconds>(timeFuncInvocation(bulk_test_single)).count();

    std::cout << "Avg Arr Bulk time: " << arr_total_bulk / ITER << " ns\n";
    std::cout << "Avg Arr Single time: " << arr_total_single / ITER << " ns\n";
    std::cout << "Avg Vector time: " << vec_total / ITER << " ns\n";
    std::cout << "Avg Vector (Reserve) time: " << vec_res_total / ITER << " ns\n";

    const auto vec_fl = static_cast<double>(vec_total);
    const auto vec_res_fl = static_cast<double>(vec_res_total);
    double vec_bulk = vec_fl / arr_total_bulk;
    double vec_single = vec_fl / arr_total_single;
    double vec_res_bulk = vec_res_fl / arr_total_bulk;
    double vec_res_single = vec_res_fl / arr_total_single;
    std::cout << "Vector took " << vec_bulk << "x more time to complete then bulk\n";
    std::cout << "Vector took " << vec_single << "x more time to complete then single\n";
    std::cout << "Vector (Reserve) took " << vec_res_bulk << "x more time to complete then bulk\n";
    std::cout << "Vector (Reserve) took " << vec_res_single << "x more time to complete then single\n";

    Arr<int> a;
    a.push_back(1);
    int test[5] = {1, 2, 3, 4, 5};
    a.push_back_batch(test, 5);
    a[0] = 100;
    a.push_back(50);
    a.push_back_batch(test, 5);
    a.print();
    a.del(2);
    a.del(0);
    a.del(0);
    a.print();
    int twos[6] = {1, 2, 1, 2, 1, 2};
    a.push_back_batch(twos, 6);
    a.print();
    a.remove(2);
    a.remove(3);
    a.print();
    a.del(8);
    a.print();

    return 0;
}