b A Proposal to Add a Fixed Size Array Wrapper to the Standard Library Alisdair Meredith <alisdair.meredith@uk.renaultf1.com>
28 Oct 2003
Doc number N1548=03-0131

A Proposal to Add a Fixed Size Array Wrapper to the Standard Library Technical Report

I. Motivation

The containers section of the standard library has become a familiar and valued tool over the years since standardisation, replacing low level manipulation of data structures and pointers with a consistent higher level interface. This proposal extends these now familiar facilities to traditional arrays.

The idea of such a wrapper has been known for a long time, serving as an introductory example in many leading texts [1][2][3] An implementation by Nicolai Josuttis was one of the earliest libraries distributed through Boost.

In addition to the convenience of a familiar interface, some typical uses of the traditional array are simpler through this interface

Compared to traditional array syntax the wrapper more clearly associates the number of elements as part of the type.

In addition the library implementor may offer additional features, such as range-checked access, without recourse to compiler internals or switches.

Compared to the existing standard containers the array can offer several advantages

As an aside, the standard library is often looked to for examples of best practices, especially when learning the language. This proposal would add a prominent example of the use of a non-type template parameter.

II. Impact On the Standard

This proposal is a pure library extension. It does not require changes to any standard classes, functions or headers. While it does not require any changes in the core language, it might benefit from relaxing some of the conditions on aggregate types. It has been implemented in standard C++.

III. Design Decisions

The class is designed to function as closely as possible as a drop-in replacement for a traditional array. This places several constraints on the design, chiefly as it must be implemented as an aggregate type [8.5.1] in order to support initializer syntax

Initialization

Traditional arrays are frequently initialized using an initializer-list

int x[4] = { 0, 1, 2, 3 };
In order to support this the array class must be implemented as an aggregate [8.5.1]
array<int, 4> = { 0, 1, 2, 3 };
Note: By [8.5.1.11] the common practice with existing wrappers of using double-braces
array<int, 4> = { { 0, 1, 2, 3 } };
should not be necessary on conforming compilers, supporting a true drop-in replacement.

Constructors

A requirement of implementing an aggregate is that the class declares no constructors [8.5.1.1] It is understood that the automatically generated default constructor, copy constructor and assignment operator meet the container requirements in table 65.

Public Data

While the use of public data is not explicitly mandated by this proposal, it is implied by the required implementation as an aggregate [8.5.1.1] Any future relaxing of this requirement would likewise pass on to implementations of array.

Traditionally public data members are discouraged but in this case it does not appear to be an issue, given the class member functions whole purpose is to directly expose this data. Further the name of the data member is implementation defined so cannot be portably relied on.

Iterators

While the types of the iterators might typically be the typedefs of pointer to the parametrized type, this is not mandated to allow implementors freedom to offer checked iterators or other enhancements they deem appropriate.

data()

With a similar intent to the basic_string member function data() that is provided to ease compatability with legacy APIs, array supplies the data() member function that returns that address of the wrapped array. As with vector, it is likely that the iterators may be implemented in terms other than raw pointers so begin() may not be relied on for this purpose. It is believed supplying a clearly named function, rather than relying on &array[0], will be clearer to users and reduce the likelihood of calling begin() where inappropriate.

The return type of data() is chosen to be (const) T * rather than trying to return a reference to T[0] (which could decay to a pointer as required.) This maintains the similarity with basic_string::data(), avoids surprises if template type deduction is performed on the result, and reduces temptation to try clever manipulations that are more easily available elsewhere in the interface (such as trying to deduce value for N.)

Unlike basic_string::data() both const and non-const overloads are offered. This retains the important ability to pass an array as a return buffer in legacy APIs

Comparison operations

The comparison operations are specified by Table 65 - Container requirements. This mandates elementwise comparison, and total ordering by a lexicographical compare.

swap()

Table 65 - Container requirements, demands that swap be a constant complexity operation. While swap is clearly linear in N, N is fixed for a given template instantiation and so this requirement can be met.

[23.1] para 10 requires that "unless otherwise specified" swap() should be a no-throw operation. array must relax this guarantee to be that offered by calling swap() on its element type T

