1.1   P0009r0 : Pre 2015-10-Kona Mailing

Original non-owning multidimensional array reference (view) paper with motivation, specification, and examples.

1.2   P0009r1 : Pre 2016-02-Jacksonville Mailing

LEWG review at 2015-10-Kona.

LEWG Poll: What should this feature be called?

LEWG Poll: Do we want 0-length static extents?

LEWG POLL: Do we want the language to support syntaxes like X[3][][][5]?

LEWG POLL: Do we want the variadic property list in template args (either raw or in properties<>)? Note there is no precedence for this in the library.

LEWG POLL: Do we want the per-view bounds-checking knob?

Changes from P0009r0:

• Renamed view to array_ref.
• How are users allowed to add properties? Needs elaboration in paper.
• view<int[][][]>::layout should be named.

• Rename is_regular (possibly to is_affine) to avoid overloading the

  term with the Regular concept.

• Make static span(), operator(), constructor, etc variadic.
• Demonstrate the need for improper access in the paper.
• In operator(), take integral types by value.

1.3   P0009r2 : Pre 2016-06-Oulu Mailing

LEWG review at 2016-02-Jacksonville.

Changes from P0009r1:

• Adding details for extensibility of layout mapping.
• Move motivation, examples, and relaxed incomplete array type proposal to separate papers. - P0331: Motivation and Examples for Polymorphic Multidimensional Array. - P0332: Relaxed Incomplete Multidimensional Array Type Declaration.

1.4   P0009r3 : Post 2016-06-Oulu Mailing

LEWG review at 2016-06-Oulu

LEWG did not like the name array_ref, and suggested the following alternatives: - sci_span - numeric_span - multidimensional_span - multidim_span - mdspan - md_span - vla_span - multispan - multi_span

LEWG Poll: Are member begin()/end() still good?

LEWG Poll: Want this proposal to provide range-producing functions outside array_ref?

LEWG Poll: Want a separate proposal to explore iteration design space?

Changes from P0009r2:

• Removed iterator support; a future paper will be written on the subject.
• Noted difference between multidimensional array versus language's array-of-array-of-array...
• Clearly describe requirements for the embedded type aliases (element_type, reference, etc).
• Expanded description of how the variadic properties list would work.
• Stopped allowing array_ref<T[N]> in addition to array_ref<extents<N>>.
• Clarified domain, codomain, and domain -> codomain mapping specifications.
• Consistently use extent and extents for the multidimensional index space.

1.5   P0009r4 : Pre 2017-11-Albuquerque Mailing

LEWG review at 2017-03-Kona meeting

LEWG review of P0546r1 at 2017-03-Kona meeting

LEWG Poll: Should we have a single template that covers both single and multi-dimensional spans?

Changes from P0009r3:

• Align with P0122r5 ``span` proposal <https://wg21.link/P0122r5>`_.
• Rename to mdspan, multidimensional span, to align with span.
• Move preferred array extents mechanism to appendix.
• Expose codomain as a span.
• Add layout mapping concept.

1.6   P0009r5 : Pre 2018-03-Jacksonville Mailing

LEWG review of P0009r4 at 2017-11-Albuquerque meeting

LEWG Poll: We should be able to index with span<int type[N]> (in addition to array).

Against comment - there is not a proven needs for this feature.

LEWG Poll: We should be able to index with 1d mdspan.

LEWG Poll: We should put the requirement on "rank() <= N" back to "rank() == N".

Unanimous consent

LEWG Poll: With the editorial changes from small group, plus the above polls, forward this to LWG for Fundamentals v3.

Unanimous consent

Changes from P0009r4:

• Removed nullptr constructor.
• Added constexpr to indexing operator.
• Indexing operator requires that rank() == sizeof...(indices).
• Fixed typos in examples and moved them to appendix.
• Converted note on how extentions to access properties may cause reference to be a proxy type to an "see below" to make it normative.

1.7   P0009r6 : Pre 2018-06-Rapperswil Mailing

P0009r5 was not taken up at 2018-03-Jacksonville meeting. Related LEWG review of P0900 at 2018-03-Jacksonville meeting

LEWG Poll: We want the ability to customize the access to elements of span (ability to restrict, etc):

span<T, N, Accessor=...>

LEWG Poll: We want the customization of basic_mdspan to be two concepts Mapper and Accessor (akin to Allocator design).

