6
\$\begingroup\$

I'd like to have a review on my C-style array wrapper. I based this on std::array implementation. I hope you can leave some feedback!

array.ixx

module;

#include <cstddef>
#include <stdexcept>
#include <utility>
#include <type_traits>
#include <compare>

export module array;

export namespace stl
{
    template<class T, std::size_t N> struct array
    {
        using value_type            = T;
        using size_type             = std::size_t;
        using reference             = value_type&;
        using const_reference       = const value_type&;
        using pointer               = value_type*;
        using const_pointer         = const value_type*;
        using iterator              = value_type*;
        using const_iterator        = const value_type*;

        T _items[N ? N : 1];

        constexpr reference at(size_type pos);

        constexpr const_reference at(size_type pos) const;

        constexpr reference operator[](size_type pos);

        constexpr const_reference operator[](size_type pos) const;

        constexpr reference front();

        constexpr const_reference front() const;

        constexpr reference back();

        constexpr const_reference back() const;

        constexpr pointer data() noexcept;

        constexpr const_pointer data() const noexcept;

        constexpr iterator begin() noexcept;

        constexpr iterator end() noexcept;

        constexpr const_iterator begin() const noexcept;

        constexpr const_iterator end() const noexcept;

        [[nodiscard]] constexpr bool empty() const noexcept;

        constexpr size_type size() const noexcept;

        constexpr size_type max_size() const noexcept;

        constexpr void fill(value_type value);

        constexpr void swap(array& other) noexcept(std::is_nothrow_swappable_v<T>);
    };

    template<std::size_t I, class T, std::size_t N> constexpr T& get(array<T, N>& a) noexcept;

    template<std::size_t I, class T, std::size_t N> constexpr const T& get(const array<T, N>& a) noexcept;

    template<std::size_t I, class T, std::size_t N> constexpr T&& get(array<T, N>&& a) noexcept;

    template<std::size_t I, class T, std::size_t N> constexpr const T&& get(const array<T, N>&& a) noexcept;

    template<class T, std::size_t N> constexpr bool operator==(const array<T, N>& lhs, const array<T, N>& rhs);

    template<class T, std::size_t N> constexpr auto operator<=>(const array<T, N>& lhs, const array<T, N>& rhs);
}

template<class T, std::size_t N>
constexpr T& stl::array<T, N>::at(size_type pos)
{
    /**
    *   @brief: Returns a reference to the element at specified location pos, with bounds checking.
    *           If pos is not within the range of the container, an exception of type std::out_of_range is thrown.  
    *   
    *   @param: pos - position of the element to return.
    * 
    *   @return: Reference to the requested element.
    * 
    *   @excep: std::out_of_range if !(pos < size()).
    * 
    *   @complex: O(1).
    */
    return !(pos < N) ? throw std::out_of_range("Out of range") : _items[pos];
}

template<class T, std::size_t N>
constexpr const T& stl::array<T, N>::at(size_type pos) const
{
    /**
    *   @brief: Returns a reference to the element at specified location pos, with bounds checking.
    *           If pos is not within the range of the container, an exception of type std::out_of_range is thrown.
    *
    *   @param: pos - position of the element to return.
    *
    *   @return: Reference to the requested element.
    *
    *   @excep: std::out_of_range if !(pos < size()).
    * 
    *   @complex: O(1).
    */
    return !(pos < size()) ? throw std::out_of_range("Out of range") : _items[pos];
}

template<class T, std::size_t N>
constexpr T& stl::array<T, N>::operator[](size_type pos)
{
    /**
    *   @brief: Returns a reference to the element at specified location pos. No bounds checking is performed.
    *
    *   @param: pos - position of the element to return.
    *
    *   @return: Reference to the requested element.
    * 
    *   @excep: None;
    * 
    *   @complex: O(1).
    */
    return _items[pos];
}

template<class T, std::size_t N>
constexpr const T& stl::array<T, N>::operator[](size_type pos) const
{
    /**
    *   @brief: Returns a reference to the element at specified location pos. No bounds checking is performed.
    *
    *   @param: pos - position of the element to return.
    *
    *   @return: Reference to the requested element.
    * 
    *   @excep: None;
    * 
    *   @complex: O(1).
    */
    return _items[pos];
}

template<class T, std::size_t N>
constexpr T& stl::array<T, N>::front()
{
    /**
    *   @brief: Returns a reference to the first element in the container.
    *           Calling front on an empty container is undefined.
    *
    *   @param: None.
    *
    *   @return: Reference to the first element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return *_items;
}

template<class T, std::size_t N>
constexpr const T& stl::array<T, N>::front() const
{
    /**
    *   @brief: Returns a reference to the first element in the container.
    *           Calling front on an empty container is undefined.
    *
    *   @param: None.
    *
    *   @return: Reference to the first element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return *_items;
}

template<class T, std::size_t N>
constexpr T& stl::array<T, N>::back()
{
    /**
    *   @brief: Returns a reference to the last element in the container.
    *           Calling back on an empty container causes undefined behavior.
    *
    *   @param: None.
    *
    *   @return: Reference to the last element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return *(_items + N);
}

template<class T, std::size_t N>
constexpr const T& stl::array<T, N>::back() const
{
    /**
    *   @brief: Returns a reference to the last element in the container.
    *           Calling back on an empty container causes undefined behavior.
    *
    *   @param: None.
    *
    *   @return: Reference to the last element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return *(_items + N);
}

template<class T, std::size_t N>
constexpr T* stl::array<T, N>::data() noexcept
{
    /**
    *   @brief: Returns pointer to the underlying array serving as element storage.
    *
    *   @param: None.
    *
    *   @return: Pointer to the underlying element storage. For non-empty containers, 
    *            the returned pointer compares equal to the address of the first element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return _items;
}

template<class T, std::size_t N>
constexpr const T* stl::array<T, N>::data() const noexcept
{
    /**
    *   @brief: Returns pointer to the underlying array serving as element storage.
    *
    *   @param: None.
    *
    *   @return: Pointer to the underlying element storage. For non-empty containers,
    *            the returned pointer compares equal to the address of the first element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return _items;
}

template<class T, std::size_t N>
constexpr T* stl::array<T, N>::begin() noexcept
{
    /**
    *   @brief: Returns an iterator to the first element of the array.
    *           If the array is empty, the returned iterator will be equal to end().
    *
    *   @param: None.
    *
    *   @return: Iterator to the first element.
    * 
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return _items;
}

template<class T, std::size_t N>
constexpr T* stl::array<T, N>::end() noexcept
{
    /**
    *   @brief: Returns an iterator to the element following the last element of the array.
    *           This element acts as a placeholder; attempting to access it results in undefined behavior.
    *
    *   @param: None.
    *
    *   @return: Iterator to the element following the last element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return _items + N;
}

template<class T, std::size_t N>
constexpr const T* stl::array<T, N>::begin() const noexcept
{
    /**
    *   @brief: Returns an iterator to the first element of the array.
    *           If the array is empty, the returned iterator will be equal to end().
    *
    *   @param: None.
    *
    *   @return: Iterator to the first element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return _items;
}

template<class T, std::size_t N>
constexpr const T* stl::array<T, N>::end() const noexcept
{
    /**
    *   @brief: Returns an iterator to the element following the last element of the array.
    *           This element acts as a placeholder; attempting to access it results in undefined behavior.
    *
    *   @param: None.
    *
    *   @return: Iterator to the element following the last element.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return _items + N;
}

template<class T, std::size_t N>
constexpr bool stl::array<T, N>::empty() const noexcept
{
    /**
    *   @brief: Checks if the container has no elements, i.e. whether begin() == end().
    *
    *   @param: None.
    *
    *   @return: true if the container is empty, false otherwise.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return begin() == end();
}

template<class T, std::size_t N>
constexpr std::size_t stl::array<T, N>::size() const noexcept
{
    /**
    *   @brief: Returns the number of elements in the container.
    *
    *   @param: None.
    *
    *   @return: The number of elements in the container.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return N;
}

template<class T, std::size_t N>
constexpr std::size_t stl::array<T, N>::max_size() const noexcept
{
    /**
    *   @brief: Returns the maximum number of elements the container is able to
    *           hold due to system or library implementation limitations.
    *
    *   @param: None.
    *
    *   @return: Maximum number of elements.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return N;
}

template<class T, std::size_t N>
constexpr void stl::array<T, N>::fill(value_type value)
{
    /**
    *   @brief: Assigns the given value value to all elements in the container.
    *
    *   @param: value - the value to assign to the elements
    *
    *   @return: None.
    *
    *   @excep: None;
    *
    *   @complex: O(n).
    */
    for (auto& i : _items)
    {
        i = value;
    }
}

template<class T, std::size_t N>
constexpr void stl::array<T, N>::swap(array& other) noexcept(std::is_nothrow_swappable_v<T>)
{
    /**
    *   @brief: Exchanges the contents of the container with those of other.
    *
    *   @param: other - container to exchange the contents with
    *
    *   @return: None.
    *
    *   @excep: None;
    *
    *   @complex: O(n).
    */
    for (std::size_t i = 0; i < size(); i++)
    {
        std::swap(_items[i], other[i]);
    }
}

template<std::size_t I, class T, std::size_t N>
constexpr T& stl::get(array<T, N>& a) noexcept
{
    /**
    *   @brief: Extracts the Ith element element from the array.
    *           I must be an integer value in range [0, N).
    *
    *   @param: array - whose contents to extract
    *
    *   @return: A reference to the Ith element of a.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    static_assert(I < a.size());

    return a[I];
}

template<std::size_t I, class T, std::size_t N>
constexpr T&& stl::get(array<T, N>&& a) noexcept
{
    /**
    *   @brief: Extracts the Ith element element from the array.
    *           I must be an integer value in range [0, N).
    *
    *   @param: array - whose contents to extract
    *
    *   @return: A reference to the Ith element of a.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    static_assert(I < a.size());

    return a[I];
}

template<std::size_t I, class T, std::size_t N>
constexpr const T& stl::get(const array<T, N>& a) noexcept
{
    /**
    *   @brief: Extracts the Ith element element from the array.
    *           I must be an integer value in range [0, N).
    *
    *   @param: array - whose contents to extract
    *
    *   @return: A reference to the Ith element of a.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    static_assert(I < a.size());

    return a[I];
}

template<std::size_t I, class T, std::size_t N>
constexpr const T&& stl::get(const array<T, N>&& a) noexcept
{
    /**
    *   @brief: Extracts the Ith element element from the array.
    *           I must be an integer value in range [0, N).
    *
    *   @param: array - whose contents to extract
    *
    *   @return: A reference to the Ith element of a.
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    static_assert(I < a.size());

    return a[I];
}

template<class T, std::size_t N>
constexpr bool stl::operator==(const array<T, N>& lhs, const array<T, N>& rhs)
{
    /**
    *   @brief: Checks if the contents of lhs and rhs are equal, that is, they have the same number of elements 
    *           and each element in lhs compares equal with the element in rhs at the same position.
    *
    *   @param: lhs, rhs - arrays whose contents to compare.
    *
    *   @return: true if the contents of the arrays are equal, false otherwise.
    *
    *   @excep: None;
    *
    *   @complex: O(n).
    */
    std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template<class T, std::size_t N>
constexpr auto stl::operator<=>(const array<T, N>& lhs, const array<T, N>& rhs)
{
    /**
    *   @brief: The comparison is performed as if by calling std::lexicographical_compare_three_way on two arrays
    *           with a function object performing synthesized three-way comparison
    *
    *   @param: lhs, rhs - arrays whose contents to compare.
    *
    *   @return: lhs.size() <=> rhs.size().
    *
    *   @excep: None;
    *
    *   @complex: O(1).
    */
    return lhs.size() <=> rhs.size();
}
```
\$\endgroup\$
1
  • 1
    \$\begingroup\$ It's nice to see someone using modules! \$\endgroup\$
    – JDługosz
    Commented Oct 19, 2021 at 15:16

1 Answer 1

4
\$\begingroup\$
template<class T, std::size_t N>
constexpr const T& stl::array<T, N>::back() const
{
    return *(_items + N);
}

bug: Shouldn't this be accessing element (N - 1)?

(Same issue with the non-const version).


Otherwise everything looks pretty good. It's just nitpicking below:


    T _items[N ? N : 1];

I think this works (allows zero-sized array with no compiler error, still ensures that begin() == end() because we use N to calculate them). But some comments to explain it would be nice.


template<class T, std::size_t N>
constexpr T& stl::array<T, N>::at(size_type pos)
{
    return !(pos < N) ? throw std::out_of_range("Out of range") : _items[pos];
}

Just style, but I think it's a bit clearer to put the throw outside of the return statement (we don't return anything if we throw).

template<class T, std::size_t N>
constexpr T& stl::array<T, N>::at(size_type pos)
{
    if (!(pos < N)) 
        throw std::out_of_range("Out of range");
    
    return _items[pos];
}

template<class T, std::size_t N>
constexpr void stl::array<T, N>::swap(array& other) noexcept(std::is_nothrow_swappable_v<T>)
{
    for (std::size_t i = 0; i < size(); i++)
    {
        std::swap(_items[i], other[i]);
    }
}

Could use the size_type typedef for the loop index.

There is an array version of std::swap which calls std::swap_ranges internally, so I think we can just do: std::swap(_items, other._items).


Don't forget to implement reverse iterators!


If you want to go for completeness, there's also make_array, to_array, tuple_size, tuple_element and the deduction guide. See cppreference.

\$\endgroup\$
5
  • \$\begingroup\$ What do you mean by "deudction guide"? Anyway, thank you for the review! \$\endgroup\$
    – Never
    Commented Oct 19, 2021 at 11:45
  • 3
    \$\begingroup\$ The deduction guide lets users write something like: std::array a{ 1, 2, 3, 4}; without directly specifying the type or size: en.cppreference.com/w/cpp/container/array/deduction_guides \$\endgroup\$
    – user673679
    Commented Oct 19, 2021 at 11:54
  • \$\begingroup\$ re throw inside the return: it could be legacy from an implementation that was written right after constexpr functions were added, when that was how you had to do it. Like, 10 years ago. \$\endgroup\$
    – JDługosz
    Commented Oct 19, 2021 at 15:19
  • 2
    \$\begingroup\$ !(pos < N) should really be written pos >= N for integral types. Complexity is bad. T _items[N ? N : 1]; does not work for types which aren't trivially (or at least cheaply without side-effects) default-constructible for N == 0. std::array<T, 0> x; and std::array<T, 0> x {}; must always be valid, side-effect free and dirt cheap. \$\endgroup\$ Commented Oct 20, 2021 at 16:50
  • 1
    \$\begingroup\$ All the mainstream implementations use specialization to resolve the issue mentioned by @Deduplicator: libstdc++, libc++, Microsoft STL. \$\endgroup\$ Commented May 11, 2023 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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