Issue 4307: Make good use of sized-random-access-range and bidirectional-common in <ranges>

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

4307. Make good use of `sized-random-access-range` and `bidirectional-common` in `<ranges>`

Section: 25.2 [ranges.syn], 25.4.6 [range.refinements], 25.5.3.1 [view.interface.general], 25.7.10.1 [range.take.overview], 25.7.12.1 [range.drop.overview], 25.7.12.2 [range.drop.view], 25.7.14.3 [range.join.iterator], 25.7.15.2 [range.join.with.view], 25.7.15.3 [range.join.with.iterator], 25.7.20.2 [range.common.view], 25.7.25.2 [range.zip.view], 25.7.30.2 [range.slide.view], 25.7.33.2 [range.cartesian.view] Status: New Submitter: Hewill Kang Opened: 2025-07-28 Last modified: 2025-08-02

Priority: Not Prioritized

View other active issues in [ranges.syn].

View all other issues in [ranges.syn].

View all issues with New status.

Discussion:

P3179 introduces a new exposition-only concept, sized-random-access-range, into <ranges> to simplify the signature of parallel range algorithms. However, this also applies more broadly to <ranges>, as we often need to determine whether a range satisfies both sized_range and random_access_range in order to dispatch optimized branches.

In addition, we often need to determine whether a range satisfies both common_range and bidirectional_range to decide whether to provide backward traversal capabilities, which is expressed by the exposition-only concept bidirectional-common introduced in P2441. Unfortunately, this concept currently only applies to a single section.

It would be much simpler and more readable if both concepts were available throughout <ranges>, which would also allow newly introduced adapters or other library features to take advantage of them. Note that since some of these simplifications change the order in which the concepts are spelled, they may not be purely editorial.

Proposed resolution:

This wording is relative to this CD preview draft.

Modify 25.2 [ranges.syn], header <ranges> synopsis, as indicated:

// mostly freestanding
#include <compare>              // see 17.12.1 [compare.syn]
#include <initializer_list>     // see 17.11.2 [initializer.list.syn]
#include <iterator>             // see 24.2 [iterator.synopsis]

namespace std::ranges {
  […]
  template<class T>
    concept sized-random-access-range = see below;              // exposition only
  
  template<class T>
    concept common-bidirectional-range = see below;             // exposition only
  […]
}

Modify 25.4.6 [range.refinements] as indicated:
[…]
-8- The exposition-only concept sized-random-access-range specifies the requirements of a range type that is sized and allows random access to its elements.
```
template<class T>
  concept sized-random-access-range =           // exposition only
    random_access_range<T> && sized_range<T>;
```
[Note 1: This concept constrains some parallel algorithm overloads; see [algorithms]. — end note]
-?- The exposition-only concept common-bidirectional-range specifies the requirements of a range type that is bidirectional and whose iterator and sentinel types are the same.
```
template<class T>
  concept common-bidirectional-range =           // exposition only
    bidirectional_range<T> && common_range<T>;
```

Modify 25.5.3.1 [view.interface.general] as indicated:

-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 {
  private:
    […]
  public:
    […]
    constexpr decltype(auto) back() requires bidirectional_range<D> && common_range<D>common-bidirectional-range<D>;
    constexpr decltype(auto) back() const
      requires bidirectional_range<const D> && common_range<const D>common-bidirectional-range<const D>;
    […]
  };
}

Modify 25.5.3.2 [view.interface.members] as indicated:

constexpr decltype(auto) back() requires bidirectional_range<D> && common_range<D>common-bidirectional-range<D>;
constexpr decltype(auto) back() const
  requires bidirectional_range<const D> && common_range<const D>common-bidirectional-range<const D>;
-3- Hardened preconditions: !empty() is true.
-4- Effects: Equivalent to: return *ranges::prev(ranges::end(derived()));

Modify 25.7.10.1 [range.take.overview] as indicated:
-2- The name views::take denotes a range adaptor object (25.7.2 [range.adaptor.object]). Let E and F be expressions, let T be remove_cvref_t<decltype((E))>, and let D be range_difference_t<decltype((E))>. If decltype((F)) does not model convertible_to<D>, views::take(E, F) is ill-formed. Otherwise, the expression views::take(E, F) is expression-equivalent to:
1. […]
2. (2.2) — Otherwise, if T models ~~random_access_range and sized_range~~sized-random-access-range and is a specialization of span (23.7.2.2 [views.span]), basic_string_view (27.3 [string.view]), or ranges::subrange (25.5.4 [range.subrange]), then U(ranges::begin(E), ranges::begin(E) + std::min<D>(ranges::distance(E), F)), except that E is evaluated only once, where U is a type determined as follows:
  […]
