1034. Clarify generality of Container Requirement tables

Section: 23.2.2 [container.requirements.general] Status: C++11 Submitter: Alisdair Meredith Opened: 2009-03-12 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [container.requirements.general].

View all other issues in [container.requirements.general].

View all issues with C++11 status.

Discussion:

Addresses UK 222 [CD1]

It is not clear what purpose the Requirement tables serve in the Containers clause. Are they the definition of a library Container? Or simply a conventient shorthand to factor common semantics into a single place, simplifying the description of each subsequent container? This becomes an issue for 'containers' like array, which does not meet the default-construct-to-empty requirement, or forward_list which does not support the size operation. Are these components no longer containers? Does that mean the remaining requirements don't apply? Or are these contradictions that need fixing, despite being a clear design decision?

Recommend:

Clarify all the tables in 23.2 [container.requirements] are there as a convenience for documentation, rather than a strict set of requirements. Containers should be allowed to relax specific requirements if they call attention to them in their documentation. The introductory text for array should be expanded to mention a default constructed array is not empty, and forward_list introduction should mention it does not provide the required size operation as it cannot be implemented efficiently.

[ Summit: ]

Agree in principle.

[ 2009-07 post-Frankfurt: ]

We agree in principle, but we have a timetable. This group feels that the issue should be closed as NAD unless a proposed resolution is submitted prior to the March 2010 meeting.

[ 2009-10 Santa Cruz: ]

Looked at this and still intend to close as NAD in March 2010 unless there is proposed wording that we like.

[ 2010-02-02 Nicolai M. Josuttis updates proposed wording and adds: ]

I just came across issue #1034 (response to UK 222), which covers the role of container requirements. The reason I found this issue was that I am wondering why array<> is specified to be a sequence container. For me, currently, this follows from Sequence containers 23.2.4 [sequence.reqmts] saying:

The library provides five basic kinds of sequence containers: array, vector, forward_list, list, and deque. while later on in Table 94 "Sequence container requirements" are defined.

IMO, you can hardly argue that this is NAD. We MUST say somewhere that either array is not a sequence container or does not provide all operations of a sequence container (even not all requirements of a container in general).

Here is the number of requirements array<> does not meet (AFAIK):

general container requirements:

Note also that swap not only has linear complexity it also invalidates iterators (or to be more precise, assigns other values to the elements), which is different from the effect swap has for other containers. For this reason, I must say that i tend to propose to remove swap() for arrays.

sequence container requirements:

In fact, out of all sequence container requirements array<> only provides the following operations: from sequence requirements (Table 94): 

X(il);
a = il;

and from optional requirements (Table 95): 

[], at(), front(), back()

This is almost nothing!

Note in addition, that due to the fact that array is an aggregate and not a container with initializer_lists a construction or assignment with an initializer list is valid for all sequence containers but not valid for array: 

vector<int>  v({1,2,3});   // OK
v = {4,5,6};               // OK

array<int,3> a({1,2,3});   // Error
array<int,3> a = {1,2,3};  // OK
a = {4,5,6};               // Error

BTW, for this reason, I am wondering, why <array> includes <initializer_list>.

IMO, we can't really say that array is a sequence container. array is special. As the solution to this issue seemed to miss some proposed wording where all could live with, let me try to suggest some.

[ 2010-02-12 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

[ 2010 Pittsburgh: Ok with move to Ready except for "OPEN:" part. ]

Proposed resolution:

In Sequence containers 23.2.4 [sequence.reqmts] modify paragraph 1 as indicated:

1 A sequence container organizes a finite set of objects, all of the same type, into a strictly linear arrangement. The library provides five four basic kinds of sequence containers: array, vector, forward_list, list, and deque. In addition, array is provided as a sequence container that only provides limited sequence operations because it has a fixed number of elements. It The library also provides container adaptors that make it easy to construct abstract data types, such as stacks or queues, out of the basic sequence container kinds (or out of other kinds of sequence containers that the user might define).

Modify paragraph 2 as follows (just editorial):

2 The five basic sequence containers offer the programmer different complexity trade-offs and should be used accordingly. vector or array is the type of sequence container that should be used by default. list or forward_list should be used when there are frequent insertions and deletions from the middle of the sequence. deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

In Class template array 23.3.3 [array] modify paragraph 3 as indicated:

3 Unless otherwise specified, all array operations are as described in 23.2. An array satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.2 [container.requirements]) except that a default constructed array is not empty, swap does not have constant complexity, and swap may throw exceptions. An array satisfies some of the requirements of a sequence container (given in 23.2.4 [sequence.reqmts]). Descriptions are provided here only for operations on array that are not described in that Clause in one of these tables or for operations where there is additional semantic information.

In array specialized algorithms 23.3.3.4 [array.special] add to the specification of swap(): 

template <class T, size_t N> void swap(array<T,N>& x, array<T,N>& y);

1 Effects: ...

Complexity: Linear in N.