时间戳

首页 > 解决方案 > 在并行算法中使用 range::view::iota

c++ - 在并行算法中使用 range::view::iota

问题描述

由于在中没有基于索引的并行算法，我想知道是否可以结合使用来模拟它。那是：ranges::view::iotastd::for_each

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似乎为适当的类型（[range.iota.iterator]）提供随机访问：

iota_view<I, Bound>::iterator::iterator_category定义如下：

(1.1) — 如果I模型Advanceable，那么iterator_category是random_access_iterator_tag。

(1.2) — 否则，如果I模型Decrementable，iterator_category则为bidirectional_iterator_tag。

(1.3) — 否则，如果I模型Incrementable，iterator_category则为forward_iterator_tag。

(1.4) — 否则，iterator_category是input_iterator_tag。

上面的代码正确吗？iota_view使用这种方式是否有任何性能损失？

编辑：我用range-v3、cmcstl2和 Intel 的PSTL做了一些测试。

使用 range-v3，上面的示例无法使用 GCC 8 编译。编译器抱怨begin并end具有不同的类型：

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

使用 cmcstl2 代码可以干净地编译，但不能并行运行。在我看来，它回退到顺序版本，可能是因为不满足前向迭代器的要求（https://godbolt.org/z/yvr-M2）。

有一个有点相关的 PSTL 问题（https://github.com/intel/parallelstl/issues/22）。

标签： c++c++17stl-algorithmrange-v3c++20

解决方案

深挖标准草案后，恐怕答案是否定的： ranges::iota_view在for_each.

的并行重载for_each被声明为[alg.foreach]：

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

另一方面，在[algorithms.requirements]中，我们找到了约束：

如果算法的模板参数命名为ForwardIterator、ForwardIterator1或ForwardIterator2，则模板参数应满足Cpp17ForwardIterator要求。

正如比利奥尼尔在我在问题中发布的一个链接中所指出的那样，合理的实现ranges::iota_view::iterator不太可能满足“相等的迭代器引用相同的对象”前向迭代器要求[iterator.cpp17]。因此，据我了解，ranges::iota_view::iterator不会满足Cpp17ForwardIterator要求，例如 boost::counting_iterator.

但是，在实践中，我希望实现将用于std::iterator_traits::iterator_category调度算法的适当重载，就像 PSTL 似乎所做的那样。因此，我相信 OP 中的示例代码会按预期工作。cmcstl2 不起作用的原因可能是 usediterator_category属于__stl2命名空间而不是std那些。

推荐阅读