c++ - 是否可以使用 openMP 以 O(1) 复杂度初始化 vector ？ (C++)

Question

我正在尝试使用 openMP 在结构中并行化一些 vector 函数。虽然它适用于我的大多数实现，但我发现由于 std::vector<> 的构造函数具有线性复杂度，我无法获得更好的性能，反而得到比按顺序进行初始化更糟糕的东西。

这是初始化器之一

         /**
         * @brief Construct a new constant parallel Vector object with a given value constantEntry
         * 
         * @param dim 
         * @param constantEntry 
         */
        parallelVector(const int dim, const double constantEntry){
            dimension = dim;
            values = std::vector<double>(dimension);

            #pragma omp parallel for schedule(static)
            for (int i=0 ; i<dimension; i++){
                values[i] = constantEntry;
            }
        }

std::vector<>文档说我可以使用分配器获得 O(1) 复杂度，但由于我对它们不太熟悉，我想知道是否可以使用唯一指针来代替？

Answer 1

template<class T>
struct uninitialized_allocator:std::allocator<T> {
  template<class...Us>
  void construct( T* p, Us&&... us ){
    ::new((void*)p) T(std::forward<Us>(us)...);
  }
  // don't construct when passed 0 arguments
  void construct( T* p ) {};
};

然后:

    int dimension = 0;
    std::vector<double, uninitialized_allocator<double>> values;
    parallelVector(const int dim, const double constantEntry):
      dimension(dim),
      values(dim)
    {
        #pragma omp parallel for schedule(static)
        for (int i=0 ; i<dimension; i++){
            values[i] = constantEntry;
        }
    }

但请注意，您需要负责在调用 resize 以及使用 0 个参数的 emplace_back() 时初始化新的 vector 元素。

理论上，std::vector仍然对每个元素调用construct(T*)，但这是一个空操作，编译器擅长死-代码消除。因此，在重要的优化设置下，这应该可以满足您的需求。

请注意，我将 operator= 的使用更改为构造；它们不相同，并且 vector 在这两种情况下可以自由地表现得非常不同。