StaticVector.h

Go to the documentation of this file.

/* Copyright (C) 2023 Wildfire Games.
 * This file is part of 0 A.D.
 *
 * 0 A.D. is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * 0 A.D. is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef INCLUDED_PS_STATICVECTOR
#define INCLUDED_PS_STATICVECTOR

#include <algorithm>
#include <array>
#include <cstdint>
#include <fmt/format.h>
#include <initializer_list>
#include <limits>
#include <memory>
#include <new>
#include <stdexcept>

namespace PS
{

struct CapacityExceededException : public std::length_error
{
    using std::length_error::length_error;
};

template<size_t N>
constexpr auto MakeSmallestCapableUnsigned()
{
    if constexpr (N <= std::numeric_limits<uint_fast8_t>::max())
        return static_cast<uint_fast8_t>(0);
    else if constexpr (N <= std::numeric_limits<uint_fast16_t>::max())
        return static_cast<uint_fast16_t>(0);
    else if constexpr (N <= std::numeric_limits<uint_fast32_t>::max())
        return static_cast<uint_fast32_t>(0);
    else if constexpr (N <= std::numeric_limits<uint_fast64_t>::max())
        return static_cast<uint_fast64_t>(0);
    else
    {
        static_assert(N <= std::numeric_limits<uintmax_t>::max());
        return static_cast<uintmax_t>(0);
    }
}

template<size_t N>
constexpr auto MakeSmallestCapableSigned()
{
    // TODO C++20: Use std::cmp_*
    if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast8_t>::max()) &&
        -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast8_t>::min())
        return static_cast<int_fast8_t>(0);
    else if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast16_t>::max()) &&
        -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast16_t>::min())
        return static_cast<int_fast16_t>(0);
    else if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast32_t>::max()) &&
        -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast32_t>::min())
        return static_cast<int_fast32_t>(0);
    else if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast64_t>::max()) &&
        -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast64_t>::min())
        return static_cast<int_fast64_t>(0);
    else
    {
        static_assert(N <= static_cast<uintmax_t>(std::numeric_limits<intmax_t>::max()) &&
            -static_cast<intmax_t>(N) >= std::numeric_limits<intmax_t>::min());
        return static_cast<intmax_t>(0);
    }
}

/**
 * A conntainer close to std::vector but the elements are stored in place:
 * There is a fixed capacity and there is no dynamic memory allocation.
 * Note: moving a StaticVector will be slower than moving a std::vector in
 * case of sizeof(StaticVector) > sizeof(std::vector).
 */
template<typename T, size_t N>
class StaticVector
{
public:
    static_assert(std::is_nothrow_destructible_v<T>);

    using value_type = T;
    using size_type = decltype(MakeSmallestCapableUnsigned<N>());
    using difference_type = decltype(MakeSmallestCapableSigned<N>());
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using iterator = pointer;
    using const_iterator = const_pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;


    StaticVector() = default;
    StaticVector(const StaticVector& other) noexcept(std::is_nothrow_copy_constructible_v<T>)
        : m_Size{other.size()}
    {
        std::uninitialized_copy(other.begin(), other.end(), begin());
    }

    template<size_t OtherN>
    explicit StaticVector(const StaticVector<T, OtherN>& other) noexcept(
        std::is_nothrow_copy_constructible_v<T>)
        : m_Size{other.size()}
    {
        static_assert(OtherN < N);

        std::uninitialized_copy(other.begin(), other.end(), begin());
    }

    StaticVector& operator=(const StaticVector& other) noexcept(std::is_nothrow_copy_constructible_v<T>
        && std::is_nothrow_copy_assignable_v<T>)
    {
        const size_type initializedCopies{std::min(other.size(), size())};
        std::copy_n(other.begin(), initializedCopies, begin());
        std::uninitialized_copy(other.begin() + initializedCopies, other.end(),
            begin() + initializedCopies);
        std::destroy(begin() + initializedCopies, end());

        m_Size = other.size();
        return *this;
    }

    template<size_t OtherN>
    StaticVector& operator=(const StaticVector<T, OtherN>& other) noexcept(
        std::is_nothrow_copy_constructible_v<T> && std::is_nothrow_copy_assignable_v<T>)
    {
        static_assert(OtherN < N);

        const size_type initializedCopies{std::min(other.size(), size())};
        std::copy_n(other.begin(), initializedCopies, begin());
        std::uninitialized_copy(other.begin() + initializedCopies, other.end(),
            begin() + initializedCopies);
        std::destroy(begin() + initializedCopies, end());

        m_Size = other.size();
        return *this;
    }

    StaticVector(StaticVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>)
        : m_Size{other.size()}
    {
        std::uninitialized_move(other.begin(), other.end(), begin());
    }

