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 copy and assign 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-impl = // exposition only requires(T&& t) { ranges::begin(std::forward<T>(t)); // sometimes equality-preserving (see below) ranges::end(std::forward<T>(t)); }; template<class T> concept range = range-impl<T&>; template<class T> concept forwarding-range = // exposition only range<T> && range-impl<T>;
The required expressions ranges​::​begin(std​::​forward<T>(t)) and ranges​::​end(std​::​forward<​T>(t)) of the range-impl concept do not require implicit expression variations ([concepts.equality]).
Given an expression E such that decltype((E)) is T, T models range-impl only if
  • [ranges​::​begin(E), ranges​::​end(E)) denotes a range ([iterator.requirements.general]),
  • both ranges​::​begin(E) and ranges​::​end(E) are amortized constant time and non-modifying, and
  • if the type of ranges​::​begin(E) models forward_­iterator, ranges​::​begin(E) 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
 ]
Given an expression E such that decltype((E)) is T and an lvalue t that denotes the same object as E, T models forwarding-range only if
  • ranges​::​begin(E) and ranges​::​begin(t) are expression-equivalent,
  • ranges​::​end(E) and ranges​::​end(t) are expression-equivalent, and
  • 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 forwarding-range, a function can accept arguments of such a type by value and return iterators obtained from it without danger of dangling.
β€” end note
 ]
Example
:
Specializations of class template subrange ([range.subrange]) model forwarding-range.
subrange provides non-member rvalue overloads of begin and end with the same semantics as its member lvalue overloads, and subrange's iterators – since they are β€œborrowed” from some other range – do not have validity tied to the lifetime of a subrange object.
β€” 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]

template<class T> concept view = range<T> && semiregular<T> && enable_view<T>;
The view concept specifies the requirements of a range type that has constant time copy, move, and assignment operators; that is, the cost of these operations is not proportional to the number of elements in the view.
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 copying the container copies 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> && (forwarding-range<T> || view<decay_t<T>>);