7
\$\begingroup\$

C++20 added the span library under the header <span>. As voluntary exercise (not homework!), I spent approximately 1.5 hours implement it under C++17. Please tell me if I used stuff that is not available under C++17.

Most stuff is in the namespace ::my_std, but tuple_size, etc. are in the namespace ::std, otherwise they are useless. The ::my_std::span_detail namespace contains implementation details that are not to be exposed.

I used the C++ standard draft, HTML version as a reference.

Here is my code, within 400 lines:

// a C++17 implementation of <span>

#ifndef INC_SPAN_HPP_c2GLAK6Onz
#define INC_SPAN_HPP_c2GLAK6Onz

#include <array>       // for std::array, etc.
#include <cassert>     // for assert
#include <cstddef>     // for std::size_t, etc.
#include <iterator>    // for std::reverse_iterator, etc.
#include <type_traits> // for std::enable_if, etc.

#define CONSTRAINT(...) \
  std::enable_if_t<(__VA_ARGS__), int> = 0
#define EXPECTS(...) \
  assert((__VA_ARGS__))

namespace my_std {

  // constants

  // equivalent to std::numeric_limits<std::size_t>::max()
  inline constexpr std::size_t dynamic_extent = -1;

  // class template span

  template <class T, std::size_t N = dynamic_extent>
  class span;

  namespace span_detail {

    // detect specializations of span

    template <class T>
    struct is_span :std::false_type {};

    template <class T, std::size_t N>
    struct is_span<span<T, N>> :std::true_type {};

    template <class T>
    inline constexpr bool is_span_v = is_span<T>::value;

    // detect specializations of std::array

    template <class T>
    struct is_array :std::false_type {};

    template <class T, std::size_t N>
    struct is_array<std::array<T, N>> :std::true_type {};

    template <class T>
    inline constexpr bool is_array_v = is_array<T>::value;

    // ADL-aware data() and size()

    using std::data;
    using std::size;

    template <class C>
    constexpr decltype(auto) my_data(C& c)
    {
      return data(c);
    }

    template <class C>
    constexpr decltype(auto) my_size(C& c)
    {
      return size(c);
    }

    // detect container

    template <class C, class = void>
    struct is_cont :std::false_type {};

    template <class C>
    struct is_cont<C,
      std::void_t<
    std::enable_if_t<!is_span_v<C>>,
    std::enable_if_t<!is_array_v<C>>,
    std::enable_if_t<!std::is_array_v<C>>,
    decltype(data(std::declval<C>())),
        decltype(size(std::declval<C>()))
    >> :std::true_type {};

    template <class C>
    inline constexpr bool is_cont_v = is_cont<C>::value;
  }

  template <class T, std::size_t N>
  class span {
  public:    
    // constants and types

    using element_type = T;
    using value_type = std::remove_cv_t<T>;
    using index_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = 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>;

    static constexpr index_type extent = N;

    // constructors, copy, and assignment

    // LWG 3198 applied
    constexpr span() noexcept
      : size_{0}, data_{nullptr}
    {
      static_assert(N == dynamic_extent || N == 0);
    }

    constexpr span(T* ptr, index_type n)
      : size_{n}, data_{ptr}
    {
      EXPECTS(N == dynamic_extent || N == n);
    }

    constexpr span(T* first, T* last)
      : size_{last - first}, data_{first}
    {
      EXPECTS(N == dynamic_extent || last - first = N);
    }