basic_mdspan<T, Extents, Mapper, Accessor>
mdspan<T, N...>

LEWG Poll: We want the customization of basic_mdspan to be an arbitrary (and potentially user-extensible) list of properties.

basic_mdspan<T, Extents, Properties...>

Changes from P0009r5 due to related LEWG reviews:

• Replaced variadic property list with extents, layout mapping, and accessor properties.
• Incorporated P0454r1. - Added accessor policy concept. - Renamed mdspan to basic_mdspan. - Added a mdspan alias to basic_mdspan.

3.1   Add to same section and header as span

namespace std {

  inline constexpr ptrdiff_t dynamic_extent = -1; // as per span

  // Multidimensional extents:
  template< ptrdiff_t ... StaticExtents >
  class extents ;

  template< ptrdiff_t ... LHS , ptrdiff_t ... RHS >
  constexpr bool operator == ( extents<LHS...> const & lhs , extents<RHS...> const & rhs ) ;

  template< ptrdiff_t ... LHS , ptrdiff_t ... RHS >
  constexpr bool operator != ( extents<LHS...> const & lhs , extents<RHS...> const & rhs ) ;

  // Layout mapping of multidimensional extents:
  class layout_right ;
  class layout_left ;
  class layout_stride ;

  // Multidimensional span:
  template <typename ElementType,
            typename Extents,
            typename LayoutPolicy = layout_right,
            typename AccessorPolicy = accessor_basic>
  class basic_mdspan;

  template <class T, ptrdiff_t... Extents>
  using mdspan = basic_mdspan<T, extents<Extents...>>;

  // return type of subspan free function is an mdspan
  template< typename ElementType , typename Extents, typename LayoutPolicy ,
            typename AccessorPolicy , typename ... SliceSpecifiers >
    // for exposition only:
    detail::subspan_deduction_t< basic_mdspan<ElementType, Properties...>,SliceSpecifiers...>
  subspan( basic_mdspan< ElementType, Extents , LayoutPolicy , AccessorPolicy > const & , SliceSpecifiers ... ) noexcept;

  // tag supporting subspan
  struct all_type {};
  inline constexpr all_type all = all_type{};
}

The basic_mdspan class maps a multi-index within a multi-index domain to a reference an element the codomain span.

The subspan free function generates an basic_mdspan with a domain contained within the input basic_mdspan domain and codomain contained within the input basic_mdspan codomain.

The detail::subspan_deduction_t template class is not proposed and appears for exposition only. An implementation metafunction of this form is necessary to deduce the specific basic_mdspan return type of the subspan function.

3.2   Class template basic_mdspan

namespace std {

template< typename ElementType , typename Extents , typename LayoutPolicy , typename AccessorPolicy >
class basic_mdspan {
public:
  // Domain and codomain types

  using layout   = LayoutPolicy;
  using mapping  = typename layout::mapping<Extents>;
  using accessor = typename AccessorPolicy::accessor<ElementType>;

  using element_type    = typename accessor::value_type;
  using value_type      = remove_cv_t<element_type>;
  using index_type      = ptrdiff_t ;
  using difference_type = ptrdiff_t ;
  using pointer         = typename accessor::pointer;
  using reference       = typename accessor::reference;

  // Standard constructors, assignments, and destructor

  ~basic_mdspan() noexcept ;

  constexpr basic_mdspan() noexcept ;
  constexpr basic_mdspan(basic_mdspan&&) noexcept = default ;
  constexpr basic_mdspan(basic_mdspan const&) noexcept = default ;
  basic_mdspan& operator=(basic_mdspan&&) noexcept = default ;
  basic_mdspan& operator=(basic_mdspan const&) noexcept = default ;

  // Constructor and assignment for assignable basic_mdspan

  template <typename UT, typename UExt, typename ULayPol, typename UAccPol>
  constexpr basic_mdspan(const basic_mdspan<UT, UExt, ULayPol, UAccPol>& other) noexcept;

  template <typename UType, typename ... UProp>
  constexpr basic_mdspan& operator=(const basic_mdspan<UT, UExt, ULayPol, UAccPol>& other) noexcept;

  // Wrapping constructors

  template< class ... IndexType >
  explicit constexpr basic_mdspan(pointer, IndexType ... DynamicExtents ) noexcept;