    template<size_t OtherN>
    explicit StaticVector(StaticVector<T, OtherN>&& other)
        noexcept(std::is_nothrow_move_constructible_v<T>)
        : m_Size{other.size()}
    {
        static_assert(OtherN < N);

        std::uninitialized_move(other.begin(), other.end(), begin());
    }

    StaticVector& operator=(StaticVector&& other) noexcept(std::is_nothrow_move_constructible_v<T> &&
        std::is_nothrow_move_assignable_v<T>)
    {
        const size_type initializedMoves{std::min(other.size(), size())};
        std::move(other.begin(), other.begin() + initializedMoves, begin());
        std::uninitialized_move(other.begin() + initializedMoves, other.end(),
            begin() + initializedMoves);
        std::destroy(begin() + initializedMoves, end());

        m_Size = other.size();
        return *this;
    }

    template<size_t OtherN>
    StaticVector& operator=(StaticVector<T, OtherN>&& other) noexcept(
        std::is_nothrow_move_constructible_v<T> && std::is_nothrow_move_assignable_v<T>)
    {
        static_assert(OtherN < N);

        const size_type initializedMoves{std::min(other.size(), size())};
        std::move(other.begin(), other.begin() + initializedMoves, begin());
        std::uninitialized_move(other.begin() + initializedMoves, other.end(),
            begin() + initializedMoves);
        std::destroy(begin() + initializedMoves, end());

        m_Size = other.size();
        return *this;
    }

    ~StaticVector()
    {
        clear();
    }

    StaticVector(const size_type count, const T& value)
        : m_Size{count}
    {
        if (count > N)
            throw CapacityExceededException{fmt::format(
                "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
                count, N)};

        std::uninitialized_fill(begin(), end(), value);
    }

    StaticVector(const size_type count)
        : m_Size{count}
    {
        if (count > N)
            throw CapacityExceededException{fmt::format(
                "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
                count, N)};

        std::uninitialized_default_construct(begin(), end());
    }

    StaticVector(const std::initializer_list<T> init)
        : m_Size{static_cast<size_type>(init.size())} // Will be tested below.
    {
        if (init.size() > N)
            throw CapacityExceededException{fmt::format(
                "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
                init.size(), N)};

        std::uninitialized_copy(init.begin(), init.end(), begin());
    }

    StaticVector& operator=(const std::initializer_list<T> init)
    {
        if (init.size() > N)
            throw CapacityExceededException{fmt::format(
                "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
                init.size(), N)};

        clear();
        std::uninitialized_copy(init.begin(), init.end(), begin());
        m_Size = init.size();
    }



    reference at(const size_type index)
    {
        if (index >= m_Size)
            throw std::out_of_range{fmt::format("Called at({}) but there are only {} elements.",
                index, size())};

        return (*this)[index];
    }

    const_reference at(const size_type index) const
    {
        if (index >= size())
            throw std::out_of_range{fmt::format("Called at({}) but there are only {} elements.",
                index, size())};

        return (*this)[index];
    }

    reference operator[](const size_type index) noexcept
    {
        ASSERT(index < size());
        return *(begin() + index);
    }

    const_reference operator[](const size_type index) const noexcept
    {
        ASSERT(index < size());
        return *(begin() + index);
    }

    reference front() noexcept
    {
        ASSERT(!empty());
        return *begin();
    }

    const_reference front() const noexcept
    {
        ASSERT(!empty());
        return *begin();
    }

    reference back() noexcept
    {
        ASSERT(!empty());
        return *std::prev(end());
    }

    const_reference back() const noexcept
    {
        ASSERT(!empty());
        return *std::prev(end());
    }

    pointer data() noexcept
    {
        return std::launder(reinterpret_cast<pointer>(m_Data.data()));
    }

    const_pointer data() const noexcept
    {
        return std::launder(reinterpret_cast<const_pointer>(m_Data.data()));
    }


    iterator begin() noexcept
    {
        return data();
    }

    const_iterator begin() const noexcept
    {
        return cbegin();
    }

    const_iterator cbegin() const noexcept
    {
        return data();
    }

    iterator end() noexcept
    {
        return begin() + size();
    }

    const_iterator end() const noexcept
    {
        return cend();
    }

    const_iterator cend() const noexcept
    {
        return cbegin() + size();
    }

    reverse_iterator rbegin() noexcept
    {
        return std::make_reverse_iterator(end());
    }

    const_reverse_iterator rbegin() const noexcept
    {
        return crbegin();
    }

    const_reverse_iterator crbegin() const noexcept
    {
        return std::make_reverse_iterator(end());
    }

    reverse_iterator rend() noexcept
    {
        return std::make_reverse_iterator(begin());
    }

    const_reverse_iterator rend() const noexcept
    {
        return crend();
    }

    const_reverse_iterator crend() const noexcept
    {
        return std::make_reverse_iterator(cbegin());
    }

    bool empty() const noexcept
    {
        return size() == 0;
    }

    bool full() const noexcept
    {
        return size() == N;
    }

