Working Draft, Technical Specification — Array Extensions

ISO/IEC JTC1 SC22 WG21 N3820 - 2013-10-10

Editor: Lawrence Crowl, [email protected]

Foreword
Introduction
Scope
Conformance
Normative references
Terms and definitions
Requirements
Wording changes
    3.9 Types [basic.types]
    3.9.2 Compound Types [basic.compound]
    4.2 Array-to-pointer conversion [conv.array]
    5.1.2 Lambda expressions [expr.prim.lambda]
    5.2.8 Type identification [expr.typeid]
    5.3.1 Unary operators [expr.unary.op]
    5.3.3 Sizeof [expr.sizeof]
    7.1.3 The typedef specifier [dcl.typedef]
    7.1.6.2 Simple type specifiers [dcl.type.simple]
    8 Declarators [dcl.decl]
    8.3.1 Pointers [dcl.ptr]
    8.3.2 References [dcl.ref]
    8.3.4 Arrays [dcl.array]
    8.3.5 Functions [dcl.fct]
    8.5.1 Aggregates [dcl.init.aggr]
    8.5.2 Character arrays [dcl.init.string]
    9.2 Class members [class.mem]
    14.1 Template parameters [temp.param]
    15.1 Throwing an exception [except.throw]
    18.6.2.new Class bad_array_length [bad.array.length]
    Chapter 23 Containers library [containers]
    23.2.3 Sequence containers [sequence.reqmts]
    23.3.1 In general [sequences.general]
    23.3.4 Class template dynarray [dynarray]
    23.3.4.1 Class template dynarray overview [dynarray.overview]
    23.3.4.2 dynarray constructor and destructor [dynarray.cons]
    23.3.4.3 dynarray::data [dynarray.data]
    23.3.4.4 Mutating operations [dynarray.mutate]
    23.3.4.5 Zero sized dynarrays [dynarray.zero]
    23.3.4.6 Traits [dynarray.traits]
Revision History

Foreword

ISO requires a foreword, with most content supplied by the Central Secretariat of ISO. It will be added by the editor before the final document is sent to ISO.

ISO specifies "The introduction is an optional preliminary element used, if required, to give specific information or commentary about the technical content of the document, and about the reasons prompting its preparation. It shall not contain requirements."

This Technical Specification specifies requirements for implementations of various extensions for arrays to the C++ language and library. Included are:

arrays of runtime bound: The core language is extended to permit run-time computation of the bound of an array with automatic storage duration.
class dynarray: The library is extended with a class that specifies an array size only on construction.

Scope

This Technical Specification is applicable to information technology systems that implement the C++ language and standard library. This Technical Specification is applicable only to vendors who wish to provide the interface it describes.

Conformance

No content (yet).

Normative references

The following referenced documents are indispensable for the application of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies. ISO required wording.

ISO/IEC 14882, Programming Language C++

[Note: The programming language and library described in ISO/IEC 14882 is herein called the C++ Standard. —end note]

Unless otherwise specified, the whole of the C++ Standard's Library introduction [lib.library] is included into this Technical Specification by reference.

Terms and definitions

All terms and definitions in N3797. apply unless otherwise stated.

Requirements

All requirements in N3797. apply unless otherwise stated.

Wording changes

The proposed wording changes are relative to the expected contents of N3797.

3.9 Types [basic.types]

Edit within paragraph 10 as follows.

A type is a literal type if it is:

...

an array of literal type other than an array of runtime bound; or
...

3.9.2 Compound Types [basic.compound]

Edit paragraph 2 as follows.

These methods of constructing types can be applied recursively; restrictions are mentioned in 8.3.1 dcl.ptr, 8.3.4 dcl.array, 8.3.5 dcl.fct, and 8.3.2 dcl.ref. Constructing a type such that the number of bytes in its object representation exceeds the maximum value representable in the type std::size_t (18.2 support.types) is ill-formed.

4.2 Array-to-pointer conversion [conv.array]