3. (2.3) — otherwise, if T is a specialization of iota_view (25.6.4.2 [range.iota.view]) that models ~~random_access_range and sized_range~~sized-random-access-range, then iota_view(*ranges::begin(E), *(ranges::begin(E) + std::min<D>(ranges::distance(E), F))), except that E is evaluated only once.
Modify 25.7.12.1 [range.drop.overview] as indicated:
-2- The name views::drop denotes a range adaptor object (25.7.2 [range.adaptor.object]). Let E and F be expressions, let T be remove_cvref_t<decltype((E))>, and let D be range_difference_t<decltype((E))>. If decltype((F)) does not model convertible_to<D>, views::drop(E, F) is ill-formed. Otherwise, the expression views::drop(E, F) is expression-equivalent to:
1. […]
2. (2.2) — Otherwise, if T models ~~random_access_range and sized_range~~sized-random-access-range and is
  […]
3. (2.3) — Otherwise, if T is a specialization of subrange (25.5.4 [range.subrange]) that models ~~random_access_range and sized_range~~sized-random-access-range, then T(ranges::begin(E) + std::min<D>(ranges::distance(E), F), ranges::end(E), to-unsigned-like(ranges::distance(E) - std::min<D>(ranges::distance(E), F))), except that E and F are each evaluated only once.

Modify 25.7.12.2 [range.drop.view] as indicated:

namespace std::ranges {
  template<view V>
  class drop_view : public view_interface<drop_view<V>> {
  public:
    […]
    constexpr auto begin()
      requires (!(simple-view<V> &&
                  random_access_range<const V> && sized_range<const V>sized-random-access-range<const V>));
    constexpr auto begin() const
      requires random_access_range<const V> && sized_range<const V>sized-random-access-range<const V>;
    […]
  };
  […]
}

[…]

constexpr auto begin()
  requires (!(simple-view<V> &&
              random_access_range<const V> && sized_range<const V>sized-random-access-range<const V>));
constexpr auto begin() const
  requires random_access_range<const V> && sized_range<const V>sized-random-access-range<const V>;

-3- Returns: ranges::next(ranges::begin(base_), count_, ranges::end(base_)).

Modify 25.7.14.3 [range.join.iterator] as indicated:

namespace std::ranges {
  template<input_range V>
    requires view<V> && input_range<range_reference_t<V>>
  template<bool Const>
  struct join_view<V>::iterator {
  private:
    […]
  public:
    […]
    constexpr iterator& operator--()
      requires ref-is-glvalue && bidirectional_range<Base> &&
               bidirectional_range<range_reference_t<Base>> &&
               common_range<range_reference_t<Base>>common-bidirectional-range<range_reference_t<Base>>;

    constexpr iterator operator--(int)
      requires ref-is-glvalue && bidirectional_range<Base> &&
               bidirectional_range<range_reference_t<Base>> &&
               common_range<range_reference_t<Base>>common-bidirectional-range<range_reference_t<Base>>;
    […]
  };
}

-1- iterator::iterator_concept is defined as follows::

(1.1) — If ref-is-glvalue is true, Base models bidirectional_range, and range_reference_t<Base> models ~~both bidirectional_range and common_range~~common-bidirectional-range, then iterator_concept denotes bidirectional_iterator_tag.
[…]

[…]

constexpr iterator& operator--()
  requires ref-is-glvalue && bidirectional_range<Base> &&
           bidirectional_range<range_reference_t<Base>> &&
           common_range<range_reference_t<Base>>common-bidirectional-range<range_reference_t<Base>>;

-16- Effects: Equivalent to:
[…]

constexpr iterator operator--(int)
  requires ref-is-glvalue && bidirectional_range<Base> &&
           bidirectional_range<range_reference_t<Base>> &&
           common_range<range_reference_t<Base>>common-bidirectional-range<range_reference_t<Base>>;

-17- Effects: Equivalent to:
[…]

Modify 25.7.15.2 [range.join.with.view] as indicated:

namespace std::ranges {
  template<class R>
  concept bidirectional-common = bidirectional_range<R> && common_range<R>;    // exposition only
  […]
}

Modify 25.7.15.3 [range.join.with.iterator] as indicated:

namespace std::ranges {
  template<input_range V, forward_range Pattern>
    requires view<V> && input_range<range_reference_t<V>>
          && view<Pattern> && concatable<range_reference_t<V>, Pattern>
  template<bool Const>
  class join_with_view<V, Pattern>::iterator {
  private:
    […]
  public:
    […]
    constexpr iterator& operator--()
      requires ref-is-glvalue && bidirectional_range<Base> &&
               bidirectional-commoncommon-bidirectional-range<InnerBase> && bidirectional-commoncommon-bidirectional-range<PatternBase>;
    constexpr iterator operator--(int)
      requires ref-is-glvalue && bidirectional_range<Base> &&
               bidirectional-commoncommon-bidirectional-range<InnerBase> && bidirectional-commoncommon-bidirectional-range<PatternBase>;
    […]
  };
}

-1- iterator::iterator_concept is defined as follows::

(1.1) — If ref-is-glvalue is true, Base models bidirectional_range, and InnerBase and PatternBase each model ~~bidirectional-common~~common-bidirectional-range, then iterator_concept denotes bidirectional_iterator_tag.
[…]

[…]

constexpr iterator& operator--()
  requires ref-is-glvalue && bidirectional_range<Base> &&
           bidirectional-commoncommon-bidirectional-range<InnerBase> && bidirectional-commoncommon-bidirectional-range<PatternBase>;

-16- Effects: Equivalent to:

[…]

constexpr iterator operator--(int)
  requires ref-is-glvalue && bidirectional_range<Base> &&
           bidirectional-commoncommon-bidirectional-range<InnerBase> && bidirectional-commoncommon-bidirectional-range<PatternBase>;

-17- Effects: Equivalent to:
[…]

Modify 25.7.20.2 [range.common.view] as indicated:

namespace std::ranges {
  template<view V>
    requires (!common_range<V> && copyable<iterator_t<V>>)
  class common_view : public view_interface<common_view<V>> {
  private:
    V base_ = V();  // exposition only

  public:
    […]
    constexpr auto begin() requires (!simple-view<V>) {
      if constexpr (random_access_range<V> && sized_range<V>sized-random-access-range<V>)
        return ranges::begin(base_);
      else
        return common_iterator<iterator_t<V>, sentinel_t<V>>(ranges::begin(base_));
    }

    constexpr auto begin() const requires range<const V> {
      if constexpr (random_access_range<const V> && sized_range<const V>sized-random-access-range<const V>)
        return ranges::begin(base_);
      else
        return common_iterator<iterator_t<const V>, sentinel_t<const V>>(ranges::begin(base_));
    }

    constexpr auto end() requires (!simple-view<V>) {
      if constexpr (random_access_range<V> && sized_range<V>sized-random-access-range<V>)
        return ranges::begin(base_) + ranges::distance(base_);
      else
        return common_iterator<iterator_t<V>, sentinel_t<V>>(ranges::end(base_));
    }

    constexpr auto end() const requires range<const V> {
      if constexpr (random_access_range<const V> && sized_range<const V>sized-random-access-range<const V>)
        return ranges::begin(base_) + ranges::distance(base_);
      else
        return common_iterator<iterator_t<const V>, sentinel_t<const V>>(ranges::end(base_));
    }
    […]
  };
  […]
}

Modify 25.7.25.2 [range.zip.view] as indicated:

namespace std::ranges {
  template<class... Rs>
  concept zip-is-common =                             // exposition only
    (sizeof...(Rs) == 1 && (common_range<Rs> && ...)) ||
    (!(bidirectional_range<Rs> && ...) && (common_range<Rs> && ...)) ||
    ((random_access_range<Rs> && ...) && (sized_range<Rs> && ...)sized-random-access-range<Rs> && ...);
  […]
}

Modify 25.7.30.2 [range.slide.view] as indicated:

namespace std::ranges {
  template<class V>
  concept slide-caches-nothing = random_access_range<V> && sized_range<V>sized-random-access-range<V>;       // exposition only
  
  template<class V>
  concept slide-caches-last =                                            // exposition only
    !slide-caches-nothing<V> && bidirectional_range<V> && common_range<V>common-bidirectional-range<V>;
  
  […]
}

Modify 25.7.33.2 [range.cartesian.view] as indicated:

namespace std::ranges {
  template<bool Const, class First, class... Vs>
  concept cartesian-product-is-random-access =          // exposition only
    (random_access_range<maybe-const<Const, First>> && ... &&
      (random_access_range<maybe-const<Const, Vs>>
        && sized_range<maybe-const<Const, Vs>>)sized-random-access-range<maybe-const<Const, Vs>>);

  template<class R>
  concept cartesian-product-common-arg =                // exposition only
    common_range<R> || (sized_range<R> && random_access_range<R>)sized-random-access-range<R>;
  […]
}

4307. Make good use of sized-random-access-range and bidirectional-common in <ranges>

4307. Make good use of `sized-random-access-range` and `bidirectional-common` in `<ranges>`