    template <std::size_t M,
          CONSTRAINT(N == dynamic_extent || N == M
             && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<T(&)[M]>()))>(*)[], T(*)[]>)>
    constexpr span(T (&arr)[M]) noexcept
      : size_{M}, data_{arr}
    {
    }

    template <std::size_t M,
              CONSTRAINT(N == dynamic_extent || N == M
                 && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<T(&)[M]>()))>(*)[], T(*)[]>)>
    constexpr span(std::array<value_type, M>& arr) noexcept
      : size_{M}, data_{arr.data()}
    {
    }

    template <std::size_t M,
              CONSTRAINT(N == dynamic_extent || N == M
                 && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<T(&)[M]>()))>(*)[], T(*)[]>)>
    constexpr span(const std::array<value_type, M>& arr) noexcept
      : size_{M}, data_{arr.data()}
    {
    }

    template <class Cont,
          CONSTRAINT(N == dynamic_extent
             && span_detail::is_cont_v<Cont>
             && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<Cont>()))>(*)[], T(*)[]>)>
    constexpr span(Cont& c)
      : size_{span_detail::my_size(c)},
        data_{span_detail::my_data(c)}
    {
    }

    template <class Cont,
          CONSTRAINT(N == dynamic_extent
             && span_detail::is_cont_v<Cont>
             && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<Cont>()))>(*)[], T(*)[]>)>
    constexpr span(const Cont& c)
      : size_{span_detail::my_size(c)},
        data_{span_detail::my_data(c)}
    {
    }

    constexpr span(const span& other) noexcept = default;

    template <class U, std::size_t M,
          CONSTRAINT(N == dynamic_extent || N == M
             && std::is_convertible_v<U(*)[], T(*)[]>)>
    constexpr span(const span<U, M>& s) noexcept
      : size_{s.size()}, data_{s.data()}
    {      
    }

    ~span() noexcept = default;

    constexpr span& operator=(const span& other) noexcept = default;

    // subviews

    template <std::size_t Cnt>
    constexpr span<T, Cnt> first() const
    {
      EXPECTS(Cnt <= size());
      return {data(), Cnt};
    }

    template <std::size_t Cnt>
    constexpr span<T, Cnt> last() const
    {
      EXPECTS(Cnt <= size());
      return {data() + (size() - Cnt), Cnt};
    }

    template <std::size_t Off, std::size_t Cnt = dynamic_extent>
    constexpr auto subspan() const
    {
      EXPECTS(Off <= size() && (Cnt == dynamic_extent || Off + Cnt <= size()));
      if constexpr (Cnt != dynamic_extent)
        return span<T, Cnt>{data() + Off, Cnt};
      else if constexpr (N != dynamic_extent)
        return span<T, N - Off>{data() + Off, size() - Off};
      else
    return span<T, dynamic_extent>{data() + Off, size() - Off};
    }

    constexpr span<T, dynamic_extent> first(index_type cnt) const
    {
      EXPECTS(cnt <= size());
      return {data(), cnt};
    }

    constexpr span<T, dynamic_extent> last(index_type cnt) const
    {
      EXPECTS(cnt <= size());
      return {data() + (size() - cnt), cnt};
    }

    constexpr span<T, dynamic_extent> subspan(index_type off,
                          index_type cnt = dynamic_extent) const
    {
      EXPECTS(off <= size() && (cnt == dynamic_extent || off + cnt <= size()));
      return {data() + off, cnt == dynamic_extent ? size() - off : cnt};
    }

    // observers

    constexpr index_type size() const noexcept
    {
      return size_;
    }

    constexpr index_type size_bytes() const noexcept
    {
      return size() * sizeof(T);
    }

    [[nodiscard]] constexpr bool empty() const noexcept
    {
      return size() == 0;
    }

    // element access

    constexpr reference operator[](index_type idx) const
    {
      EXPECTS(idx < size());
      return *(data() + idx);
    }

    constexpr reference front() const
    {
      EXPECTS(!empty());
      return *data();
    }

    constexpr reference back() const
    {
      EXPECTS(!empty());
      return *(data() + (size() - 1));
    }

    constexpr pointer data() const noexcept
    {
      return data_;
    }

    // iterator support

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

    constexpr iterator end() const noexcept
    {
      return data() + size();
    }

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

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

    constexpr reverse_iterator rbegin() const noexcept
    {
      return reverse_iterator{end()};
    }

    constexpr reverse_iterator rend() const noexcept
    {
      return reverse_iterator{begin()};
    }

    constexpr const_reverse_iterator crbegin() const noexcept
    {
      return reverse_iterator{cend()};
    }

    constexpr const_reverse_iterator crend() const noexcept
    {
      return reverse_iterator{cbegin()};
    }

    friend constexpr iterator begin(span s) noexcept
    {
      return s.begin();
    }

    friend constexpr iterator end(span s) noexcept
    {
      return s.end();
    }

  private:
    pointer data_;
    index_type size_;
  };

  // deduction guide

  template <class T, std::size_t N>
  span(T (&)[N]) -> span<T, N>;

  template <class T, std::size_t N>
  span(std::array<T, N>&) -> span<T, N>;

  template <class T, std::size_t N>
  span(const std::array<T, N>&) -> span<const T, N>;

  template <class Cont>
  span(Cont&) -> span<typename Cont::value_type>;

  template <class Cont>
  span(const Cont&) -> span<const typename Cont::value_type>;

  // views of objects representation

  template <class T, std::size_t N>
  auto as_bytes(span<T, N> s) noexcept
    -> span<const std::byte,
        N == dynamic_extent ? dynamic_extent : sizeof(T) * N>
  {
    return {reinterpret_cast<const std::byte*>(s.data()), s.size_bytes()};
  }

  template <class T, std::size_t N,
        CONSTRAINT(!std::is_const_v<T>)>
  auto as_writable_bytes(span<T, N> s) noexcept
    -> span<std::byte,
        N == dynamic_extent ? dynamic_extent : sizeof(T) * N>
  {
    return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
  }

}

namespace std {

  // tuple interface
  // the primary template declarations are included in <array>

  template <class T, std::size_t N>
  struct tuple_size<my_std::span<T, N>>
    : std::integral_constant<std::size_t, N> {};

