3
\$\begingroup\$

In many cases, we want a variable-size array like std::vector, but we know an upper limit on the size. In such cases, the vector can be allocated on the stack. We have been doing this in C:

char a[100];
fgets(a, 100, STDIN);

The problem is that the array doesn't know how many elements are actually there. All it knows is the "100" and it is up to us to keep track of the length of the string. std::vector doesn't allow us to allocate the memory on stack either. Therefore, I invested several weekends to write static_vector to solve this problem. To quote from my documentation:

template<typename T, std::size_t N>
class ethereal::static_vector< T, N >

Vector with stack storage.

static_vector never allocates dynamic memory. (The static_vector object itself may still be placed on the heap if the user prefers to.) The elements are allocated as part of the vector object itself. This can be useful when dynamic memory allocation is to be avoided. As a result, there is a compile-time determined limit on the size, supplied as the template parameter N. Internally, static_vector holds a data member of type std::array<std::aligned_storage_t<sizeof(T), alignof(T)>, N>. [...]

static_vector can be used pretty much the same way std::vector can. It throws an exception of type std::length_error if the size limit is exceeded. See the documentation for details. As a bonus, the std::vector<bool> problem is fixed.

/**
 * @file static_vector.hpp
 */

#ifndef INC_STATIC_VECTOR_HPP_o5GgaN4bAq
#define INC_STATIC_VECTOR_HPP_o5GgaN4bAq

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <type_traits>

/**
 * @cond DETAIL
 */

#define REQUIRES(...) std::enable_if_t<(__VA_ARGS__), int> = 0

/**
 * @endcond
 */

// inspired by Merriam-Webster's word of the day on August 20, 2019
namespace ethereal {

    /**
     * @cond DETAIL
     */

    namespace detail {
        template <typename It>
        using iter_category_t = typename std::iterator_traits<It>::iterator_category;
        template <typename It>
        using iter_reference_t = typename std::iterator_traits<It>::reference;

        // determines whether T is contextually convertible to bool
        template <typename T>
        struct is_boolean :std::is_constructible<bool, T> {};
        template <typename T>
        inline constexpr bool is_boolean_v = is_boolean<T>::value;

        // define the copy constructor and copy assignment as deleted
        template <bool Enabled>
        struct copy_base {};
        template <>
        struct copy_base<false> {
            copy_base() = default;
            copy_base(const copy_base&) = delete;
            copy_base(copy_base&&) = default;
            copy_base& operator=(const copy_base&) = delete;
            copy_base& operator=(copy_base&&) = default;
            ~copy_base() = default;
        };

        // define the move constructor and move assignment as deleted
        template <bool Enabled>
        struct move_base {};
        template <>
        struct move_base<false> {
            move_base() = default;
            move_base(const move_base&) = delete;
            move_base(move_base&&) = delete;
            move_base& operator=(const move_base&) = delete;
            move_base& operator=(move_base&&) = delete;
            ~move_base() = default;
        };
    } // namespace detail

    /**
     * @endcond
     */

    /**
     * @brief Vector with stack storage.
     *
     * [Documentation removed due to Code Review limitations.]
     *
     * @tparam T The element type.
     * @tparam N The maximum size of the vector.
     */

    /**
     * @cond DETAIL
     */

    // The actual stuff is implemented in `detail::static_vector`, and
    // make the actual `static_vector` derive from it to make the copy
    // operations and move operations conditionally enabled.  This
    // shouldn't be exposed to Doxygen.
    namespace detail {

    /**
     * @endcond
     */

    template <typename T, std::size_t N>
    class static_vector {
        static_assert(std::is_destructible_v<T>,
                      "static_vector<T, N> requires std::is_destructible_v<T>");
        static_assert(N <= std::numeric_limits<std::ptrdiff_t>::max(),
                      "static_vector<T, N> requires "
                      "N <= std::numeric_limits<std::ptrdiff_t>::max()");
    public:

        /**
         * @name Member types
         * @{
         */

        using value_type = T;
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;

        using reference = T&;
        using const_reference = const T&;
        using pointer = T*;
        using const_pointer = const T*;

        using iterator = T*;
        using const_iterator = const T*;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;

        /**
         * @}
         */

        /**
         * @name Constructors
         * @{
         */

        /**
         * @brief Constructs an empty vector.
         *
         * Does not construct any elements.
         */
        static_vector() noexcept = default;

        /**
         * @brief Constructs a vector with `n` value-initialized
         * elements.
         *
         * Equivalent to `static_vector()` followed by
         * `insert_back(n);`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_default_constructible_v<T>`.
         *
         * @param n The number of elements to construct.  Can be zero.
         */
        template <typename..., typename U = T, REQUIRES(std::is_default_constructible_v<U>)>
        explicit static_vector(size_type n)
        {
            insert_back(n);
        }
        /**
         * @brief Constructs a vector with `n` elements
         * copy-initialized from `value`.
         *
         * Equivalent to `static_vector()` followed by `insert_back(n,
         * value);`.
         *
         * Unlike the corresponding constructor in `std::vector`, this
         * constructor is `explicit`.  Therefore,
         * `static_vector<std::string, 3> vec = {2, "foo"}` is
         * ill-formed.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         *
         * @param n     The number of elements to construct.  Can be
         * zero.
         * @param value The value of the elements.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        explicit static_vector(size_type n, const_reference value)
        {
            insert_back(n, value);
        }
        /**
         * @brief Constructs a vector from the range `[first, last)`.
         *
         * Equivalent to `static_vector()` followed by
         * `insert_back(first, last);`.
         *
         * This function does not participate in overload resolution
         * unless `std::iterator_traits<It>::%iterator_category` is
         * valid and denotes a type and `std::is_constructible_v<T,
         * typename std::iterator_traits<It>::%reference>`.
         *
         * @param first `[first, last)` denotes the range to construct
         * the vector from.  The range can be empty.
         * @param last  See `first`.
         */
        template <typename It, typename..., typename = detail::iter_category_t<It>,
                  REQUIRES(std::is_constructible_v<T, detail::iter_reference_t<It>>)>
        static_vector(It first, It last)
        {
            insert_back(first, last);
        }
        /**
         * @brief Constructs a vector from `ilist`.
         *
         * Equivalent to `static_vector(ilist.begin(), ilist.end())`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         *
         * @param ilist The list of elements.  Can be empty.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        static_vector(std::initializer_list<T> ilist)
            :static_vector(ilist.begin(), ilist.end())
        {
        }
        /**
         * @brief Constructs a vector by copying from the elements in
         * `other`.
         *
         * Equivalent to `static_vector(other.begin(), other.end())`.
         *
         * This function is defined as deleted unless
         * `std::is_copy_constructible_v<T>`.
         *
         * @param other The vector to copy from.
         */
        static_vector(const static_vector& other)
            :static_vector(other.begin(), other.end())
        {
        }
        /**
         * @brief Constructs a vector by moving from the elements in
         * `other`.
         *
         * Equivalent to
         * `static_vector(std::make_move_iterator(other.begin()),
         * std::make_move_iterator(other.end()))`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_move_constructible_v<T>`.  This function is
         * noexcept if and only if
         * `std::is_nothrow_move_constructible_v<T>`.
         *
         * @param other The vector to move from.
         */
        static_vector(static_vector&& other) noexcept(std::is_nothrow_move_constructible_v<T>)
            :static_vector(std::make_move_iterator(other.begin()),
                           std::make_move_iterator(other.end()))
        {
        }

