Why can views::reverse transform a non-sized_range into a size_range?

Question

In [range.sized#1]:

The sized_­range concept refines range with the requirement that the number of elements in the range can be determined in amortized constant time using ranges​::​size.

template<class T>   
  concept sized_­range =
  range<T> &&
    requires(T& t) { ranges::size(t); };

The standard states that obtaining the size of ranges::sized_range is guaranteed to be in constant time. Consider the following:

auto r1 = std::views::iota(0)
    | std::views::filter([](int x){ return x % 2 == 0; })
    | std::views::take(1'000'000);

r1 is obviously not sized_range, because it is impossible to get its size in constant time, which also means that we use ranges::size to evaluate its size is also ill-formed.

But I discovered by accident that if we apply views::reverse on it, the new range r2 suddenly becomes a sized_range, and we can directly use ranges::size to get its size correctly, godbolt:

auto r2 = r1 | views::reverse;

static_assert(!ranges::sized_range<decltype(r1)>);
static_assert( ranges::sized_range<decltype(r2)>);
std::cout << std::ranges::size(r2) << "\n"; // print 500'000

However, it is obvious that the new range r2 is not a sized_range, since we can never get its size in constant time, this seems to violate what the standard says.

Why can views::reverse transform a non-sized_range into a sized_range? Obviously, this conversion will not have any effect on the size of the original range. Is this a standard defect or is it a library bug?

Answer 1

The requirement is amortized constant, not always constant.

• take_view<...> produces counted_iterators.
• So reverse_view<take_view<...>> produces reverse_iterator<counted_iterator<...>>
• counted_iterators can always be subtracted: you just subtract the count.
• So reverse_iterator<counted_iterator<...>> can always be subtracted too.
• ranges::size is defined for any range whose iterator/sentinel models sized_sentinel_for. That includes reverse_view<take_view<...>>.

To meet the amortized constant complexity requirement, reverse_view::begin caches the end of the source range if it needs to compute it (i.e., the source range isn't common).