1.1   Multidimensional array, not array-of-array-of-array-of-array...

The multidimensional array abstraction has been fundamental to numerical computations for over five decades. However, the C/C++ language provides only a one dimensional array abstraction which can be composed into array-of-array-of-array... types. While such types have some similarity to multidimensional arrays they do not provide adequate multidimensional array functionality of this proposal. Two critical functionality differences are (1) multiple dynamic extents and (2) polymorphic mapping of multi-indices to member objects.

1.2   Relationship to P0454 : Wording for a Minimal mdspan

P0454, Wording for a Minimal mdspan, includes a minimal version of the polymorphic multidimensional array reference capability that aligns with span as proposed in P0122.

Assuming acceptance of P0454 our intent is for a subsequent version of this paper to propose extensions to mdspan for layout extensibility and other essential properties.

Note that the array_ref name in this paper is not entirely satisfactory and the following alternatives were brainstormed during prior LEWG reviews.

When P0454 is accepted the name will become mdspan.

1.3   Alternative mechanisms for specifying the domain multi-index space

Two potential mechanisms for specifying the domain multi-index space are possible.

(A) The preferred mechanism is concise and aligns with language syntax for specifying multidimensional array extents. However, the preferred mechanism requires a trivial language change to relax the specification for incomplete array types to support multiple dynamic extents. This trivial language change is proposed in P0332.

using A_type = std::array_ref< int[][8][3] > ;

// standard array traits extracted from data type

static_assert( std::rank<   int[][8][3]     >::value == 3 );
static_assert( std::extent< int[][8][3] , 0 >::value == 0 );
static_assert( std::extent< int[][8][3] , 1 >::value == 8 );
static_assert( std::extent< int[][8][3] , 2 >::value == 3 );

(B) The undesirable mechanism requires an additional extents and dyn property symbols. This mechanism is more verbose and requires the introduction of a magic integral value to denote a dynamic extent.

// array traits given through new array traits types

using A_type std::array_ref< int , std::extents<std::dyn,8,3> > ;

Common Result

The array_ref type resulting from either specification mechanism has the same interface.

int * buffer = /* buffer to span of integers */ ;

A_type A( buffer , N );

// static rank and extents

static_assert( A_type::rank() == 3 );
static_assert( A_type::static_extent(0) = 0 );
static_assert( A_type::static_extent(1) = 8 );
static_assert( A_type::static_extent(2) = 3 );

// runtime extents

assert( A.extent(0) = N );
assert( A.extent(1) = 8 );
assert( A.extent(2) = 3 );

// member access through operator()

assert( & A(0,0,0) == buffer );

2.1   Header <array_ref> synopsis: array_ref and subarray

namespace std {
namespace experimental {

  template< typename DataType , typename ... Properties >
  class array_ref ;

  // return type of subarray free function is an array_ref
  template< typename DataType , typename ... Properties , typename ... SliceSpecifiers >
    // for exposition only:
    detail::subarray_deduction_t< array_ref<DataType,Properties...>,SliceSpecifiers...>
  subarray( array_ref< DataType, Properties ... > const & , SliceSpecifiers ... ) noexcept;

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

The array_ref class maps a multi-index within a multi-index space (the domain) to a reference to an object within a span of objects (the codomain).

The subarray free function generates an array_ref with a domain contained within the input array_ref domain and codomain contained within the input array_ref codomain.

The alias detail::subarray_deduction_t class is not proposed and only appears for exposition. An implementation metafunction of this form is necessary to deduce the specific array_ref return type of the subarray function.

2.2   template class array_ref

namespace std {
namespace experimental {

template <typename DataType, typename... Properties>
class array_ref {
public:
  // domain and codomain types

  using value_type = typename remove_all_extents<DataType>::type ;
  using pointer    = value_type * ;
  using reference  = /* implementation deduces from value_type and Properties... */ ;
  using size_type  = /* implementation deduces from Properties... */ ;
  using layout     = /* implementation deduces from Properties... */ ;

  // Standard constructors, assignments, and destructor

  ~array_ref() noexcept ;

  constexpr array_ref() noexcept;
  constexpr array_ref(array_ref&&) noexcept ;
  constexpr array_ref(array_ref const&) noexcept ;
  array_ref& operator=(array_ref&&) noexcept ;
  array_ref& operator=(array_ref const&) noexcept ;

  // Constructor and assignment for assignables

  template <typename UType, typename ... UProp>
  constexpr array_ref( array_ref<UType, UProp...> const& ) noexcept;

  template <typename UType, typename ... UProp>
  array_ref& operator=( array_ref<UType, UProp...> const& ) noexcept;

  // Wrapping constructors

  template <typename... IntegralExtent>
  explicit constexpr array_ref(pointer, IntegralExtent... ) noexcept;

  explicit constexpr array_ref(pointer, layout const&) noexcept;

  // mapping domain multi-index to access codomain member

  template <typename... IntegralIndex>
  reference operator()(IntegralIndex...) const noexcept;

  template <typename IntegralIndex>
  reference operator[]( IntegralIndex ) const noexcept; // requires rank() == 1

  // observers of domain: [0..extent(0))X[0..extent(1))X...X[0..extent(rank()-1))

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

  static constexpr size_type static_extent(int) noexcept;

  constexpr size_type extent(int) const noexcept;

  constexpr size_type size() const noexcept;

  // observers of the codomain: [data()..data()+span())

  constexpr pointer data() const noexcept;

  constexpr size_type span() const noexcept;

