24 Ranges library [ranges]

24.4 Range requirements [range.req]

24.4.1 General [range.req.general]

Ranges are an abstraction that allow 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 the number of elements in the range can be determined in constant time using the ranges​::​size function.
The view concept specifies requirements on a range type with constant-time destruction and move operations.
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.

24.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); };
The required expressions ranges​::​begin(t) and ranges​::​end(t) of the range concept do not require implicit expression variations ([concepts.equality]).
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
:
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, repeated calls might not return equal values or might not be well-defined; ranges​::​begin should be called at most once for such a range.
β€” end note
 ]
template<class T> concept safe_­range = range<T> && (is_lvalue_reference_v<T> || enable_safe_range<remove_cvref_t<T>>);
Given an expression E such that decltype((E)) is T, T models safe_­range only if the validity of iterators obtained from the object denoted by E is not tied to the lifetime of that object.
Note
:
Since the validity of iterators is not tied to the lifetime of an object whose type models safe_­range, a function can accept arguments of such a type by value and return iterators obtained from it without danger of dangling.
β€” end note
 ]
template<class> inline constexpr bool enable_safe_range = false;
Remarks: Pursuant to [namespace.std], users may specialize enable_­safe_­range for cv-unqualified program-defined types.
Such specializations shall be usable in constant expressions ([expr.const]) and have type const bool.
Example
:
Each specialization S of class template subrange ([range.subrange]) models safe_­range because
  • enable_­safe_­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
 ]

24.4.3 Sized ranges [range.sized]

The sized_­range concept specifies the requirements of a range type that knows its size in constant time with the size function.
template<class T> concept sized_­range = range<T> && !disable_sized_range<remove_cvref_t<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 , does not modify t, and is equal to ranges​::​distance(t), and
  • if iterator_­t<T> models forward_­iterator, ranges​::​size(t) is well-defined regardless of the evaluation of ranges​::​begin(t).
    Note
    : ranges​::​size(t) is otherwise not required to be well-defined after evaluating ranges​::​begin(t). For example, ranges​::​size(t) might 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
     ]
Note
:
The complexity requirement for the evaluation of ranges​::​size is non-amortized, unlike the case for the complexity of the evaluations of ranges​::​begin and ranges​::​end in the range concept.
β€” end note
 ]
template<class> inline 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
:
disable_­sized_­range allows use of range types with the library that satisfy but do not in fact model sized_­range.
β€” end note
 ]

24.4.4 Views [range.view]

The view concept specifies the requirements of a range type that has constant time move construction, move assignment, and destruction; that is, the cost of these operations is independent of the number of elements in the view.
template<class T> concept view = range<T> && movable<T> && default_constructible<T> && enable_view<T>;
T models view only if:
  • T has move construction; and
  • T has move assignment; and
  • T has destruction; and
  • copy_­constructible<T> is false, or T has copy construction; and
  • copyable<T> is false, or T has copy assignment.
Example
:
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.
Most containers are not views since destruction of the container destroys 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> inline constexpr bool enable_view = see below;
Remarks: For a type T, the default value of enable_­view<T> is:
  • If derived_­from<T, view_­base> is true, true.
  • Otherwise, if T is a specialization of class template initializer_­list ([support.initlist]), set ([set]), multiset ([multiset]), unordered_­set ([unord.set]), unordered_­multiset ([unord.multiset]), or match_­results ([re.results]), false.
  • Otherwise, if both T and const T model range and range_­reference_­t<T> is not the same type as range_­reference_­t<const T>, false.
    Note
    : Deep const-ness implies element ownership, whereas shallow const-ness implies reference semantics. β€” end note
     ]
  • Otherwise, true.
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.

24.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]).
input_­range, forward_­range, bidirectional_­range, and random_­access_­range are defined similarly.
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 ([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>>>; };
The common_­range concept specifies requirements of a range type for which ranges​::​begin and ranges​::​end return objects of the same type.
Example
:
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>>;
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> && (safe_range<T> || view<decay_t<T>>);