        /**
         * @}
         */

        /**
         * @name Assignment operators
         * @{
         */

        /**
         * @brief Replaces the elements in the vector with `ilist`.
         *
         * Equivalent to `assign(ilist.begin(), ilist.end())`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         *
         * @return `*this`
         * @param  ilist The list of elements.  Can be empty.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        static_vector& operator=(std::initializer_list<T> ilist)
        {
            assign(ilist.begin(), ilist.end());
            return *this;
        }
        /**
         * @brief Replaces the elements in the vector with a copy of
         * the elements in `other`.
         *
         * Equivalent to `assign(other.begin(), other.end())`.
         *
         * This function is defined as deleted unless
         * `std::is_copy_constructible_v<T>`.
         *
         * @return `*this`
         * @param  other The vector to copy from.
         */
        static_vector& operator=(const static_vector& other)
        {
            assign(other.begin(), other.end());
            return *this;
        }
        /**
         * @brief Replaces the elements in the vector with the
         * elements in `other` moved.
         *
         * Equivalent to
         * `assign(std::make_move_iterator(other.begin()),
         * std::make_move_iterator(other.end()))`.
         *
         * Unless the move assignment operator of `std::vector`, this
         * function actually moves the elements, therefore having
         * linear time complexity.
         *
         * This function does not participate in overload resolution
         * unless `std::is_move_constructible_v<T>`.  This function is
         * `noexcept` if and only if
         * `std::is_nothrow_move_constructible_v<T>`.
         *
         * @return `*this`
         * @param  other The vector to move from.
         */
        static_vector& operator=(static_vector&& other)
            noexcept(std::is_nothrow_move_constructible_v<T>)
        {
            assign(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
            return *this;
        }

        /**
         * @}
         */

        /**
         * @brief Destroys the elements.
         *
         * Equivalent to `clear()`.
         */
        ~static_vector()
        {
            clear();
        }

        /**
         * @name Iterators
         * @{
         */

        /**
         * @brief Returns a non-constant iterator to the first
         * element, or an unspecified value such that `begin() ==
         * end()` if the vector is empty.
         */
        [[nodiscard]] iterator begin() noexcept
        {
            return data();
        }
        /**
         * @brief Returns a constant iterator to the first element, or
         * an unspecified value such that `begin() == end()` if the
         * vector is empty.
         */
        [[nodiscard]] const_iterator begin() const noexcept
        {
            return data();
        }
        /**
         * @brief Returns a non-constant iterator to one past the last
         * element, or an unspecified value such that `begin() ==
         * end()` is the vector is empty.
         */
        [[nodiscard]] iterator end() noexcept
        {
            return data() + size();
        }
        /**
         * @brief Returns a constant iterator to one past the last
         * element, or an unspecified value such that `begin() ==
         * end()` is the vector is empty.
         */
        [[nodiscard]] const_iterator end() const noexcept
        {
            return data() + size();
        }
        /**
         * @brief Returns `begin()`.
         */
        [[nodiscard]] const_iterator cbegin() const noexcept
        {
            return begin();
        }
        /**
         * @brief Returns `end()`.
         */
        [[nodiscard]] const_iterator cend() const noexcept
        {
            return end();
        }

        /**
         * @brief Returns `reverse_iterator(end())`.
         */
        [[nodiscard]] reverse_iterator rbegin() noexcept
        {
            return reverse_iterator(end());
        }
        /**
         * @brief Returns `const_reverse_iterator(end())`.
         */
        [[nodiscard]] const_reverse_iterator rbegin() const noexcept
        {
            return const_reverse_iterator(end());
        }
        /**
         * @brief Returns `reverse_iterator(begin())`.
         */
        [[nodiscard]] reverse_iterator rend() noexcept
        {
            return reverse_iterator(begin());
        }
        /**
         * @brief Returns `const_reverse_iterator(begin())`.
         */
        [[nodiscard]] const_reverse_iterator rend() const noexcept
        {
            return const_reverse_iterator(begin());
        }
        /**
         * @brief Returns `rbegin()`.
         */
        [[nodiscard]] const_reverse_iterator crbegin() const noexcept
        {
            return rbegin();
        }
        /**
         * @brief Returns `rend()`.
         */
        [[nodiscard]] const_reverse_iterator crend() const noexcept
        {
            return rend();
        }

        /**
         * @brief Returns the number of elements.
         */
        [[nodiscard]] size_type size() const noexcept
        {
            return count;
        }
        /**
         * @brief Returns the number of elements as a signed integer.
         *
         * Equivalent to `static_cast<difference_type>(size())`.
         */
        [[nodiscard]] difference_type ssize() const noexcept
        {
            return static_cast<difference_type>(size());
        }
        /**
         * @brief Returns the number of elements that can be inserted
         * subject to the size limit.
         *
         * Equivalent to `max_size() - size()`.
         */
        [[nodiscard]] size_type space() const noexcept
        {
            return max_size() - size();
        }
        /**
         * @brief Returns the limit on the number of elements.
         *
         * @return `N`
         */
        [[nodiscard]] size_type max_size() const noexcept
        {
            return N;
        }
        /**
         * @brief Returns a `bool` value indicating whether the vector
         * is empty.
         *
         * @return `size() == 0`
         */
        [[nodiscard]] bool empty() const noexcept
        {
            return size() == 0;
        }

        /**
         * @brief Returns a non-constant reference to the element with
         * index `n`.  The behavior is undefined if `n >= size()`.
         *
         * @return `begin()[n]`.
         */
        reference operator[](size_type n)
        {
            assert(n < size());
            return begin()[n];
        }
        /**
         * @brief Returns a constant reference to the element with
         * index `n`.  The behavior is undefined if `n >= size()`.
         *
         * @return `begin()[n]`.
         */
        const_reference operator[](size_type n) const
        {
            assert(n < size());
            return begin()[n];
        }
        /**
         * @brief If `n >= size()`, throws an exception of type
         * `std::out_of_range`.  Otherwise, returns `operator[](n)`.
         */
        reference at(size_type n)
        {
            if (n >= size())
                throw std::out_of_range{"static_vector<T, N>::at(n) out of range"};
            return begin()[n];
        }
        /**
         * @brief If `n >= size()`, throws an exception of type
         * `std::out_of_range`.  Otherwise, returns `operator[](n)`.
         */
        const_reference at(size_type n) const
        {
            if (n >= size())
                throw std::out_of_range{"static_vector<T, N>::at(n) out of range"};
            return begin()[n];
        }
        /**
         * @brief Returns a non-constant reference to the first
         * element.  The behavior is undefined if the vector is empty.
         *
         * @return `*begin()`
         */
        reference front()
        {
            assert(!empty());
            return *begin();
        }
        /**
         * @brief Returns a constant reference to the first element.
         * The behavior is undefined if the vector is empty.
         *
         * @return `*begin()`
         */
        const_reference front() const
        {
            assert(!empty());
            return *begin();
        }
        /**
         * @brief Returns a non-constant reference to the last
         * element.  The behavior is undefined if the vector is empty.
         *
         * @return `*std::%prev(end())`
         */
        reference back()
        {
            assert(!empty());
            return *std::prev(end());
        }
        /**
         * @brief Returns a constant reference to the last
         * element.  The behavior is undefined if the vector is empty.
         *
         * @return `*std::%prev(end())`
         */
        const_reference back() const
        {
            assert(!empty());
            return *std::prev(end());
        }

        /**
         * @brief Returns a non-constant pointer to the first element.
         * Returns an unspecified valid pointer if the vector is
         * empty.
         */
        [[nodiscard]] T* data() noexcept
        {
            return std::launder(reinterpret_cast<T*>(elems.data()));
        }
        /**
         * @brief Returns a constant pointer to the first element.
         * Returns an unspecified valid pointer if the vector is
         * empty.
         */
        [[nodiscard]] const T* data() const noexcept
        {
            return std::launder(reinterpret_cast<const T*>(elems.data()));
        }

        /**
         * @}
         */

        /**
         * @name Insertion
         * @{
         */

        /**
         * @brief Constructs an element with the arguments given
         * before the element pointed to by `pos`, or at the end of
         * the vector if `pos == end()`.
         *
         * Let `p` be an `iterator` such that `p == pos`.  Equivalent
         * to `emplace_back(std::forward<Args>(args)...);
         * std::rotate(pos, std::prev(end()), end());`.  `pos` points
         * to the inserted element after the insertion.  The behavior
         * is undefined if `pos != end()` and `pos` doesn't point to
         * an element in the vector.
         *
         * This function does not participate in overload resolution
         * unless all of the following are `true`:
         * `std::is_move_constructible_v<T>`,
         * `std::is_move_assignable_v<T>`,
         * `std::is_swappable_v<T>`, and
         * `std::is_constructible_v<T, Args...>`.
         *
         * @return `p`.
         * @param  pos  The position to insert the element.
         * @param  args The arguments used to construct the element.
         */
        template <typename... Args, REQUIRES(std::is_constructible_v<T, Args...> &&
                                             std::is_move_constructible_v<T> &&
                                             std::is_move_assignable_v<T> &&
                                             std::is_swappable_v<T>)>
        iterator emplace(const_iterator pos, Args&&... args)
        {
            assert(begin() <= pos && pos <= end());
            auto p = strip_const(pos);

            emplace_back(std::forward<Args>(args)...);
            std::rotate(p, std::prev(end()), end());
            return p;
        }
        /**
         * @brief Copies an element into the vector before the element
         * pointed to by `pos`, or at the end of the vector if `pos ==
         * end()`.
         *
         * Let `p` be an `iterator` such that `p == pos`.  Equivalent
         * to `emplace(pos, value)`.  `pos` points to the inserted
         * element after the insertion.  The behavior is undefined if
         * `pos != end()` and `pos` doesn't point to an element in the
         * vector.
         *
         * This function does not participate in overload resolution
         * unless all of the following are `true`:
         * `std::is_copy_constructible_v<T>`,
         * `std::is_move_constructible_v<T>`,
         * `std::is_move_assignable_v<T>`, and
         * `std::is_swappable_v<T>`.
         *
         * @return `p`.
         * @param  pos   The position to insert the element.
         * @param  value The element to copy from.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U> &&
                                                        std::is_move_constructible_v<U> &&
                                                        std::is_move_assignable_v<U> &&
                                                        std::is_swappable_v<U>)>
        iterator insert(const_iterator pos, const T& value)
        {
            return emplace(pos, value);
        }
        /**
         * @brief Moves an element into the vector before the element
         * pointed to by `pos`, or at the end of the vector if `pos ==
         * end()`.
         *
         * Let `p` be an `iterator` such that `p == pos`.  Equivalent
         * to `emplace(pos, std::move(value))`.  `pos` points to the
         * inserted element after the insertion.  The behavior is
         * undefined if `pos != end()` and `pos` doesn't point to an
         * element in the vector.
         *
         * This function does not participate in overload resolution
         * unless all of the following are `true`:
         * `std::is_move_constructible_v<T>`,
         * `std::is_move_assignable_v<T>`, and
         * `std::is_swappable_v<T>`.
         *
         * @return `p`.
         * @param  pos   The position to insert the element.
         * @param  value The element to move from.
         */
        template <typename..., typename U = T, REQUIRES(std::is_move_constructible_v<U> &&
                                                        std::is_move_assignable_v<U> &&
                                                        std::is_swappable_v<U>)>
        iterator insert(const_iterator pos, T&& value)
        {
            return emplace(pos, std::move(value));
        }
        /**
         * @brief Inserts `n` copies of the same element before the
         * element pointed to by `pos`, or at the end of the vector if
         * `pos == end()`.
         *
         * Let `p` be an `iterator` such that `p == pos`.  Equivalent
         * to `auto it = insert_back(n, value); std::rotate(p, it,
         * end());`.  If `n == 0`, `pos` points to the same position
         * after the insertion; otherwise, `pos` points to the first
         * inserted element after the insertion.  The behavior is
         * undefined if `pos != end()` and `pos` doesn't point to an
         * element in the vector.
         *
         * This function does not participate in overload resolution
         * unless all of the following are `true`:
         * `std::is_copy_constructible_v<T>`,
         * `std::is_move_constructible_v<T>`,
         * `std::is_move_assignable_v<T>`, and
         * `std::is_swappable_v<T>`.
         *
         * @return `p`.
         * @param  pos   The position to insert the elements.
         * @param  n     The number of elements to insert.
         * @param  value The value of the elements.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U> &&
                                                        std::is_move_constructible_v<U> &&
                                                        std::is_move_assignable_v<U> &&
                                                        std::is_swappable_v<U>)>
        iterator insert(const_iterator pos, size_type n, const_reference value)
        {
            auto p = strip_const(pos);

            auto it = insert_back(n, value);
            std::rotate(p, it, end());
            return p;
        }
        /**
         * @brief Inserts a range of elements before the element
         * pointed to by `pos`, or at the end of the vector if `pos ==
         * end()`.
         *
         * Let `p` be an `iterator` such that `p == pos`.  Equivalent
         * to `auto it = insert_back(first, last); std::rotate(p, it,
         * end());`.  If `first == last`, `pos` points to the same
         * position after the insertion; otherwise, `pos` points to
         * the first inserted element after the insertion.  The
         * behavior is undefined if `pos != end()` and `pos` doesn't
         * point to an element in the vector.
         *
         * This function does not participate in overload resolution
         * unless `std::iterator_traits<It>::%iterator_category` is
         * valid and denotes a type and all of the following are
         * `true`: `std::is_constructible_v<T, typename
         * std::iterator_traits<It>::%reference>`,
         * `std::is_move_constructible_v<T>`,
         * `std::is_move_assignable_v<T>`, and
         * `std::is_swappable_v<T>`.
         *
         * @return `p`.
         * @param  pos   The position to insert the elements.
         * @param  first `[first, last)` denotes the range of elements
         * to insert.
         * @param  last  See `first`.
         */
        template <typename..., typename It, typename = detail::iter_category_t<It>,
                  REQUIRES(std::is_constructible_v<T, detail::iter_reference_t<It>> &&
                           std::is_move_constructible_v<T> &&
                           std::is_move_assignable_v<T> &&
                           std::is_swappable_v<T>)>
        iterator insert(const_iterator pos, It first, It last)
        {
            assert(begin() <= pos && pos <= end());
            auto p = strip_const(pos);

            auto it = insert_back(first, last);
            std::rotate(p, it, end());
            return p;
        }
        /**
         * @brief Inserts a list of elements before the element
         * pointed to by `pos`, or at the end of the vector if `pos ==
         * end()`.
         *
         * Equivalent to `insert(pos, ilist.begin(), ilist.end())`.
         *
         * This function does not participate in overload resolution
         * unless all of the following are `true`:
         * `std::is_copy_constructible_v<T>`,
         * `std::is_move_constructible_v<T>`,
         * `std::is_move_assignable_v<T>`, and
         * `std::is_swappable_v<T>`.
         *
         * @return `p`, an iterator such that `p == pos`.
         * @param  pos   The position to insert the elements.
         * @param  ilist The list of elements to insert.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U> &&
                                                        std::is_move_constructible_v<U> &&
                                                        std::is_move_assignable_v<U> &&
                                                        std::is_swappable_v<U>)>
        iterator insert(const_iterator pos, std::initializer_list<T> ilist)
        {
            return insert(pos, ilist.begin(), ilist.end());
        }
        /**
         * @brief Constructs an element with the given arguments at
         * the end of the vector.
         *
         * If `max_size() - size() < 1`, throws an exception of type
         * `std::length_error`.  Otherwise, effectively calls `::%new
         * (p) T(std::forward<Args>(args)...)` to construct the
         * element, where `p` is a pointer of type `void*` that
         * denotes the position in which the element is constructed.
         *
         * This function does not participate in overload resolution
         * unless `std::is_constructible_v<T, Args...>`.
         *
         * @return A reference to the new element.
         * @param  args The arguments used to construct the element.
         */
        template <typename... Args, REQUIRES(std::is_constructible_v<T, Args...>)>
        reference emplace_back(Args&&... args)
        {
            ensure_space(1);

            T* new_elem = ::new (static_cast<void*>(end())) T(std::forward<Args>(args)...);
            ++count;
            return *new_elem;
        }
        /**
         * @brief Copies an element to the end of the vector.
         *
         * Equivalent to `emplace_back(value)`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         *
         * @param value The element to be copied from.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        void push_back(const T& value)
        {
            emplace_back(value);
        }
        /**
         * @brief Moves an element to the end of the vector.
         *
         * Equivalent to `emplace_back(std::move(value))`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_move_constructible_v<T>`.
         *
         * @param value The element to be moved from.
         */
        template <typename..., typename U = T, REQUIRES(std::is_move_constructible_v<U>)>
        void push_back(T&& value)
        {
            emplace_back(std::move(value));
        }
        /**
         * @brief Extended functionality.  Inserts `n`
         * value-initialized elements at the end of the vector.
         *
         * If `max_size() - size() < n`, throws an exception of type
         * `std::length_error`.  Otherwise, effectively calls
         * `std::uninitialized_value_construct_n` to construct the
         * elements.
         *
         * This function does not participate in overload resolution
         * unless `std::is_default_constructible_v<T>`.
         *
         * @return An iterator that points to the first element
         * inserted, or `end()` if `n == 0`.
         * @param n The number of elements to insert.  Can be zero.
         */
        template <typename..., typename U = T, REQUIRES(std::is_default_constructible_v<U>)>
        iterator insert_back(size_type n)
        {
            ensure_space(n);
            return insert_back_unchecked(n);
        }
        /**
         * @brief Extended functionality.  Inserts `n` copies of
         * `value` at the end of the vector.
         *
         * If `max_size() - size() < n`, throws an exception of type
         * `std::length_error`.  Otherwise, effectively calls
         * `std::uninitialized_fill_n` to construct the elements.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         *
         * @return An iterator that points to the first element
         * inserted, or `end()` if `n == 0`.
         * @param n     The number of elements to insert.  Can be
         * zero.
         * @param value The element to copy from.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        iterator insert_back(size_type n, const_reference value)
        {
            ensure_space(n);
            return insert_back_unchecked(n, value);
        }
        /**
         * @brief Extended functionality.  Inserts the range `[first,
         * last)` at the end of the vector.
         *
         * If `std::iterator_traits<It>::%iterator_category` is
         * convertible to `std::random_access_iterator_tag`, first
         * checks if `max_size() - size() >= last - first`, throws an
         * exception of type `std::length_error` if not, and
         * effectively calls `std::uninitialized_copy` to construct
         * the elements.  Otherwise, equivalent to `for (; first !=
         * last; ++first) emplace_back(*first);`.
         *
         * This function does not participate in overload resolution
         * unless `std::iterator_traits<It>::%iterator_category` is
         * valid and denotes a type and `std::is_constructible_v<T,
         * detail::iter_reference_t<It>>`.
         *
         * @return An iterator that points to the first element
         * inserted, or `end()` if `first == last`.
         * @param first `[first, last)` denotes the range of elements
         * to insert.
         * @param last  See `first`.
         */
        template <typename It, typename..., typename Cat = detail::iter_category_t<It>,
                  REQUIRES(std::is_constructible_v<T, detail::iter_reference_t<It>>)>
        iterator insert_back(It first, It last)
        {
            return insert_back_dispatch(first, last, Cat{});
        }

        /**
         * @}
         */

        /**
         * @name Erasure
         * @{
         */

        /**
         * @brief Removes the element pointed to by `pos`.
         *
         * Let `p` be an `iterator` such that `p == pos`.  Equivalent
         * to `std::move(std::next(p), end(), p); pop_back();`.  The
         * behavior is undefined if `pos` does not point to an element
         * in the vector.  (In particular, `pos` cannot be `end()`.)
         *
         * The function does not participate in overload resolution
         * unless `std::is_move_assignable_v<T>`.
         *
         * @return An iterator to the element after the removed
         * element, or `end()` if the last element was removed.
         * @param pos The element to remove.
         */
        template <typename..., typename U = T, REQUIRES(std::is_move_assignable_v<U>)>
        iterator erase(const_iterator pos)
        {
            assert(begin() <= pos && pos < end());
            auto p = strip_const(pos);

            std::move(std::next(p), end(), p);
            pop_back();
            return p;
        }
        /**
         * @brief Removes the range of elements `[first, last)`.
         *
         * Let `f` and `l` be `iterator`s such that `f == first` and
         * `l == last`.  Equivalent to `std::move(l, end(), f);
         * pop_back(l - f);`.  The behavior is undefined unless both
         * `first` and `last` point to elements in the vector and
         * `first <= last`.
         *
         * The function does not participate in overload resolution
         * unless `std::is_move_assignable_v<T>`.
         *
         * @return If `first == last`, returns `f`.  Otherwise,
         * returns an iterator to the element after the removed
         * elements, or `end()` if there is no such element.
         * @param first `[first, last)` denotes the elements to
         * remove.
         * @param last  See `first`.
         */
        iterator erase(const_iterator first, const_iterator last)
        {
            assert(begin() <= first && first <= last && last <= end());
            auto f = strip_const(first);
            auto l = strip_const(last);

            // std::move(i, j, k) requires that k is not in [i, j)
            auto n = static_cast<size_type>(last - first);
            if (n != 0) {
                std::move(l, end(), f);
                pop_back(n);
            }
            return f;
        }
        /**
         * @brief Removes the last element.
         *
         * Equivalent to `pop_back(1)`.  The behavior is undefined if
         * `empty()`.
         */
        void pop_back()
        {
            pop_back(1);
        }
        /**
         * @brief Extended functionality.  Removes the last `n`
         * elements.
         *
         * Effectively calls `std::destroy` to destroy the elements.
         * The behavior is undefined if `size() < n`.
         *
         * @param n The number of elements to remove.  Can be zero.
         */
        void pop_back(size_type n)
        {
            assert(n <= size());
            std::destroy(end() - n, end());
            count -= n;
        }
        /**
         * @brief Removes all elements.
         *
         * Equivalent to `pop_back(size())`.
         */
        void clear() noexcept
        {
            std::destroy(begin(), end());
            count = 0;
        }

        /**
         * @}
         */

        /**
         * @name Modifiers
         * @{
         */

        /**
         * @brief Extended functionality.  Replaces the contents of
         * the vector with `n` value-initialized elements.
         *
         * Equivalent to `clear(); insert_back(n);`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_default_constructible_v<T>`.
         *
         * @param n The number of elements to replace the contents of
         * the vector with.
         */
        template <typename..., typename U = T, REQUIRES(std::is_default_constructible_v<U>)>
        void assign(size_type n)
        {
            ensure_size(n);

            clear();
            insert_back_unchecked(n);
        }
        /**
         * @brief Replaces the contents of the vector with `n` copies
         * of `value`.
         *
         * Equivalent to `clear(); insert_back(n, value);`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         *
         * @param n     The number of elements to replace the contents
         * of the vector with.
         * @param value The value of the elements.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        void assign(size_type n, const_reference value)
        {
            ensure_size(n);

            clear();
            insert_back_unchecked(n, value);
        }
        /**
         * @brief Replaces the contents of the vector with the
         * elements in the range `[first, last)`.
         *
         * Equivalent to `clear(); insert_back(first, last);`.
         *
         * This function does not participate in overload resolution
         * unless `std::iterator_traits<It>::%iterator_category` is
         * valid and denotes a type and `std::is_constructible_v<T,
         * std::iterator_traits<It>::%reference>`.
         *
         * @param first `[first, last)` denotes the range of elements
         * to replace the vector with.
         * @param last  See `first`.
         */
        template <typename It, typename..., typename Cat = detail::iter_category_t<It>,
                  REQUIRES(std::is_constructible_v<T, detail::iter_reference_t<It>>)>
        void assign(It first, It last)
        {
            return assign_dispatch(first, last, Cat{});
        }
        /**
         * @brief Replaces the contents of the vector with the list of
         * elements `ilist`.
         *
         * Equivalent to `assign(ilist.begin(), ilist.end())`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        void assign(std::initializer_list<T> ilist)
        {
            assign(ilist.begin(), ilist.end());
        }
        /**
         * @brief Resizes the vector to `n` elements, where new
         * elements are value-initialized.
         *
         * If `n < size()`, equivalent to `pop_back(size() - n)`;
         * otherwise, equivalent to `insert_back(n - size())`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_default_constructible_v<T>`.
         */
        template <typename..., typename U = T, REQUIRES(std::is_default_constructible_v<U>)>
        void resize(size_type n)
        {
            if (n < size())
                pop_back(size() - n);
            else
                insert_back(n - size());
        }
        /**
         * @brief Resizes the vector to `n` elements, where new
         * elements are copied from `value`.
         *
         * If `n < size()`, equivalent to `pop_back(size() - n)`;
         * otherwise, equivalent to `insert_back(n - size(), value)`.
         *
         * This function does not participate in overload resolution
         * unless `std::is_copy_constructible_v<T>`.
         */
        template <typename..., typename U = T, REQUIRES(std::is_copy_constructible_v<U>)>
        void resize(size_type n, const_reference value)
        {
            if (n < size())
                pop_back(size() - n);
            else
                insert_back(n - size(), value);
        }

        /**
         * @brief Swaps the vector with `other`.
         *
         * Let `common_size` be `std::min(size(), other.size())`.  The
         * first `common_size` elements are swapped as if by
         * `std::swap_ranges`.  Then, if the vectors differ in size,
         * new elements are appended to the smaller vector by moving
         * from the remaining elements in the bigger vector as if by
         * `small.insert_back(std::make_move_iterator(big.begin() +
         * common_size), std::make_move_iterator(big.end()));
         * big.pop_back(big.size() - common_size)`, where `big` is the
         * vector with more elements and `small` is the vector with
         * fewer elements.
         *
         * This function does not participate in overload resolution
         * unless `std::is_move_constructible_v<T> &&
         * std::is_swappable_v<T>`.  This function is `noexcept` if
         * and only if `std::is_nothrow_move_constructible_v<T> &&
         * std::is_nothrow_swappable_v<T>`.
         *
         * @param other The vector to swap with.
         */
        template <typename..., typename U = T, REQUIRES(std::is_move_constructible_v<U> &&
                                                        std::is_swappable_v<U>)>
        void swap(static_vector& other)
            noexcept(std::is_nothrow_move_constructible_v<T> && std::is_nothrow_swappable_v<T>)
        {
            auto common_size = std::min(size(), other.size());
            std::swap_ranges(begin(), begin() + common_size, other.begin());

            if (size() > common_size) {
                other.insert_back(std::make_move_iterator(begin() + common_size),
                                  std::make_move_iterator(end()));
                pop_back(size() - common_size);
            } else {
                insert_back(std::make_move_iterator(other.begin() + common_size),
                            std::make_move_iterator(other.end()));
                other.pop_back(other.size() - common_size);
            }
        }

        /**
         * @}
         */

    private:
        iterator strip_const(const_iterator pos) noexcept
        {
            assert(begin() <= pos && pos <= end());
            return const_cast<iterator>(pos);
        }
        void ensure_size(size_type n) const
        {
            if (max_size() < n)
                throw std::length_error{"static_vector<T, N> not enough space"};
        }
        void ensure_space(size_type n) const
        {
            if (space() < n)
                throw std::length_error{"static_vector<T, N> not enough space"};
        }
        iterator insert_back_unchecked(size_type n)
        {
            auto pos = end();
            std::uninitialized_value_construct_n(pos, n);
            count += n;
            return pos;
        }
        iterator insert_back_unchecked(size_type n, const_reference value)
        {
            auto pos = end();
            std::uninitialized_fill_n(pos, n, value);
            count += n;
            return pos;
        }
        template <typename It>
        iterator insert_back_dispatch(It first, It last, std::random_access_iterator_tag)
        {
            auto n = static_cast<size_type>(last - first);
            assert(n >= 0);
            ensure_space(n);
            return insert_back_dispatch_unchecked(first, last, n);
        }
        template <typename It>
        iterator insert_back_dispatch(It first, It last, std::input_iterator_tag)
        {
            return insert_back_dispatch_unchecked(first, last);
        }
        template <typename It>
        iterator insert_back_dispatch_unchecked(It first, It last, size_type n)
        {
            auto pos = end();
            std::uninitialized_copy(first, last, pos);
            count += n;
            return pos;
        }
        template <typename It>
        iterator insert_back_dispatch_unchecked(It first, It last)
        {
            auto pos = end();
            for (; first != last; ++first)
                emplace_back(*first);
            return pos;
        }
        template <typename It>
        void assign_dispatch(It first, It last, std::random_access_iterator_tag)
        {
            assert(first <= last);

            auto n = static_cast<size_type>(last - first);
            ensure_size(n);

            clear();
            insert_back_dispatch_unchecked(first, last, n);
        }
        template <typename It>
        void assign_dispatch(It first, It last, std::input_iterator_tag)
        {
            clear();
            insert_back_dispatch_unchecked(first, last);
        }

        std::array<std::aligned_storage_t<sizeof(T), alignof(T)>, N> elems;
        std::size_t count{0}; // invariant: count <= N
    }; // class static_vector

