GSL-like array_view implementation

Question

I've seen a couple GSL-like string_view-ish implementations on CR recently, but don't recall seeing anything like array_view yet (AKA span in the GSL), so I wrote one just for fun!

My implementation is a simplified array_view that doesn't support the bounds and indexing in the same way the GSL span does. I also didn't add support for multidimensional arrays, data is always assumed to be a flat 1D array. Here's the documentation for a complete array_view class that might some day make into the Standard library.

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <iterator>
#include <stdexcept>
#include <type_traits>

namespace cr 
{

template<typename T>
class array_view final
{
public:

    //
    // Nested types:
    //

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

    using pointer                = std::add_pointer_t<value_type>;
    using reference              = std::add_lvalue_reference_t<value_type>;
    using const_pointer          = std::add_pointer_t<const value_type>;
    using const_reference        = std::add_lvalue_reference_t<const value_type>;

    using iterator               = array_iterator_base<value_type, array_view, mutable_iterator_tag>;
    using const_iterator         = array_iterator_base<const value_type, const array_view, const_iterator_tag>;
    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    //
    // Constructors / assignment:
    //

    constexpr array_view() noexcept
        : m_pointer{ nullptr }
        , m_size_in_items{ 0 }
    { }

    template<typename ArrayType, std::size_t ArraySize>
    constexpr explicit array_view(ArrayType (&arr)[ArraySize]) noexcept
        : m_pointer{ arr }
        , m_size_in_items{ ArraySize }
    { }

    template<typename ContainerType>
    constexpr explicit array_view(ContainerType & container) noexcept
        : m_pointer{ container.data() }
        , m_size_in_items{ container.size() }
    { }

    template<typename ConvertibleType>
    constexpr array_view(ConvertibleType * array_ptr, const size_type size_in_items) noexcept
        : m_pointer{ array_ptr }
        , m_size_in_items{ size_in_items }
    { }

    template<typename ConvertibleType>
    constexpr array_view(array_view<ConvertibleType> other) noexcept
        : m_pointer{ other.data() }
        , m_size_in_items{ other.size() }
    { }

    template<typename ConvertibleType>
    constexpr array_view & operator = (array_view<ConvertibleType> other) noexcept
    {
        m_pointer = other.data();
        m_size_in_items = other.size();
        return *this;
    }

    //
    // Helper methods:
    //

    void reset() noexcept
    {
        m_pointer = nullptr;
        m_size_in_items = 0;
    }

    array_view slice(const size_type offset_in_items) const
    {
        return slice(offset_in_items, size());
    }

    array_view slice(const size_type start_offset, const size_type end_offset) const
    {
        check_not_null();

        if (end_offset == start_offset)
        {
            throw std::out_of_range("array_view slice start and end offsets are the same!");
        }
        if (start_offset > end_offset)
        {
            throw std::out_of_range("array_view slice start offset greater than end offset!");
        }

        auto slice_size = end_offset - start_offset;
        auto slice_ptr  = data() + start_offset;
        auto end_ptr    = data() + size();

        if (slice_ptr > end_ptr)
        {
            throw std::out_of_range("array_view slice start offset is out-of-bounds!");
        }
        if (slice_size > (size() - start_offset))
        {
            throw std::out_of_range("array_view slice is larger than size!");
        }

        return { slice_ptr, slice_size };
    }

    //
    // Data access:
    //

    const_reference at(const size_type index) const
    {
        // at() always validates the array_view and index.
        // operator[] uses assert()s that can be disabled if
        // you care more about performance than runtime checking.
        check_not_null();
        if (index >= size())
        {
            throw std::out_of_range("array_view::at(): index is out-of-bounds!");
        }
        return *(data() + index);
    }
    reference at(const size_type index)
    {
        check_not_null();
        if (index >= size())
        {
            throw std::out_of_range("array_view::at(): index is out-of-bounds!");
        }
        return *(data() + index);
    }

    constexpr const_reference operator[](const size_type index) const noexcept
    {
        // Unlike with at() these checks can be disabled for ultimate performance.
        assert(data() != nullptr);
        assert(index < size());
        return *(data() + index);
    }
    constexpr reference operator[](const size_type index) noexcept
    {
        assert(data() != nullptr);
        assert(index < size());
        return *(data() + index);
    }

