[range.req] (original) (raw)

25 Ranges library [ranges]

25.4 Range requirements [range.req]

25.4.1 General [range.req.general]

25.4.2 Ranges [range.range]

25.4.3 Approximately sized ranges [range.approximately.sized]

25.4.4 Sized ranges [range.sized]

25.4.5 Views [range.view]

25.4.1 General [range.req.general]

Ranges are an abstraction that allows a C++ program to operate on elements of data structures uniformly.

Calling ranges::end on a range returns an object whose type S, together with the type I of the object returned by ranges::begin, models sentinel_for<S, I>.

The library formalizes the interfaces, semantics, and complexity of ranges to enable algorithms and range adaptors that work efficiently on different types of sequences.

The range concept requires thatranges::begin and ranges::endreturn an iterator and a sentinel, respectively.

The sized_range concept refines range with the requirement that ranges::size be amortized .

The view concept specifies requirements on a range type to provide operations with predictable complexity.

Several refinements of range group requirements that arise frequently in concepts and algorithms.

Common ranges are ranges for whichranges::begin and ranges::endreturn objects of the same type.

(Contiguous, bidirectional, forward, input, and output ranges are defined similarly.)

Viewable ranges can be converted to views.

25.4.2 Ranges [range.range]

The range concept defines the requirements of a type that allows iteration over its elements by providing an iterator and sentinel that denote the elements of the range.

