在并行算法中使用ranges::view::iota

Question

由于c++17中没有基于索引的并行算法，我想知道

ranges::view::iota

是否可以与

std::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和英特尔的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)。

Answer 1

更新：

c++23采用P2408R5使得可以使用范围迭代器（例如

iota::iterator

）作为并行算法的输入。

主要库供应商已通过以下提交实施了此更改：

• libstdc++
• libc++
• MSVC STL

---

旧答案：

深入研究标准草案后，恐怕答案是否定的：使用它并不严格符合标准

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 要求。

正如 Billy O'Neal 在我在问题中发布的链接之一中指出的，

ranges::iota_view::iterator

的合理实现不太可能满足“相等迭代器引用同一对象”前向迭代器要求 [iterator.cpp17] 。因此，根据我的理解，

ranges::iota_view::iterator

不会满足Cpp17ForwardIterator的要求，同样的情况也适用于例如

boost::counting_iterator

。

但是，在实践中，我希望实现将使用

std::iterator_traits::iterator_category

来调度 算法的适当重载，正如 PSTL 似乎所做的那样。因此，我相信OP中的示例代码会按预期工作。 cmcstl2 不起作用的原因可能是使用的

iterator_category

属于

__stl2

命名空间，而不是

std

命名空间。

Answer 2

在 C++20 中，有一个

std::views::common

，它使范围适应标准迭代器对接受算法。将输入范围转换为

std::ranges::common_range

后，使用

std::ranges::begin

和

std::ranges::end

函数获取一对

std::transform

或您使用的任何算法的迭代器。

这里是一个示例程序，假设使用 C++20 编译器（这不是基于

ranges-v3

的实现）。我测试过的唯一一个（截至 2020 年 10 月）是 G++ 版本 10。

#include <algorithm>
#include <numeric>
#include <execution>
#include <iostream>
#include <vector>
#include <ranges>

int main()
{
    // A "large" number of elements (limited to ten for a reasonably small std::cout output)
    constexpr int N = 10;

    // Some range with a finite number of values (views::take at the end)
    auto very_long_input_range = std::views::iota(0) | std::views::take(N);

    // Source range converted to common_range (which supports std::begin & std::end)
    auto input_range = std::ranges::common_view(very_long_input_range);

    // Element processing function. E.g., if 'i' is a file name and this lambda parses it, it might be a big time-saver
    auto some_complex_function = [](auto i){ return i * i; };

    // Declare and allocate an output array (maybe range_value_t is an overkill here, but still)
    // Using std::ranges::size(input_range) instead of N can also help generalize this code,
    // but input_range must satisfy the std::ranges::sized_range concept
    std::vector< std::ranges::range_value_t<decltype(input_range)> > output_array( N );

    // Use C++17 std::execution::par with a pair of C++20 iterators from std::ranges
    std::transform(std::execution::par,
            std::ranges::begin(input_range),
            std::ranges::end(input_range),
            output_array.begin(),
            some_complex_function);

    // Test the output
    for (auto p: output_array)
            std::cout << p << std::endl;
}

G++10 (Ubuntu 20.20) 的命令行是

g++-10 -std=c++2a -o ptest ptest.cpp -ltbb -lstdc++

Answer 3

我自己也遇到过这个；我相信本质上根本问题是 std::ranges 和 range-v3 现在都需要 snetinels 的概念才能正常工作 - 请参阅here 获取有关此问题的帖子。我添加了一个单独的答案，因为这个概念是代码无法编译的理论原因。感谢其他答案指出了正确的解决方法，然后将它们转换为通用范围。

正如您所提到的，旧的 std 算法具有相同类型的迭代器，因此可以执行比较

i != end

以控制循环结构。各种标准库函数的重载依赖于两个迭代器具有相同的推导类型。现在，这被称为“公共范围”，因为迭代器共享公共类型。然而，对于范围来说，这种方法是有效的，我们的数据概念更加通用，并且在到达终点之前可能无法知道终点。因此，像以前一样，“结束”标记表示没有更多数据可供使用，但此行为现在被编码为单独的类型（sentinel），而不是依赖于比较，因为比较无法执行例如无限序列。因此，范围算法现在需要重载两个单独的模板参数 - 迭代器和哨兵，以便正确运行。如果没有适配器，范围就无法在传统迭代器算法中使用，但这正是 views::common 为我们做的事情。