24 Ranges library [ranges]

24.5 Range utilities [range.utility]

24.5.1 General [range.utility.general]

1
#
The components in [range.utility] are general utilities for representing and manipulating ranges.

24.5.2 Helper concepts [range.utility.helpers]

1
#
Many of the types in subclause [range.utility] are specified in terms of the following exposition-only concepts: template<class R> concept simple-view = // exposition only 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 = // exposition only input_­iterator<I> && (is_pointer_v<I> || requires(I i) { i.operator->(); }); template<class T, class U> concept not-same-as = // exposition only !same_­as<remove_cvref_t<T>, remove_cvref_t<U>>;

24.5.3 View interface [view.interface]

24.5.3.1 General [view.interface.general]

1
#
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 : public view_base { private: constexpr D& derived() noexcept { // exposition only return static_cast<D&>(*this); } constexpr const D& derived() const noexcept { // exposition only return static_cast<const D&>(*this); } public: constexpr bool empty() requires forward_­range<D> { return ranges::begin(derived()) == ranges::end(derived()); } constexpr bool empty() const requires forward_­range<const D> { return ranges::begin(derived()) == ranges::end(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 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 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]; } }; }
2
#
The template parameter D for view_­interface may be an incomplete type.
Before any member of the resulting specialization of view_­interface other than special member functions is referenced, D shall be complete, and model both derived_­from<view_­interface<D>> and view.

24.5.3.2 Members [view.interface.members]

🔗
constexpr decltype(auto) front() requires forward_­range<D>; constexpr decltype(auto) front() const requires forward_­range<const D>;
1
#
Preconditions: !empty().
2
#
Effects: Equivalent to: return *ranges​::​begin(derived());
🔗
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>;
3
#
Preconditions: !empty().
4
#
Effects: Equivalent to: return *ranges​::​prev(ranges​::​end(derived()));

24.5.4 Sub-ranges [range.subrange]

24.5.4.1 General [range.subrange.general]

1
#
The subrange class template combines together an iterator and a sentinel into a single object that models the view concept.
Additionally, it models the sized_­range concept when the final template parameter is subrange_­kind​::​sized.
namespace std::ranges { template<class From, class To> concept convertible-to-non-slicing = // exposition only convertible_to<From, To> && !(is_pointer_v<decay_t<From>> && is_pointer_v<decay_t<To>> && not-same-as<remove_pointer_t<decay_t<From>>, remove_pointer_t<decay_t<To>>>); template<class T> concept pair-like = // exposition only !is_reference_v<T> && requires(T t) { typename tuple_size<T>::type; // ensures tuple_­size<T> is complete requires derived_­from<tuple_size<T>, integral_constant<size_t, 2>>; typename tuple_element_t<0, remove_const_t<T>>; typename tuple_element_t<1, remove_const_t<T>>; { get<0>(t) } -> convertible_­to<const tuple_element_t<0, T>&>; { get<1>(t) } -> convertible_­to<const tuple_element_t<1, T>&>; }; template<class T, class U, class V> concept pair-like-convertible-from = // exposition only !range<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<class T> concept iterator-sentinel-pair = // exposition only !range<T> && pair-like<T> && sentinel_­for<tuple_element_t<1, T>, tuple_element_t<0, 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 || !sized_­sentinel_­for<S, I>) class subrange : public view_interface<subrange<I, S, K>> { private: static constexpr bool StoreSize = // exposition only K == subrange_kind::sized && !sized_­sentinel_­for<S, I>; I begin_ = I(); // exposition only S end_ = S(); // exposition only make-unsigned-like-t<iter_difference_t<I>> size_ = 0; // exposition only; present only // when StoreSize is true public: subrange() = 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<not-same-as<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<not-same-as<subrange> PairLike> requires pair-like-convertible-from<PairLike, const I&, const S&> constexpr operator PairLike() const; constexpr I begin() const requires copyable<I>; [[nodiscard]] constexpr I begin() requires (!copyable<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); [[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) const & requires forward_iterator<I>; [[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) &&; [[nodiscard]] 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<iterator-sentinel-pair P> subrange(P) -> subrange<tuple_element_t<0, P>, tuple_element_t<1, P>>; template<iterator-sentinel-pair P> subrange(P, make-unsigned-like-t<iter_difference_t<tuple_element_t<0, P>>>) -> subrange<tuple_element_t<0, P>, tuple_element_t<1, P>, 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>; template<size_t N, class I, class S, subrange_kind K> requires (N < 2) 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); } namespace std { using ranges::get; }

24.5.4.2 Constructors and conversions [range.subrange.ctor]

🔗
constexpr subrange(convertible-to-non-slicing<I> auto i, S s) requires (!StoreSize);
1
#
Preconditions: [i, s) is a valid range.
2
#
Effects: Initializes begin_­ with std​::​move(i) and end_­ with s.
🔗
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);
3
#
Preconditions: [i, s) is a valid range, and n == to-unsigned-like(ranges​::​distance(i, s)).
4
#
Effects: Initializes begin_­ with std​::​move(i) and end_­ with s.
If StoreSize is true, initializes size_­ with n.
5
#
[Note 1:
Accepting the length of the range and storing it to later return from size() enables subrange to model sized_­range even when it stores an iterator and sentinel that do not model sized_­sentinel_­for.
— end note]
🔗
template<not-same-as<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>);
6
#
Effects: Equivalent to:
  • (6.1)
    If StoreSize is true, subrange{r, ranges​::​size(r)}.
  • (6.2)
    Otherwise, subrange{ranges​::​begin(r), ranges​::​end(r)}.
🔗
template<not-same-as<subrange> PairLike> requires pair-like-convertible-from<PairLike, const I&, const S&> constexpr operator PairLike() const;
7
#
Effects: Equivalent to: return PairLike(begin_­, end_­);

24.5.4.3 Accessors [range.subrange.access]

🔗
constexpr I begin() const requires copyable<I>;
1
#
Effects: Equivalent to: return begin_­;
🔗
[[nodiscard]] constexpr I begin() requires (!copyable<I>);
2
#
Effects: Equivalent to: return std​::​move(begin_­);
🔗
constexpr S end() const;
3
#
Effects: Equivalent to: return end_­;
🔗
constexpr bool empty() const;
4
#
Effects: Equivalent to: return begin_­ == end_­;
🔗
constexpr make-unsigned-like-t<iter_difference_t<I>> size() const requires (K == subrange_kind::sized);
5
#
Effects:
  • (5.1)
    If StoreSize is true, equivalent to: return size_­;
  • (5.2)
    Otherwise, equivalent to: return to-unsigned-like(end_­ - begin_­);
🔗
[[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) const & requires forward_iterator<I>;
6
#
Effects: Equivalent to: auto tmp = *this; tmp.advance(n); return tmp;
🔗
[[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) &&;
7
#
Effects: Equivalent to: advance(n); return std::move(*this);
🔗
[[nodiscard]] constexpr subrange prev(iter_difference_t<I> n = 1) const requires bidirectional_­iterator<I>;
8
#
Effects: Equivalent to: auto tmp = *this; tmp.advance(-n); return tmp;
🔗
constexpr subrange& advance(iter_difference_t<I> n);
9
#
Effects: Equivalent to:
  • (9.1)
    If StoreSize is true, auto d = n - ranges::advance(begin_, n, end_); if (d >= 0) size_ -= to-unsigned-like(d); else size_ += to-unsigned-like(-d); return *this;
  • (9.2)
    Otherwise, ranges::advance(begin_, n, end_); return *this;
🔗
template<size_t N, class I, class S, subrange_kind K> requires (N < 2) 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);
10
#
Effects: Equivalent to: if constexpr (N == 0) return r.begin(); else return r.end();

24.5.5 Dangling iterator handling [range.dangling]

1
#
The tag type dangling is used together with the template aliases borrowed_­iterator_­t and borrowed_­subrange_­t to indicate that an algorithm that typically returns an iterator into or subrange of a range argument does not return an iterator or subrange which could potentially reference a range whose lifetime has ended for a particular rvalue range argument which does not model borrowed_­range ([range.range]).
namespace std::ranges { struct dangling { constexpr dangling() noexcept = default; template<class... Args> constexpr dangling(Args&&...) noexcept { } }; }
2
#
[Example 1: vector<int> f(); auto result1 = ranges::find(f(), 42); // #1 static_assert(same_­as<decltype(result1), ranges::dangling>); auto vec = f(); auto result2 = ranges::find(vec, 42); // #2 static_assert(same_­as<decltype(result2), vector<int>::iterator>); auto result3 = ranges::find(subrange{vec}, 42); // #3 static_assert(same_­as<decltype(result3), vector<int>::iterator>);
The call to ranges​::​find at #1 returns ranges​::​dangling since f() is an rvalue vector; the vector could potentially 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 subrange model borrowed_­range.
— end example]