26 Ranges library [ranges]

26.4 Range requirements [range.req]

26.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 that ranges​::​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 .
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 which ranges​::​begin and ranges​::​end return objects of the same type.
Random access ranges are ranges for which ranges​::​begin returns a type that models random_access_iterator ([iterator.concept.random.access]).
(Contiguous, bidirectional, forward, input, and output ranges are defined similarly.)
Viewable ranges can be converted to views.

26.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 = 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]),
  • both ranges​::​begin(t) and ranges​::​end(t) are amortized constant time and non-modifying, and
  • if the type of ranges​::​begin(t) models forward_iterator, ranges​::​begin(t) is equality-preserving.
[Note 1: 
Equality preservation of both ranges​::​begin and ranges​::​end enables passing a range whose iterator type models forward_iterator to multiple algorithms and making multiple passes over the range by repeated calls to ranges​::​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 = 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 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<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]

26.4.3 Sized ranges [range.sized]

The sized_range concept refines 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 = range<T> && requires(T& t) { ranges::size(t); };
Given an lvalue t of type remove_reference_t<T>, T models 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 of ranges​::​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]

26.4.4 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 = range<T> && movable<T> && enable_view<T>;
T models view only if:
  • T has 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 destruction; and
  • copy_constructible<T> is false, or T has copy construction; and
  • copyable<T> 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 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_ptr and 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 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<T, view_base> || is-derived-from-view-interface<T>;
For a type T, is-derived-from-view-interface<T> is true if and only if T has exactly one public base class view_interface<U> for some type U and T has no base classes of type view_interface<V> for any other type V.
Remarks: Pursuant to [namespace.std], users may specialize enable_view to true for cv-unqualified program-defined types which model view, and false for types which do not.
Such specializations shall be usable in constant expressions ([expr.const]) and have type const bool.

26.4.5 Other range refinements [range.refinements]

The output_range concept specifies requirements of a range type for which ranges​::​begin returns a model of output_iterator ([iterator.concept.output]).
template<class R, class T> concept output_range = range<R> && output_iterator<iterator_t<R>, T>; template<class T> concept input_range = range<T> && input_iterator<iterator_t<T>>; template<class T> concept forward_range = input_range<T> && forward_iterator<iterator_t<T>>; template<class T> concept bidirectional_range = forward_range<T> && bidirectional_iterator<iterator_t<T>>; template<class T> concept random_access_range = bidirectional_range<T> && random_access_iterator<iterator_t<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 = random_access_range<T> && contiguous_iterator<iterator_t<T>> && requires(T& t) { { ranges::data(t) } -> same_as<add_pointer_t<range_reference_t<T>>>; };
Given an expression t such that decltype((t)) is T&, T models contiguous_range only if to_address(​ranges​::​begin(t)) == ranges​::​data(t) is true.
The common_range concept specifies requirements of a range type for which ranges​::​begin and ranges​::​end return objects of the same type.
[Example 1: 
The standard containers ([containers]) model common_range.
β€” end example]
template<class T> concept common_range = range<T> && same_as<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 if remove_cvref_t<R> is a specialization of initializer_list.
The viewable_range concept specifies the requirements of a range type that can be converted to a view safely.
template<class T> concept viewable_range = range<T> && ((view<remove_cvref_t<T>> && constructible_from<remove_cvref_t<T>, T>) || (!view<remove_cvref_t<T>> && (is_lvalue_reference_v<T> || (movable<remove_reference_t<T>> && !is-initializer-list<T>))));
The constant_range concept specifies the requirements of a range type whose elements are not modifiable.
template<class T> concept constant_range = input_range<T> && constant-iterator<iterator_t<T>>;