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_as<iterator_t<R>, iterator_t<const R>> &&
    same_as<sentinel_t<R>, sentinel_t<const R>>;

template<input_iterator 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_as<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_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];
      }
  };
}
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.2.1 Members [view.interface.members]

constexpr decltype(auto) front() requires forward_range<D>; constexpr decltype(auto) front() const requires forward_range<const D>;
Expects: !empty().
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>;
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 sized_­range 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 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-to =                     // exposition only
      !range<T> && pair-like<remove_reference_t<T>> &&
      requires(T&& t) {
        { get<0>(std::forward<T>(t)) } -> convertible_to<U>;
        { get<1>(std::forward<T>(t)) } -> convertible_to<V>;
      };

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

  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(I i, S s) requires (!StoreSize);

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

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

    template<forwarding-range R>
      requires convertible_to<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-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, make-unsigned-like-t(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 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;
    [[nodiscard]] constexpr subrange prev(iter_difference_t<I> n = 1) const
      requires bidirectional_iterator<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<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<forwarding-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<forwarding-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);
}

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, make-unsigned-like-t(iter_difference_t<I>) n) requires (K == subrange_kind::sized);
Expects: [i, s) is a valid range, and n == make-unsigned-like(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 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 forwarding-range<R> && convertible_to<iterator_t<R>, I> && convertible_to<sentinel_t<R>, S> constexpr subrange(R&& r) requires (!StoreSize || sized_range<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 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 make-unsigned-like-t(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 forward_­iterator, next can invalidate *this.
— end note
 ]
[[nodiscard]] constexpr subrange prev(iter_difference_t<I> n = 1) const requires bidirectional_iterator<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,
    auto d = n - ranges::advance(begin_, n, end_);
    if (d >= 0)
      size_ -= make-unsigned-like(d);
    else
      size_ += make-unsigned-like(-d);
    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_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 forwarding-range.
— end example
 ]