Почему views::reverse может преобразовать non-sized_range в size_range?

В [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 внезапно становится sized_range, и мы можем напрямую использовать ranges::size, чтобы получить правильный размер, 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? Очевидно, что это преобразование никак не повлияет на размер исходного диапазона. Это стандартный дефект или ошибка библиотеки?


person 康桓瑋    schedule 21.04.2021    source источник
comment
Обратите внимание, что r2.size() не работает с candidate: 'constexpr auto std::ranges::reverse_view<_Vp>::size() requires sized_range<_Vp>.   -  person eerorika    schedule 21.04.2021
comment
Амортизированный делает много работы здесь.   -  person T.C.    schedule 21.04.2021


Ответы (1)


Требование амортизируется постоянно, не всегда постоянно.

  • 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 кэширует конец исходного диапазона, если ему необходимо его вычислить (т. е. исходный диапазон не является общим).

person T.C.    schedule 21.04.2021