  template <typename... IntegralExtent>
  static constexpr size_type required_span( IntegralExtent ... ) noexcept;

  static constexpr size_type required_span( layout const & ) noexcept;

  // observers of the mapping : domain -> codomain

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

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

  constexpr size_type stride(int) const noexcept;
};

}}

2.3   subarray

The detail::subarray_deduction_t is for exposition only to indicate that the implementation will require a metafunction to deduce the resulting array_ref type from the input array_ref and slice specifiers.

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 [0..extent(ith))

Let the ith member of S be denoted by S[ith].

Requires: U.rank() == sizeof...(SliceSpecifiers). S[ith] is an integral value or an integral range. If S[ith] is an integral range then let begin(S[ith]) be the beginning of the integral range end(S[ith]) be the end of the integral range. If S[ith] is an integral value then let begin(S[ith]) == S[ith] and end(S[ith]) == S[ith]+1. 0 <= begin(S[ith]) <= end(S[ith]) <= A.extent(ith).

Returns: An array_ref 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 SlicedSpecifiers , U( begin(S)... ) refers to the same codomain member refered to by the mapping the zero-index of V , each integral value in S... contracts the corresponding extent of U.

Example:

// A.rank() == 4 and reference is lvalue reference
void foo( array_ref< DataType , Properties ... > const & A )
{
  auto B = subarray( A , make_pair(1,A.extent(0)-1) , 1 , make_pair(2,A.extent(2) , 2 );
  assert( & B(0,0) == A(1,1,2,2) );
  assert( & B(1,0) == A(2,1,2,2) );
  assert( & B(0,1) == A(1,1,3,2) );
}

3.1   Header <array_ref> synopsis for properties

namespace std {
namespace experimental {

  // predefined layout mapping properties
  struct layout_right ;
  struct layout_left ;
  struct layout_stride ;

  template <typename T> struct is_layout ;
  template <typename T> constexpr bool is_layout_v = is_layout<T>::value;

  // extent size_type property
  template< typename T > struct extent_size_type ;

  // bounds checking property
  template< bool Enable >
  struct bounds_check_if ;

  using bounds_check = bounds_check_if< true > ;

  template< typename >
  struct is_array_property /* = std::integral_constant<bool,?> */ ;

  template< typename T >
  using is_array_property_v = is_array_property<T>::value ;

}}

3.2   Layout Mapping

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

class layout_concept /* exposition only */ {
public:

  template< typename ExtentType , ExtentType ... >
  class mapping {
  public:

    // domain types

    using size_type = ExtentType ;

    // constructors, copy, assignment, and destructor

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

    template <typename... IntegralExtent>
    explicit constexpr mapping( IntegralExtent... ) noexcept;

    explicit constexpr mapping( layout_concept const&) noexcept;

    ~mapping() noexcept ;

    // observers of domain: [0..extent(0)) X [0..extent(1)) X ... X [0..extent(rank()-1))

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

    constexpr size_type size() const noexcept;

    constexpr size_type extent(int) const noexcept;

    constexpr size_type static_extent(int) noexcept;

    // observers of the codomain: [0..span())

    constexpr size_type span() const noexcept;

    template <typename... IntegralExtent>
    static constexpr size_type required_span( IntegralExtent ... ) noexcept;

    static constexpr size_type required_span( layout_concept const & ) noexcept;

    // observers of the mapping from domain to codomain

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

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

    constexpr size_type stride(int) const noexcept;

    // mapping domain index to access codomain element

    template <typename... IntegralIndex>
    constexpr size_type operator()(IntegralIndex...) const noexcept;
  };
};

3.3   Property: extent_size_type< integral >

template< typename integral > struct extent_size_type ;

Requires: is_integral< integral >. Specify array_ref::size_type as integral . If unspecified then array_ref::size_type is size_t ; .

3.4   Property: bounds_check_if< bool >

When array_ref Properties... includes bounds_check_if<true> then the mapping operators array_ref::operator() and array_ref::operator[] verify that each index is valid, 0 <= index[ith] < extent(ith). Verification failure shall be reported.

6.1   P0009r0

Original multidimensional array reference paper with motivation, specification, and examples.

6.2   P0009r1

Revised with renaming from view to array_ref and allow unbounded rank through variadic arguments.

6.3   P0009r2

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

6.4   P0009r3

Oulu-2016 LEWG strawpoll: Move iterator from this paper to a subsequent paper.

Oulu-2016 LEWG feedback: http://wiki.edg.com/bin/view/Wg21oulu/P0009

• Array extents specification mechanism options are either-or, not both.
• List potential names for LEWG and/or LWG todo bikeshedding.
• Clearly & concisely note difference between multidimensional array versus language's array-of-array-of-array...
• Actual specification of reference type (and others), not "typically is" vagueness.
• Future directions / extensibility section regarding Properties...

The domain space specification preferred and undesirable mechanisms changed from accepting both to accepting only one.

Tighten up domain, codomain, and domain -> codomain mapping specifications.

Consistently use extent and extents for the multidimensional index space.

6.5   Future reversion

Align with and extend layout properties of P0454, Wording for Minimal mdspan.

7.1   P0454 : Wording for a Minimal mdspan

The mdspan is a minimal version of the multidimensional array view capability.

7.2   P0122 : span: bounds-safe views for sequences of objects

The array_ref codomain concept of span is well-aligned with this paper.

7.3   P0367 : Accessors

The P0367 Accessors proposal includes polymorphic mechanisms for accessing the memory an object or span of objects. The Properties... extension point in this proposal is intended to include such memroy access properties.