How to fill the middle of a dynamic 2D array with a smaller one?

Question

I am working with a dynamic square 2D array that I sometimes need to enlarge for my needs. The enlarging part consist in adding a new case on each border of the array, like this:

To achieve this, I first copy the content of my actual 2D array in a temporary other 2D array of the same size. Then I create the new 2D array with the good size, and copy the original content of the array in the middle of the new one.

Is there any quick way to copy the content of the old array in the middle of my new array? The only way I have found so far is only by using two for sections:

for(int i = 1; i < arraySize-1; i++)
{
    for(int j = 1; j < arraySize-1; j++)
    {
        array[i][j] = oldArray[i-1][j-1];
    }
}

But I'm wondering if there is no quicker way to achieve this. I thought about using std::fill, but I don't see how it would be possible to use it in this particular case.

My EnlargeArray function:

template< typename T >
void MyClass<T>::EnlargeArray()
{
    const int oldArraySize = tabSize;

    // Create temporary array
    T** oldArray = new T*[oldArraySize];
    for(int i = 0; i < oldArraySize; i++)
    {
        oldArray[i] = new T[oldArraySize];
    }

    // Copy old array content in the temporary array
    for(int i = 0; i < arraySize; i++)
    {
        for(int j = 0; j < arraySize; j++)
        {
            oldArray[i][j] = array[i][j];
        }
    }

    tabSize+=2;

    const int newArraySize = arraySize;

    // Enlarge the array
    array= new T*[newArraySize];
    for(int i = 0; i < newArraySize; i++)
    {
        array[i] = new T[newArraySize] {0};
    }

    // Copy of the old array in the center of the new array
    for(int i = 1; i < arraySize-1; i++)
    {
        for(int j = 1; j < arraySize-1; j++)
        {
            array[i][j] = oldArray[i-1][j-1];
        }
    }

    for(int i = 0; i < oldArraySize; i++)
    {
        delete [] oldArray[i];
    }
    delete [] oldArray;
}

Answer 1

Is there any quick way to copy the content of the old array in the middle of my new array?

(Assuming the question is "can I do better than a 2D for-loop?".)

Short answer: no - if your array has R rows and C columns you will have to iterate over all of them, performing R*C operations.

std::fill and similar algorithms still have to go through every element internally.

---

Alternative answer: if your array is huge and you make sure to avoid false sharing, splitting the copy operation in multiple threads that deal with a independent subset of the array could be beneficial (this depends on many factors and on the hardware - research/experimentation/profiling would be required).

Answer 2

First, you can use std::make_unique<T[]> to manage the lifetime of your arrays. You can make your array contiguous if you allocate a single array of size row_count * col_count and perform some simple arithmetic to convert (col, row) pairs into array indices. Then, assuming row-major order:

• Use std::fill to fill the first and last rows with zeros.
• Use std::copy to copy the old rows into the middle of the middle rows.
• Fill the cells at the start and end of the middle rows with zero using simple assignment.

Answer 3

Do not enlarge the array. Keep it as it is and allocate new memory only for the borders. Then, in the public interface of your class, adapt the calculation of the offets.

To the client of the class, it will appear as if the array had been enlarged, when in fact it wasn't really touched by the supposed enlargement. The drawback is that the storage for the array contents is no longer contiguous.

Here is a toy example, using std::vector because I cannot see any reason to use new[] and delete[]:

#include <vector>
#include <iostream>
#include <cassert>

template <class T>
class MyClass
{
public:
    MyClass(int width, int height) :
        inner_data(width * height),
        border_data(),
        width(width),
        height(height)
    {
    }

    void Enlarge()
    {
        assert(border_data.empty()); // enlarge only once
        border_data.resize((width + 2) * 2 + (height * 2));
        width += 2;
        height += 2;
    }

    int Width() const
    {
        return width;
    }

    int Height() const
    {
        return height;
    }

    T& operator()(int x, int y)
    {
        assert(x >= 0);
        assert(y >= 0);
        assert(x < width);
        assert(y < height);

        if (border_data.empty())
        {
            return inner_data[y * width + x];
        }
        else
        {
            if (y == 0)
            {
                return border_data[x]; // top border
            }
            else if (y == height - 1)
            {
                return border_data[width + x]; // bottom border
            }
            else if (x == 0)
            {
                return border_data[width + height + y]; // left border
            }
            else if (x == width - 1)
            {
                return border_data[width * 2 + height * 2 + y]; // right border
            }
            else
            {
                return inner_data[(y - 1) * (width - 2) + (x - 1)]; // inner matrix
            }
        }
    }


private:
    std::vector<T> inner_data;
    std::vector<T> border_data;
    int width;
    int height;
};

int main()
{
    MyClass<int> test(2, 2);

    test(0, 0) = 10;
    test(1, 0) = 20;
    test(0, 1) = 30;
    test(1, 1) = 40;

    for (auto y = 0; y < test.Height(); ++y)
    {
        for (auto x = 0; x < test.Width(); ++x)
        {
            std::cout << test(x, y) << '\t';
        }
        std::cout << '\n';
    }
    std::cout << '\n';

    test.Enlarge();

    test(2, 0) = 50;
    test(1, 1) += 1;
    test(3, 3) = 60;

    for (auto y = 0; y < test.Height(); ++y)
    {
        for (auto x = 0; x < test.Width(); ++x)
        {
            std::cout << test(x, y) << '\t';
        }
        std::cout << '\n';
    }
}

Output:

10      20
30      40

0       0       50      0
0       11      20      0
0       30      40      0
0       0       0       60

The key point is that the physical representation of the enlarged "array" no longer matches the logical one.