    /**
     * @cond DETAIL
     */

    } // namespace detail

    // actual static vector, with copy operations and move operations
    // conditionally disabled
    template <typename T, std::size_t N>
    class static_vector :
        public detail::static_vector<T, N>,
        private detail::copy_base<std::is_copy_constructible_v<T>>,
        private detail::move_base<std::is_move_constructible_v<T>>
    {
        using detail::static_vector<T, N>::static_vector;
    };

    /**
     * @endcond
     */

    /**
     * @name Comparison operators
     * @{
     */

    /**
     * @brief Checks whether two vectors are equal.
     *
     * Equivalent to `std::equal(lhs.begin(), lhs.end(), rhs.begin(),
     * rhs.end())`.  The behavior is undefined if this expression
     * triggers undefined behavior.
     *
     * This function does not participate in overload resolution
     * unless `decltype(a == b)` denotes a valid type and is
     * contextually convertible to `bool`, where `a` and `b` are
     * lvalues of type `const T`.
     *
     * @param lhs The left operand of the comparison.
     * @param rhs The right operand of the comparison.
     */
    template <typename T, std::size_t N, typename...,
              typename Result = decltype(std::declval<const T&>() == std::declval<const T&>()),
              REQUIRES(detail::is_boolean_v<Result>)>
    bool operator==(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs)
    {
        return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
    }
    /**
     * @brief Checks whether two vectors are not equal.
     *
     * Equivalent to `!%ethereal::operator==(lhs, rhs)`.  The behavior
     * is undefined if this expression triggers undefined behavior.
     *
     * This function does not participate in overload resolution
     * unless the aforementioned expression is valid.
     *
     * @param lhs The left operand of the comparison.
     * @param rhs The right operand of the comparison.
     */
    template <typename T, std::size_t N>
    auto operator!=(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs)
        -> decltype(!ethereal::operator==(lhs, rhs)) // for SFINAE
    {
        // qualified call to disable ADL
        return !ethereal::operator==(lhs, rhs);
    }
    /**
     * @brief Checks whether the first vector lexicographically
     * compares less than the second vector.
     *
     * Equivalent to `std::lexicographical_compare(lhs.begin(),
     * lhs.end(), rhs.begin(), rhs.end())`.  The behavior is undefined
     * if this expression triggers undefined behavior.
     *
     * This function does not participate in overload resolution
     * unless `decltype(a < b)` denotes a valid type and is
     * contextually convertible to `bool`, where `a` and `b` are
     * lvalues of type `const T`.
     *
     * @param lhs The left operand of the comparison.
     * @param rhs The right operand of the comparison.
     */
    template <typename T, std::size_t N, typename...,
              typename Result = decltype(std::declval<const T&>() < std::declval<const T&>()),
              REQUIRES(detail::is_boolean_v<Result>)>
    bool operator<(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs)
    {
        return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
    }
    /**
     * @brief Checks whether the first vector lexicographically
     * compares greater than the second vector.
     *
     * Equivalent to `ethereal::operator<(rhs, lhs)`.  The behavior is
     * undefined if this expression triggers undefined behavior.
     *
     * This function does not participate in overload resolution
     * unless the aforementioned expression is valid.
     *
     * @param lhs The left operand of the comparison.
     * @param rhs The right operand of the comparison.
     */
    template <typename T, std::size_t N>
    auto operator>(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs)
        -> decltype(ethereal::operator<(rhs, lhs)) // for SFINAE
    {
        // qualified call to block ADL
        return ethereal::operator<(rhs, lhs);
    }
    /**
     * @brief Checks whether the first vector lexicographically
     * compares less than or equal to the second vector.
     *
     * Equivalent to `!%ethereal::operator<(rhs, lhs)`.  The behavior
     * is undefined if this expression triggers undefined behavior.
     *
     * This function does not participate in overload resolution
     * unless the aforementioned expression is valid.
     *
     * @param lhs The left operand of the comparison.
     * @param rhs The right operand of the comparison.
     */
    template <typename T, std::size_t N>
    auto operator<=(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs)
        -> decltype(!ethereal::operator<(rhs, lhs))
    {
        return !ethereal::operator<(rhs, lhs);
    }
    /**
     * @brief Checks whether the first vector lexicographically
     * compares greater than or equal to the second vector.
     *
     * Equivalent to `!%ethereal::operator<(lhs, rhs)`.  The behavior
     * is undefined if this expression triggers undefined behavior.
     *
     * This function does not participate in overload resolution
     * unless the aforementioned expression is valid.
     *
     * @param lhs The left operand of the comparison.
     * @param rhs The right operand of the comparison.
     */
    template <typename T, std::size_t N>
    auto operator>=(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs)
        -> decltype(!ethereal::operator<(lhs, rhs))
    {
        return !ethereal::operator<(lhs, rhs);
    }