    //
    // Begin/end range iterators, front()/back():
    //

    // forward begin:
    iterator begin() noexcept
    {
        return make_iterator(0);
    }
    const_iterator begin() const noexcept
    {
        return make_const_iterator(0);
    }
    const_iterator cbegin() const noexcept
    {
        return make_const_iterator(0);
    }

    // forward end:
    iterator end() noexcept
    {
        return make_iterator(size());
    }
    const_iterator end() const noexcept
    {
        return make_const_iterator(size());
    }
    const_iterator cend() const noexcept
    {
        return make_const_iterator(size());
    }

    // reverse begin:
    reverse_iterator rbegin() noexcept
    {
        return reverse_iterator{ end() };
    }
    const_reverse_iterator rbegin() const noexcept
    {
        return const_reverse_iterator{ end() };
    }
    const_reverse_iterator crbegin() const noexcept
    {
        return const_reverse_iterator{ cend() };
    }

    // reverse end:
    reverse_iterator rend() noexcept
    {
        return reverse_iterator{ begin() };
    }
    const_reverse_iterator rend() const noexcept
    {
        return const_reverse_iterator{ begin() };
    }
    const_reverse_iterator crend() const noexcept
    {
        return const_reverse_iterator{ cbegin() };
    }

    reference front()
    {
        check_not_null();
        return *data();
    }
    const_reference front() const
    {
        check_not_null();
        return *data();
    }

    reference back()
    {
        check_not_null();
        return *(data() + size() - 1);
    }
    const_reference back() const
    {
        check_not_null();
        return *(data() + size() - 1);
    }

    //
    // Miscellaneous queries:
    //

    constexpr bool empty() const noexcept
    {
        return size() == 0;
    }
    constexpr size_type size() const noexcept
    {
        return m_size_in_items;
    }
    constexpr size_type size_bytes() const noexcept
    {
        return m_size_in_items * sizeof(value_type);
    }
    constexpr const_pointer data() const noexcept
    {
        return m_pointer;
    }
    constexpr pointer data() noexcept
    {
        return m_pointer;
    }

    //
    // Compare against nullptr (test for a null array_view):
    //

    constexpr bool operator == (std::nullptr_t) const noexcept
    {
        return data() == nullptr;
    }
    constexpr bool operator != (std::nullptr_t) const noexcept
    {
        return !(*this == nullptr);
    }

    //
    // Compare for same array pointer and size:
    //

    constexpr bool operator == (const array_view & other) const noexcept
    {
        return data() == other.data() && size() == other.size();
    }
    constexpr bool operator != (const array_view & other) const noexcept
    {
        return !(*this == other);
    }

    //
    // Compare pointer value for ordering (useful for containers/sorting):
    //

    constexpr bool operator < (const array_view & other) const noexcept
    {
        return data() < other.data();
    }
    constexpr bool operator > (const array_view & other) const noexcept
    {
        return data() > other.data();
    }
    constexpr bool operator <= (const array_view & other) const noexcept
    {
        return !(*this > other);
    }
    constexpr bool operator >= (const array_view & other) const noexcept
    {
        return !(*this < other);
    }

    //
    // Non-throwing swap() overload for array_views:
    //

    friend void swap(array_view & lhs, array_view & rhs) noexcept
    {
        using std::swap;
        swap(lhs.m_pointer, rhs.m_pointer);
        swap(lhs.m_size_in_items, rhs.m_size_in_items);
    }

private:

    void check_not_null() const
    {
        if (data() == nullptr || size() == 0)
        {
            throw std::logic_error("array_view pointer is null or size is zero!");
        }
    }

    iterator make_iterator(const difference_type start_offset) noexcept
    {
        return (data() != nullptr) ? iterator{ this, start_offset } : iterator{};
    }

    const_iterator make_const_iterator(const difference_type start_offset) const noexcept
    {
        return (data() != nullptr) ? const_iterator{ this, start_offset } : const_iterator{};
    }

