Alisdair Meredith <alisdair.meredith@uk.renaultf1.com>
23 Apr 2003
Doc number N1479=03-0062

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 stack-allocated 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 proposes minor changes to the container requirements tables to accomodate a new classification of (fixed size) container, but it does not require changes to any standard classes or functions and it does not require changes to any of the standard 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.

Fixed size container

To meet the post-condition on default construction in Table 65 that array<T,N>().size() == 0 the notion of a fixed size container is introduced. A fixed size container object always returns the same value for a call to size() and is exempted from the size() == 0 postcondition above.

This definition of a fixed size containers supports future containers where the fixed size is determined at runtime, rather than compile time eg. a non-resizable analog of vector initialized by a pair of iterators.

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.

c_array()

With a similar intent to the basic_string member function c_str() that is provided to ease compatability with legacy APIs, array supplies the c_array() 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 c_array() is chosen to be (const) T * rather than trying to return a reference to T[N] (which could decay to a pointer as required.) This maintains the similarity with c_str(), 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::c_str() 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. It would be reasonable to retain this behaviour

An 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() == 0.

This solution preferred by the proposal removes a potential error from library use. This may be particularly valuable when writing generic code parameterized on N. However, it is a change of behaviour compared to the traditional C array.

IV. Proposed Text

Header

Add an extra row to table 63

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

Fixed size containers

Add an extra paragraph to clause 23

-12- A container may be either fixed size, or variable size. A variable size container supports insertion and removal of elements, a fixed size container does not. A fixed size container object will always return the same value for a call of size().

Modify the two rows of table 65 that refer to default construction such that the size() == 0 postcondition only holds for variable sized containers


Container requirements
expressionreturn typeassertion/notecomplexity
  pre/post-condition
X u; post: u.size() == 0 for variable sized containers.constant
X();  X().size() == 0 for variable sized containers.constant

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

Header <array> synopsis

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

-1- An array is a fixed size container that 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- An array satisfies all of the requirements of a fixed-size container and of a reversible container (given in two tables in lib.container.requirements.) Descriptions are provided here only for operations on array that are not described in one of these tables or for operations where there is additional semantic information.

namespace std {
  template <class T, unsigned int 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 implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    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 *       c_array();
    const T * c_array() const;
  };
  template <class T, unsigned int N>
    bool operator==(const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, unsigned int N>
    bool operator< (const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, unsigned int N>
    bool operator!=(const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, unsigned int N>
    bool operator> (const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, unsigned int N>
    bool operator>=(const array<T,N>& x,
		    const array<T,N>& y);
  template <class T, unsigned int N>
    bool operator<=(const array<T,N>& x,
		    const array<T,N>& y);
  //  specialized algorithms:
  template <class T, unsigned int 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, unsigned int N>
  void swap(array<T,N>& x, array<T,N>& y);

-1- Effects:

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

V Open 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.

Container-without-allocator

As written several clauses in the Containers section of the library assume containers support allocators, and specify for the allocator as well as the container. It is proposed to reword those clauses refer to 'containers that support allocators' are than simply 'containers', but that opens the issue of specifying which containers must support allocators (initially all standard containers but array.)

Alternatively array could specifically exempt itself from those clauses, and introduce language to permit such an exemption.

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