    /**
     * @}
     */

    /**
     * @name Specialized algorithms
     * @{
     */

    /**
     * @brief Swaps two vectors.
     *
     * Equivalent to `lhs.swap(rhs)`.
     *
     * This function does not participate in overload resolution
     * unless `lhs.swap(rhs)` is valid.  This function is `noexcept`
     * if and only if `noexcept(lhs.swap(rhs))`.
     *
     * @param lhs The first vector.
     * @param rhs The second vector.
     */
    template <typename T, std::size_t N>
    auto swap(static_vector<T, N>& lhs, static_vector<T, N>& rhs) noexcept(noexcept(lhs.swap(rhs)))
        -> decltype(lhs.swap(rhs)) // for SFINAE
    {
        lhs.swap(rhs);
    }

    /**
     * @brief Performs three-way lexicographical comparison on two
     * vectors with a custom comparator.
     *
     * If `std::lexicographical_compare(lhs.begin(), lhs.end(),
     * rhs.begin(), rhs.end(), pred)`, returns a negative value;
     * otherwise, if `std::lexicographical_compare(rhs.begin(),
     * rhs.end(), lhs.begin(), lhs.end(), pred)`, returns a positive
     * value; otherwise, returns `0`.  The behavior is undefined
     * unless `pred` induces a strict weak ordering on the values.
     *
     * This function does not participate in overload resolution
     * unless `decltype(pred(a, b))` denotes a valid type and is
     * contextually convertible to `bool`, where `a` and `b` are
     * lvalue expressions of type `const T`.
     *
     * @param lhs  The left operand of the comparison.
     * @param rhs  The right operand of the comparison.
     * @param pred The comparator.
     */
    template <typename T, std::size_t N, typename Pred, typename...,
              typename Result = decltype(std::declval<Pred&>()(std::declval<const T&>(),
                                                               std::declval<const T&>())),
              REQUIRES(detail::is_boolean_v<Result>)>
    int compare(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs, Pred pred)
    {
        auto common_size = std::min(lhs.size(), rhs.size());
        for (typename static_vector<T, N>::size_type i = 0; i < common_size; ++i) {
            if (pred(lhs[i], rhs[i]))
                return -1;
            else if (pred(rhs[i], lhs[i]))
                return 1;
        }
        return lhs.ssize() - rhs.ssize();
    }

