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

要求是摊销常数，并不总是常数。

• take_view<...>产生counted_iterator.
• 所以reverse_view<take_view<...>>产生reverse_iterator<counted_iterator<...>>
• counted_iterators 总是可以减去：您只需减去计数。
• 所以reverse_iterator<counted_iterator<...>>也总是可以减去。
• ranges::size为迭代器/哨兵模型的任何范围定义sized_sentinel_for。这包括reverse_view<take_view<...>>.

为了满足摊销的恒定复杂度要求，reverse_view::begin如果需要计算源范围的末尾，则缓存它（即源范围不常见）。