  // not defined
  template <class T>
  struct tuple_size<my_std::span<T, my_std::dynamic_extent>>;

  template <std::size_t I, class T, std::size_t N>
  struct tuple_element<I, my_std::span<T, N>> {
    static_assert(N != my_std::dynamic_extent && I < N);
    using type = T;
  };

  template <std::size_t I, class T, std::size_t N>
  constexpr T& get(my_std::span<T, N> s) noexcept
  {
    static_assert(N != my_std::dynamic_extent && I < N);
    return s[I];
  }

}

#undef CONSTRAINT
#undef EXPECTS

#endif

Constructive criticism is highly appreciated!

\$\endgroup\$
5
\$\begingroup\$

Well, it looks quite nice. But now let's try to find all the corners which can still be improved:

  1. I'm not quite sure why you list a few members of each include you added. But, at least it simplifies checking for extraneous includes, and they are sorted.

  2. Simply restating the code in vaguer words, or otherwise restating the obvious, is an abuse of comments. They just detract from anything relevant.

    Well, at least some of them could be justified as breaking long blocks of declarations and definitions into easier digestible logical chunks.

  3. Conversion to and arithmetic using unsigned types being done using modulo-arithmetic should not be a surprise to any reviewer and/or maintainer. If it is, they lack basic knowledge, and your sources should not be a basic language-primer.

  4. You had extraneous whitespace at the end of some lines. An automatic formatter, or format-checker, either of which can be put in a commit-hook, would have fixed or at least found them.

  5. You use your macro CONSTRAINT seven times, leading to a total saving of \$((40-13)-(15-3)) \times 7 - 71 - 19 = 15 \times 7 - 90 = 15\$ bytes. That's quite a paltry compensation for adding this cognitive burden on any maintainer, and breaking any user-code defining CONSTRAINT before the include. At least the damage is limited due to you undefining it too.

  6. Your use of the macro EXPECTS does not even have that silver lining, as it expanded your code by \$((12-3)-(21-13)) \times 11 + 49 + 16 = 1 \times 11 + 65 = 76\$ bytes. And it leaves me even more puzzled as you should have just used assert() directly, that's exactly what it's for.

  7. You use an extra template-parameter for SFINAE of a function once. While ctors have to do SFINAE there or not at all, functions can avoid any potential extra-cost by using the return-type for that.

  8. If you were actually writing part of the standard library, or had C++20 with it customisation-points, my_size() and my_data() would be pointless. Even though you don't actually need it, I would suggest enabling their use for SFINAE.

  9. You aren't currently optimizing the case of non-dynamic extent. Not too surprising, as you go down to the metall everywhere. Just always delegate to span::span(T*, std::size_t) (at least ultimately), and see everything get magically easier. Yes, when you conditionally remove the backing-field for size, you need to adapt .size().

  10. Unifying the ctors span::span(Container&) and span::span(Container const&) is simplicity itself:

    template <class Container, class = std::enable_if_t<
        !std::is_rvalue_reference_v<Container>
        && previous_constraint>>
    span(Container&& c)
    
  11. Building on the above, you only have one point left interested in whether you have a non-std::array, non-span, container. Thus, you can simplify all the machinery to detect that, unify detection of std::array and span, and inline it all:

    template <class T, template <auto> class TT>
    struct is_template_instantiation : std::false_type {};
    template <template <auto> class TT, auto N>
    struct is_template_instantiation<TT<N>, TT> : std::true_type {};
    
    template <class Container, class = std::enable_if_t<
        !std::is_rvalue_reference_v<Container>
        && !span_detail::is_template_instantiation<Container, span>()
        && !span_detail::is_template_instantiation<Container, std::array>()
        && !std::is_array<Container>(), decltype(
        span_detail::my_size(std::declval<Container&>()), void(),
        span_detail::my_data(std::declval<Container&>()), void())>>
    span(Container&& c)
    : span(span_detail::my_data(c), span_detail::my_size(c))
    {}
    
  12. I suggest adding computed noexcept even where not mandated. Doing so even allows you to unify more members.

\$\endgroup\$
  • \$\begingroup\$ Hi Deduplicator! Thank you for your detailed review! Well, let me find some excuses: the points 2, 3, 9, and 10 are consequences of my trying to align with the standard as much as possible ... And about points 5 and 6: I appreciate your enthusiasm in math! I deliberately did that, not for saving characters. In case I adapt this for C++20, all instances of CONSTRAINT should be replaced by requires and EXPECTS by [[ expects : ... ]]. Thank you again! \$\endgroup\$ – L. F. Apr 22 at 2:24
  • 1
    \$\begingroup\$ @L.F. You are welcome. Regarding aligning with the standard: Remember that "Exposition Only" means that using it simplifies the explanation, reality might differ. \$\endgroup\$ – Deduplicator Apr 22 at 15:11

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.