    /**
     * @brief Performs three-way lexicographical comparison on two
     * vectors.
     *
     * Equivalent to `compare(lhs, rhs, std::less<>{})`.  The behavior
     * is undefined unless `std::less<>{}` induces a strict weak
     * ordering on the values.
     *
     * This function does not participate in overload resolution
     * unless `compare(lhs, rhs, std::less<>{})` is valid.
     *
     * @param lhs The left operand of the comparison.
     * @param rhs The right operand of the comparison.
     */
    template <typename T, std::size_t N>
    auto compare(const static_vector<T, N>& lhs, const static_vector<T, N>& rhs)
        -> decltype(ethereal::compare(lhs, rhs, std::less<>{})) // for SFINAE
    {
        // qualified call to block ADL
        return ethereal::compare(lhs, rhs, std::less<>{});
    }

    /**
     * @}
     */

} // namespace ethereal

#undef REQUIRES

#endif

There is some Doxygen stuff here, which reviewers can choose to review or not. As indicated by [Documentation removed due to Code Review limitations.], the documentation is too long to fit in a Code Review question, so I have left it out. It can be found on pastebin.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to consider creating a repository at GitHub or GitLab and create separate documentation. If people like the implementation having user documentation might be helpful. Having your own repository might be helpful in a job search as well, you can add a link to it to your cover letter or resume. \$\endgroup\$ – pacmaninbw Aug 25 '19 at 14:19
  • \$\begingroup\$ Why don't you want to consider Boost? \$\endgroup\$ – Michael K Aug 25 '19 at 18:22
  • \$\begingroup\$ @MichaelK Well, I didn't really think of that. Consider this a self-exercise then :) \$\endgroup\$ – L. F. Aug 25 '19 at 23:08
2
\$\begingroup\$

A more normal code review :-)

