c++ - 有条件地并行填充 vector

Question

我想编写以下代码的多线程版本

template<typename Out, typename In, typename Cond, typename Func>
std::vector<Out> collect(std::vector<In> const&values,
                         Cond const&cond, Func const&func)
{
    std::vector<Out> result;
    for(auto const&val : values)
        if(cond(val))
            result.emplace_back(func(val));
    return result;
}

所选元素的顺序无关紧要。

一个简单的方法是

template<typename Out, typename In, typename Cond, typename Func>
std::vector<Out> collect(std::vector<In> const&values,
                         Cond const&cond, Func const&func)
{
    std::vector<Out> result(values.size());
    std::atomic<size_t> index = 0;
    // some multithreaded for loop implementation
    parallel_for(size_t(0),values.size(),[&](size_t i) {
        if(cond(values[i]))
            result[index++] = func(values[i]);
    });
    result.resize(index);
    return result;
}

(当然，初始化result是串行的，这里先忽略)。这似乎有效，但可能不是无锁的。有没有更好的办法？特别是，我能否避免分配太多数据(如果只选择了少量输入数据)？

问题与 std::copy_if 非常相似(它会是 std::transform_if 存在)——并行版本如何 std::copy_if(std::par,...)已实现(这是 C++17，但我仅限于 C++11)？

Answer 1

一个不错的方法是使用在最后合并的线程本地 vector 。如果不是因为它使用 OMP，这个答案(特别是最后一个代码示例)将是一个很好的拷贝:

https://stackoverflow.com/a/18671256/9528746

编辑:更改为更好的答案。