为什么views::reverse可以把non-sized_range变成size_range?

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

[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); };

标准规定获取ranges::sized_range的大小保证在常数时间内。考虑以下因素:

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

r1显然不是sized_range,因为在 常数时间,这也意味着我们使用 ranges::size 来评估其大小也是错误的。

但是我无意中发现如果我们应用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

但是,很明显新范围r2不是sized_range,因为我们永远无法在常数时间内得到它的大小,这似乎违反了标准所说的。

为什么 views::reverse 可以将非 sized_range 转换为 sized_range?显然,这种转换不会对原始范围的大小产生任何影响。这是标准缺陷还是库错误?

要求是摊销常量,不总是常量。

  • take_view<...> 产生 counted_iterators.
  • 所以 reverse_view<take_view<...>> 产生 reverse_iterator<counted_iterator<...>>
  • counted_iterators 总是可以减去:你只需减去计数即可。
  • 所以reverse_iterator<counted_iterator<...>>也总是可以减去。
  • ranges::size 是为 iterator/sentinel 模型 sized_sentinel_for 的任何范围定义的。这包括 reverse_view<take_view<...>>.

为了满足摊销常量复杂性要求,reverse_view::begin 如果需要计算源范围的结尾(即源范围不常见),则缓存它。