OK. This code is good. So anything I have to say is going to have be extremely nit picky to even say anything. So only bother to read if you want to see me at my nit pickiest (I am bored).


I have one question. I don't understand this:

OK. I don't understand this.

        template <typename..., typename U = T, REQUIRES(std::is_default_constructible_v<U>)>
        explicit static_vector(size_type n)
        {
            insert_back(n);
        }

What is happening with the ... in this context?


Ahhhh documentation tools

**
 * @file static_vector.hpp
 */

Nothing more to say on the subject.
I''l delete the comments before doing any more reviews.

OK. one more thing to say:

        /**
         * @brief Returns `reverse_iterator(begin())`.
         */
        [[nodiscard]] reverse_iterator rend() noexcept
        {
            return reverse_iterator(begin());
        }

7 lines to do what you could have done in 1.

OK time to invest some time into finding a vim plugin to fold documentation comments so they are not visible. Still want to see normal comments but documentation comments are not really useful for a code review (only the documentation tool generator).

OK. one more real thing to say. Please be consistent with your spacing between comments.

        reference operator[](size_type n)
        {
            assert(n < size());
            return begin()[n];
        }
        // MIY added comment.
        // Sometimes you leave a space beteen the function function and comment
        // Sometimes you don't. If I find a comment folding plugin that will
        // mean that sometimes there is a space between functions and sometimes
        // they are smashed together.
        /**
         * @brief Returns a constant reference to the element with
         * index `n`.  The behavior is undefined if `n >= size()`.
         *
         * @return `begin()[n]`.
         */
        const_reference operator[](size_type n) const
        {
            assert(n < size());
            return begin()[n];
        }

