Почему параллельный for_each требует прямых итераторов?

Question

Я проектировал итератор, который работает с несколькими контейнерами и, таким образом, имеет прокси-объект в качестве возвращаемого типа.Из-за этого лучшее, что он может сделать, это быть входным итератором (это потому, что для прямых итераторов требуется reference, чтобы быть реальным ссылочным типом, в то время как это не так для входных итераторов, насколько я вижу).

(позвольте мне сказать) обычный for_each работает как шарм с моим итератором.
Однако, когда я посмотрел на его параллельную версию, я увидел, что он принимает только прямые итераторы.Поэтому я не могу использовать сложный итератор, который возвращает прокси-объект вместе с ним, и это раздражает.
С другой стороны, я посмотрел в Интернете другие известные реализации, и это не так часто, как я думал изначально - например, Intel TBB предлагаетсвоя параллель для каждого, который принимает входные итераторы.

Мой вопрос: почему параллель std::for_each не работает с входными итераторами?
Я не вижу смысла в том, что они являются прямыми итераторами, потому чтона первый взгляд, он должен прекрасно работать даже с входными итераторами.Чего мне не хватает?

Answer 1

Существует известная ошибка в модели итераторов C ++ 17, заключающаяся в том, что прокси-итераторы могут быть только входными итераторами по указанным вами причинам. Это имеет много минусов. Параллельным алгоритмам не нужны не-прокси итераторы, но им определенно нужна многопроходная гарантия. И текущая модель категории итератора объединяет два.

С диапазонами C ++ 20 мы получаем идею iterator_concept, которая является обратно совместимой оболочкой для правильной поддержки прокси-итераторов. Вы можете иметь iterator_category input_iterator_tag, но, например, iterator_concept forward_iterator_tag. Новая концепция ForwardIterator не смотрит на категорию, она смотрит на концепцию:

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

Изменится ли параллельный алгоритм или нет - это другой вопрос, на который я не могу ответить.

Answer 2

Концепции итератора C ++ 17 определяют прямой итератор как самую слабую форму итератора, для работы которой требуется несколько итераторов в одном диапазоне. То есть вам разрешено копировать прямой итератор, увеличивать его, но при этом обращаться к исходному значению через оригинальный итератор.

Чистая концепция IntputIterator требует только однопроходного. Как только вы увеличиваете итератор, все его копии становятся недействительными.

Возможность распараллеливания for_each в конечном счете требует, чтобы каждый параллельный вызов получал отдельный набор итераторов и значений для работы. Это означает, что итератор должен быть копируемым и независимым от других. Что требует, чтобы они были прямыми итераторами.

Теперь да, это означает, что вы не можете использовать прокси-итераторы с параллельными for_each, даже если ваши итераторы независимы друг от друга. Это всего лишь ограничения концептуальной модели итератора C ++ 17.