Why does the parallel for_each require forward iterators?

Question

I was designing an iterator that goes over multiple containers and thus has a proxy object as a return type. Because of that, the best it can do is to be an input iterator (this is because forward iterators require reference to be an actual reference type, while this isn't true for input iterators as far as I see).

The (let me say) plain for_each works like a charm with my iterator.
However, when I looked at its parallel version, I saw that it accepts only forward iterators. Therefore I cannot use a complex iterator that returns a proxy object with it and this is annoying.
On the other side, I looked online to other notable implementations and this isn't as common as I thought initially - eg Intel TBB offers its own parallel for each that accepts input iterators.

My question is then: why doesn't the parallel std::for_each work with input iterators?
I cannot see the point of them being forward iterators, because at first glance it should work fine even with input iterators. What am I missing?

Answer 1

There is a known flaw with the C++17 iterator model in that proxy iterators can only ever be input iterators, for the reasons you point out. This has lots of downsides. The parallel algorithms don't need non-proxy iterators, but they definitely need the multi-pass guarantee. And the current iterator category model conflates the two.

With C++20 ranges, we get this idea of iterator_concept, which is a backwards-compatible shim to properly support proxy iterators. You can have an iterator_category of input_iterator_tag but an iterator_concept of forward_iterator_tag, for instance. The new ForwardIterator concept does not look at the category, it looks at the concept:

template<class I>
  concept ForwardIterator =
    InputIterator<I> &&
    DerivedFrom<ITER_CONCEPT(I), forward_iterator_tag> &&
    Incrementable<I> &&
    Sentinel<I, I>;

Whether or not the parallel algorithms will change is a different question that I can't answer.

Answer 2

The C++17 iterator concepts define a forward iterator as being the weakest form of iterator that requires multiple iterators in the same range to function. That is, you're allowed to copy a forward iterator, increment the copy, but still access the original value through the original iterator.

The pure IntputIterator concept only requires single-pass. Once you increment an iterator, all other copies of it become effectively invalid.

Being able to parallelize for_each ultimately requires each parallel invocation to get a distinct set of iterators and values to operate on. That means the iterator has to be copyable and independent of the others. Which requires them to be forward iterators.

Now yes, that means you can't use proxy iterators with parallel for_each, even if your iterators are independent of each other. That's just the limitations of the C++17 iterator concept model.