Document number: N3794
Project: Programming Language C++, Library Working Group
Date: 2013-10-10
Reply-to: Daryle Walker <darylew at gmail dot com>

Proposal to Add Multi-Dimensional Support to std::array

I. Table of Contents

  1. Table of Contents
  2. Introduction
  3. Motivation and Scope
  4. Impact on the Standard
  5. Design Decisions
  6. Technical Specifications
  7. Acknowledgments
  8. References

II. Introduction

The std::array class template adapts array types to standard library classes. But the adaptation is only for the outermost level; the inner dimensions of a multidimensional array type are not considered. This proposal is to change std::array to take multiple dimensions as variadic template arguments.

III. Motivation and Scope

When reading up on the variadic template feature, I made a multidimensional variant of std::array as an exercise. After making the single-extent case compatible with std::array, I realized it is better to propose a change in std::array instead of creating a near-identical class template. The exercise code, at <https://github.com/CTMacUser/ArrayMD>, could be considered as a reference implementation and test suite.

I later found out that a multidimensional array class template was one of the examples given in the original variadic template proposal.

With constructions that can express array types and array subscript usage in comma-separated lists, array entities may be invoked during variadic template- and function-argument processing.

IV. Impact on the Standard

The proposal adds two class templates (and corresponding type-alias templates), three function templates, and several members to an existing class template. It modifies descriptions of std::array in the sequence container requirements. And it modifies the relational operator function templates to take mixed element types. The implementation should work with current language features.

V. Design Decisions

