CODEWITHSUNDEEP
c++c++20range-v3std-ranges
康桓瑋
康桓瑋

Reputation: 42736

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

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?

Upvotes: 6

Views: 278

Answers (1)

T.C.
T.C.

Reputation: 137310

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

Upvotes: 5

Related Questions