3219. std::array overview container requirements are incorrect

Section: 23.3.3.1 [array.overview], 23.2.2 [container.requirements.general] Status: New Submitter: Nevin Liber & Christian Trott Opened: 2019-06-13 Last modified: 2022-04-24

Priority: 3

View other active issues in [array.overview].

View all other issues in [array.overview].

View all issues with New status.

Discussion:

The requirements specified in 23.3.3.1 [array.overview] p3 are incorrect; namely:

• A default constructed array<T, N> where 0 < N has linear, not constant complexity.

• A default constructed array<T, 0> is empty and has constant complexity.

[2019-07 Issue Prioritization]

Priority to 3 after discussion on the reflector.

Previous resolution [SUPERSEDED]:

This wording is relative to N4810.

1. Modify 23.2.2 [container.requirements.general], Table 62 — "Container requirements", as indicated (This table can be identified by the "section" identifier [tab:container.req] in the next working draft):

   Table 62 — Container requirements

   Expression	Return type	Operational semantics	Assertion/note pre/post-condition	Complexity
   […]
   X u;			Ensures: !u.empty() for array<T, N> where 0 < N, and Ensures: u.empty() for all other standard containers.	constant(Note A)
   X()			Ensures: !X().empty() for array<T, N> where 0 < N, and Ensures: X().empty() for all other standard containers.	constant(Note A)
   […]

   Those entries marked "(Note A)" or "(Note B)" have linear complexity for array<T, N> where 0 < N and have constant complexity for all other standard containers.

2. Modify 23.3.3.1 [array.overview] as indicated:

   -2- An array is an aggregate (9.4.2 [dcl.init.aggr]) that can be list-initialized with up to N elements whose types are convertible to T.

   -3- An array<T, 0> satisfies all of the requirements of a container and of a reversible container (23.2 [container.requirements]). An array<T, N> where 0 < N satisfies all of the requirements of a container and of a reversible container (23.2 [container.requirements]), except that a default constructed array<T, N> object is not empty and thatboth default construction and swap does not have constantlinear complexity. An array satisfies some of the requirements of a sequence container (23.2.4 [sequence.reqmts]). Descriptions are provided here only for operations on array that are not described in one of these tables and for operations where there is additional semantic information.

[2022-04-24; Daniel rebases wording on N4910]

Proposed resolution:

This wording is relative to N4910.

1. Modify 23.2.2.2 [container.reqmts] as indicated:

   X u;
   X u = X();
   

   -10- Postconditions: !u.empty() for array<T, N> where 0 < N, and u.empty() for all other standard containers.

   -11- Complexity: ConstantLinear for array<T, N> where 0 < N and constant for all other standard containers.

   […]

   X u(rv);
   X u = rv;
   

   -15- Postconditions: u is equal to the value that rv had before this construction.

   -11- Complexity: Linear for array<T, N> where 0 < N and constant for all other standard containers.

   […]

   a.swap(b)
   

   -45- Result: void

   -46- Effects: Exchanges the contents of a and b.

   -47- Complexity: Linear for array<T, N> where 0 < N and constant for all other standard containers.

2. Modify 23.3.3.1 [array.overview] as indicated:

   -2- An array is an aggregate (9.4.2 [dcl.init.aggr]) that can be list-initialized with up to N elements whose types are convertible to T.

   -3- An array<T, 0> meets all of the requirements of a container (23.2.2.2 [container.reqmts]) and of a reversible container (23.2.2.3 [container.rev.reqmts]). An array<T, N> where 0 < N meets all of the requirements of a container (23.2.2.2 [container.reqmts]) and of a reversible container (23.2.2.3 [container.rev.reqmts]), except that a default constructed array<T, N> object is not empty if N > 0 and default construction, move construction, and swap have linear complexity if N > 0. An array meets some of the requirements of a sequence container (23.2.4 [sequence.reqmts]). Descriptions are provided here only for operations on array that are not described in one of these tables and for operations where there is additional semantic information.