N4284
revision of N4132
Jens Maurer <[email protected]>
2014-11-07

N4284: 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

Add a new paragraph after 24.2.1 [iterator.requirements.general] paragraph 4:
Iterators that further satisfy the requirements of output iterators are called mutable iterators. Nonmutable iterators are referred to as constant iterators.
Iterators that further satisfy the requirement that, for integral values n and dereferenceable iterator values a and (a + n), *(a + n) is equivalent to *(addressof(*a) + n), are called contiguous iterators. [ Note: For example, the type "pointer to int" is a contiguous iterator, but reverse_iterator<int *> is not. For a valid iterator range [a, b) with dereferenceable a, the corresponding range denoted by pointers is [addressof(*a), 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]). A basic_string is a contiguous container (23.2.1 [container.requirements.general]).
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().
Add a new paragraph after 23.2.1 [container.requirements.general] paragraph 12:
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.
A contiguous container is a container that supports random access iterators (24.2.7 [random.access.iterators]) and whose member types iterator and const_iterator are contiguous iterators (24.2.1 [iterator.requirements.general]).
Change in 23.3.2.1 [array.overview] paragraph 1:
... An array supports random access iterators is a contiguous container. ... 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] paragraphs 1 and 2:
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. ... 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().

A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.2), of a sequence container, including most of the optional sequence container requirements (23.2.3 [sequence.reqmts]), and of an allocator-aware container (Table 99), and, for an element type other than bool, of a contiguous container (23.2.1 [container.requirements.general]). The exceptions are ...

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]) and of a contiguous iterator (24.2.1 iterator.requirements.general]) 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]) and of a contiguous iterator (24.2.1 [iterator.requirements.general]) 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 and contiguous iterator type such that, for a const_iterator it, if &*(it+N) is valid, then it is equal to (&*it)+N.
]