    // Pointer is just a reference to external memory. Not owned by array_view.
    pointer   m_pointer;
    size_type m_size_in_items;
};

//
// make_array_view() helpers:
//
template<typename ArrayType, std::size_t ArraySize>
constexpr auto make_array_view(ArrayType (&arr)[ArraySize]) noexcept
{
    return array_view<ArrayType>{ arr, ArraySize };
}
template<typename ArrayType>
constexpr auto make_array_view(ArrayType * array_ptr, const std::size_t size_in_items) noexcept
{
    return array_view<ArrayType>{ array_ptr, size_in_items };
}
template<typename ContainerType>
constexpr auto make_array_view(ContainerType & container) noexcept
{
    return array_view<typename ContainerType::value_type>{ container };
}

} // namespace cr

And following is the RandomAccessIterator type used by array_view:

namespace cr 
{

struct mutable_iterator_tag { };
struct const_iterator_tag   { };

template
<
    typename T,
    typename ParentType,
    typename AccessQualifierTag
>
class array_iterator_base
    : public std::iterator<std::random_access_iterator_tag, T>
{
public:

    //
    // Nested types:
    //

    using parent_type          = ParentType;
    using access_tag_type      = AccessQualifierTag;
    using parent_iterator_type = std::iterator<std::random_access_iterator_tag, T>;

    using size_type            = std::size_t;
    using difference_type      = std::ptrdiff_t;
    using value_type           = typename parent_iterator_type::value_type;
    using pointer              = typename parent_iterator_type::pointer;
    using reference            = typename parent_iterator_type::reference;

    //
    // Constructors / assignment:
    //

    constexpr array_iterator_base() noexcept
        : m_parent_array{ nullptr }
        , m_current_index{ 0 }
    { }

    constexpr array_iterator_base(parent_type * parent, const difference_type index) noexcept
        : m_parent_array{ parent }
        , m_current_index{ index }
    { }

    //
    // Pointer-emulation operator overloads:
    //

    difference_type operator - (const array_iterator_base & other) const
    {
        check_same_parent(other);
        return m_current_index - other.m_current_index;
    }

    array_iterator_base operator + (const difference_type displacement) const
    {
        array_iterator_base temp{ *this };
        return temp.increment(displacement);
    }
    array_iterator_base operator - (const difference_type displacement) const
    {
        array_iterator_base temp{ *this };
        return temp.decrement(displacement);
    }

    array_iterator_base & operator += (const difference_type displacement)
    {
        return increment(displacement);
    }
    array_iterator_base & operator -= (const difference_type displacement)
    {
        return decrement(displacement);
    }

    array_iterator_base & operator++() // pre-increment
    {
        return increment(1);
    }
    array_iterator_base operator++(int) // post-increment
    {
        array_iterator_base temp{ *this };
        increment(1);
        return temp;
    }

    array_iterator_base & operator--() // pre-decrement
    {
        return decrement(1);
    }
    array_iterator_base operator--(int) // post-decrement
    {
        array_iterator_base temp{ *this };
        decrement(1);
        return temp;
    }

    reference operator*() const
    {
        if (!is_dereferenceable())
        {
            throw std::logic_error("array_iterator_base::operator*: iterator not dereferenceable!");
        }
        return (*m_parent_array)[m_current_index];
    }
    reference operator->() const
    {
        if (!is_dereferenceable())
        {
            throw std::logic_error("array_iterator_base::operator->: iterator not dereferenceable!");
        }
        return (*m_parent_array)[m_current_index];
    }
    reference operator[](const size_type index) const
    {
        if (!is_dereferenceable())
        {
            throw std::logic_error("array_iterator_base::operator[]: iterator not dereferenceable!");
        }

        const size_type array_index = m_current_index + index;
        if (array_index >= m_parent_array->size())
        {
            throw std::out_of_range("array_iterator_base::operator[]: array index is out-of-bounds!");
        }
        return (*m_parent_array)[array_index];
    }

    constexpr bool operator == (std::nullptr_t) const noexcept
    {
        return m_parent_array == nullptr;
    }
    constexpr bool operator != (std::nullptr_t) const noexcept
    {
        return !(*this == nullptr);
    }

    bool operator == (const array_iterator_base & other) const
    {
        check_same_parent(other);
        return m_current_index == other.m_current_index;
    }
    bool operator != (const array_iterator_base & other) const
    {
        return !(*this == other);
    }

    bool operator < (const array_iterator_base & other) const
    {
        check_same_parent(other);
        return m_current_index < other.m_current_index;
    }
    bool operator > (const array_iterator_base & other) const
    {
        check_same_parent(other);
        return m_current_index > other.m_current_index;
    }

    bool operator <= (const array_iterator_base & other) const
    {
        return !(*this > other);
    }
    bool operator >= (const array_iterator_base & other) const
    {
        return !(*this < other);
    }

    //
    // One way conversion from mutable_iterator to const_iterator:
    //

    operator array_iterator_base<const value_type, const parent_type, const_iterator_tag>() const noexcept
    {
        return array_iterator_base<const value_type, const parent_type, const_iterator_tag>{ m_parent_array, m_current_index };
    }

    //
    // Non-throwing swap() overload for array_iterator_base:
    //

    friend void swap(array_iterator_base & lhs, array_iterator_base & rhs) noexcept
    {
        using std::swap;
        swap(lhs.m_parent_array,  rhs.m_parent_array);
        swap(lhs.m_current_index, rhs.m_current_index);
    }

private:

    constexpr bool is_dereferenceable() const noexcept
    {
        return m_parent_array != nullptr && m_current_index >= 0 &&
               static_cast<size_type>(m_current_index) < m_parent_array->size();
    }

    void check_same_parent(const array_iterator_base & other) const
    {
        if (m_parent_array != other.m_parent_array)
        {
            throw std::logic_error("Array iterators belong to different objects!");
        }
    }

    array_iterator_base & increment(const difference_type displacement)
    {
        if (m_parent_array == nullptr)
        {
            throw std::logic_error("Incrementing an invalid array iterator!");
        }
        m_current_index += displacement;
        return *this;
    }

    array_iterator_base & decrement(const difference_type displacement)
    {
        if (m_parent_array == nullptr)
        {
            throw std::logic_error("Decrementing an invalid array iterator!");
        }
        m_current_index -= displacement;
        return *this;
    }

    // Reference to the object that holds the data
    // this iterator points to (the array_view that
    // created to the iterator).
    parent_type * m_parent_array;

    // Current dereference index in the m_parent_array.
    difference_type m_current_index;
};

} // namespace cr

