Transform a vector of elements into another vector of elements in parallel, without requiring the latter to be initialized

Question

I have a const std::vector<T> source of a big size, and a std::vector<T> dest. I want to apply a transformation to each element in source and store it in dest; all of this in parallel, and knowing that T is not default constructible.

What I initially attempted was using std::transform with a parallel execution policy:

std::transform(std::execution::par_unseq,
  source.begin(), source.end(),
  dest.begin(),
  [](const T& elem) { return op(elem); }
);

However, when I first compiled and run this, to my surprise, I discovered that, although the transform "loops" for source.size() times, dest's content remains unchanged.

I discovered that this is because dest must have the same size of source prior to the transform. However, I cannot do resize dest to the size of source, because T is not default constructible as it does not have a default constructor. I also would prefer not to provide a default constructor for it (first of all, it does not make sense in T's logic, but you can think that it would be expensive to call).

Does C++ STL offer any other algorithm for achieving what I have in mind?

What would suffice is an algorithm where each thread computes its own part of the source vector, and then the results are collected and joined into the same dest vector.

Answer 1

Try using a std::vector<> of std::optional<T>:

#include <algorithm>
#include <execution>
#include <optional>
#include <vector>

struct T { // NOTE: T is NOT default-constructible!
    T(int x) : value(x) {}
    operator int() { return value; }
    int value;
};

T op(const T& in) {
    return in.value * 2;
}

#include <iostream>

int main() {
    const std::vector<T> source = {4, 5, 6, 7, 8, 9, 10, 11};
    std::vector<std::optional<T>> dest(source.size());

    std::transform(
        std::execution::par_unseq,
        source.begin(), source.end(),
        dest.begin(),
        [](const T& elem) { return op(elem); }
    );
    for (auto i : dest) {
        std::cout << *i << " ";
    }
    std::cout << std::endl;
}

Sample output: 8 10 12 14 16 18 20 22

Godbolt demo: https://godbolt.org/z/ecf95cneq

This is admittedly not that idiomatic, as your dest array now has every element wrapped up in an std::optional<> container, but I believe it otherwise offers the semantics you specify.

Answer 2

Also inspired by @saxbophone's answer, here's a solution that avoids the (minor) overhead that std::optional introduces. It is based on the following simple, roll-your own container:

template <class T> class SimpleVector
{
public:
    SimpleVector (size_t capacity) :
        m_capacity (capacity), storage (static_cast <T *> (malloc (capacity * sizeof (T)))) { }
    ~SimpleVector () { free (storage); }

    T *data () { return storage; }
    T &operator [] (size_t i) { return storage [i]; }
    T *begin () { return storage; }
    T *end () { return storage + m_capacity; }

private:
    size_t m_capacity;
    T *storage;
};

This requires one T to be constructed and subsequently moved for each element generated by std::transform, which is the same as the std::optional solution (I did test this). Note the use of malloc and free to avoid default-constructing any Ts.

The complete code is here and looks like this (it generates the same output as @sax):

#include <iostream>
#include <algorithm>
#include <execution>
#include <vector>
#include <utility>

template <class T> class SimpleVector
{
public:
    SimpleVector (size_t capacity) :
        m_capacity (capacity), storage (static_cast <T *> (malloc (capacity * sizeof (T)))) { }
    ~SimpleVector () { free (storage); }

    T *data () { return storage; }
    T &operator [] (size_t i) { return storage [i]; }
    T *begin () { return storage; }
    T *end () { return storage + m_capacity; }

private:
    size_t m_capacity;
    T *storage;
};

struct T
{
    T (int x) : value (x) { }
    operator int () const { return value; }
    int value;
};

T op (const T& in) { return in.value * 2; }

int main ()
{
    const std::vector <T> source = {4, 5, 6, 7, 8, 9, 10, 11};
    SimpleVector <T> dest (source.size ());

    std::transform (std::execution::par_unseq,
        source.cbegin (), source.cend (), dest.begin (),
        [] (const T& elem) { return op (elem); } );

    for (const auto &it : dest) { std::cout << it << " "; }
}

Feel free to use SimpleVector for anything you like if you so choose. You can always add accessor / convenience methods to it if you need them.

Answer 3

Inspired by @saxbophone answer, you could also use a vector of pointers.

Credit for the code template to @saxbophone.

#include <algorithm>
#include <execution>
#include <optional>
#include <vector>

struct T { // NOTE: T is NOT default-constructible!
    T(int x) : value(x) {}
    operator int() { return value; }
    int value;
};

T* op(const T& in) {
    return new T(in.value*2);
}

#include <iostream>

int main() {
    const std::vector<T> source = {4, 5, 6, 7, 8, 9, 10, 11};
    std::vector<T*> dest(source.size());

    std::transform(
        std::execution::par_unseq,
        source.begin(), source.end(),
        dest.begin(),
        [](const T& elem) { return op(elem); }
    );
    for (auto i : dest) {
        std::cout << *i << " ";
    }
    std::cout << std::endl;

    // Don't forget to delete dest.
}

Live example: https://godbolt.org/z/r73qr1ze3