Title
view_interface::empty is overconstrained
Status
ready
Section
[view.interface.general]
Submitter
Hewill Kang

Created on 2022-06-12.00:00:00 last changed 5 days ago

Messages

Date: 2022-06-21.11:47:28

Proposed resolution:

This wording is relative to N4910.

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

    namespace std::ranges {
      template<class D>
        requires is_class_v<D> && same_as<D, remove_cv_t<D>>
      class view_interface {
      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 sized_range<D> || forward_range<D> {
          if constexpr (sized_range<D>)
            return ranges::size(derived()) == 0;
          else
            return ranges::begin(derived()) == ranges::end(derived());
        }
        constexpr bool empty() const requires sized_range<const D> || forward_range<const D> {
          if constexpr (sized_range<const D>)
            return ranges::size(derived()) == 0;
          else
            return ranges::begin(derived()) == ranges::end(derived());
        }
        […]
      };
    }
    
Date: 2022-06-15.00:00:00

[ 2022-06-21; Reflector poll ]

Set status to Tentatively Ready after six votes in favour during reflector poll.

Date: 2022-06-12.00:00:00

Currently, view_interface::empty has the following constraints

constexpr bool empty() requires forward_range<D> {
  return ranges::begin(derived()) == ranges::end(derived());
}

which seems reasonable, since we need to guarantee the equality preservation of the expression ranges::begin(r).

However, this prevents a more efficient way in some cases, i.e., when D models sized_range, we only need to determine whether the value of ranges::size is 0. Since sized_range and forward_range are orthogonal to each other, this also prevents any range that models sized_range but not forward_range.

Consider:

#include <iostream>
#include <ranges>

int main() {
  auto f = std::views::iota(0, 5)
         | std::views::filter([](int) { return true; });
  auto r = std::views::counted(f.begin(), 4)
         | std::views::slide(2);
  std::cout << (r.size() == 0) << "\n"; // #1
  std::cout << r.empty() << "\n";       // #2, calls r.begin() == r.end()
}

Since r models sized_range, #1 will invoke slide_view::size, which mainly invokes ranges::distance; However, #2 invokes view_interface::empty and evaluates r.begin() == r.end(), which constructs the iterator, invokes ranges::next, and caches the result, which is unnecessary.

Also consider:

#include <iostream>
#include <ranges>

int main() {
  auto i = std::views::istream<int>(std::cin);
  auto r = std::views::counted(i.begin(), 4)
         | std::views::chunk(2);
  std::cout << (r.size() == 0) << "\n"; // #1
  std::cout << !r << "\n";              // #2, equivalent to r.size() == 0
  std::cout << r.empty() << "\n";       // #3, ill-formed
}

Since r is still sized_range, #1 will invoke chunk_view::size. #2 is also well-formed since view_interface::operator bool only requires the expression ranges::empty(r) to be well-formed, which first determines the validity of r.empty(), and ends up evaluating #1; However, #3 is ill-formed since r is not a forward_range.

Although we can still use ranges::empty to determine whether r is empty, this inconsistency of the validity of !r and r.empty() is quite unsatisfactory.

I see no reason to prevent view_interface::empty when D is sized_range, since checking whether ranges::size(r) == 0 is an intuitive way to check for empty, as ranges::empty does.

History
Date User Action Args
2022-06-21 11:47:28adminsetmessages: + msg12525
2022-06-21 11:47:28adminsetstatus: new -> ready
2022-06-12 18:22:38adminsetmessages: + msg12502
2022-06-12 00:00:00admincreate