是否可以使用复杂度为 O(1) 的 openMP 初始化向量？(C++)

Question

我正在尝试使用 openMP 在结构中并行化一些向量函数。虽然它适用于我的大多数实现，但我发现由于 for 的构造函数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以及以及emplace_back()与0参数。

理论上，std::vector仍然会调用construct(T*)每一个元素，但那是无用的，编译器擅长消除死代码。所以在非平凡的优化设置下，这应该做你想做的。

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