24 Ranges library [ranges]

24.5 Range utilities [range.utility]

The components in this subclause are general utilities for representing and manipulating ranges.

24.5.1 Helper concepts [range.utility.helpers]

Many of the types in this subclause are specified in terms of the following exposition-only concepts:
template<class R>
  concept simple-view =                         // exposition only
    View<R> && Range<const R> &&
    Same<iterator_t<R>, iterator_t<const R>> &&
    Same<sentinel_t<R>, sentinel_t<const R>>;

template<InputIterator I>
  concept has-arrow =                           // exposition only
    is_pointer_v<I> || requires(I i) { i.operator->(); };

template<class T, class U>
  concept not-same-as =                         // exposition only
    !Same<remove_cvref_t<T>, remove_cvref_t<U>>;

24.5.2 View interface [view.interface]

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<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 ForwardRange<D> {
      return ranges::begin(derived()) == ranges::end(derived());
    }
    constexpr bool empty() const requires ForwardRange<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 ContiguousIterator<iterator_t<D>> {
      return ranges::empty(derived()) ? nullptr : addressof(*ranges::begin(derived()));
    }
    constexpr auto data() const
      requires Range<const D> && ContiguousIterator<iterator_t<const D>> {
        return ranges::empty(derived()) ? nullptr : addressof(*ranges::begin(derived()));
      }

    constexpr auto size() requires ForwardRange<D> &&
      SizedSentinel<sentinel_t<D>, iterator_t<D>> {
        return ranges::end(derived()) - ranges::begin(derived());
      }
    constexpr auto size() const requires ForwardRange<const D> &&
      SizedSentinel<sentinel_t<const D>, iterator_t<const D>> {
        return ranges::end(derived()) - ranges::begin(derived());
      }

    constexpr decltype(auto) front() requires ForwardRange<D>;
    constexpr decltype(auto) front() const requires ForwardRange<const D>;

    constexpr decltype(auto) back() requires BidirectionalRange<D> && CommonRange<D>;
    constexpr decltype(auto) back() const
      requires BidirectionalRange<const D> && CommonRange<const D>;

    template<RandomAccessRange R = D>
      constexpr decltype(auto) operator[](iter_difference_t<iterator_t<R>> n) {
        return ranges::begin(derived())[n];
      }
    template<RandomAccessRange R = const D>
      constexpr decltype(auto) operator[](iter_difference_t<iterator_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 of view_­interface other than special member functions is referenced, D shall be complete, and model both DerivedFrom<view_­interface<D>> and View.

24.5.2.1 Members [view.interface.members]

constexpr decltype(auto) front() requires ForwardRange<D>; constexpr decltype(auto) front() const requires ForwardRange<const D>;
Expects: !empty().
Effects: Equivalent to: return *ranges::begin(derived());
constexpr decltype(auto) back() requires BidirectionalRange<D> && CommonRange<D>; constexpr decltype(auto) back() const requires BidirectionalRange<const D> && CommonRange<const D>;
Expects: !empty().
Effects: Equivalent to: return *ranges::prev(ranges::end(derived()));

24.5.3 Sub-ranges [range.subrange]

The subrange class template combines together an iterator and a sentinel into a single object that models the View concept.
Additionally, it models the SizedRange concept when the final template parameter is subrange_­kind::sized.
namespace std::ranges {
  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 DerivedFrom<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) } -> const tuple_element_t<0, T>&;
        { get<1>(t) } -> const tuple_element_t<1, T>&;
      };

  template<class T, class U, class V>
    concept pair-like-convertible-to =                  // exposition only
      !Range<T> && pair-like<remove_reference_t<T>> &&
      requires(T&& t) {
        { get<0>(std::forward<T>(t)) } -> ConvertibleTo<U>;
        { get<1>(std::forward<T>(t)) } -> ConvertibleTo<V>;
      };

  template<class T, class U, class V>
    concept pair-like-convertible-from =                // exposition only
      !Range<T> && pair-like<T> && Constructible<T, U, V>;

  template<class T>
    concept iterator-sentinel-pair =                    // exposition only
      !Range<T> && pair-like<T> &&
      Sentinel<tuple_element_t<1, T>, tuple_element_t<0, T>>;

  template<Iterator I, Sentinel<I> S = I, subrange_kind K =
      SizedSentinel<S, I> ? subrange_kind::sized : subrange_kind::unsized>
    requires (K == subrange_kind::sized || !SizedSentinel<S, I>)
  class subrange : public view_interface<subrange<I, S, K>> {
  private:
    static constexpr bool StoreSize =                   // exposition only
      K == subrange_kind::sized && !SizedSentinel<S, I>;
    I begin_ = I();                                     // exposition only
    S end_ = S();                                       // exposition only
    iter_difference_t<I> size_ = 0;                     // exposition only; present only
                                                        // when StoreSize is true
  public:
    subrange() = default;

    constexpr subrange(I i, S s) requires (!StoreSize);

    constexpr subrange(I i, S s, iter_difference_t<I> n)
      requires (K == subrange_kind::sized);

    template<not-same-as<subrange> R>
      requires forwarding-range<R> &&
        ConvertibleTo<iterator_t<R>, I> && ConvertibleTo<sentinel_t<R>, S>
    constexpr subrange(R&& r) requires (!StoreSize || SizedRange<R>);

    template<forwarding-range R>
      requires ConvertibleTo<iterator_t<R>, I> && ConvertibleTo<sentinel_t<R>, S>
    constexpr subrange(R&& r, 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-to<PairLike, I, S>
    constexpr subrange(PairLike&& r) requires (!StoreSize)
      : subrange{std::get<0>(std::forward<PairLike>(r)),
                 std::get<1>(std::forward<PairLike>(r))}
    {}

    template<pair-like-convertible-to<I, S> PairLike>
    constexpr subrange(PairLike&& r, iter_difference_t<I> n)
      requires (K == subrange_kind::sized)
      : subrange{std::get<0>(std::forward<PairLike>(r)),
                 std::get<1>(std::forward<PairLike>(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;
    constexpr S end() const;

    constexpr bool empty() const;
    constexpr iter_difference_t<I> size() const
      requires (K == subrange_kind::sized);

    [[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) const;
    [[nodiscard]] constexpr subrange prev(iter_difference_t<I> n = 1) const
      requires BidirectionalIterator<I>;
    constexpr subrange& advance(iter_difference_t<I> n);

    friend constexpr I begin(subrange&& r) { return r.begin(); }
    friend constexpr S end(subrange&& r) { return r.end(); }
  };

  template<Iterator I, Sentinel<I> S>
    subrange(I, S, 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, iter_difference_t<tuple_element_t<0, P>>) ->
      subrange<tuple_element_t<0, P>, tuple_element_t<1, P>, subrange_kind::sized>;

  template<forwarding-range R>
    subrange(R&&) ->
      subrange<iterator_t<R>, sentinel_t<R>,
               (SizedRange<R> || SizedSentinel<sentinel_t<R>, iterator_t<R>>)
                 ? subrange_kind::sized : subrange_kind::unsized>;

  template<forwarding-range R>
    subrange(R&&, iter_difference_t<iterator_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);
}

namespace std {
  using ranges::get;
}

24.5.3.1 Constructors and conversions [range.subrange.ctor]

constexpr subrange(I i, S s) requires (!StoreSize);
Expects: [i, s) is a valid range.
Effects: Initializes begin_­ with i and end_­ with s.
constexpr subrange(I i, S s, iter_difference_t<I> n) requires (K == subrange_kind::sized);
Expects: [i, s) is a valid range, and n == ranges::distance(i, s).
Effects: Initializes begin_­ with i and end_­ with s.
If StoreSize is true, initializes size_­ with n.
[Note
:
Accepting the length of the range and storing it to later return from size() enables subrange to model SizedRange even when it stores an iterator and sentinel that do not model SizedSentinel.
end note
]
template<not-same-as<subrange> R> requires forwarding-range<R> && ConvertibleTo<iterator_t<R>, I> && ConvertibleTo<sentinel_t<R>, S> constexpr subrange(R&& r) requires (!StoreSize || SizedRange<R>);
Effects: Equivalent to:
  • If StoreSize is true, subrange{ranges::begin(r), ranges::end(r), ranges::size(r)}.
  • 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;
Effects: Equivalent to: return PairLike(begin_­, end_­);

24.5.3.2 Accessors [range.subrange.access]

constexpr I begin() const;
Effects: Equivalent to: return begin_­;
constexpr S end() const;
Effects: Equivalent to: return end_­;
constexpr bool empty() const;
Effects: Equivalent to: return begin_­ == end_­;
constexpr iter_difference_t<I> size() const requires (K == subrange_kind::sized);
Effects:
  • If StoreSize is true, equivalent to: return size_­;
  • Otherwise, equivalent to: return end_­ - begin_­;
[[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) const;
Effects: Equivalent to:
auto tmp = *this;
tmp.advance(n);
return tmp;
[Note
:
If I does not model ForwardIterator, next can invalidate *this.
end note
]
[[nodiscard]] constexpr subrange prev(iter_difference_t<I> n = 1) const requires BidirectionalIterator<I>;
Effects: Equivalent to:
auto tmp = *this;
tmp.advance(-n);
return tmp;
constexpr subrange& advance(iter_difference_t<I> n);
Effects: Equivalent to:
  • If StoreSize is true,
    size_ -= n - ranges::advance(begin_, n, end_);
    return *this;
    
  • 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);
Effects: Equivalent to:
if constexpr (N == 0)
  return r.begin();
else
  return r.end();

24.5.4 Dangling iterator handling [range.dangling]

The tag type dangling is used together with the template aliases safe_­iterator_­t and safe_­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 forwarding-range ([range.range]).
namespace std::ranges {
  struct dangling {
    constexpr dangling() noexcept = default;
    template<class... Args>
      constexpr dangling(Args&&...) noexcept { }
  };
}
[Example
:
vector<int> f();
auto result1 = ranges::find(f(), 42);                                   // #1
static_assert(Same<decltype(result1), ranges::dangling>);
auto vec = f();
auto result2 = ranges::find(vec, 42);                                   // #2
static_assert(Same<decltype(result2), vector<int>::iterator>);
auto result3 = ranges::find(subrange{vec}, 42);                         // #3
static_assert(Same<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 forwarding-range.
end example
]