[range.utility] (original) (raw)
25 Ranges library [ranges]
25.5 Range utilities [range.utility]
25.5.1 General [range.utility.general]
The components in [range.utility] are general utilities for representing and manipulating ranges.
25.5.2 Helper concepts [range.utility.helpers]
Many of the types in [range.utility] are specified in terms of the following exposition-only concepts:template<class R> concept simple-view = view<R> && range<const R> && same_as<iterator_t<R>, iterator_t<const R>> && same_as<sentinel_t<R>, sentinel_t<const R>>;template<class I> concept has-arrow = input_iterator<I> && (is_pointer_v<I> || requires(const I i) { i.operator->(); });template<class T, class U> concept different-from = <remove_cvref_t<T>, remove_cvref_t<U>>;template<class R> concept range-with-movable-references = input_range<R> && move_constructible<range_reference_t<R>> && move_constructible<range_rvalue_reference_t<R>>;
25.5.3 View interface [view.interface]
25.5.3.1 General [view.interface.general]
The class template view_interface is a helper for defining view-like types that offer a container-like interface.
It is parameterized with the type that is derived from it.
namespace std::ranges { template<class D> requires is_class_v<D> && same_as<D, remove_cv_t<D>> class view_interface { private: constexpr D& derived() noexcept { return static_cast<D&>(*this);} constexpr const D& derived() const noexcept { return static_cast<const D&>(*this);} public: constexpr bool empty() requires sized_range<D> || forward_range<D> { if constexpr (sized_range<D>) return ranges::size(derived()) == 0;else return ranges::begin(derived()) == ranges::end(derived());} constexpr bool empty() const requires sized_range<const D> || forward_range<const D> { if constexpr (sized_range<const D>) return ranges::size(derived()) == 0;else return ranges::begin(derived()) == ranges::end(derived());} constexpr auto cbegin() requires input_range<D> { return ranges::cbegin(derived());} constexpr auto cbegin() const requires input_range<const D> { return ranges::cbegin(derived());} constexpr auto cend() requires input_range<D> { return ranges::cend(derived());} constexpr auto cend() const requires input_range<const D> { return ranges::cend(derived());} constexpr explicit operator bool() requires requires { ranges::empty(derived()); } { return !ranges::empty(derived());} constexpr explicit operator bool() const requires requires { ranges::empty(derived()); } { return !ranges::empty(derived());} constexpr auto data() requires contiguous_iterator<iterator_t<D>> { return to_address(ranges::begin(derived()));} constexpr auto data() const requires range<const D> && contiguous_iterator<iterator_t<const D>> { return to_address(ranges::begin(derived()));} constexpr auto size() requires forward_range<D> && sized_sentinel_for<sentinel_t<D>, iterator_t<D>> { return to-unsigned-like(ranges::end(derived()) - ranges::begin(derived()));} constexpr auto size() const requires forward_range<const D> && sized_sentinel_for<sentinel_t<const D>, iterator_t<const D>> { return to-unsigned-like(ranges::end(derived()) - ranges::begin(derived()));} constexpr decltype(auto) front() requires forward_range<D>;constexpr decltype(auto) front() const requires forward_range<const D>;constexpr decltype(auto) back() requires bidirectional_range<D> && common_range<D>;constexpr decltype(auto) back() const requires bidirectional_range<const D> && common_range<const D>;template<random_access_range R = D> constexpr decltype(auto) operator[](range_difference_t<R> n) { return ranges::begin(derived())[n];} template<random_access_range R = const D> constexpr decltype(auto) operator[](range_difference_t<R> n) const { return ranges::begin(derived())[n];} };}
The template parameter D for view_interface may be an incomplete type.
Before any member of the resulting specialization ofview_interface other than special member functions is referenced, D shall be complete, and model both derived_from<view_interface<D>> and view.
25.5.3.2 Members [view.interface.members]
constexpr decltype(auto) front() requires [forward_range](range.refinements#concept:forward%5Frange "25.4.5 Other range refinements [range.refinements]")<D>;constexpr decltype(auto) front() const requires [forward_range](range.refinements#concept:forward%5Frange "25.4.5 Other range refinements [range.refinements]")<const D>;
Preconditions: !empty() is true.
Effects: Equivalent to: return *ranges::begin(derived());
Preconditions: !empty() is true.
Effects: Equivalent to: return *ranges::prev(ranges::end(derived()));
25.5.4 Sub-ranges [range.subrange]
25.5.4.1 General [range.subrange.general]
The subrange class template combines together an iterator and a sentinel into a single object that models theview concept.
Additionally, it models thesized_range concept when the final template parameter issubrange_kind::sized.
namespace std::ranges { template<class From, class To> concept uses-nonqualification-pointer-conversion = is_pointer_v<From> && is_pointer_v<To> && <remove_pointer_t<From>(*)[], remove_pointer_t<To>(*)[]>;template<class From, class To> concept convertible-to-non-slicing = convertible_to<From, To> &&
<decay_t<From>, decay_t<To>>;template<class T, class U, class V> concept pair-like-convertible-from =
<T> && !is_reference_v<T> && pair-like<T> && constructible_from<T, U, V> && convertible-to-non-slicing<U, tuple_element_t<0, T>> && convertible_to<V, tuple_element_t<1, T>>;template<input_or_output_iterator I, sentinel_for<I> S = I, subrange_kind K = sized_sentinel_for<S, I> ? subrange_kind::sized : subrange_kind::unsized> requires (K == subrange_kind::sized ||
<S, I>) class subrange : public view_interface<subrange<I, S, K>> { private: static constexpr bool StoreSize = K == subrange_kind::sized &&
<S, I>; I begin_ = I(); S end_ = S(); make-unsigned-like-t<iter_difference_t<I>> size_ = 0; public: subrange() requires default_initializable<I> = default;constexpr subrange(convertible-to-non-slicing<I> auto i, S s) requires (!StoreSize);constexpr subrange(convertible-to-non-slicing<I> auto i, S s,make-unsigned-like-t<iter_difference_t<I>> n) requires (K == subrange_kind::sized);template<different-from<subrange> R> requires borrowed_range<R> && convertible-to-non-slicing<iterator_t<R>, I> && convertible_to<sentinel_t<R>, S> constexpr subrange(R&& r) requires (!StoreSize || sized_range<R>);template<borrowed_range R> requires convertible-to-non-slicing<iterator_t<R>, I> && convertible_to<sentinel_t<R>, S> constexpr subrange(R&& r, make-unsigned-like-t<iter_difference_t<I>> n) requires (K == subrange_kind::sized) : subrange{ranges::begin(r), ranges::end(r), n} {} template<different-from<subrange> PairLike> requires pair-like-convertible-from<PairLike, const I&, const S&> constexpr operator PairLike() const;constexpr I begin() const requires copyable<I>;constexpr I begin() requires (
<I>);constexpr S end() const;constexpr bool empty() const;constexpr make-unsigned-like-t<iter_difference_t<I>> size() const requires (K == subrange_kind::sized);constexpr subrange next(iter_difference_t<I> n = 1) const & requires forward_iterator<I>;constexpr subrange next(iter_difference_t<I> n = 1) &&;constexpr subrange prev(iter_difference_t<I> n = 1) const requires bidirectional_iterator<I>;constexpr subrange& advance(iter_difference_t<I> n);};template<input_or_output_iterator I, sentinel_for<I> S> subrange(I, S) -> subrange<I, S>;template<input_or_output_iterator I, sentinel_for<I> S> subrange(I, S, make-unsigned-like-t<iter_difference_t<I>>) -> subrange<I, S, subrange_kind::sized>;template<borrowed_range R> subrange(R&&) -> subrange<iterator_t<R>, sentinel_t<R>,(sized_range<R> || sized_sentinel_for<sentinel_t<R>, iterator_t<R>>) ? subrange_kind::sized : subrange_kind::unsized>;template<borrowed_range R> subrange(R&&, make-unsigned-like-t<range_difference_t<R>>) -> subrange<iterator_t<R>, sentinel_t<R>, subrange_kind::sized>;}
25.5.4.2 Constructors and conversions [range.subrange.ctor]
constexpr subrange([_convertible-to-non-slicing_](#concept:convertible-to-non-slicing "25.5.4.1 General [range.subrange.general]")<I> auto i, S s) requires (!_StoreSize_);
Preconditions: [i, s) is a valid range.
Effects: Initializes begin_ with std::move(i) and end_ withs.
constexpr subrange([_convertible-to-non-slicing_](#concept:convertible-to-non-slicing "25.5.4.1 General [range.subrange.general]")<I> auto i, S s,_make-unsigned-like-t_<iter_difference_t<I>> n) requires (K == subrange_kind::sized);
Preconditions: [i, s) is a valid range, andn == _to-unsigned-like_(ranges::distance(i, s))is true.
Effects: Initializes begin_ with std::move(i) and end_ withs.
If StoreSize is true, initializes size_ withn.
[Note 1:
Accepting the length of the range and storing it to later return fromsize() enables subrange to model sized_range even when it stores an iterator and sentinel that do not modelsized_sentinel_for.
— _end note_]
Effects: Equivalent to:
- If StoreSize is true,subrange(r, static_cast<decltype(_size__)>(ranges::size(r))).
- Otherwise, subrange(ranges::begin(r), ranges::end(r)).
template<[_different-from_](#concept:different-from "25.5.2 Helper concepts [range.utility.helpers]")<subrange> PairLike> requires [_pair-like-convertible-from_](#concept:pair-like-convertible-from "25.5.4.1 General [range.subrange.general]")<PairLike, const I&, const S&> constexpr operator PairLike() const;
Effects: Equivalent to: return PairLike(begin_, end_);
25.5.4.3 Accessors [range.subrange.access]
constexpr I begin() const requires [copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]")<I>;
Effects: Equivalent to: return begin_;
constexpr I begin() requires (<I>);
Effects: Equivalent to: return std::move(begin_);
Effects: Equivalent to: return end_;
constexpr bool empty() const;
Effects: Equivalent to: return begin_ == end_;
constexpr _make-unsigned-like-t_<iter_difference_t<I>> size() const requires (K == subrange_kind::sized);
Effects:
- If StoreSize is true, equivalent to: return size_;
- Otherwise, equivalent to: return to-unsigned-like(end_ - begin_);
constexpr subrange next(iter_difference_t<I> n = 1) const & requires [forward_iterator](iterator.concept.forward#concept:forward%5Fiterator "24.3.4.11 Concept forward_iterator [iterator.concept.forward]")<I>;
Effects: Equivalent to:auto tmp = *this; tmp.advance(n);return tmp;
constexpr subrange next(iter_difference_t<I> n = 1) &&;
Effects: Equivalent to:advance(n);return std::move(*this);
Effects: Equivalent to:auto tmp = *this; tmp.advance(-n);return tmp;
constexpr subrange& advance(iter_difference_t<I> n);
Effects: Equivalent to:if constexpr (bidirectional_iterator<I>) { if (n < 0) { ranges::advance(begin_, n);if constexpr (StoreSize) size_ += to-unsigned-like(-n);return *this;} } auto d = n - ranges::advance(begin_, n, end_);if constexpr (StoreSize) size_ -= to-unsigned-like(d);return *this;
template<size_t N, class I, class S, subrange_kind K> requires ((N == 0 && [copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]")<I>) || N == 1) constexpr auto get(const subrange<I, S, K>& r);template<size_t N, class I, class S, subrange_kind K> requires (N < 2) constexpr auto get(subrange<I, S, K>&& r);
Effects: Equivalent to:if constexpr (N == 0) return r.begin();else return r.end();
25.5.5 Dangling iterator handling [range.dangling]
The type dangling is used together with the template aliasesborrowed_iterator_t and borrowed_subrange_t.
When an algorithm that typically returns an iterator into, or a subrange of, a range argument is called with an rvalue range argument that does not model borrowed_range ([range.range]), the return value possibly refers to a range whose lifetime has ended.
In such cases, the type dangling is returned instead of an iterator or subrange.
namespace std::ranges { struct dangling { constexpr dangling() noexcept = default;constexpr dangling(auto&&...) noexcept {} };}
[Example 1: vector<int> f();auto result1 = ranges::find(f(), 42); static_assert(same_as<decltype(result1), ranges::dangling>);auto vec = f();auto result2 = ranges::find(vec, 42); static_assert(same_as<decltype(result2), vector<int>::iterator>);auto result3 = ranges::find(ranges::subrange{vec}, 42); static_assert(same_as<decltype(result3), vector<int>::iterator>);
The call to ranges::find at #1 returns ranges::danglingsince f() is an rvalue vector; it is possible for the vector to be destroyed before a returned iterator is dereferenced.
However, the calls at #2 and #3 both return iterators since the lvalue vec and specializations of subrangemodel borrowed_range.
— _end example_]
For a type R that models range:
- if R models borrowed_range, thenborrowed_iterator_t<R> denotes iterator_t<R>, andborrowed_subrange_t<R> denotes subrange<iterator_t<R>>;
- otherwise, both borrowed_iterator_t<R> and borrowed_subrange_t<R>denote dangling.
25.5.6 Class template elements_of [range.elementsof]
Specializations of elements_of encapsulate a range and act as a tag in overload sets to disambiguate when a range should be treated as a sequence rather than a single value.
[Example 1: template<bool YieldElements>generator<any> f(ranges::input_range auto&& r) { if constexpr (YieldElements) co_yield ranges::elements_of(r); else co_yield r; } — _end example_]
namespace std::ranges { template<range R, class Allocator = allocator<byte>> struct elements_of { [[no_unique_address]] R range;[[no_unique_address]] Allocator allocator = Allocator();};template<class R, class Allocator = allocator<byte>> elements_of(R&&, Allocator = Allocator()) -> elements_of<R&&, Allocator>;}
25.5.7 Range conversions [range.utility.conv]
25.5.7.1 General [range.utility.conv.general]
The range conversion functions construct an object (usually a container) from a range, by using a constructor taking a range, a from_range_t tagged constructor, or a constructor taking a pair of iterators, or by inserting each element of the range into the default-constructed object.
ranges::to is applied recursively, allowing the conversion of a range of ranges.
[Example 1: string_view str = "the quick brown fox";auto words = views::split(str, ' ') | to<vector<string>>(); — _end example_]
Let reservable-container be defined as follows:template<class Container> constexpr bool reservable-container = sized_range<Container> && requires(Container& c, range_size_t<Container> n) { c.reserve(n);{ c.capacity() } -> same_as<decltype(n)>;{ c.max_size() } -> same_as<decltype(n)>;};
Let container-appendable be defined as follows:template<class Container, class Ref> constexpr bool container-appendable = requires(Container& c, Ref&& ref) { requires (requires { c.emplace_back(std::forward<Ref>(ref)); } || requires { c.push_back(std::forward<Ref>(ref)); } || requires { c.emplace(c.end(), std::forward<Ref>(ref)); } || requires { c.insert(c.end(), std::forward<Ref>(ref)); });};
Let container-append be defined as follows:template<class Container> constexpr auto container-append(Container& c) { return [&c]<class Ref>(Ref&& ref) { if constexpr (requires { c.emplace_back(declval<Ref>()); }) c.emplace_back(std::forward<Ref>(ref));else if constexpr (requires { c.push_back(declval<Ref>()); }) c.push_back(std::forward<Ref>(ref));else if constexpr (requires { c.emplace(c.end(), declval<Ref>()); }) c.emplace(c.end(), std::forward<Ref>(ref));else c.insert(c.end(), std::forward<Ref>(ref));};}
25.5.7.2 ranges::to [range.utility.conv.to]
template<class C, [input_range](range.refinements#concept:input%5Frange "25.4.5 Other range refinements [range.refinements]") R, class... Args> requires (<C>) constexpr C to(R&& r, Args&&... args);
Mandates: C is a cv-unqualified class type.
Returns: An object of type Cconstructed from the elements of r in the following manner:
- If C does not satisfy input_range orconvertible_to<range_reference_t<R>, range_value_t<C>>is true:
- If constructible_from<C, R, Args...> is true:C(std::forward<R>(r), std::forward<Args>(args)...)
- Otherwise, ifconstructible_from<C, from_range_t, R, Args...>is true:C(from_range, std::forward<R>(r), std::forward<Args>(args)...)
- Otherwise, if
* common_range<R> is true,
* the qualified-id iterator_traits<iterator_t<R>>::iterator_categoryis valid and denotes a type that modelsderived_from<input_iterator_tag>, and
* constructible_from<C, iterator_t<R>, sentinel_t<R>, Args...>is true:
C(ranges::begin(r), ranges::end(r), std::forward<Args>(args)...)
- Otherwise, if
* constructible_from<C, Args...> is true, and
* container-appendable<C, range_reference_t<R>> is true:
C c(std::forward<Args>(args)...);if constexpr (approximately_sized_range<R> && reservable-container<C>) c.reserve(static_cast<range_size_t<C>>(ranges::reserve_hint(r))); ranges::for_each(r, container-append(c));
- Otherwise, the program is ill-formed.
- Otherwise, if input_range<range_reference_t<R>> is true:to<C>(ref_view(r) | views::transform([](auto&& elem) { return to<range_value_t<C>>(std::forward<decltype(elem)>(elem));}), std::forward<Args>(args)...);
- Otherwise, the program is ill-formed.
template<template<class...> class C, [input_range](range.refinements#concept:input%5Frange "25.4.5 Other range refinements [range.refinements]") R, class... Args> constexpr auto to(R&& r, Args&&... args);
Let input-iterator be an exposition-only type:struct input-iterator { using iterator_category = input_iterator_tag;using value_type = range_value_t<R>;using difference_type = ptrdiff_t;using pointer = add_pointer_t<range_reference_t<R>>;using reference = range_reference_t<R>; reference operator*() const; pointer operator->() const;input-iterator& operator++();input-iterator operator++(int);bool operator==(const input-iterator&) const;};
[Note 1:
input-iterator meets the syntactic requirements of Cpp17InputIterator.
— _end note_]
Let DEDUCE_EXPR be defined as follows:
- C(declval<R>(), declval<Args>()...) if that is a valid expression,
- otherwise, C(from_range, declval<R>(), declval<Args>()...)if that is a valid expression,
- otherwise,C(declval<_input-iterator_>(), declval<_input-iterator_>(), declval<Args>()...) if that is a valid expression,
- otherwise, the program is ill-formed.
Returns: to<decltype(_DEDUCE_EXPR_)>(std::forward<R>(r), std::forward<Args>(args)...).
25.5.7.3 ranges::to adaptors [range.utility.conv.adaptors]
template<class C, class... Args> requires (<C>) constexpr auto to(Args&&... args);template<template<class...> class C, class... Args> constexpr auto to(Args&&... args);
Mandates: For the first overload,C is a cv-unqualified class type.
Returns: A range adaptor closure object ([range.adaptor.object]) fthat is a perfect forwarding call wrapper ([func.require]) with the following properties: