C++ Dynamic Arrays

ISO/IEC JTC1 SC22 WG21 N3662 - 2013-04-19

Lawrence Crowl, crowl@google.com, Lawrence@Crowl.org
Matt Austern, austern@google.com

Problem
Solution
Builtin Arrays of Runtime Bound
Proposal
    Chapter 23 Containers library [containers]
    23.2.3 Sequence containers [sequence.reqmts]
    23.3 Sequence containers [sequences]
    23.3.8 Class template dynarray [dynarray]
    23.3.8.1 Class template dynarray overview [dynarray.overview]
    23.2.8.2 dynarray constructor and destructor [dynarray.cons]
    23.2.8.3 dynarray::data [dynarray.data]
    23.2.8.4 Mutating operations [dynarray.mutate]
    23.2.8.5 Zero sized dynarrays [dynarray.zero]
    23.3.8.6 Traits [dynarray.traits]
Revision History

Problem

Programs can become more efficient when they can bind aspects of their execution earlier in program development. As an example, the std::unordered_map container provides more functionality than std::vector, but std::vector provides better performance when the programmer can bind indexes to a dense, but extensible, range near zero. Going further, built-in arrays provide even better performance by binding the range end at compilation time.

Unfortunately, for some applications, the range end is known at container construction but not at compilation time. So, built-in arrays are not applicable. On the other hand, std::vector is more general than needed, as it permits an extensibility that is not required. Ideally, we would like to be able to specify a container where the index end is bound at construction, but does not change thereafter.

The C programming language has such a container in the form of variable-length arrays. They are not general in that they are limited to automatic variables, but given that restriction they are nearly as efficient as normal arrays, requiring only mark/release stack allocation and maintenance of a frame pointer. (Maintaining a frame pointer is a good idea anyway.) Unfortunately the detailed type semantics of C variable-length arrays are probably not acceptable to C++, so we cannot simply adopt them.

The std::valarray container is intermediate between built-in arrays and std::vector, but as it supports a resize method, it cannot hold its size fixed for the lifetime of the variable. Furthermore, std::valarray supports compound member assignment operators that imply such operators in the parameter type. Such implications are workable only for types with "full interfaces", not for general types.

Solution

Instead of adopting C variable-length arrays, we propose to define a new facility for arrays where the number of elements is bound at construction. We call these dynamic arrays, dynarray. In keeping with C++ practice, we wish to make dynarrays usable with more than just automatic variables. But to take advantage of the efficiency stack allocation, we wish to make dynarray optimizable when used as an automatic variable.

Therefore, we propose to define dynarray so that compilers can recognize and implement construction and destruction directly, without appeal to any particular standard library implementation. However, to minimize the necessary burden on compilers, we propose that dynarray can be implemented as a pure library, although with lost optimization opportunity.

We believe that the compilers can introduce the optimization without impact on source or binary compatiblity. There may be some change in code profiles and operator new calls as a result of that optimization, but such risks are common to compiler and library upgrades.

Syntactically, our proposal follows the lead of std::array and std::vector containers. Semantically, our proposal follows the lead of built-in arrays. That is, we do not require more out of std::dynarray element types than we do of standard array element types.

The dynarray constructor has a parameter indicating the number of elements in the container. Dynarray requires an element type with a default constructor, just as the built-in array requires. Note that dynarray does not provide a default constructor, because there is no reasonable default size, and hence the dynarray may not take a dynarray as an element.

Dynarray provides a copy constructor, but use of the copy constructor requires that the element type also have a copy constructor. The presence of this constructor implies that users cannot explicitly instantiate the dynarray template class on a type that does not have a copy constructor. This practice already exists in the standard library.

Dynarray provides random access iterators, likely implemented as pointers. The elements must be contiguously allocated, to enable access via pointer arithmetic.

Dynarray also provides reverse iterators, but these definitions imply that the compiler implementation depends on the standard library implementation, which is the reverse of the normal dependence.

Dynarray does not provide any mechanism for determining whether heap or stack allocation was used.

Dynarray does not provide a constructor from first and last forward iterators. Such a constructor is possible, though, as one can determine the size with std::distance(first,last). The technical consideration is that determining the distance is only constant time for random access iterators.

Builtin Arrays of Runtime Bound

In N3497 Runtime-sized arrays with automatic storage duration, Jens Maurer proposes arrays with runtime bound. These arrays are to std::dynarray as normal fixed-size arrays are to std::array.

There are several similarities and differences.

