Can I convert my 1D vector to a 2D vector faster than this?

user_7790545 0
Viewed 220

The question is quite straightforward. After some trials, here is the most efficient code I found:

//For the sake of the example, I initialize every entry as zero.
vector<float> vector1D(1024 * 768, 0); 
vector<vector<float>> vector2D(768, vector<float>(1024,0));

int counter = 0;
for (int i = 0; i < 768; i++) {
    for (int j = 0; j < 1024; j++) {
        vector2D[i][j] = vector1D[counter++];
    }
}

Is there a faster way?

2d-vector vector for-loop c++
3 Answers

Yes.

You can remap the way you access the elements without needing to copy them. You can create a "view" class to achieve that:

template<typename T>
class two_dee_view
{
public:
    two_dee_view(std::vector<T>& v, std::size_t row, std::size_t col)
        : v(v), stride(col) { if(v.size() < row * col) v.resize(row * col); }

    T& operator()(std::size_t row, std::size_t col)
        { return v[(row * stride) + col]; }

    T const& operator()(std::size_t row, std::size_t col) const
        { return v[(row * stride) + col]; }

    std::size_t col_size() const { return stride; }
    std::size_t row_size() const { return v.size() / stride; }

private:
    std::vector<T>& v;
    std::size_t stride;
};

int main()
{
    std::vector<double> v {1.0, 2.0, 3.0, 4.0, 5.0, 6.0};

    two_dee_view<double> v2d(v, 2, 3);

    for(auto row = 0U; row < v2d.row_size(); ++row)
        for(auto col = 0U; col < v2d.col_size(); ++col)
            std::cout << row << ", " << col << ": " << v2d(row, col) << '\n';
}

Output:

0, 0: 1
0, 1: 2
0, 2: 3
1, 0: 4
1, 1: 5
1, 2: 6

The class simply maintains a reference to the std::vector you pass in to the constructor. You should only use the two_dee_view as long as the original std::vector lives but no longer.

user_38077290

It might be faster by using memcpy, as that is the lowest possible level of an API for copying memory and is likely that there are compiler optimizations which may use specific instructions, etc. and make if faster:

for (int i = 0; i < 768; i++) {
    memcpy(vector2D[i].data(), &vector1D[i * 1024], sizeof(float) * 1024);
}

Keep in mind that you shouldn't be using memcpy for anything but trivially-copiable data. That is, it will work fine for float and int but not for classes as the copy constructor will not be called.

user_9888580

If you have to use a vector of vectors for some reason, using memcpy or memmove is faster (because it's a single step, as described in another reply). But you should use the STL instead of doing it by yourself.

vector<float> vector1D(1024 * 768, 0);
vector<vector<float>> vector2D(768, vector<float>(1024, 0));

for (int i = 0; i < 768; i++) {
  vector2D[i].assign(next(vector1D.cbegin(), 1024 * i),
                     next(vector1D.cbegin(), 1024 * (i + 1)));
}

This results in a straight memmove (depending on the STL implementation) but is much more safe, optimized and (possibly) readable.

user_107650310
Related