6

在[range.sized#1] 中：

该sized_­range概念对范围进行了细化，要求范围内的元素数量可以在摊销的 常数时间内使用来确定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它，新的范围r2突然变成了 a sized_range，我们可以直接使用godboltranges::size来正确获取它的大小：

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不是 a sized_range，因为我们永远无法在恒定时间内得到它的大小，这似乎违反了标准所说的。

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

4

1 回答 1

5

需求是摊销不变的，并不总是不变的。

  • take_view<...>产生counted_iterators。
  • 所以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如果需要计算源范围的末尾（即源范围不常见），则缓存它。

于 2021-04-21T13:03:15.023 回答