    size_type size() const noexcept
    {
        return m_Size;
    }

    constexpr size_type capacity() const noexcept
    {
        return N;
    }


    void clear() noexcept
    {
        std::destroy(begin(), end());
        m_Size = 0;
    }

    /**
     * Inserts an element at location. The elements which were in the range
     * [ location, end() ) get moved no the next position.
     *
     * Exceptions:
     * If an exception is thrown when inserting an element at the end this
     * function has no effect (strong exception guarantee).
     * Otherwise the program is in a valid state (Basic exception guarantee).
     */
    iterator insert(const const_iterator location, const T& value)
    {
        if (full())
            throw CapacityExceededException{"Called insert but the StaticVector is already full"};

        if (location == end())
            return std::addressof(emplace_back(value));

        new(end()) T{std::move(back())};
        ++m_Size;

        const iterator mutableLocation{MutableIter(location)};
        std::move_backward(mutableLocation, std::prev(end(), 2), std::prev(end(), 1));

        *mutableLocation = value;
        return mutableLocation;
    }

    /**
     * Same as above but the new element is move-constructed.
     *
     * If an exception is thrown when inserting an element at the end this
     * function has no effect (strong exception guarantee).
     * If an exception is thrown the program is in a valid state
     * (Basic exception guarantee).
     */
    iterator insert(const const_iterator location, T&& value)
    {
        if (full())
            throw CapacityExceededException{"Called insert but the StaticVector is already full"};

        if (location == end())
            return std::addressof(emplace_back(std::move(value)));

        const iterator mutableLocation{MakeMutableIterator(location)};
        new(end()) T{std::move(back())};
        ++m_Size;

        std::move_backward(mutableLocation, end() - 2, end() -1);

        *mutableLocation = std::move(value);
        return mutableLocation;
    }

    /**
     * If an exception is thrown this function has no effect
     * (strong exception guarantee).
     */
    void push_back(const T& value)
    {
        emplace_back(value);
    }

    /**
     * If an exception is thrown this function has no effect
     * (strong exception guarantee).
     */
    void push_back(T&& value)
    {
        emplace_back(std::move(value));
    }

    /**
     * If an exception is thrown this function has no effect
     * (strong exception guarantee).
     */
    template<typename... Args>
    reference emplace_back(Args&&... args)
    {
        if (full())
            throw CapacityExceededException{
                "Called emplace_back but the StaticVector is already full"};

        const iterator location{begin() + size()};
        new(location) T{std::forward<Args>(args)...};
        ++m_Size;
        return *location;
    }

    void pop_back() noexcept
    {
        ASSERT(!empty());
        std::destroy_at(std::addressof(back()));
        --m_Size;
    }

    /**
     * Constructs or destructs elements to adjust to newSize. After this call
     * the StaticVector contains newSize elements. Unlike std::vector the
     * capacity does not get changed. If newSize is bigger then the capacity
     * a CapacityExceededException is thrown.
     *
     * If newSize is smaller than size() (shrinking) no exception is thrown
     * (Nothrow exception guarantee).
     * If an exception is thrown this function has no effect.
     * (strong exception guarantee)
     */
    void resize(const size_type newSize)
    {
        if (newSize > N)
            throw CapacityExceededException{fmt::format(
                "Can not resize StaticVector to {} the capacity is {}", newSize, N)};

        if (newSize > size())
            std::uninitialized_default_construct(end(), begin() + newSize);
        else
            std::destroy(begin() + newSize, end());

        m_Size = newSize;
    }

    /**
     * Same as above but uses value to copy-construct the new elements.
     *
     * If newSize is smaller than size() (shrinking) no exception is thrown
     * (Nothrow exception guarantee).
     * If an exception is thrown this function has no effect.
     * (strong exception guarantee)
     */
    void resize(const size_type newSize, const T& value)
    {
        if (newSize > N)
            throw CapacityExceededException{fmt::format(
                "Can't resize the StaticVector to {} the capacity is {}", newSize, N)};

        if (newSize > size())
            std::uninitialized_fill(end(), begin() + newSize, value);
        else
            std::destroy(begin() + newSize, end());

        m_Size = newSize;
    }

    template<size_t OtherN>
    friend bool operator==(const StaticVector<T, N>& lhs, const StaticVector<T, OtherN>& rhs)
    {
        return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
    }

    template<size_t OtherN>
    friend bool operator!=(const StaticVector<T, N>& lhs, const StaticVector<T, OtherN>& rhs)
    {
        return !(lhs == rhs);
    }

private:
    iterator MakeMutableIterator(const const_iterator iter) noexcept
    {
        return begin() + (iter - begin());
    }

    using EagerInitialized = std::array<T, N>;
    alignas(EagerInitialized) std::array<std::byte, sizeof(T) * N> m_Data;
    size_type m_Size{0};
};

} // namespace PS

#endif // INCLUDED_PS_STATICVECTOR