Edit paragraph 1 as follows.

An ~~lvalue or rvalue~~ expression of type "array of N T", "array of runtime bound of T", or "array of unknown bound of T" can be converted to a prvalue of type "pointer to T". The result is a pointer to the first element of the array.

5.1.2 Lambda expressions [expr.prim.lambda]

Edit within paragraph 15 as follows.

... [Note:...] An array of runtime bound (8.3.4 dcl.array) shall not be captured by copy.

Edit within paragraph 16 as follows.

An entity is captured by reference if it is implicitly or explicitly captured but not captured by copy. It is unspecified whether additional unnamed non-static data members are declared in the closure type for entities captured by reference. [Note: Capturing by reference an array of runtime bound also implicitly captures the value of the bound to support the range-based for statement (6.5.4 stmt.ranged). —end note]

5.2.8 Type identification [expr.typeid]

Insert a new paragraph before paragraph 2 (starting "When typeid is applied ...").

The typeid operator shall not be applied to an array of runtime bound.

5.3.1 Unary operators [expr.unary.op]

Edit within paragraph 3 as follows.

The result of the unary & operator is a pointer to its operand. The operand shall be an lvalue of type other than "array of runtime bound" or a qualified-id. ...

5.3.3 Sizeof [expr.sizeof]

Edit within paragraph 1 as follows.

... The sizeof operator shall not be applied to an expression that has function or incomplete type, to an enumeration type whose underlying type is not fixed before all its enumerators have been declared, to an array of runtime bound, to the parenthesized name of such types, or to an lvalue that designates a bit-field. ...

7.1.3 The `typedef` specifier [dcl.typedef]

Insert a new paragraph before paragraph 3 (starting "In a given non-class scope").

A typedef-name shall not name an array of runtime bound.

7.1.6.2 Simple type specifiers [dcl.type.simple]

Edit within paragraph 3 as follows.

For an expression e, The type denoted by decltype(e) is defined as follows:

if e has type "array of runtime bound", the program is ill-formed;

otherwise, if e is an unparenthesized

...

8 Declarators [dcl.decl]

Edit within paragraph 4 as follows.

...

noptr-declarator:

declarator-id attribute-specifier-seq_opt

noptr-declarator parameters-and-qualifiers
noptr-declarator [ ~~constant-expression_opt~~ expression_opt ] attribute-specifier-seq_opt

( ptr-declarator )

...

8.3.1 Pointers [dcl.ptr]

Edit within paragraph 1 as follows.

... Similarly, the optional attribute-specifier-seq (7.6.1) appertains to the pointer and not to the object pointed to. There shall be no pointers to arrays of runtime bound.

8.3.2 References [dcl.ref]

Edit within paragraph 5 as follows.

There shall be no references to references, no references to arrays of runtime bound, no arrays of references, and no pointers to references. ...

8.3.4 Arrays [dcl.array]

Edit within paragraph 1 as follows.

In a declaration T D where D has the form

D1 [ ~~constant-expression_opt~~ expression_opt ] attribute-specifier-seq_opt

and the type of the identifier in the declaration T D1 is "derived-declarator-type-list T", then the type of the identifier of D is an array type; if the type of the identifier of D contains the auto type-specifier, the program is ill-formed. T is called the array element type; this type shall not be a reference type, the (possibly cv-qualified) type void, a function type, an array of unknown or runtime bound, or an abstract class type. Except as noted below, if the expression is omitted, the type of the identifier of D is "derived-declarator-type-list array of unknown bound of T". If the expression is present, it is implicitly converted to std::size_t. The expression is erroneous if:

its value before converting to std::size_t or, in the case of an expression of class type, before application of the second standard conversion (13.3.3.1.2 over.ics.user) is less than or equal to zero;

its value is such that the size of the allocated object would exceed the implementation-defined limit (annex B implimits);

the initializer of the object is a braced-init-list whose number of (top-level) initializer-clauses exceeds the number of elements to initialize; or

