Ranges are an abstraction of containers that allow a C++ program to operate on elements of data structures uniformly. It their simplest form, a range object is one on which one can call begin and end to get an iterator ([iterators.iterator]) and a sentinel ([iterators.sentinel]). To be able to construct template algorithms and range adaptors that work correctly and efficiently on different types of sequences, the library formalizes not just the interfaces but also the semantics and complexity assumptions of ranges.
This document defines three fundamental categories of ranges based on the syntax and semantics supported by each: range, sized range and view, as shown in Table [tab:ranges.relations].
The Range concept requires only that begin and end return an iterator and a sentinel. The SizedRange concept refines Range with the requirement that the number of elements in the range can be determined in constant time using the size function. The View concept specifies requirements on a Range type with constant-time copy and assign operations.
In addition to the three fundamental range categories, this document defines a number of convenience refinements of Range that group together requirements that appear often in the concepts and algorithms. Bounded ranges are ranges for which begin and end return objects of the same type. Random access ranges are ranges for which begin returns a type that satisfies RandomAccessIterator ([iterators.random.access]). The range categories bidirectional ranges, forward ranges, input ranges, and output ranges are defined similarly.
The Range concept defines the requirements of a type that allows iteration over its elements by providing a begin iterator and an end sentinel. [ Note: Most algorithms requiring this concept simply forward to an Iterator-based algorithm by calling begin and end. — end note ]
template <class T>
concept bool Range =
requires(T&& t) {
ranges::begin(t); // not necessarily equality-preserving (see below)
ranges::end(t);
};
Given an lvalue t of type remove_reference_t<T>, Range<T> is satisfied only if
[begin(t),end(t)) denotes a range.
Both begin(t) and end(t) are amortized constant time and non-modifying. [ Note: begin(t) and end(t) do not require implicit expression variations ([concepts.lib.general.equality]). — end note ]
If iterator_t<T> satisfies ForwardIterator, begin(t) is equality preserving.
[ Note: Equality preservation of both begin and end enables passing a Range whose iterator type satisfies ForwardIterator to multiple algorithms and making multiple passes over the range by repeated calls to begin and end. Since begin is not required to be equality preserving when the return type does not satisfy ForwardIterator, repeated calls might not return equal values or might not be well-defined; begin should be called at most once for such a range. — end note ]
The SizedRange concept specifies the requirements of a Range type that knows its size in constant time with the size function.
template <class T>
concept bool SizedRange =
Range<T> &&
!disable_sized_range<remove_cv_t<remove_reference_t<T>>> &&
requires(T& t) {
{ ranges::size(t) } -> ConvertibleTo<difference_type_t<iterator_t<T>>>;
};
Given an lvalue t of type remove_reference_t<T>, SizedRange<T> is satisfied only if:
ranges::size(t) is Ο(1), does not modify t, and is equal to ranges::distance(t).
If iterator_t<T> satisfies ForwardIterator, size(t) is well-defined regardless of the evaluation of begin(t). [ Note: size(t) is otherwise not required be well-defined after evaluating begin(t). For a SizedRange whose iterator type does not model ForwardIterator, for example, size(t) might only be well-defined if evaluated before the first call to begin(t). — end note ]
[ Note: The disable_sized_range predicate provides a mechanism to enable use of range types with the library that meet the syntactic requirements but do not in fact satisfy SizedRange. A program that instantiates a library template that requires a Range with such a range type R is ill-formed with no diagnostic required unless disable_sized_range<remove_cv_t<remove_reference_t<R>>> evaluates to true ([structure.requirements]). — end note ]
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.
A container ( ISO/IEC 14882:2014 §[containers]) is not a View since copying the container copies the elements, which cannot be done in constant time. — end example ]
template <class T>
constexpr bool view-predicate // exposition only
= see below;
template <class T>
concept bool View =
Range<T> &&
Semiregular<T> &&
view-predicate<T>;
Since the difference between Range and View is largely semantic, the two are differentiated with the help of the enable_view trait. Users may specialize enable_view to derive from true_type or false_type.
For a type T, the value of view-predicate<T> shall be:
If enable_view<T> has a member type type, enable_view<T>::type::value;
Otherwise, if T is derived from view_base, true;
Otherwise, if T is an instantiation of class template initializer_list ( ISO/IEC 14882:2014 §[support.initlist]), set ( ISO/IEC 14882:2014 §[set]), multiset ( ISO/IEC 14882:2014 §[multiset]), unordered_set ( ISO/IEC 14882:2014 §[unord.set]), or unordered_multiset ( ISO/IEC 14882:2014 §[unord.multiset]), false;
Otherwise, if both T and const T satisfy Range and reference_t<iterator_t<T>> is not the same type as reference_t<iterator_t<const T>>, false; [ Note: Deep const-ness implies element ownership, whereas shallow const-ness implies reference semantics. — end note ]
Otherwise, true.
The BoundedRange concept specifies requirements of a Range type for which begin and end return objects of the same type. [ Note: The standard containers ( ISO/IEC 14882:2014 §[containers]) satisfy BoundedRange. — end note ]
template <class T> concept bool BoundedRange = Range<T> && Same<iterator_t<T>, sentinel_t<T>>;
The InputRange concept specifies requirements of a Range type for which begin returns a type that satisfies InputIterator ([iterators.input]).
template <class T> concept bool InputRange = Range<T> && InputIterator<iterator_t<T>>;
The OutputRange concept specifies requirements of a Range type for which begin returns a type that satisfies OutputIterator ([iterators.output]).
template <class R, class T> concept bool OutputRange = Range<R> && OutputIterator<iterator_t<R>, T>;
The ForwardRange concept specifies requirements of an InputRange type for which begin returns a type that satisfies ForwardIterator ([iterators.forward]).
template <class T> concept bool ForwardRange = InputRange<T> && ForwardIterator<iterator_t<T>>;
The BidirectionalRange concept specifies requirements of a ForwardRange type for which begin returns a type that satisfies BidirectionalIterator ([iterators.bidirectional]).
template <class T> concept bool BidirectionalRange = ForwardRange<T> && BidirectionalIterator<iterator_t<T>>;
The RandomAccessRange concept specifies requirements of a BidirectionalRange type for which begin returns a type that satisfies RandomAccessIterator ([iterators.random.access]).
template <class T> concept bool RandomAccessRange = BidirectionalRange<T> && RandomAccessIterator<iterator_t<T>>;