1042. Provide ContiguousStorage concept and apply it to corresponding containers

Section: 23.3 [sequences] Status: NAD Submitter: Alisdair Meredith Opened: 2009-03-12 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [sequences].

View all issues with NAD status.

Discussion:

Addresses UK 244 [CD1]

The validity of the expression &a[n] == &a[0] + n is contingent on operator& doing the "right thing" (as captured by the CopyConstructible requirements in table 30 in C++2003). However this constraint has been lost in the Concepts of C++0x. This applies to vector and array (it actually applies to string also, but that's a different chapter, so I'll file a separate comment there and cross-reference).

Suggested solution:

Define a ContiguousStorage and apply it to vector, array and string.

[ Summit: ]

Agree with the issue but not the details of the proposed solution. Walter to provide wording for the new concept.

[ Post Summit Alisdair adds: ]

Another LWG subgroup wondered if this concept should extend to complex<T>, and so not be built on the container concept at all?

[ 2009-07 post-Frankfurt: ]

Leave Open, pending a post-Concepts Working Draft.

[ 2009-10 Santa Cruz: ]

Mark issue 1042 as NAD, in rationale state that this was solved by removal of concepts.

Proposed resolution:

Add to <container_concepts> synopsis in [container.concepts]

concept< typename C > ContiguousStorageContainer see below;

Add a new section to the end of [container.concepts]

23.1.6.x ContiguousStorageContainer concept [container.concepts.contiguous]

concept ContiguousStorageContainer< typename C >
  : Container<C>
{
  value_type* data(C&);

  axiom Contiguity(C& c, size_type i) {
    if( i < size(c) ) {
         addressof( * (data(c) + i) )
      == addressof( * advance(data(c), i) );
    }
  }
}

The ContiguousStorageContainer concept describes a container whose elements are allocated in a single region of memory, and are stored sequentially without intervening padding other than to meet alignment requirements. For example, the elements may be stored in a single array of suitable length.

value_type * data( C& );

Returns: a pointer to the first element in the region of storage. Result is unspecified for an empty container.

Change 23.3.3 [array] p1:

-1- The header <array> defines a class template for storing fixed-size sequences of objects. An array supports random access iterators. An instance of array<T, N> stores N elements of type T, so that size() == N is an invariant. The elements of an array are stored contiguously, meaning that if a is an array<T, N> then it obeys the identity &a[n] == &a[0] + n for all 0 <= n < N satisfies the concept ContiguousStorageContainer< array<T, N>>.

Add to the synopsis in 23.3.3 [array]:

    ...
    T * data(); 
    const T * data() const; 
  };

  template< typename T, size_t N >
    concept_map ContiguousStorageContainer< array<T, N>> {};
} 

Change 23.3.11 [vector] p1:

A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Alloc> (where T is some type other than bool), then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size() satisfies the concept ContiguousStorageContainer< vector< T, Alloc>>.

Add at the end of the synopsis in 23.3.11 [vector] p2:

template< typename T, typename A >
  requires !SameType< T, bool >
  concept_map ContiguousStorageContainer< vector<T, A>> {};

Rationale:

Solved by removal of concepts.