Both proposals permit allocation on the stack or on the heap, at the discression of the implementation.
Arrays of runtime bound can be used only for variables of automatic storage duration. In contrast, dynarray can be used anywhere. However, when dynarray is not used in a automatic variable, use of the heap is necessarily required.
The types of arrays of runtime bound are not inspectable (e.g. with decltype). In contrast, dynarray has a normal template class type, but the bound is not part of that type.
Arrays of runtime bound throw std::bad_array_length when the array size is unacceptable. As currently defined, dynarray also throws throw std::bad_array_length, under the assumption that migration between the two is easier if they throw the same exception. The other choice would be to throw std::length_error as does std::vector::reserve(). Note, however, that the std::vector::vector(size_type n) does not specify an exception. The operator new[] throws std::bad_array_new_length.

Because it may allocate memory, dynarray may also throw std::bad_alloc.
Arrays of runtime bounds do no allow zero size; dynarray does.
One can use initializer lists with arrays of runtime bound. They are not currently supported with dynarray. If dynarray were to support initializer lists, it would derive its size from the initializer list. This approach prevents a specification inconsistency that is possible in arrays of runtime bound.

Proposal

The dynarray container definition is as follows. The section, paragraph, and table references are based on those of N3485 Working Draft, Standard for Programming Language C++, Stefanus Du Toit, November 2012.

Chapter 23 Containers library [containers]

Add <dynarray> to table 87:

Table 87: Containers library summary

Subclause Header(s)

23.2 Requirements

23.3 Sequence containers <array> <deque> <dynarray> <forward_list> <list> <vector>

23.4 Associative containers <map> <set>

23.5 Unordered associative containers <unordered_map> <unordered_set>

23.6 Container adaptors <queue>
<stack>

Table 87: Containers library summary
Subclause	Header(s)
23.2 Requirements
23.3 Sequence containers	`<array> <deque> <dynarray> <forward_list> <list> <vector>`
23.4 Associative containers	`<map> <set>`
23.5 Unordered associative containers	`<unordered_map> <unordered_set>`
23.6 Container adaptors	<queue> <stack>

23.2.3 Sequence containers [sequence.reqmts]

In table 101, Optional sequence container operations, add dynarray to the list of containers for operations front, back, a[n], and at(n).

23.3 Sequence containers [sequences]

Add a new synopsis:

Header <dynarray> synopsis



#include <initializer_list>

namespace std {

template< class T >
class dynarray;

template <class Type, class Alloc>
struct uses_allocator<dynarray<Type>, Alloc>;

template <class T, class Allocator>
  bool operator==(const dynarray<T>& x, const dynarray<T>& y);
template <class T, class Allocator>
  bool operator< (const dynarray<T>& x, const dynarray<T>& y);
template <class T, class Allocator>
  bool operator!=(const dynarray<T>& x, const dynarray<T>& y);
template <class T, class Allocator>
  bool operator> (const dynarray<T>& x, const dynarray<T>& y);
template <class T, class Allocator>
  bool operator>=(const dynarray<T>& x, const dynarray<T>& y);
template <class T, class Allocator>
  bool operator<=(const dynarray<T>& x, const dynarray<T>& y);

} // namespace std

23.3.8 Class template `dynarray` [dynarray]

Add a new section.

23.3.8.1 Class template `dynarray` overview [dynarray.overview]

Add a new section:

The header <dynarray> defines a class template for storing sequences of objects where the size is fixed at construction. A dynarray supports random access iterators. An instance of dynarray<T> stores elements of type T. The elements of a dynarray are stored contiguously, meaning that if d is an dynarray<T> then it obeys the identity &d[n] == &d[0] + n for all 0 <= n < d.size().

Unless otherwise specified, all dynarray operations have the same requirements and semantics as specified in 23.2.

All operations except construction, destruction, and fill shall have constant-time complexity.


namespace std {
template< typename T >
class dynarray
{
    // types:
    typedef       T                               value_type;
    typedef       T&                              reference;
    typedef const T&                              const_reference;
    typedef       T*                              pointer;
    typedef const T*                              const_pointer;
    typedef       implementation-defined          iterator;
    typedef       implementation-defined          const_iterator;
    typedef reverse_iterator<iterator>            reverse_iterator;
    typedef reverse_iterator<const_iterator>      const_reverse_iterator;
    typedef size_t                size_type;
    typedef ptrdiff_t                difference_type;

public:
    // construct/copy/destroy:
    explicit dynarray(size_type c);
    template< typename Alloc >
      dynarray(size_type c, const Alloc& alloc);
    dynarray(size_type c, const T& v);
    template< typename Alloc >
      dynarray(size_type c, const T& v, const Alloc& alloc);
    dynarray(const dynarray& d);
    template< typename Alloc >
      dynarray(const dynarray& d, const Alloc& alloc);
    dynarray(initializer_list<T>);
    template< typename Alloc >
      dynarray(initializer_list<T>, const Alloc& alloc);
    dynarray& operator=(const dynarray&) = delete;
    ~dynarray();

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

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

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