Not sure I like this without protection.

#define REQUIRES(...) std::enable_if_t<(__VA_ARGS__), int> = 0

Especially since you #undef it at the end. Personally I would add a check around it to make sure that no other system is using it.

#ifdef REQUIRES
#error "This code depends on the macro REQUIRES but it is defined in your code."
#endif
#define REQUIRES(...) std::enable_if_t<(__VA_ARGS__), int> = 0

Wimsical

// inspired by Merriam-Webster's word of the day on August 20, 2019
namespace ethereal {

        template <typename It>
        using iter_category_t = typename std::iterator_traits<It>::iterator_category;

Type names ending in _t are reserved by POSIX. Not sure I want to tread on their territory. Though i suppose that is only in the global namespace.


Not sure I like this style personally (disabling properties by inheritance) but I have seen it around (boost) so its been used before.

OK. I have now read further into the code. Nice usage as it will depend on the type T and its properties. OK. Cool like it.

        // define the copy constructor and copy assignment as deleted
        template <bool Enabled>
        struct copy_base {};

        // Put at least one blank line here.

        template <>
        struct copy_base<false> {
            copy_base() = default;
            copy_base(const copy_base&) = delete;
            copy_base(copy_base&&) = default;
            copy_base& operator=(const copy_base&) = delete;
            copy_base& operator=(copy_base&&) = default;
            ~copy_base() = default;
        };

My one complaint here is that it is hard to make out the default from deleted. I would group them together so you can at a glance see what is deleted and what is defaulted. I suppose its a common pattern that people know but in that case why not grab one of the standard version (like boost).


It's a nice touch to check N here.