  template< class ... IndexType >
  explicit constexpr basic_mdspan(span<element_type>, IndexType ... DynamicExtents ) noexcept;

  template< class IndexType , size_t N >
  explicit constexpr basic_mdspan(pointer, array<IndexType,N> const & DynamicExtents ) noexcept ;

  template< class IndexType , size_t N >
  explicit constexpr basic_mdspan(span<element_type>, array<IndexType,N> const & DynamicExtents ) noexcept ;

  // Mapping domain multi-index to access codomain element

  constexpr reference operator[]( index_type ) const noexcept;

  template< class ... IndexType >
  constexpr reference operator()( IndexType ... indices ) const noexcept;

  template< class IndexType , size_t N >
  constexpr reference operator()( array<IndexType,N> const & indices ) const noexcept;

  // Observers of the domain multi-index space

  static constexpr int rank() noexecept ;
  static constexpr int rank_dynamic() noexecept ;

  static constexpr index_type static_extent(int) noexecept ;

  constexpr index_type extent(int) const noexecept ;

  constexpr index_type size() const noexecept ;

  // Observers of the codomain:

  constexpr span<element_type> span() const noexecept ;

  template< class ... IndexType >
  static constexpr index_type required_span_size( IndexType ... DynamicExtents );

  template< class ... IndexType , size_t N >
  static constexpr index_type required_span_size( array<IndexType,N> const & DynamicExtents );

  // Observers of the mapping : domain -> codomain

  static constexpr bool is_always_unique     = mapping::is_always_unique ;
  static constexpr bool is_always_contiguous = mapping::is_always_contiguous ;
  static constexpr bool is_always_strided    = mapping::is_always_strided ;

  constexpr bool is_unique() const noexcept ;
  constexpr bool is_contiguous() const noexcept ;
  constexpr bool is_strided() const noexcept ;

  constexpr index_type stride(int) const ;

private:
  // exposition only
  accesor      access;
  mapping      map;
  pointer_type ptr;
};

}

3.3   Class template extents

An extents objects defines the lengths of the dimensions of an mdspan.

namespace std {

template< ptrdiff_t ... StaticExtents >
class extents {
public:

  using index_type = ptrdiff_t ;

  // Constructors/assignment/destructor

  ~extents() = default ;
  constexpr extents();
  constexpr extents(extents const &) = default ;
  constexpr extents(extents &&) = default ;
  extents & operator = (extents const &) noexcept = default ;
  extents & operator = (extents &&) noexcept = default ;

  template< class ... IndexType >
  constexpr extents( IndexType ... DynamicExtents ) noexcept ;

  // Observers of the index space domain:

  static constexpr int rank() noexcept ;
  static constexpr int rank_dynamic() noexcept ;

  static constexpr index_type static_extent(int) noexcept ;

  constexpr index_type extent(int) const noexcept ;
};

}

The multi-index domain space is the Cartesian product of the extents: [0..extent(0)) X [0..extent(1)) X ... X [0..extent(rank() - 1)). Each extent may be statically (at compile time) or dynamically (at runtime) specified.

template< ptrdiff_t StaticExtents... >

Requires: 0 <= StaticExtent or dynamic_extent == StaticExtent

static constexpr int rank();

Returns: Rank of the multi-index domain, sizeof...(StaticExtents).

static constexpr int rank_dynamic();

Returns: number of StaticExtents... that are dynamic_extent.

static constexpr index_type static_extent(int r);

Requires: 0 <= r.

Returns: If 0 <= r < rank() the statically specified extent. A statically declared extent of dynamic_extent denotes that the extent is dynamic. If rank() <= r then static_extent(r) == 1.

constexpr index_type extent(int r) const ;

Requires: 0 <= r.

Returns: If 0 <= r < rank() the extent of coordinate r. If rank() <= r then extent(r) == 1.

Returns: lhs.rank() == rhs.rank() and lhs.extent(r) == rhs.extent(r) for 0 <= r < lhs.rank().

Returns: ! ( lhs == rhs )

3.4   subspan

template <typename ElementType, typename Extents,
          typename LayoutPolicy, typename AccessorPolicy>
// for exposition only:
detail::subspan_deduction_t<basic_mdspan<ElementType, Extents, LayoutPolicy, AccessorPolicy>, SliceSpecifiers...>
subspan(const basic_mdspan<ElementType, Extents, LayoutPolicy, AccessorPolicy>& U , SliceSpecifiers... slices) noexcept;

