Why does `iota(0) | take(0)` not model ranges::sized_range in C++20?

user_11638718 0
Viewed 320

Consider the following code snippet:

#include <ranges>

auto r = std::views::iota(0) | std::views::take(0);
static_assert(std::ranges::sized_range<decltype(r)>);

gcc-trunk rejects it for required-expression std::ranges::size(r) is invalid. Why does r not model ranges::sized_range, i,e, why can't I use std::ranges::size on it?

Update

Compiles after using range-v3. Is this feature required for C++23, or is it an LWG issue?

#include <range/v3/all.hpp>
#include <ranges>

auto r = ranges::views::iota(0) | ranges::views::take(0);
static_assert(std::ranges::sized_range<decltype(r)>);

The problem seems to be that the sentinel_t of r in range-v3 is just ranges::default_sentinel which satisfies the std::sized_sentinel_for<ranges::counted_iterator>, since there is a valid operator- in [predef.iterators#iterators.counted] for those two types:

friend constexpr iter_difference_t<I> operator-(
  const counted_iterator& x, default_sentinel_t);
friend constexpr iter_difference_t<I> operator-(
  default_sentinel_t, const counted_iterator& y);

But in namepace std::ranges, the sentinel_t of r is std::ranges::take_view<std::ranges::iota_view>::_Sentinel<true> which cannot convert to std::default_sentinel_t.

range-v3 std-ranges c++20 c++
2 Answers

views::take only yields a sized range if the given range itself was sized. And views::iota isn't a sized range unless you use one of the two-element constructors that give it a size. Which you did not.

As for why take_view is only sized if the underlying iterator is sized, this is because take_view stops when the number of elements to take is reached or you reach the end of the underlying range. Which means that the size could be less than what you asked for. So to compute the size of a take_view, you must be able to compute the size of the underlying range to see if it is less than the given count. It doesn't matter if you just so happen to pass a count that will never need to compute the size; it's a compile-time property, not based on the value you happened to give it at runtime.

How this "works" for Range V3 is unknown, but the C++20 standard doesn't permit it to work.

user_7340690

Compiles after using range-v3. Is this feature required for C++23, or is it an LWG issue?

No and no.

take(0) is kind of a weird example since it suggests that the 0 might be important -- if we could take decisions based on the value then take(0) would always just give you empty<T> for the right T (which is a sized_range).

So let's instead consider take(5).

take(5) gives you a range with at most 5 elements. But we can only know how many if we know how many elements are in the input range, and we can only know that if the input range is a sized_range, which is how C++20's take operates. But there is actually another way that we can know how many elements r | take(5) has without r being a sized_range: if we know that r is an infinite range. Obviously taking 5 elements out of an infinite range would give you a range of with 5 elements (last I checked, infinity is in fact larger than 5, even for very large values of 5).

In range-v3, iota(0) is an infinite range. I mean, it is an infinite range in C++20 as well, but C++20 Ranges does not have this notion of infinite ranges while range-v3 does:

template<typename From, typename To /* = unreachable_sentinel_t*/>
struct RANGES_EMPTY_BASES iota_view
  : view_facade<iota_view<From, To>,
                same_as<To, unreachable_sentinel_t>
                    ? infinite
                    : std::is_integral<From>::value && std::is_integral<To>::value
                          ? finite
                          : unknown>
{

Our case here satisfies same_as<To, unreachable_sentinel_t>, so we're passing infinite into what range-v3 refers to as "cardinality".

take then detects that its input is infinite and returns default_sentinel as the sentinel:

CPP_auto_member
constexpr auto CPP_fun(end)()(const //
    requires range<Rng const>)
{
    if constexpr(sized_range<Rng const>)
        if constexpr(random_access_range<Rng const>)
            return ranges::begin(base_) +
                   static_cast<range_difference_t<Rng>>(size());
        else
            return default_sentinel;
    // Not to spec: Infinite ranges:
    else if constexpr(is_infinite<Rng const>::value)
        return default_sentinel;
    else
        return sentinel<true>{ranges::end(base_)};
}

So in this case, our iterator/sentinel pair is counted_iterator/default_sentinel, this pair satisfies sized_sentinel_for, so ranges::size works. These are equal when the count hits zero and subtraction simply negates the count.

C++20 simply, by design, does not have this notion of infinite ranges. It is unclear if it will or not in the future. I'm not even sure that Eric Niebler and Casey Carter were happy with the design in range-v3.

user_20690640
Related