N4132
Jens Maurer
2014-09-10

N4132: Contiguous Iterators

Introduction

There are four containers in the standard library that guarantee contiguous storage: vector, string, valarray, and array. In the Library Fundamentals TS, there is also string_view. This paper introduces the term "contiguous iterator" as a refinement of random-access iterator, without introducing a corresponding contiguous_iterator_tag, which was found to break code during the Issaquah discussions of Nevin Liber's paper N3884 "Contiguous Iterators: A Refinement of Random Access Iterators".

Wording Changes

Change in 24.2.1 [iterator.requirements.general] paragraph 2 and adjust the table accordingly:
... This International Standard defines five six categories of iterators, according to the operations defined on them: input iterators, output iterators, forward iterators, bidirectional iterators, and random access iterators, and contiguous iterators, as shown in Table 105.
Add a new subsection 24.2.8 [contiguous.iterators]:
24.2.8 Contiguous iterators [contiguous.iterators]

A class or pointer type X satisfies the requirements of a contiguous iterator if, in addition to satisfying the requirements for random access iterators, for dereferenceable a and (a + n), *(a + n) is equivalent to *(std::addressof(*a) + n). [ Note: For a valid iterator range [a, b) with dereferenceable a, the corresponding range denoted by pointers is [std::addressof(*a), std::addressof(*a) + (b-a) ); b might not be dereferenceable. -- end note ]

Change in 21.4 [basic.string] paragraph 3:
The iterators supported by basic_string are random access iterators (24.2.7 [random.access.iterators]). In addition, the member types iterator and const_iterator are contiguous iterators (24.2.8 [contiguous.iterators]).
Delete in 21.4.1 [string.require] paragraph 4:
The char-like objects in a basic_string object shall be stored contiguously. That is, for any basic_string object s, the identity &*(s.begin() + n) == &*s.begin() + n shall hold for all values of n such that 0 <= n < s.size().
Change in 23.3.2.1 [array.overview] paragraph 1:
... An array supports random access iterators (24.2.7 [random.access.iterators]). In addition, the member types iterator and const_iterator are contiguous iterators (24.2.8 [contiguous.iterators]). ... 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.
Change in 23.3.6.1 [vector.overview] paragraph 1:
A vector is a sequence container that supports random access iterators (24.2.7 [random.access.iterators]). In addition, the member types iterator and const_iterator are contiguous iterators (24.2.8 [contiguous.iterators]). ... The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type otherthan bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().
Change in 26.6.10 [valarray.range] paragraph 1:
In the begin and end function templates that follow, unspecified1 is a type that meets the requirements of a mutable random access iterator (24.2.7 [random.access.iterators]) contiguous iterator (24.2.8 [contiguous.iterators]) whose value_type is the template parameter T and whose reference type is T&. unspecified2 is a type that meets the requirements of a constant random access iterator (24.2.7 [random.access.iterators]) contiguous iterator (24.2.8 [contiguous.iterators]) whose value_type is the template parameter T and whose reference type is const T&.
[ Drafting note: In the library fundamentals TS, section 7.4, replace 
typedef implementation-defined const_iterator;
A constant random-access contiguous iterator type such that, for a const_iterator it, if &*(it+N) is valid, then it is equal to (&*it)+N.
]