5
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ The first overload of slice seems erroneous to me. Shouldn't the second argument to the constructor be size()-offset_in_items instead of just size()? Also, why wouldn't you allow a slice of size 0 in the second overload? \$\endgroup\$
    – MikeMB
    Jan 21 '16 at 23:11
  • \$\begingroup\$ Also on a personal note,I think the comparison operators should compare the values of the underlying arrays instead of pointer addresses. This is also the way its done in gsl and how std::string_view will probably behave in the future \$\endgroup\$
    – MikeMB
    Jan 21 '16 at 23:19
  • \$\begingroup\$ @MikeMB, I think you're right, I did make a mistake there, it should be size-offset. For the second one, a zero-sized slice didn't seem to make a lot of sense, but it could maybe return a default constructed instance (return array_view{};)?... Yep, the standard impl probably compares each element, an so does other containers like vector. I was just lazy that day, but I might rethink it ;) \$\endgroup\$
    – glampert
    Jan 21 '16 at 23:53
3
\$\begingroup\$

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).
\$\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.