Title
concat_view::iterator::operator- is overconstrained
Status
new
Section
[range.concat.iterator]
Submitter
Hewill Kang

Created on 2024-04-26.00:00:00 last changed 1 month ago

Messages

Date: 2024-04-27.16:39:59

Proposed resolution:

This wording is relative to N4981.

  1. Modify [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...>
Date: 2024-04-26.00:00:00

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-.

History
Date User Action Args
2024-04-27 16:39:59adminsetmessages: + msg14083
2024-04-26 00:00:00admincreate