4081. concat_view::iterator::operator- is overconstrained

Section: 25.7.18.3 [range.concat.iterator] Status: New Submitter: Hewill Kang Opened: 2024-04-26 Last modified: 2024-08-02

Priority: 3

View other active issues in [range.concat.iterator].

View all other issues in [range.concat.iterator].

View all issues with New status.

Discussion:

Currently, two concat_view::iterators can only be subtracted if concat-is-random-access is satisfied, which seems overconstrained since the implementation does not rely on all underlying ranges being random_access_range or common_range.

Generally speaking, iterators provide operator- mainly based on whether it satisfies sized_sentinel_for rather than being category-specific. For example, counted_iterators that only model input_iterator can still be subtracted. We have no reason to reject the following:

std::list l = {1, 2, 3};
auto r = l | std::views::take(3);
auto c = std::ranges::concat_view{r};
auto it = c.begin();
it++;
auto d = it - c.begin(); // error: no match for 'operator-'

The proposed resolution lists a minimal constraint formula based on the implementation details of operator-.

[2024-08-02; Reflector poll]

Set priority to 3 after reflector poll.

Proposed resolution:

This wording is relative to N4981.

1. Modify 25.7.18.3 [range.concat.iterator] as indicated:

   namespace std::ranges {
     template<input_range... Views>
       requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
                 concatable<Views...>
     template<bool Const>
     class concat_view<Views...>::iterator {
   
     public:
       […]
       friend constexpr difference_type operator-(const iterator& x, const iterator& y)
         requires concat-is-random-access<Const, Views...>see below;
       […]
     };
   }
   

   […]

   friend constexpr difference_type operator-(const iterator& x, const iterator& y)
     requires concat-is-random-access<Const, Views...>see below;
   

   -32- Preconditions: x.it_.valueless_by_exception() and y.it_.valueless_by_exception() are each false.

   -33- Effects: Let ix denote x.it_.index() and iy denote y.it_.index().

   1. (33.1) — if ix > iy, let dy be ranges::distance(std::get<iy>(y.it_), ranges::end(std::get<iy>(y.parent_->views_))), dx be ranges::distance(ranges::begin(std::get<ix>(x.parent_->views_)), std::get<ix>(x.it_)). Let s denote the sum of the sizes of all the ranges std::get<i>(x.parent_->views_) for every integer i in the range [iy + 1, ix) if there is any, and 0 otherwise, of type difference_type, equivalent to:

      return dy + s + dx;

      (33.2) — otherwise, if ix < iy is true, equivalent to:

      return -(y - x);

      (33.3) — otherwise, equivalent to:

      return std::get<ix>(x.it_) - std::get<iy>(y.it_);

   -?- Remarks: Let Fs be the pack that consists of all elements of Views except the last element, and let Rs be the pack that consists of all elements of Views except the first element. The expression in the requires-clause is equivalent to:

   (sized_sentinel_for<iterator_t<maybe-const<Const, Views>>,
                       iterator_t<maybe-const<Const, Views>>> && ...) &&
   (sized_sentinel_for<sentinel_t<maybe-const<Const, Fs>>,
                       iterator_t<maybe-const<Const, Fs>>> && ...) &&
   all-forward<Const, Rs...>