The detail::subspan_deduction_t is for exposition only to indicate that the implementation is required to deduce the resulting basic_mdspan type from U and slices....

Let the ith element of slices... be denoted by slices[ith].

Let an integral range be denoted by any of the following.

• an initializer_list<T> of integral type T and size 2
• a pair<T,T> of integral type T
• a tuple<T,T> of integral type T
• an array<T,2> of integral type T
• all to denote the range [0 .. U.extent(ith))

If slices[ith] is an integral range then let begin(slices[ith]) be the beginning of the integral range end(slices[ith]) be the end of the integral range. If slices[ith] is an integral value then let begin(slices[ith]) == slices[ith] and end(slices[ith]) == slices[ith]+1.

Requires:

• U.rank() == sizeof...(slices).
• Each element of the slices... pack is either an integral range or an integral value.
• 0 <= begin(slices[ith]) <= end(slices[ith]) <= U.extent(ith).

Returns: A basic_mdspan V with a domain contained within the domain of U , codomain contained within the codomain of U , V.rank() is the number of integral ranges in slices... , U( begin(slices)... ) refers to the same codomain element refered to by the mapping the zero-index of V , each integral value in slices... contracts the corresponding extent of U.

[Note: An illustrative example

// given U.rank() == 4
void foo( basic_mdspan< ElementType , Extents , LayoutPolicy > const & U )
{
  auto V = subspan( U , make_pair(1,U.extent(0)-1) , 1 , make_pair(2,U.extent(2)-2 );
  assert( V.extent(0) == U.extent(0) - 2 );
  assert( V.extent(1) == U.extent(2) - 2 );
  assert( & V(0,0) == U(1,1,2,2) );
  assert( & V(1,0) == U(2,1,2,2) );
  assert( & V(0,1) == U(1,1,3,2) );
}

--end note]

3.5   Layout Policy Requirements

A basic_mdspan maps multi-indices from the domain to reference elements in the codomain by composing a layout mapping with a span of elements. The layout mapping is an extension point such that an basic_mdspan may be instantiated with non-standard layout mappings.

class layout_property /* exposition only */ {
public:

  template< ptrdiff_t ... StaticExtents >
  class mapping {
  public:

    // Domain types

    using index_type = ptrdiff_t ;

    // Constructors, copy, assignment, and destructor

    ~mapping() noexcept = default ;
    constexpr mapping() noexcept = default ;
    constexpr mapping(mapping const&) noexcept = default ;
    mapping& operator=(mapping const&) noexcept = default ;

    // Observers of domain

    static constexpr int rank() noexcept;
    static constexpr int rank_dynamic() noexcept;

    static constexpr index_type static_extent(int) noexcept;

    constexpr index_type extent(int) const noexcept;

    // Observers of the codomain: [0..required_span_size())

    constexpr index_type required_span_size() const noexcept;

    // Observers of the mapping from domain to codomain

    static constexpr bool is_always_unique     = /* unspecified */ ;
    static constexpr bool is_always_contiguous = /* unspecified */ ;
    static constexpr bool is_always_strided    = /* unspecified */ ;

    constexpr bool is_unique() const noexcept;
    constexpr bool is_contiguous() const noexcept;
    constexpr bool is_strided() noexcept;

    constexpr index_type stride(int) const noexcept;

    // Mapping domain index to access codomain element

    template< class ... IndexType >
    constexpr index_type operator()( IndexType ... indices ) const noexcept;
  };
};

3.6   Accessor Policy Requirements

An accessor policy is a class that contains an accessor, a nested template class.

An accessor takes a pointer to an array and an index and returns a reference to the element of the array at the given index. basic_mdspan is parameterized in terms of accessor.

An accessor fulfills the DefaultConstructible and CopyAssignable requirements.

In Table �:

• AP denotes an accessor policy.
• A denotes an accessor.
• a denotes a value of type A.
• p denotes a pointer of type T.
• i denotes an integer.

3.7   Accessor Policies

struct accessor_basic
{
  template <typename T>
  struct accessor
  {
    using pointer      = T*;
    using reference    = T&;

    constexpr reference operator()(pointer p, ptrdiff_t i) const noexcept;
  };
};

template <typename Index>
constexpr reference operator()(pointer p, Index i) const noexcept;

Effects: Equivalent to return p[i];