If you see anything that can be done differently or improved, let me know!

One thing that I'd be interested in getting a few comments about is constexpr. C++14 pretty much lets you slap constexpr in front of any non-throwing function, but I'm not sure if there's any actual value in that, some functions clearly can't be resolved at compile-time. So, is it worth adding constexpr to as much stuff as you can, or is constexpr becoming the new inline?

Answer 1

Implementation

• if(slice_ptr > end_ptr) inside array_view::slice(const size_type, const size_type) might invoke undefined behavior (it's undefined if the condition would return true and the original allocation of the underlying contiguous memory ends at end_ptr). However, it could easily be replaced with the logically equivalent if(start_offset > size()). Also, the comparison should be >= instead of >, as end_ptr already points 1 past the last covered element, so starting a non-empty array slice there isn't possible.
• if (slice_size > (size() - start_offset)) in the same function could be combined with the check above to if (end_offset <= size()), as we know start_offset < end_offset from checks beforehand.
• The comparison operators invoke undefined behavior unless both array_views are slices of the same underlying array. This could be fixed by using std::less<array_view::pointer> (or corresponding equivalents) to do the comparison, but what would be a use case of comparing the addresses of the two arrays relatively to each other?

Template restrictions

• array_view::value_type should probably be restricted to std::remove_reference<T>, as there can not be an array of references.
• ArrayType (of the array_view constructor) can only ever legally be the same as array_view::value_type, so this template parameter is not necessary. With the lack of proper restrictions, it would allow to assign an array of objects derived from array_view::value_type, which cannot be indexed correctly (m_pointer[1] might not point to the address of arr[1] if sizeof(array_view::value_type) < sizeof(ArrayType)). See this SO answer for more information
• I don't think ConvertibleType (see the two constructors and the assignment operator) is treated correctly either:
  • If ConvertibleType is derived from array_view::value_type, the same problem as with ArrayType above occurs.
  • If ConvertibleType is has a conversion operator to array_view::value_type, the pointer cannot be correctly assigned to m_pointer legally (only legal for array_view::pointer or derived types).