This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD status.

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.