Title
Make good use of sized-random-access-range and bidirectional-common in <ranges>
Status
new
Section
[ranges.syn][range.refinements] [view.interface.general][range.take.overview] [range.drop.overview][range.drop.view] [range.join.iterator][range.join.with.view] [range.join.with.iterator][range.common.view] [range.zip.view][range.slide.view] [range.cartesian.view]
Submitter
Hewill Kang

Created on 2025-07-28.00:00:00 last changed 1 month ago

Messages

Date: 2025-08-16.09:29:49

Proposed resolution:

This wording is relative to N5014.

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

    // mostly freestanding
    #include <compare>              // see [compare.syn]
    #include <initializer_list>     // see [initializer.list.syn]
    #include <iterator>             // see [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
      […]
    }
    
  2. Modify [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>;
    
  3. Modify [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>;
        […]
      };
    }
    
  4. Modify [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()));

  5. Modify [range.take.overview] as indicated:

    -2- The name views::take denotes a range adaptor object ([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_rangesized-random-access-range and is a specialization of span ([views.span]), basic_string_view ([string.view]), or ranges::subrange ([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 ([range.iota.view]) that models random_access_range and sized_rangesized-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.

  6. Modify [range.drop.overview] as indicated:

    -2- The name views::drop denotes a range adaptor object ([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_rangesized-random-access-range and is

      […]
    3. (2.3) — Otherwise, if T is a specialization of subrange ([range.subrange]) that models random_access_range and sized_rangesized-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.

  7. Modify [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_)).

  8. Modify [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.1) — If ref-is-glvalue is true, Base models bidirectional_range, and range_reference_t<Base> models both bidirectional_range and common_rangecommon-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:

    […]
  9. Modify [range.join.with.view] as indicated:

    namespace std::ranges {
      template<class R>
      concept bidirectional-common = bidirectional_range<R> && common_range<R>;    // exposition only
      […]
    }
    
  10. Modify [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.1) — If ref-is-glvalue is true, Base models bidirectional_range, and InnerBase and PatternBase each model bidirectional-commoncommon-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:

    […]
  11. Modify [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_));
        }
        […]
      };
      […]
    }
    
  12. Modify [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> && ...);
      […]
    }
    
  13. Modify [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>;
      
      […]
    }
    
  14. Modify [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>;
      […]
    }
    
Date: 2025-07-28.00:00:00

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.

History
Date User Action Args
2025-08-02 13:17:27adminsetmessages: + msg14921
2025-07-28 00:00:00admincreate