C++ Dynamic Arrays

ISO/IEC JTC1 SC22 WG21 N2648 = 08-0158 - 2008-05-16

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

NOTE: This proposal is intended for consideration for Technical Report 2.

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.

Presentation

Within the proposal, regular code font indicates normative code and variable code font indicates an example implementation. The example implementation is a pure library implementation, and does not include the stack allocation optimization. Thus, the example implementation is a minimal conforming implementation.

Within the example, regular code font indicates example code. There is no use of variable code font.

Within both the proposal and the example, sample font is part of the commentary and not part of either the proposal or the example. This font is usually visually indistinguishable from code font, but should be clear from context.

The code for the definition, implementation and subsequent example can be extracted from the HTML source with the following sed script.


	1,/<code>/		d
	/<\/code>/,/<code>/	d
				s|<var>||g
				s|</var>||g
				s|&lt;|<|g
				s|&gt;|>|g
				s|&amp;|\&|g

First, to enable a fully compilable implementation and example, we include appropriate library headers then avoid reliance on a concept-enabled compiler, and finally avoid reliance on other C++0x features.


#include <stddef.h>
#include <cstring>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <memory>
#define DefaultConstructible typename
#define CPP0X( ignore )

Proposal

The dynarray container definition is as follows. The section, paragraph, and table references are based on those of N2588 Working Draft, Standard for Programming Language C++, Pete Becker, March 2008.

Chapter 23 Containers library [containers]

Add <dynarray> to table 87:

Table 87: Containers library summary
SubclauseHeader(s)
23.1 Requirements
23.2 Sequence containers <array>
<deque>
<dynarray>
<list>
<queue>
<stack>
<vector>
23.3 Associative containers <map>
<set>
23.3.5 bitset <bitset>
23.4 Unordered associative containers <unordered_map>
<unordered_set>

23.1.1 Sequence containers [sequence.reqmts]

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

[Note to the Editor: The similar edits for array appear to be missing. This column seems redundant with the synopsis.]

23.2 Sequence containers [sequences]

Add a new synopsis:

Header <dynarray> synopsis


namespace std {
template< DefaultConstructible T >
struct dynarray;
} // namespace std

23.2.7 Class template dynarray [dynarray]

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 &a[n] == &a[0] + n for all 0 <= n < N.

Unless otherwise specified, all array operations are as described in 23.1. Descriptions are provided here only for operations on dynarray that are not described in that clause or for operations where there is additional semantic information.

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


namespace std {
template< DefaultConstructible T >
struct dynarray
{
    // types:
    typedef       T                               value_type;
    typedef       T&                              reference;
    typedef const T&                              const_reference;
    typedef       T*                              iterator;
    typedef const T*                              const_iterator;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef size_t                                size_type;
    typedef ptrdiff_t                             difference_type;

    // fields:
private:
    T*        store;
    size_type count;

    // helper functions:
    void check(size_type n)
        { if ( n >= count ) throw out_of_range("dynarray"); }
    T* alloc(size_type n)
        { return reinterpret_cast<T*>( new char[ n*sizeof(T) ] ); }

public:
    // construct and destruct:
    dynarray() CPP0X( = delete ) ;
    const dynarray operator=(const dynarray&) CPP0X( = delete ) ;

    explicit dynarray(size_type c)
        : store( alloc( c ) ), count( c )
        { size_type i;
          try {
              for ( size_type i = 0; i < count; ++i )
                  new (store+i) T;
          } catch ( ... ) {
              for ( ; i > 0; --i )
                 (store+(i-1))->~T();
              throw;
          } }

    dynarray(const dynarray& d)
        : store( alloc( d.count ) ), count( d.count )
        { try { uninitialized_copy( d.begin(), d.end(), begin() ); }
          catch ( ... ) { delete store; throw; } }

    ~dynarray()
        { for ( size_type i = 0; i < count; ++i )
              (store+i)->~T();
          delete[] store; }

    // iterators:
    iterator       begin()        { return store; }
    const_iterator begin()  const { return store; }
    const_iterator cbegin() const { return store; }
    iterator       end()          { return store + count; }
    const_iterator end()    const { return store + count; }
    const_iterator cend()   const { return store + count; }

    reverse_iterator       rbegin()       
        { return reverse_iterator(end()); }
    const_reverse_iterator rbegin()  const
        { return reverse_iterator(end()); }
    reverse_iterator       rend()         
        { return reverse_iterator(begin()); }
    const_reverse_iterator rend()    const
        { return reverse_iterator(begin()); }

    // capacity:
    size_type size()     const { return count; }
    size_type max_size() const { return count; }
    bool      empty()    const { return false; }

    // element access:
    reference       operator[](size_type n)       { return store[n]; }
    const_reference operator[](size_type n) const { return store[n]; }

    reference       front()       { return store[0]; }
    const_reference front() const { return store[0]; }
    reference       back()        { return store[count-1]; }
    const_reference back()  const { return store[count-1]; }

    const_reference at(size_type n) const { check(n); return store[n]; }
    reference       at(size_type n)       { check(n); return store[n]; }

    // data access:
    T*       data()       { return store; }
    const T* data() const { return store; }
};

} // namespace std

23.2.7.1 dynarray constructor and destructor [dynarray.cons]

Add a new section:

dynarray(size_type c);

Requires: The constructor parameter shall be greater than zero.

Effects: May or may not invoke the global operator new.

dynarray(const dynarray& d);

Requires: T is Copy Constructible.

Effects: May or may not invoke the global operator new.

~dynarray();

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

23.2.7.2 dynarray::size [dynarray.size]

Add a new section:

size_type size() const;

Returns: Returns the argument to the constructor of the object.

23.2.7.3 dynarray::data [dynarray.data]

Add a new section:

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

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

Example

Finally, we show a simple set of uses of the container.

Declaring a reference parameter. Using a const iterator.


void dump( const std::dynarray< int > & source )
{
    std::dynarray< int >::const_iterator src = source.begin();
    for ( ; src != source.end(); src++ )
        std::cout << " " << *src;
    std::cout << std::endl;
}

Declaring a local dynarray of computed size. Using front, back, and a non-const iterator.


void lowrap(       std::dynarray< int > & target,
             const std::dynarray< int > & source )
{
    dump( source );

    std::dynarray< int > sorted( source );
    dump( sorted );

    std::sort( sorted.begin(), sorted.end() );
    dump( sorted );

    const int* srt = &sorted.front();
    std::dynarray< int >::iterator tgt( target.begin() );
    for ( ; tgt != target.end(); tgt++ ) {
        *tgt = *srt;
        if ( srt == &sorted.back() )
            srt = &sorted.front();
        else
            srt++;
    }
    dump( target );
}

Declaring a local dynarray of fixed size. Using size, operator[], at, index iteration, and pointer iteration.


int main() {
    std::dynarray< int > alpha(8);
    std::dynarray< int > gamma(3);
    for ( std::dynarray< int >::size_type i = 0; i < gamma.size(); i++ )
	gamma[i] = 4 - i;
    lowrap( alpha, gamma );
    int sum = 0;
    for ( std::dynarray< int >::size_type i = 0; i < alpha.size(); i++ )
	sum += alpha.at(i);
    return sum;
}