    // element access:
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;

    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back()  const;

    const_reference at(size_type n) const;
    reference       at(size_type n);

    // data access:
    T*       data()       noexcept;
    const T* data() const noexcept;

    // mutating member functions:
    void fill(const T& v);
};

} // namespace std

23.2.8.2 `dynarray` constructor and destructor [dynarray.cons]

Add a new section:

dynarray(size_type c);

Effects: Allocates storage for c elements. May or may not invoke the global operator new. The c elements of the dynarray are default-initialized (8.5).

Throws: std::bad_array_length when the size requested is larger than implementable. std::bad_alloc when there is insufficient memory.

dynarray(size_type c, const T& v);

Requires: T shall meet the CopyConstructible requirements.

Effects: Allocates storage for c elements. May or may not invoke the global operator new. The c elements of the dynarray are direct-initialized (8.5) with argument v.

Throws: std::bad_array_length when the size requested is larger than implementable. std::bad_alloc when there is insufficient memory.

dynarray(const dynarray& d);

Requires: T shall meet the CopyConstructible requirements.

Throws: std::bad_alloc when there is insufficient memory.

Effects: Allocates storage for d.size() elements. The d.size() elements of the dynarray are direct-initialized (8.5) with the corresponding elements of d. May or may not invoke the global operator new.
template< typename Alloc >
  dynarray(size_type c, const Alloc& alloc);
template< typename Alloc >
  dynarray(size_type c, const T& v, const Alloc& alloc);
template< typename Alloc >
  dynarray(const dynarray& d, const Alloc& alloc);
template< typename Alloc >
  dynarray(initializer_list<T>, const Alloc& alloc);
Requires: Alloc shall meet the requirements for an Allocator (17.6.3.5).

Effects: Equivalent to the preceding constructors except that each element is constructed with uses-allocator construction (20.6.7.2).

~dynarray();

Effects: Invokes the global operator delete if and only if the constructor invoked the global operator new.

23.2.8.3 `dynarray::data` [dynarray.data]

Add a new section:

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

Returns: A pointer to the contiguous storage containing the elements.

23.2.8.4 Mutating operations [dynarray.mutate]

Add a new section:

void fill(const T& v);

Effects: fill_n(begin(), size(), v);

23.2.8.5 Zero sized dynarrays [dynarray.zero]

Add a new section:

dynarray shall provide support for the special case of construction with a size of zero. In the case that the size is zero, begin() == end() == unique value. The return value of data() is unspecified. The effect of calling front() or back() for a zero-sized dynarray is undefined.

23.3.8.6 Traits [dynarray.traits]

Add a new section.

template <class Type, class Alloc>
  struct uses_allocator<dynarray<Type>, Alloc> : true_type { };
Requires: Alloc shall be an Allocator (17.6.3.5). [Note: Specialization of this trait informs other library components that dynarray can be constructed with an allocator, even though it does not have a nested allocator_type. —end note]

Revision History

This paper revises N3532 - 2013-03-12 as follows.

Add types pointer and const_pointer.
Add a constructor with a value fill argument.
Add an initializer_list constructor.
Add constructors that apply allocators to element construction.
Add effect of allocating memory on constructors.
Add missing reference on deleted assignment return type.
Add crbegin and crend.
Add the fill member function.
Add the swap member function.
Add comparison functions.
Mark appropriate functions as noexcept.
Make various editorial corrections.
Remove the non-normative example implementation.
Remove the Presentation section.
Remove the Example section.

N3532 revised N2648 = 08-0158 - 2008-05-16 as follows.

Add a section discussing of the relationship to N3497 Runtime-sized arrays with automatic storage duration.
Support zero-length dynarrays. Add corresponding specifications for max_size and empty. Update implementation.
Throw std::bad_array_length when the size parameter is too large. Throw std::bad_alloc when memory allocation fails.
Clarify that there is no support for determing whether heap or stack allocation was used.
Note that a constructor from initializer_list is not provided but technically feasible.
Note that a constructor from two forward iterators is not provided but technically feasible.
Update the form of the HTML, which affects the script for extracting the code.
Add a 'Revision History' section.