The common view of an enumerate view is not a random access range

[PiliLatiesa]

It is surprising to me that, even though an enumerate_view of a vector is a random access range, its common view is downgraded to a forward range:

$ cat test.cpp

#include <vector>
#include <range/v3/view/enumerate.hpp>
#include <range/v3/view/common.hpp>

int main()
{
  std::vector v = {1, 2, 3};

  auto View = ranges::views::enumerate(v) | ranges::views::common;

  static_assert(ranges::random_access_range<decltype(View)>);
}

$ g++ -std=c++20 test.cpp -I$(HOME)/range-v3-0.11.0/include/

test.cpp: En la función ‘int main()’:
test.cpp:11:25: error: static assertion failed
   11 |   static_assert(ranges::random_access_range<decltype(View)>);
      |   
[...]

/home/pililatiesa/range-v3-0.11.0/include/range/v3/iterator/concepts.hpp:345:60: nota: the required expression ‘((((-- i), (i --)), requires_<same_as<I&, decltype (-- i)> >), requires_<same_as<I, decltype ((i --))> >)’ is invalid
  343 |             --i,
      |             ~~~~
  344 |             i--,
      |             ~~~~
  345 |             concepts::requires_<same_as<I&, decltype(--i)>>,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
  346 |             concepts::requires_<same_as<I, decltype(i--)>>
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/pililatiesa/range-v3-0.11.0/include/concepts/concepts.hpp:459:7: nota: en definición de macro ‘CPP_REQUIRES_AUX_’
  459 |     { __VA_ARGS__; }
      |       ^~~~~~~~~~~
/home/pililatiesa/range-v3-0.11.0/include/concepts/concepts.hpp:67:30: nota: en expansión de macro ‘CPP_PP_CAT_’
   67 | #define CPP_PP_CAT(X, ...)   CPP_PP_CAT_(X, __VA_ARGS__)
      |                              ^~~~~~~~~~~
/home/pililatiesa/range-v3-0.11.0/include/concepts/concepts.hpp:448:5: nota: en expansión de macro ‘CPP_PP_CAT’
  448 |     CPP_PP_CAT(CPP_REQUIRES_, REQS)
      |     ^~~~~~~~~~
/home/pililatiesa/range-v3-0.11.0/include/range/v3/iterator/concepts.hpp:340:5: nota: en expansión de macro ‘CPP_requires’
  340 |     CPP_requires(bidirectional_iterator_,
      |     ^~~~~~~~~~~~

$ g++ --version
g++ (GCC) 10.2.0

[marehr]

Hi @PiliLatiesa,

the main problem is that enumerate is not a sized-ranges, and a common_view will only preserve random_access+sized-ness if the underlying view is random_access+sized.

The basic idea of the common view is to convert any (iterator, sentinel) pair into a new (iterator', iterator') pair, but this time of the same type. The main problem is, if your underlying view has no end, i.e. is not sized, it either can't jump to the end, because it is infinite, or can't jump in constant time O(1) to the end. If it can't, common will lower its guarantees to input_range or forward_range.

Without any guarantee, I think the property guarantees look like this:

underlying range	common_view
input_range	input_range + common_range
forward_range	forward_range + common_range
bidirectional_range	forward_range + common_range
bidirectional_range + common_range	bidirectional_range + common_range
random_access_range	forward_range + common_range
random_access_range + common_range	random_access_range + common_range
random_access_range + sized_range	random_access_range + common_range + sized_range
contiguos_range	contiguos_range + common_range

https://godbolt.org/z/K4Mzcs

I haven't looked into why enumerate isn't a sized_range.

[marehr]

https://github.com/ericniebler/range-v3/blob/fa00307bebb503d58107c6abab3bea4ac4930177/include/range/v3/view/enumerate.hpp#L102-L113

That means enumerate zips your given range with a special "counting" view.

https://github.com/ericniebler/range-v3/blob/fa00307bebb503d58107c6abab3bea4ac4930177/include/range/v3/view/enumerate.hpp#L33-L34

And that view is defined as infinite. My guess is that zip is not sized, because one of the ranges is not sized. So this is either a bug in zip or in enumerate. A zip of (infinite_view, sized_view) should be sized, because zip will always iterate until it reaches the first end of its iterators.

[PiliLatiesa]

Thanks for your reply @marehr!

A zip of (infinite_view, sized_view) should be sized, because zip will always iterate until it reaches the first end of its iterators.

I agree. Especially bearing in mind that enumerate uses a dedicated index view instead of iota_view.

In contrast, this is accepted by legacy algorithms expecting random access iterators:

ranges::iota_view<std::size_t, std::size_t> IotaView(0, Vector.size());

auto ZipView = ranges::views::zip(IotaView, Vector);

static_assert(std::is_same_v<std::random_access_iterator_tag,
              std::iterator_traits<decltype(std::begin(ZipView))>::iterator_category>);

even though the difference type of IotaView should ideally be that of the vector.

[PiliLatiesa]

It seem that the range-v3 implementation of enumerate is not in sync with the std proposal (P2164R3), which IMHO is more sensible because an enumerate view of a common, sized range produces a common, sized range.