Range checking

The same range checking options are offered as for vector. Array-subscript access is unchecked, and a checked at() function is supplied which throws std::range_error if called with a bad value.

Note that if some future metacode language extension was accepted, both could offer compile-time range-checking when the argument value can be determined at compile time. Further comment goes beyond the scope of the current proposal.

Empty arrays

Consideration should be given to the case where N == 0. For traditional arrays this is an error that should be diagnosed by the compiler. While it would be reasonable to retain this behaviour the alternative offerred by the proposal is to partially specialize the template on the case N == 0, such that it has no internal state, empty() == true, and begin() == end() == unique value.

This solution is preferred as it removes a potential error from library use which may be particularly valuable when writing generic code.

Not quite a container

array cannot meet the post-condition on default construction in Table 65 that array<T,N>().size() == 0. The idea of introducing a fixed size container concept was considered, but the Library TR is the wrong place to revise container requirements.

array has no use for allocators, which are implicitly required in several clauses for conforming containers.

In all other ways array meets the requirements for both container and reversible container.

IV. Proposed Text

Header

Add an extra row to table 63

Containers library summary
SubclauseHeader(s)
23.5.X lib.array array<array>

23.3.X - Class template array [lib.array]

Header <array> synopsis

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

-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 N elements of type T, so that size() == N 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 &a[n] == &a[0] + n for all 0 <= n < N.

-2-An array is an aggregate (8.5.1) that can be initialized with the syntax

    array a = { initializer-list };
where initializer-list is a comma separated list of up to N elements of type convertible-to-T.

-3- Unless specified others, all array operations are as described in 23.1 lib.container.requirements. Descriptions are provided here only for operations on array that are not described in this clause or for operations where there is additional semantic information.

namespace std {
  template <class T, size_t N >
  struct array {
    //  types:
    typedef T &                                   reference;
    typedef const T &                             const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef size_t                                size_type;
    typedef ptrdiff_t                             difference_type;
    typedef T                                     value_type;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
	T       elems[N];

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

    void assign(const T& u);
    void swap( array<T, N> &);

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;
    //  capacity:
    size_type size() const;
    size_type max_size() const;
    bool      empty() const;
    //  element access:
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
    const_reference at(size_type n) const;
    reference       at(size_type n);
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;
    T *       data();
    const T * data() const;
  };
  template <class T, size_t N>
    bool operator==(const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, size_t N>
    bool operator< (const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, size_t N>
    bool operator!=(const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, size_t N>
    bool operator> (const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, size_t N>
    bool operator>=(const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, size_t N>
    bool operator<=(const array<T,N>& x,
		    const array<T,N>& y);
  //  specialized algorithms:
  template <class T, size_t N>
    void swap(array<T,N>& x, array<T,N>& y);
}

23.3.X.1 - array constructors, copy, and assignment [lib.array.cons]

-1- Initialization:

The conditions for an aggregate (8.5.1) must be met. Class array relies on the implicitly-declared special member functions (12.1, 12.4, and 12.8) to satisfy the requirements of table 65

23.3.X.2 - array specialized algorithms [lib.array.special]

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

-1- Effects:

  swap_ranges(x.begin(), x.end(), y.begin() );

23.3.X.3 - array size [lib.array.size]

-1- Returns: N.

23.3.X.4 - Zero sized arrays [lib.array.zerosize]

array shall provide support for the special case N == 0.

In the case that N == 0

-1- Requires: elems is not required.

-2- Requires: begin() == end() == unique value.

V Future Issues

Uninitialized data

If no initializer-list is supplied, a default constructed array may contain uninitialized data. If T is a user defined type with a default constructor, all array elements should be default constructed. However if T is a built-in type such as int or float, then the value of each element will be undefined until assigned.

Array size deduction

A popular use of traditional arrays is to automatically deduce size from the initializer list. eg,

int x[] = { 0, 1, 2 };
declares an array of size 3.

It would be nice if we had automatic type deduction of the form

array<int> x = { 0, 1, 2 };
automatically deducing N == 3. However, I do not know of any way to achieve this convenience in the language today, nor of any proposed extensions that might resolve this.

VI References