the object is initialized with a string literal and there are more initializers than there are array elements.

If the expression, after converting to std::size_t, is a core constant expression and the expression is erroneous, the program is ill-formed.

If the expression, after converting to std::size_t, is a core constant expression whose value is N, the type of the identifier of D is "derived-declarator-type-list array of N T".

Otherwise, the type of the identifier of D is "derived-declarator-type-list array of runtime bound of T" and the value of the expression designates the number of elements N in the array. If the expression is erroneous, an exception of a type that would match a handler (15.3 except.handle) of type std::bad_array_length (18.6.2.2 bad.array.length) is thrown.

If the constant-expression (5.19 expr.const) is present, it shall be an integral constant expression and its value shall be greater than zero. The constant expression specifies the bound of (number of elements in) the array. If the value of the constant expression is N, the array has N elements numbered 0 to N-1, and the type of the identifier of D is "derived-declarator-type-list array of N T".

An object of array type contains a contiguously allocated non-empty set of N subobjects of type T. ~~Except as noted below, if the constant expression is omitted, the type of the identifier of D is "derived-declarator-type-list array of unknown bound of T", an incomplete object type.~~ The type "derived-declarator-type-list array of N T" is a different type from the type "derived-declarator-type-list array of unknown bound of T", see 3.9 basic.types. Any type of the form "cv-qualifier-seq array of N T" is adjusted to "array of N cv-qualifier-seq T", and similarly for "array of unknown bound of T" and "array of runtime bound of T". The optional attribute-specifier-seq appertains to the array. [Example:
typedef int A[5], AA[2][3];
typedef const A CA;   // type is "array of 5 const int"
typedef const AA CAA; // type is "array of 2 array of 3 const int"

void f(unsigned int n) {
  int a[n]; // type of "a" is "array of runtime bound of int"
}
—end example] [Note: ... ]

Edit within paragraph 3 as follows.

When several "array of" specifications are adjacent, a multidimensional array is created~~; only the first of the constant expressions that specify the bounds of the arrays may be omitted~~. In addition to ...

Add a new paragraph before paragraph 4.

An array of runtime bound shall only be used as the type of a local object with automatic storage duration. If the size of the array exceeds the size of the memory available for objects with automatic storage duration, the behavior is undefined. [Footnote: Implementations that detect this case are encouraged to throw an exception that would match a handler (15.3 except.handle) of type std::bad_array_length (18.6.2.2 bad.array.length). —end footnote] It is unspecified whether a global allocation function (3.7.4 basic.stc.dynamic) is invoked to obtain storage for the array. If it is invoked, the corresponding global deallocation function is invoked to release the storage after the lifetime of the array ended. [Footnote: Alternatively, an implementation could allocate such an array on the usual stack or obtain storage via malloc (20.6.13 c.malloc). —end footnote]

8.3.5 Functions [dcl.fct]

Edit within paragraph 8 as follows.

If the type of a parameter includes a type of the form "array of runtime bound of T", "pointer to array of unknown bound of T", or "reference to array of unknown bound of T," the program is ill-formed. [Footnote: ...] Functions shall not have a return type of type array or function, although they may have a return type of type pointer or reference to such things.

8.5.1 Aggregates [dcl.init.aggr]

Edit within paragraph 6 as follows.

For types other than arrays of runtime bound (8.3.4 dcl.array), An an initializer-list is ill-formed if the number of initializer-clauses exceeds the number of members or elements to initialize. [Example: ... ]

8.5.2 Character arrays [dcl.init.string]

Edit whithin paragraph 2 as follows.