template<class T> concept [range](#concept:range "25.4.2 Ranges [range.range]") = requires(T& t) { ranges::begin(t); // sometimes equality-preserving (see below) ranges::end(t);};

Given an expression t such that decltype((t)) is T&,T models range only if

[ranges::begin(t), ranges::end(t)) denotes a range ([iterator.requirements.general]),
bothranges::begin(t)andranges::end(t)are amortized constant time and non-modifying, and
if the type of ranges::begin(t) modelsforward_iterator, ranges::begin(t) is equality-preserving.

[Note 1:

Equality preservation of both ranges::begin andranges::end enables passing a range whose iterator type models forward_iterator to multiple algorithms and making multiple passes over the range by repeated calls toranges::begin and ranges::end.

Since ranges::begin is not required to be equality-preserving when the return type does not model forward_iterator, it is possible for repeated calls to not return equal values or to not be well-defined.

— _end note_]

template<class T> concept [borrowed_range](#concept:borrowed%5Frange "25.4.2 Ranges [range.range]") = [range](#concept:range "25.4.2 Ranges [range.range]")<T> && (is_lvalue_reference_v<T> || enable_borrowed_range<remove_cvref_t<T>>);

Let U be remove_reference_t<T>if T is an rvalue reference type, and T otherwise.

Given a variable u of type U,T models borrowed_range only if the validity of iterators obtained from uis not tied to the lifetime of that variable.

[Note 2:

Since the validity of iterators is not tied to the lifetime of a variable whose type models borrowed_range, a function with a parameter of such a type can return iterators obtained from it without danger of dangling.

— _end note_]

template<class> constexpr bool enable_borrowed_range = false;

Remarks: Pursuant to [namespace.std], users may specialize enable_borrowed_rangefor cv-unqualified program-defined types.

Such specializations shall be usable in constant expressions ([expr.const]) and have type const bool.

[Example 1:

Each specialization S of class template subrange ([range.subrange]) models borrowed_range because

enable_borrowed_range<S> is specialized to have the value true, and
S's iterators do not have validity tied to the lifetime of an S object because they are “borrowed” from some other range.

— _end example_]

25.4.3 Approximately sized ranges [range.approximately.sized]

The approximately_sized_range concept refines rangewith the requirement that an approximation of the number of elements in the range can be determined in amortized constant time using ranges::reserve_hint.

template<class T> concept [approximately_sized_range](#concept:approximately%5Fsized%5Frange "25.4.3 Approximately sized ranges [range.approximately.sized]") = [range](#concept:range "25.4.2 Ranges [range.range]")<T> && requires(T& t) { ranges::reserve_hint(t); };

Given an lvalue t of type remove_reference_t<T>,T models approximately_sized_range only if

ranges::reserve_hint(t) is amortized , does not modify t, and has a value that is not negative and is representable in range_difference_t<T>, and
if iterator_t<T> models forward_iterator,ranges::reserve_hint(t) is well-defined regardless of the evaluation of ranges::begin(t).
[Note 1:
ranges::reserve_hint(t) is otherwise not required to be well-defined after evaluating ranges::begin(t).
For example, it is possible for ranges::reserve_hint(t) to be well-defined for an approximately_sized_range whose iterator type does not model forward_iteratoronly if evaluated before the first call to ranges::begin(t).
— _end note_]

25.4.4 Sized ranges [range.sized]

The sized_range concept refines approximately_sized_range with the requirement that the number of elements in the range can be determined in amortized constant time using ranges::size.

template<class T> concept [sized_range](#concept:sized%5Frange "25.4.4 Sized ranges [range.sized]") = [approximately_sized_range](#concept:approximately%5Fsized%5Frange "25.4.3 Approximately sized ranges [range.approximately.sized]")<T> && requires(T& t) { ranges::size(t); };

Given an lvalue t of type remove_reference_t<T>, Tmodels sized_range only if

ranges::size(t) is amortized , does not modify t, and is equal to ranges::distance(ranges::begin(t), ranges::end(t)), and
if iterator_t<T> models forward_iterator,ranges::size(t) is well-defined regardless of the evaluation ofranges::begin(t).
[Note 1:
ranges::size(t) is otherwise not required to be well-defined after evaluating ranges::begin(t).
For example, it is possible for ranges::size(t) to be well-defined for a sized_range whose iterator type does not model forward_iteratoronly if evaluated before the first call to ranges::begin(t).
— _end note_]

template<class> constexpr bool disable_sized_range = false;

Remarks: Pursuant to [namespace.std], users may specialize disable_sized_rangefor cv-unqualified program-defined types.

Such specializations shall be usable in constant expressions ([expr.const]) and have type const bool.

[Note 2:

disable_sized_range allows use of range types with the library that satisfy but do not in fact model sized_range .

— _end note_]

25.4.5 Views [range.view]

The view concept specifies the requirements of a range type that has the semantic properties below, which make it suitable for use in constructing range adaptor pipelines ([range.adaptors]).

template<class T> concept [view](#concept:view "25.4.5 Views [range.view]") = [range](#concept:range "25.4.2 Ranges [range.range]")<T> && [movable](concepts.object#concept:movable "18.6 Object concepts [concepts.object]")<T> && enable_view<T>;

T models view only if

T has move construction; and
move assignment of an object of type Tis no more complex than destruction followed by move construction; and
if N copies and/or moves are made from an object of type Tthat contained M elements, then those N objects have destruction; and
copy_constructible<T> is false, orT has copy construction; and
copyable<T> is false, or copy assignment of an object of type Tis no more complex than destruction followed by copy construction.

[Note 1:

The constraints on copying and moving imply that a moved-from object of type T has destruction.

— _end note_]

[Example 1:

Examples of views are:

A range type that wraps a pair of iterators.
A range type that holds its elements by shared_ptrand shares ownership with all its copies.
A range type that generates its elements on demand.

A container such as vector<string>does not meet the semantic requirements of viewsince copying the container copies all of the elements, which cannot be done in constant time.

— _end example_]

Since the difference between range and view is largely semantic, the two are differentiated with the help of enable_view.

template<class T> constexpr bool _is-derived-from-view-interface_ = _see below_; // _exposition only_ template<class T> constexpr bool enable_view = [derived_from](concept.derived#concept:derived%5Ffrom "18.4.3 Concept derived_from [concept.derived]")<T, view_base> || _is-derived-from-view-interface_<T>;

For a type T,is-derived-from-view-interface<T> is trueif and only ifT has exactly one public base class view_interface<U>for some type U andT has no base classes of type view_interface<V>for any other type V.

Remarks: Pursuant to [namespace.std], users may specialize enable_viewto truefor cv-unqualified program-defined types that model view, and false for types that do not.

Such specializations shall be usable in constant expressions ([expr.const]) and have type const bool.

input_range, forward_range, bidirectional_range, and random_access_range are defined similarly.

contiguous_range additionally requires that the ranges::data customization point object ([range.prim.data]) is usable with the range.

template<class T> concept [contiguous_range](#concept:contiguous%5Frange "25.4.6 Other range refinements [range.refinements]") = [random_access_range](#concept:random%5Faccess%5Frange "25.4.6 Other range refinements [range.refinements]")<T> && [contiguous_iterator](iterator.concept.contiguous#concept:contiguous%5Fiterator "24.3.4.14 Concept contiguous_iterator [iterator.concept.contiguous]")<iterator_t<T>> && requires(T& t) { { ranges::data(t) } -> [same_as](concept.same#concept:same%5Fas "18.4.2 Concept same_as [concept.same]")<add_pointer_t<range_reference_t<T>>>;};

Given an expression t such that decltype((t)) is T&,T models contiguous_range only ifto_address(ranges::begin(t)) == ranges::data(t)is true.

The common_range concept specifies requirements of a range type for which ranges::begin andranges::end return objects of the same type.

[Example 1:

— _end example_]

template<class T> concept [common_range](#concept:common%5Frange "25.4.6 Other range refinements [range.refinements]") = [range](#concept:range "25.4.2 Ranges [range.range]")<T> && [same_as](concept.same#concept:same%5Fas "18.4.2 Concept same_as [concept.same]")<iterator_t<T>, sentinel_t<T>>;

template<class R> constexpr bool _is-initializer-list_ = _see below_; // _exposition only_

For a type R,is-initializer-list<R> is true if and only ifremove_cvref_t<R> is a specialization of initializer_list.

The viewable_range concept specifies the requirements of arange type that can be converted to a view safely.

template<class T> concept [viewable_range](#concept:viewable%5Frange "25.4.6 Other range refinements [range.refinements]") = [range](#concept:range "25.4.2 Ranges [range.range]")<T> && (([view](#concept:view "25.4.5 Views [range.view]")<remove_cvref_t<T>> && [constructible_from](concept.constructible#concept:constructible%5Ffrom "18.4.11 Concept constructible_from [concept.constructible]")<remove_cvref_t<T>, T>) || (![view](#concept:view "25.4.5 Views [range.view]")<remove_cvref_t<T>> && (is_lvalue_reference_v<T> || ([movable](concepts.object#concept:movable "18.6 Object concepts [concepts.object]")<remove_reference_t<T>> && !_is-initializer-list_<T>))));

The constant_range concept specifies the requirements of arange type whose elements are not modifiable.

The exposition-only concept sized-random-access-rangespecifies the requirements of a range type that is sized and allows random access to its elements.

template<class T> concept [_sized-random-access-range_](#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") = // _exposition only_ [random_access_range](#concept:random%5Faccess%5Frange "25.4.6 Other range refinements [range.refinements]")<T> && [sized_range](#concept:sized%5Frange "25.4.4 Sized ranges [range.sized]")<T>;

[Note 1:

This concept constrains some parallel algorithm overloads; see [algorithms].

— _end note_]