I adapted std::array for multidimensional arrays by making the inner array object a built-in multidimensional array type. Since built-in types are used, only the first level of access via operator []() has to be a function instead of a built-in operation. Similar multidimensional container libraries where the array class template consists of nested instantiations of itself have the disadvantages of possible padding (making the elements noncontiguous) and of working in the wrong units (the largest sub-array type instead of the user's original element type).

The implementation is mostly as straight forward as the current std::array, so there is not much effort needed from implementers.

VI. Technical Specifications

The changes are based off C++ Working Draft Standard N3691. The section numbers for new sections have letters as place-holders; the final numbers, plus moving existing section numbers to fit, are to be determined later.

In section 20.11.2 [meta.type.synop], change the subsection introducing array modifications:

// 20.11.7.4, array modifications:
template <class T> struct remove_extent;
template <class T> struct remove_all_extents;
template <class T, size_t I> struct remove_some_extents;
template <class T, size_t... N> struct append_extents;

template <class T>
  using remove_extent_t = typename remove_extent<T>::type;
template <class T>
  using remove_all_extents_t = typename remove_all_extents<T>::type;
template <class T, size_t I>
  using remove_some_extents_t = typename remove_some_extents<T, I>::type;
template <class T, size_t... N>
  using append_extents_t = typename append_extents<T, N...>::type;

In section 20.11.7.4 [meta.trans.arr], add a third and fourth row to Table 55:

Addition to: Table 55 — Array modifications
Template Comments 
template <class T, size_t I>
struct remove_some_extents;
 If I is zero, then the member typedef type shall be T. Otherwise, the member typedef type shall be the same as applying remove_extent I times. [Note: When T is either a non-array type or an array type with an extent count at most I, this class template acts like remove_all_extents. —end note] 
template <class T, size_t... N>
struct append_extents;
 If N is an empty parameter pack, then the member typedef type shall be T. Otherwise, let X be the first entry of N, Y be a (possibly empty) parameter pack representing the remainder of N, and U be an alias to typename append_extents<T, Y...>::type. Then the member typedef type shall alias U[X] when X is non-zero, else it shall alias U[]. [Note: Since an array of unknown bound is not permitted to be an array element type (8.3.4), only the first (i.e. left-most) entry of N may be zero. —end note]

and add a third example:

-3- [Example

// the following assertions hold:
assert((is_same<remove_some_extents<int, 0>::type, int>::value));
assert((is_same<remove_some_extents<int, 1>::type, int>::value));
assert((is_same<remove_some_extents<int[2], 0>::type, int[2]>::value));
assert((is_same<remove_some_extents<int[2], 1>::type, int>::value));
assert((is_same<remove_some_extents<int[2], 2>::type, int>::value));
assert((is_same<remove_some_extents<int[2][3], 0>::type, int[2][3]>::value));
assert((is_same<remove_some_extents<int[2][3], 1>::type, int[3]>::value));
assert((is_same<remove_some_extents<int[2][3], 2>::type, int>::value));
assert((is_same<remove_some_extents<int[][3], 0>::type, int[][3]>::value));
assert((is_same<remove_some_extents<int[][3], 1>::type, int[3]>::value));
assert((is_same<remove_some_extents<int[][3], 2>::type, int>::value));
assert((is_same<remove_some_extents<int[][3], 3>::type, int>::value));

—end example]

In section 23.2.3 [sequence.reqmts], modify the last column for the last two rows of Table 101:

Modification to: Table 101 — Optional sequence container operations (continued)
Expression Return type Operational semantics Container
a[n] reference; const_reference for constant a *(a.begin() + n) basic_string, array (with one extent), deque, dynarray, vector
a.at(n) reference; const_reference for constant a *(a.begin() + n) basic_string, array (with one extent), deque, dynarray, vector

and modify the paragraph that follows that table:

-17- The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size(). For instantiations of array with an extent count besides one, there are modifications (23.3.2.D) to the return types and the operational semantics of a[n] and a.at().

In section 23.3.1 [sequences.general], modify the "Header <array> synopsis":

#include <initializer_list>
#include <type_traits>

namespace std {
  template <class T, size_t... N > struct array;
  template <class T, class U, size_t... N>
    bool operator==(const array<T,N...>& x, const array<TU,N...>& y);
  template <class T, class U, size_t... N>
    bool operator!=(const array<T,N...>& x, const array<TU,N...>& y);
  template <class T, class U, size_t... N>
    bool operator<(const array<T,N...>& x, const array<TU,N...>& y);
  template <class T, class U, size_t... N>
    bool operator>(const array<T,N...>& x, const array<TU,N...>& y);
  template <class T, class U, size_t... N>
    bool operator<=(const array<T,N...>& x, const array<TU,N...>& y);
  template <class T, class U, size_t... N>
    bool operator>=(const array<T,N...>& x, const array<TU,N...>& y);
  template <class T, size_t... N >
    void swap(array<T,N...>& x, array<T,N...>& y) noexcept(noexcept(x.swap(y)));

  template <class T> class tuple_size;
  template <size_t I, class T> class tuple_element;
  template <class T, size_t... N>
    struct tuple_size<array<T, N...> >;
  template <size_t I, class T, size_t... N>
    struct tuple_element<I, array<T, N...> >;
  template <size_t I, class T, size_t... N>
    constexpr T& get(array<T, N...>&) noexcept;
  template <size_t I, class T, size_t... N>
    constexpr T&& get(array<T, N...>&&) noexcept;
  template <size_t I, class T, size_t... N>
    constexpr const T& get(const array<T, N...>&) noexcept;

  template <class T, size_t... N, class... Args>
    constexpr array<T, N...> make_array(Args&&...);
  template <class... Args>
    constexpr array<common_type_t<Args...>, sizeof...(Args)>
    make_auto_array(Args&&...);
  template <class TO, size_t... NO, class TI, size_t... NI>
    constexpr array<TO, NO...> reshape_array(const array<TI, NI...>&);
}

Modify section 23.3.2.1 [array.overview]:

-1- The header <array> defines a class template for storing fixed-size sequences of objects. An array supports random access iterators. An instance of array<T, N...> stores NP elements of type T, where P is the product of the entries from the pack expansion N, so that size() == NP is an invariant. The elements of an array are stored contiguously, meaning that if a is an array<T, N...> then it obeys the identity &((T*)&a)[n] == &((T*)&a)[0] + n for all 0 <= n < NP.

-2- An array is an aggregate (8.5.1) that can be initialized with the syntax
array<T, NN0, ..., Nsizeof...(N)-1> a = { initializer-list };
where initializer-list is a comma-separated (and possibly braced-partitioned) list of up to NP elements whose types are convertible to T, and P is the product of the entries N0 through Nsizeof...(N)-1 from the pack expansion N. [Note: P is 1 when N is empty. —end note]

-3- An array satisfies all of the requirements of a container and of a reversible container (23.2), except that a default constructed array object is not empty and that swap does not have constant complexity. An array satisfies some of the requirements of a sequence container (23.2.3). Descriptions are provided here only for operations on array that are not described in one of these tables and for operations where there is additional semantic information.

namespace std {
  template <class T, size_t ...N >
  struct array {
    // types:
    typedef append_extents_t<T, N...>         type;
    typedef T&                                reference;
    typedef const T&                          const_reference;
    typedef implementation-defined            iterator;
    typedef implementation-defined            const_iterator;
    typedef size_t                            size_type;
    typedef ptrdiff_t                         difference_type;
    typedef T                                 value_type;
    typedef T*                                pointer;
    typedef const T*                          const_pointer;
    typedef reverse_iterator<iterator>        reverse_iterator;
    typedef reverse_iterator<const_iterator>  const_reverse_iterator;
    typedef remove_extent_t<type>             dereference;  // iff sizeof...(N) > 0

    Tconditional_t<!sizeof...(N) ||
     extent<type>::value, type,
     aligned_storage_t<sizeof(T), alignof(T)>>       elems[N];  // exposition only

    static constexpr size_type
       value_count = sizeof...(N) ? extent<type>::value * sizeof(dereference) / sizeof(value_type) : 1,
      extent_count = sizeof...(N),
         extents[] = { N... };  // iff sizeof...(N) > 0

    // no explicit construct/copy/destroy for aggregate type

    void fill(const T& u);
    void swap(array&) noexcept(noexcept(swap(declval<T&>(), declval<T&>())));
    template <class F> void apply(F&& f);
    template <class F> void apply(F&& f) const;
    template <class F> void capply(F&& f) const;

    // iterators:
    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    iterator end() noexcept;
    const_iterator end() const noexcept;

    reverse_iterator rbegin() noexcept;
    const_reverse_iterator rbegin() const noexcept;
    reverse_iterator rend() noexcept;
    const_reverse_iterator rend() const noexcept;

    const_iterator cbegin() const noexcept;
    const_iterator cend() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    const_reverse_iterator crend() const noexcept;

    // capacity:
    constexpr size_type size() const noexcept;
    constexpr size_type max_size() const noexcept;
    constexpr bool empty() const noexcept;

    // element access:
    referencedereference& operator[](size_type n);  // iff sizeof...(N) > 0
    constexpr const_referenceconst dereference& operator[](size_type n) const;  // iff sizeof...(N) > 0
    reference at(size_type n);
    constexpr const_reference at(size_type n) const;
    template <class ...SizeType> auto operator()(const SizeType&... n)
     -> remove_some_extents_t<type, sizeof...(SizeType)>&;
    template <class ...SizeType> constexpr auto operator()(const SizeType&... n) const
     -> const remove_some_extents_t<type, sizeof...(SizeType)>&;
    template <class ...SizeType> auto at(const SizeType&... n)
     -> remove_some_extents_t<type, sizeof...(SizeType)>&;
    template <class ...SizeType> constexpr auto at(const SizeType&... n) const
     -> const remove_some_extents_t<type, sizeof...(SizeType)>&;
    reference operator[](initializer_list<size_type> i);
    constexpr const_reference operator[](initializer_list<size_type> i) const;
    reference operator()(initializer_list<size_type> i);
    constexpr const_reference operator()(initializer_list<size_type> i) const;
    reference at(initializer_list<size_type> i);
    constexpr const_reference at(initializer_list<size_type> i) const;
    reference front();
    constexpr const_reference front() const;
    reference back();
    constexpr const_reference back() const;

    T *pointer data() noexcept;
    const T *const_pointer data() const noexcept;
  };
}

-4- [ Note: The member variable elems is shown for exposition only, to emphasize that array is a class aggregate. The name elems is not part of array’s interface. —end note ]

No modifications for section 23.3.2.2 [array.cons]:

-1- The conditions for an aggregate (8.5.1) shall be met. Class array relies on the implicitly-declared special member functions (12.1, 12.4, and 12.8) to conform to the container requirements table in 23.2. In addition to the requirements specified in the container requirements table, the implicit move constructor and move assignment operator for array require that T be MoveConstructible or MoveAssignable, respectively.

Modify section 23.3.2.3 [array.special]:

template <class T, size_t... N> void swap(array<T,N...>& x, array<T,N...>& y) noexcept(noexcept(x.swap(y)));

-1- Effects:
x.swap(y);

-2- Complexity: linear in Narray<T,N...>::value_count.

Add new section 23.3.2.A [array.create], titled "array creation":

template <class T, size_t... N, class... Args> constexpr array<T, N...> make_array(Args&&... args);

-1- Requires: sizeof...(Args) <= array<T, N...>::value_count. When T is not DefaultConstructible, sizeof...(Args) == array<T, N...>::value_count. Each type within Args is explicitly convertible to T.

-2- Returns: an object that is

template <class... Args> constexpr array<common_type_t<Args...>, sizeof...(Args)> make_auto_array(Args&&... args);

-3- Requires: sizeof...(Args) > 0. common_type_t<Args...> is well-formed.

-4- Returns: make_array<common_type_t<Args...>, sizeof...(Args)>( forward<Args>(args)... ).

template <class TO, size_t... NO, class TI, size_t... NI> constexpr array<TO, NO...> reshape_array(const array<TI, NI...>& x);

-5- Requires: TO is DefaultConstructible. TI is explicitly convertible to TO.

-6- Returns: an object y such that each *(y.begin() + d) is equivalent to static_cast<TO>(*(x.begin() + d)) for 0 <= d < min(x.size(), y.size()) and the trailing elements of y, if any, are value-initialized.

Modify section 23.3.2.4 [array.size]:

template <class T, size_t N> constexpr size_type array<T,N>::size() const noexcept;

-1- Returns: Nvalue_count

Modify section 23.3.2.5 [array.data]:

T *pointer data() noexcept;
const T *const_pointer data() const noexcept;

-1- Returns: When extent_count == 0, addressof(elems), otherwise the address of the first (possibly nested) element of T in elems.

Modify section 23.3.2.6 [array.fill]:

void fill(const T& u);

-1- Effects: fill_n(begin(), Nvalue_count, u)

No modifications for section 23.3.2.7 [array.swap]:

void swap(array& y) noexcept(noexcept(swap(declval<T&>(), declval<T&>())));

-1- Effects: swap_ranges(begin(), end(), y.begin())

-2- Throws: Nothing unless one of the element-wise swap calls throws an exception.

-3- Note: Unlike the swap function for other containers, array::swap takes linear time, may exit via an exception, and does not cause iterators to become associated with the other container.

Add new section 23.3.2.B [array.apply]:

template <class F> void apply(F&& f);
template <class F> void apply(F&& f) const;
template <class F> void capply(F&& f) const;

-1- Requires: f is compatible with function<void(cv T&, size_type, ..., size_type)>, where cv is the cv-qualification of *this and the number of trailing size_type arguments is extent_count.

-2- Effects: f is called once for each element with the following constraints:

-3- Throws: Nothing unless an application call throws an exception.

Author's Note: Element traversal order should be the in-memory order or some other order that minimizes cache misses.

Add new section 23.3.2.C [array.iter], titled "array iteration":

-1- The beginning value of forward iteration points to the element at the address returned by data(). The past-the-end value corresponds to data() + value_count. Propagation of forward iteration follows the (nested) row-wise storage order (8.3.4).

Author's Note: The above section explicitly defines the intuitive order elements are linearly visited when the array object is multidimensional.

Add new section 23.3.2.D [array.access], titled "Element access":

dereference& operator[](size_type n);
constexpr const dereference& operator[](size_type n) const;

-1- Requires: sizeof...(N) > 0 and n < extents[0].

-2- Returns: elems[n].

-3- Throws: Nothing.

template <class ...SizeType> auto operator()(const SizeType&... n)
  -> remove_some_extents_t<type, sizeof...(SizeType)>&;
template <class ...SizeType> constexpr auto operator()(const SizeType&... n) const
  -> const remove_some_extents_t<type, sizeof...(SizeType)>&;

-4- Requires: sizeof...(SizeType) <= extent_count. Each entry in the pack expansion SizeType has to have an implicit conversion to size_type. Each entry in the pack expansion n, in order, needs to be less than the corresponding value in extents.

-5- Returns: elems followed by sizeof...(n) calls of the built-in subscript operator, with each operator using an entry from the pack expansion n, in order, as an index.

-6- Throws: Nothing unless a conversion from an entry of the pack expansion n to a size_type value throws an exception.

-7- Remarks: If any of the types in the pack expansion SizeType cannot be implicitly converted to size_type, or if sizeof...(SizeType) > extent_count, then that function shall not participate in overload resolution.

reference operator[](initializer_list<size_type> i);
constexpr const_reference operator[](initializer_list<size_type> i) const;
reference operator()(initializer_list<size_type> i);
constexpr const_reference operator()(initializer_list<size_type> i) const;

-8- Requires: i.size() == extent_count. For 0 <= d < extent_count, *(i.begin() + d) < extents[d].

-9- Returns: operator()(i0, ..., iextent_count-1), where the ik are the elements of i, in order.

-10- Throws: Nothing.

template <class ...SizeType> auto at(const SizeType&... n)
  -> remove_some_extents_t<type, sizeof...(SizeType)>&;
template <class ...SizeType> constexpr auto at(const SizeType&... n) const
  -> const remove_some_extents_t<type, sizeof...(SizeType)>&;
reference at(initializer_list<size_type> i);
constexpr const_reference at(initializer_list<size_type> i) const;

-11- Requires: the same requirements as the corresponding version of operator()().

-12- Returns: operator()( X ), where X is the argument list at() received.

-13- Throws: Nothing unless: a conversion from an entry of the pack expansion n to a size_type value throws an exception; a particular index is equal or greater than its corresponding entry in extents, in which out_of_range is thrown; or i.size() != extent_count, in which length_error is thrown.

-14- Remarks: If any of the types in the pack expansion SizeType cannot be implicitly converted to size_type, or if sizeof...(SizeType) > extent_count, then that function shall not participate in overload resolution.

Author's Note: The contained (array) object, elems, can be directly referenced by calling operator()(), at(), or the initializer_list overload of operator[]() with no indexes.

Add new section 23.3.2.E [array.extents], titled "Zero extent arrays":

-1- array shall provide support for the special case of N being an empty pack expansion.

-2- In the case that sizeof...(N) == 0, the dereference and extents members are not provided. Neither are the overloads of operator[]() that take one size_type parameter provided. It is implementation-defined if the overloads of operator()() and at() that do not take an initializer_list are replaced with equivalent non-template members that take zero parameters.

Modify section 23.3.2.8 [array.zero]

-1- array shall provide support for the special case Nvalue_count == 0. [Note: Such array instantiations are made by using at least one extent and setting the first extent to zero. They have the same size and alignment specifications as instantiations with value_count == 1. They are always DefaultConstructible, even when T is not. —end note]

-2- In the case that Nvalue_count == 0, the values of begin() ==and end() == unique valueare unspecified but they shall be identical. The return value of data() is unspecified.

-3- The effect of calling front() or back() for a zero-sized array is undefined.

-4- Member function swap() shall have a noexcept-specification which is equivalent to noexcept(true).

Modify section 23.3.2.9 [array.tuple]

tuple_size<array<T, N...> >::value

-1- Return type: integral constant expression.

-2- Value: Narray<T, N...>::value_count

tuple_element<I, array<T, N...> >::type

-3- Requires: I < Narray<T, N...>::value_count. The program is ill-formed if I is out of bounds.

-4- Value: The type T.

template <size_t I, class T, size_t ...N>
constexpr T& get(array<T, N...>& a) noexcept;

-5- Requires: I < Narray<T, N...>::value_count. The program is ill-formed if I is out of bounds.

-6- Returns: A reference to the Ith element of a, where indexing is zero-based and uses the forward-iteration order (23.3.2.C).

template <size_t I, class T, size_t ...N>
constexpr T&& get(array<T, N...>&& a) noexcept;

-7- Effects: Equivalent to return std::move(get<I>(a));

template <size_t I, class T, size_t ...N>
constexpr const T& get(const array<T, N...>& a) noexcept;

-8- Requires: I < Narray<T, N...>::value_count. The program is ill-formed if I is out of bounds.

-9- Returns: A const reference to the Ith element of a, where indexing is zero-based and uses the forward-iteration order (23.3.2.C).

Author's Note: When sizeof...(N) == 1, get acts with the expected semantics. When N is empty, 0 is the only valid value for I and get returns the sole element. Otherwise, the multiple indexes needed to reference an element are flattened to the index in "row-major" linear traversal order.

VII. Acknowledgements

VIII. References