Using ranges::view::iota in parallel algorithms

Question

Since there is no index based parallel for algorithm in c++17, I'm wondering if ranges::view::iota can be used in combination with std::for_each to emulate that. That is:

using namespace std;

constexpr int N= 10'000'000;
ranges::iota_view indices(0,N);
vector<int> v(N);

for_each(execution::par_unseq,indices.begin(),indices.end(),[&](int i) { v[i]= i; });

iota_view seems to provide random access for appropriate types ([range.iota.iterator]):

iota_view<I, Bound>::iterator::iterator_category is defined as follows:

(1.1) — If I models Advanceable, then iterator_category is random_access_iterator_tag.

(1.2) — Otherwise, if I models Decrementable, then iterator_category is bidirectional_iterator_tag.

(1.3) — Otherwise, if I models Incrementable, then iterator_category is forward_iterator_tag.

(1.4) — Otherwise, iterator_category is input_iterator_tag.

Is the above code correct? Is there any performance penalty in using iota_view this way?

---

EDIT: I've made some tests with range-v3, cmcstl2, and Intel's PSTL.

Using range-v3, the above example fails to compile with GCC 8. The compiler complains about begin and end having different types:

deduced conflicting types for parameter ‘_ForwardIterator’ (‘ranges::v3::basic_iterator<ranges::v3::iota_view<int, int> >’ and ‘ranges::v3::default_sentinel’)

Using cmcstl2 the code compiles cleanly, but it doesn't run in parallel. It seems to me that it falls back to the sequential version, maybe because the forward iterators requirements are somehow not met (https://godbolt.org/z/yvr-M2).

There is a somewhat related PSTL issue (https://github.com/intel/parallelstl/issues/22).

Answer 1

After digging in the standard draft, I'm afraid that the answer is no: it is not strictly standard compliant to use ranges::iota_view in the parallel version of for_each.

The parallel overload of for_each is declared as [alg.foreach]:

template<class ExecutionPolicy, class ForwardIterator, class Function>
  void for_each(ExecutionPolicy&& exec,
                ForwardIterator first, ForwardIterator last,
                Function f);

On the other hand, in [algorithms.requirements] we find the constraint:

If an algorithm's template parameter is named ForwardIterator, ForwardIterator1, or ForwardIterator2, the template argument shall satisfy the Cpp17ForwardIterator requirements.

As noted by Billy O'Neal in one of the links I posted in the question, a sensible implementation of ranges::iota_view::iterator is very unlikely to meet the "equal iterators reference the same object" forward iterator requirement [iterator.cpp17]. Therefore, in my understanding, ranges::iota_view::iterator won't satisfy the Cpp17ForwardIterator requirements, and the same goes for e.g. boost::counting_iterator.

However, in practice I would expect that implementations will use std::iterator_traits::iterator_category to dispatch the appropriate overload of the algorithm, as PSTL seems to do. Therefore, I believe that the example code in the OP would work as intended. The reason that cmcstl2 doesn't work is probably that the used iterator_category belong to the __stl2 namespace instead of being the std ones.