为什么并行的for_each需要正向迭代器？

Question

我正在设计一个遍历多个容器的迭代器，因此将代理对象作为返回类型。因此，最好的办法是成为输入迭代器（这是因为前向迭代器需要reference是实际的引用类型，而据我所知，这对于输入迭代器而言并非如此）。

（让我说）plain for_each就像我的迭代器一样具有魅力。
但是，当我查看其并行版本时，我发现它仅接受转发迭代器。因此，我不能使用复杂的迭代器来返回代理对象，这很烦人。
另一方面，我在网上寻找其他著名的实现，这并不像我最初想象的那么普遍-例如，英特尔®TBB为每个接受输入迭代器的设备提供了自己的并行处理。

那么我的问题是：为什么并行不能std::for_each与输入迭代器一起使用？
我看不到它们是正向迭代器的意义，因为乍一看它即使在输入迭代器中也能正常工作。我想念什么？

Answer 1

由于您指出的原因，C ++ 17迭代器模型存在一个已知缺陷，即代理迭代器只能是输入迭代器。这有很多缺点。并行算法不需要非代理迭代器，但它们确实需要多遍保证。并且当前的迭代器类别模型将两者合并。

在C ++ 20范围中，我们有了的想法iterator_concept，这是向后兼容的填充程序，可以正确地支持代理迭代器。例如，您可以拥有一个iterator_categoryof，input_iterator_tag但是一个iterator_conceptof 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 迭代器概念将前向迭代器定义为最弱的迭代器形式，它需要同一范围内的多个迭代器才能发挥作用。也就是说，您可以复制前向迭代器，增加副本，但仍然可以通过原始迭代器访问原始值。

纯粹的 InputIterator 概念只需要单次传递。一旦你增加了一个迭代器，它的所有其他副本都变得无效。

能够并行化for_each最终需要每个并行调用来获得一组不同的迭代器和值来操作。这意味着迭代器必须是可复制的并且独立于其他迭代器。这要求它们是前向迭代器。

现在是的，这意味着您不能将代理迭代器与 parallel 一起使用for_each，即使您的迭代器彼此独立。这只是 C++17 迭代器概念模型的局限性。