[Note: There cannot be more initializers than there are array elements; see 8.3.4 dcl.array. [Example:
char cv[4] = "asdf";                 // error
is ill-formed since there is no space for the implied trailing '\0'. —end note]

9.2 Class members [class.mem]

Edit within paragraph 10 as follows.

~~Non-static~~ A non-static (9.4 class.static) data ~~members~~ member shall not have incomplete ~~types.~~ type or type "array of runtime bound". [Note: In particular, a class C shall not contain a non-static member of class C, but it can contain a pointer or reference to an object of class C. —end note]

14.1 Template parameters [temp.param]

Edit within paragraph 7 as follows.

A non-type template-parameter shall not be declared to have floating point, class, array of runtime bound, or void type. [Example: ... ]

15.1 Throwing an exception [except.throw]

Edit within paragraph 1 as follows.

... [Note: An exception can be thrown from one of the following contexts: throw-expression (see below), allocation functions (3.7.4.1 basic.stc.dynamic.allocation), dynamic_cast (5.2.7 expr.dynamic.cast), typeid (5.2.8 expr.typeid), new-expression (5.3.4 expr.new), array of runtime bound (8.3.4 dcl.array), and standard library functions (17.5.1.4 structure.specifications). —end note] ...

18.6.2.new Class `bad_array_length` [bad.array.length]

Add a new section just before 18.6.2.2 new.badlength as follows.

namespace std {
  class bad_array_length : public bad_alloc {
    public:
      bad_array_length() noexcept;
  };
}
The class bad_array_length defines the type of objects thrown as exceptions by the implementation to report an attempt to allocate an array of runtime bound with a size less than or equal to zero or greater than an implementation-defined limit (8.3.4 dcl.array).
bad_array_length() noexcept;
Effects: constructs an object of class bad_array_length.

Remarks: the result of calling what() on the newly constructed object is implementation-defined.

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.1 In general [sequences.general]

Edit paragraph 1 as follows.

The headers <array>, <deque>, <dynarray>, <forward_list>, <list>, and <vector> define template classes that meet the requirements for sequence containers.

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.4 Class template `dynarray` [dynarray]

Add a new section after the deque section.

23.3.4.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 <class 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;       // See [container.requirements]
    typedef implementation-defined const_iterator; // See [container.requirements]
    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:
    // [dynarray.cons] 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();

    dynarray& operator=(const dynarray&) = delete;

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

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

    // [dynarray.data] data access:
    T*       data()       noexcept;
    const T* data() const noexcept;

    // [dynarray.mutate] mutating member functions:
    void fill(const T& v);
  };

} // namespace std

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

Add a new section:

explicit 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 ([decl.init]) 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.

Effects: Allocates storage for d.size() elements. The d.size() elements of the dynarray are direct-initialized ([dcl.init]) with the corresponding elements of d. May or may not invoke the global operator new.

Throws: std::bad_alloc when there is insufficient memory.
template <class Alloc >
  dynarray(size_type c, const Alloc& alloc);
template <class Alloc >
  dynarray(size_type c, const T& v, const Alloc& alloc);
template <class Alloc >
  dynarray(const dynarray& d, const Alloc& alloc);
template <class Alloc >
  dynarray(initializer_list<T>, const Alloc& alloc);
Requires: Alloc shall meet the requirements for an Allocator ([allocator.requirements]).

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

~dynarray();

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

23.3.4.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.3.4.4 Mutating operations [dynarray.mutate]

Add a new section:

void fill(const T& v);

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

23.3.4.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.4.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 ([allocator.requirements]). [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 section will be removed before final publication.

N3820

The initial revision originates with the papers N3639 Runtime-sized arrays with automatic storage duration (revision 5) and N3662 C++ Dynamic Arrays.
The initial revision derives from the following commits to the source of standard managed at https://github.com/cplusplus/draft/.

Arrays with Runtime Bound

commit/010f14c77212bcb5dfed3c4b9a55f0ddc24c51c0

Dynarray

commit/d2c727eba9f8b64be697e6d8cc6b75fb7d43193a commit/cec76a769f35cc348805f254c22cc3d83d7eac12 commit/bb583f2005070c700c8b4405f5030e4307b5771a commit/c8054d9d8ca074ee7b125eb55fdc6774a22e3e83

Working Draft, Technical Specification — Array Extensions

Contents