    class static_vector {
        static_assert(std::is_destructible_v<T>,
                      "static_vector<T, N> requires std::is_destructible_v<T>");
        static_assert(N <= std::numeric_limits<std::ptrdiff_t>::max(),
                      "static_vector<T, N> requires "
                      "N <= std::numeric_limits<std::ptrdiff_t>::max()");

But the test N <= std::numeric_limits<std::ptrdiff_t>::max() is not accurate. I would suspect most systems have a limit on the size of the stack frame (OK its been over two decades since I wrote a compiler so that may not be true on modern hardware).

In the old days the size of the stack frame (for the kids the chunk of memory reserved for local variables when a function is entered) was limited. Usually by hardware but sometimes also be compiler. This test is a bit meaningless as std::numeric_limits<std::ptrdiff_t>::max() is very large.

Having a quick look at GCC I found this: https://gcc.gnu.org/onlinedocs/gcc-3.0.4/gcc/Stack-Checking.html

STACK_CHECK_MAX_FRAME_SIZE
The maximum size of a stack frame, in bytes. GCC will generate probe instructions in non-leaf functions to ensure at least this many bytes of stack are available. If a stack frame is larger than this size, stack checking will not be reliable and GCC will issue a warning. The default is chosen so that GCC only generates one instruction on most systems. You should normally not change the default value of this macro.


As mention before I have to find a check you have initialized all the members.

        static_vector() noexcept = default;

That makes it hard to do a code review.
Think of the people you work with. Do you have a documented way to find members so you can check that they are all being correctly initialized.


All of these function. I would have made one liners.

        [[nodiscard]] iterator begin() noexcept
        {
            return data();
        }
        [[nodiscard]] const_iterator begin() const noexcept
        {
            return data();
        }
        // etc

What's this for?

        [[nodiscard]] difference_type ssize() const noexcept
        {
            return static_cast<difference_type>(size());
        }

Why is it diffent from size()?


Bad habit.
Not putting the braces around the throw.

        reference at(size_type n)
        {
            if (n >= size())
                throw std::out_of_range{"static_vector<T, N>::at(n) out of range"};
            return begin()[n];
        }

Should this not return pointer?

        [[nodiscard]] T* data() noexcept
        {
            return std::launder(reinterpret_cast<T*>(elems.data()));
        }
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Wow, this is nice! The typename ... is used to prevent over smart users from manually specifying the template arguments. ssize is a useful feature that is standardized in c++20, so I decided to include it. (I used it in compare.) data should return T* not pointer because pointer has a different meaning (in the same way you don't want to return an iterator here, though using iterator = T*;) \$\endgroup\$ – L. F. Aug 28 '19 at 6:02
  • \$\begingroup\$ As a side note, the copy_base idiom is what the standard library uses to forward traits to wrapper objects / containers. A really nice talk featuring this and even why there is use for const T&& is from Simon Brand youtube.com/watch?v=J4A2B9eexiw \$\endgroup\$ – miscco Aug 28 '19 at 11:18
4
\$\begingroup\$

Two bugs my tests didn't catch:

Self assignment

This is a serious bug. The copy assignment of the class works by clearing *this first and then insert the values using iterators. This causes problems with self assignment — the iterators are invalidated after the clear. The following program is flagged by valgrind for access to uninitialized memory:

static_vector<std::string, 5> sv(3, std::string(20, 'x'));
sv = sv;
std::cout << sv[0] << " " << sv[1] << " " << sv[2] << "\n";

This bug is not easily testable. I included self assignment tests but valgrind didn't fire. The code above also works fine if I replace 20 with 10!

Possible fix: for copy assignment, explicitly test for self-assignment, like

if (this == &other)
    return;

For assign(iterator, iterator), state in the documentation that it's undefined behavior if the iterators point into *this. Or, more generally, if the elements in *this are accessed by copy constructing from the result of dereferencing the iterator. (Also affect other functions.)

#include <array>

It's missing. I discovered this bug by running the test on a Windows machine.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

What I hate most.
Is looking for the variables that the class uses to hold the values. IT took my 10 minutes to find them:

    std::array<std::aligned_storage_t<sizeof(T), alignof(T)>, N> elems;
    std::size_t count{0}; // invariant: count <= N
}; // class static_vector

/**
 * @cond DETAIL
 */

} // namespace detail

They are like three quarters of the way down the file. This is the most important part of the class it should not be hard to find them. If you are not going to put them at the top at least mark them in a way that we can search for them!

You know why I searched for them. Because the constructors don't initialize them so I was wondering are they self initialized. So yes they are but it was hard to find them because they are not mentioned in the constructors. This is why I dislike this way of initializing the members. I want to look at the constructor and see all them members correctly initialized not rely on code review to search through the code and check (a bit pedantic as turning on warnings would tell me but still I hate it).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Sorry to have stolen 10 minutes of your precious time! :) I have always been putting them at the very end of the class because it seems to be common practice (e.g., NL.16), but now that I think of it, the original intent is to make the public interface more visible. Given that I have created documentation, this doesn't seem necessary anymore, so I may as well put them at the beginning. \$\endgroup\$ – L. F. Aug 27 '19 at 3:41
  • 1
    \$\begingroup\$ I know this is frustrating and your reviews are generally a delight to read but that is really more a rant than a code review. Especially given the rather high quality of the code for review this is not appropriate. \$\endgroup\$ – miscco Aug 27 '19 at 7:29
  • \$\begingroup\$ @miscco I ran out of time to do the review because I could not find the things I need to validate the code and thus do the review. But saying that this is where I disagree with Bjorn. Always put the private variables at the top (so you have context). There is usually not a lot of them. Then the public interface then the protected interface and finally the private interface. \$\endgroup\$ – Martin York Aug 27 '19 at 19:45
  • \$\begingroup\$ @miscco I just saw the discussion between you and Martin York. Well, I actually upvoted the answer, but thank you for calling my code "high quality" :) \$\endgroup\$ – L. F. Aug 28 '19 at 4:19
  • \$\begingroup\$ @L.F. As marco said hi quality code so not really that much to comment on. \$\endgroup\$ – Martin York Aug 28 '19 at 4:33
0
\$\begingroup\$

Might I suggest taking a look at ETL(embedded template library) to get a comparison of your implementations? https://github.com/ETLCPP/etl/blob/master/include/etl/vector.h

This is a whole library specifically designed to do what you are trying to accomplish.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.