28 KiB
[range.req]
25 Ranges library [ranges]
25.4 Range requirements [range.req]
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::begin on a range returns an object whose type models input_or_output_iterator ([iterator.concept.iterator]).
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::end return an iterator and a sentinel, respectively.
The sized_range concept refines range with the requirement that ranges::size be amortized O(1).
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::end return objects of the same type.
Random access ranges are ranges for which ranges::begin returns a type that modelsrandom_access_iterator ([iterator.concept.random.access]).
(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_range "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 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 u is 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_range for 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 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 range with 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_sized_range "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 models approximately_sized_range only if
ranges::reserve_hint(t) is amortized O(1), does not modify t, and has a value that is not negative and is representable in range_difference_t, and
if iterator_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_iterator only 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_range "25.4.4 Sized ranges [range.sized]") = [approximately_sized_range](#concept:approximately_sized_range "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 models sized_range only if
ranges::size(t) is amortized O(1), does not modify t, and is equal to ranges::distance(ranges::begin(t), ranges::end(t)), and
if iterator_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_iterator only 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_range for 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 O(1) move construction; and
move assignment of an object of type T is no more complex than destruction followed by move construction; and
if N copies and/or moves are made from an object of type T that contained M elements, then those N objects have O(N+M) destruction; and
copy_constructible is false, orT has O(1) copy construction; and
copyable is false, or copy assignment of an object of type T is 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 O(1) destruction.
â end note]
[Example 1:
Examples of views are:
A container such as vector does not meet the semantic requirements of view since 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_from "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 is true if and only ifT has exactly one public base class view_interface for some type U andT has no base classes of type view_interface for any other type V.
Remarks: Pursuant to [namespace.std], users may specialize enable_view to true for 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.
25.4.6 Other range refinements [range.refinements]
The output_range concept specifies requirements of arange type for which ranges::begin returns a model of output_iterator ([iterator.concept.output]).
input_range, forward_range, bidirectional_range, and random_access_range are defined similarly.
`template<class R, class T> concept output_range = range && output_iterator<iterator_t, T>;
template concept input_range = range && input_iterator<iterator_t>;
template concept forward_range = input_range && forward_iterator<iterator_t>;
template concept bidirectional_range = forward_range && bidirectional_iterator<iterator_t>;
template concept random_access_range = bidirectional_range && random_access_iterator<iterator_t>; `
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_range "25.4.6 Other range refinements [range.refinements]") = [random_access_range](#concept:random_access_range "25.4.6 Other range refinements [range.refinements]")<T> && [contiguous_iterator](iterator.concept.contiguous#concept:contiguous_iterator "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_as "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:
The standard containers ([containers]) model common_range.
â end example]
template<class T> concept [common_range](#concept:common_range "25.4.6 Other range refinements [range.refinements]") = [range](#concept:range "25.4.2 Ranges [range.range]")<T> && [same_as](concept.same#concept:same_as "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 is true if and only ifremove_cvref_t 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_range "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_from "18.4.11 Concept constructible_from [concept.constructible]")<remove_cvref_t<T>, T>) || (<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.
template<class T> concept [constant_range](#concept:constant_range "25.4.6 Other range refinements [range.refinements]") = [input_range](#concept:input_range "25.4.6 Other range refinements [range.refinements]")<T> && [constant-iterator](const.iterators.alias#concept:constant-iterator "24.5.3.2 Alias templates [const.iterators.alias]")<iterator_t<T>>;
The exposition-only concept sized-random-access-range specifies 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_access_range "25.4.6 Other range refinements [range.refinements]")<R> && [sized_range](#concept:sized_range "25.4.4 Sized ranges [range.sized]")<R>;
[Note 1:
This concept constrains some parallel algorithm overloads; see [algorithms].
â end note]