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

• The number of elements in the array can be determined easily
• It is simple to obtain the end of the array when passing a range to a standard algorithm
• An array can be copied and passed as a function parameter while retaining type where traditional arrays suffer pointer-decay

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

• Stack allocation is typically more efficient and safer than dynamic allocation
• Fixing size at compile time often requires fewer consistency checks in client code

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 };

array<int, 4> = { 0, 1, 2, 3 };

array<int, 4> = { { 0, 1, 2, 3 } };

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()

[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

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

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

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 };

-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);
}

-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

-1- Effects:

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

V Open Issues

Uninitialized data

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 };

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

array<int> x = { 0, 1, 2 };

VI References

• [1] Bjarne Stroustrup, The C++ Programming Language 3rd edition, 1997, Addison Wesley ISBN 0-201-88954-4 p496
• [2] Matthew H. Austern, Generic Programming and the STL, 1998, Addison Wesley ISBN 0-201-30956-4 pp59-67
• [3] Nicolai M. Josuttis, The C++ Standard Library - A Tutorial and Reference, 1999, Addison Wesley ISBN 0-201-37926-0 pp218-221
• [4] Boost library array documentation http://www.boost.org/libs/array/array.html