analog feelings, digital world

Dynamic, multidimensional arrays are not supported directly by C++. If you create such an array in following way:

array = new int*[_size];
for( unsigned int i = 0; i < _size; i++ )
    array[i] = new int[_size];

you are in fact creating one dimensional array of pointers to other arrays. Main two disadvantages of this approach:

• Initialization can take a while (image really big 2-3 dimensional array, lets say: 16384 x 16384: how many times memory allocation is being performed? 1 + 16384. Quite a lot, right?
• dynamic arrays created like in the code above can not be used as a parameters for memcmp, memcpy, memset & similar functions. the memory allocated is not a continuous memory block.

As I needed a 2-dimensional array that occupies continuous block of memory – I started googling :) I have found a great solution by  David Maisonave (Axter) (code, header). The code above could be rewritten as follows:

Pixel** Initialize2dArray( int size )
{
    Pixel **array2d;
    Pixel *temp;
    array2d = new Pixel*[size];
    temp = new Pixel[size * size];

    for( int i = 0; i < size; i++ )
    {
        array2d[i] = temp;
        temp += size;
    }
    return array2d;
}

void Deinitialize2dArray( Pixel** array2d )
{
    delete [] *array2d;
    delete [] array2d;
}

How does it work? The idea is to put in every ‘cell’ of the array a pointer that will point to a part of the ‘temp’ array. The parts are of the ‘width’ size. So, when you type array[2][3] it actually selects the data that is indexed 2 * width + 3 = exactly what you’re expecting, right? But beware, there is a little difference when using array created in described way and all those mem* functions I wrote at the beginning, instead of writing:

memcpy( array2d, source, sizeof(int) * size * size );

you actually need to write:

memcpy( &array2d[0][0], source, sizeof(int) * size * size );

It is great, right? And, of course, you could try using std::vector (it allocates continuous block of memory – correct me if I am wrong) or Boost Multi Array instead – but if you’re worrying about performance… I think the presented solution is the best.

Tags: c++