How can I get contiguous memory in dynamic array allocation?

[VernonDozier]

Some similar recent threads have reminded me that I've been wanting to ask this for a while. I would like to declare a 3-dimensional array that uses contiguous memory so that I can calculate memory offsets from the base array element ( x[0][0][0] ) and use pointer arithmetic to access any array element I want. This pointer arithmetic requires that the memory allocated for the array is guaranteed to be contiguous. This seems to be possible when the array dimensions are known at compile time, but I've been unsuccessful at doing so when those dimensions are known only at runtime. Here is my program. It dynamically allocates memory, then statically allocates it. The address and value of each element is displayed. The static array elements are contiguous. The dynamic array elements are not. Dynamic array allocation code is lines 17 through 26.

#include <iostream>
using namespace std;

int main ()
{
    const int DIM1 = 2;
    const int DIM2 = 3;
    const int DIM3 = 4;
    int dim1, dim2, dim3;
    cout << "Enter dimension 1 of array: ";
    cin >> dim1;
    cout << "Enter dimension 2 of array: ";
    cin >> dim2;
    cout << "Enter dimension 3 of array: ";
    cin >> dim3;
    
    int*** x;
    x = new int**[dim1];
    for (int i = 0; i < dim1; i++)
    {
        x[i] = new int*[dim2];
        for (int j = 0; j < dim2; j++)
        {
            x[i][j] = new int[dim3];
        }
    }
    
    for (int i = 0; i < dim1; i++)
    {
        for (int j = 0; j < dim2; j++)
        {
            for (int k = 0; k < dim3; k++)
            {
                x[i][j][k] = 10000 * i + 100 * j + k;
            }
        }
    }

    cout << "\nDynamic array display\n";
    cout << 'i' << '\t' << 'j' << '\t' << 'k' << '\t';
    cout << "&x[i][j][k]" << '\t' << "x[i][j][k]\n\n";    
    for (int i = 0; i < dim1; i++)
    {
        for (int j = 0; j < dim2; j++)
        {
            for (int k = 0; k < dim3; k++)
            {
                cout << i << '\t' << j << '\t' << k << '\t';
                cout << &x[i][j][k] << '\t' << x[i][j][k] << endl;
            }
        }
    }
    
    int y[DIM1][DIM2][DIM3];
    
    for (int i = 0; i < DIM1; i++)
    {
        for (int j = 0; j < DIM2; j++)
        {
            for (int k = 0; k < DIM3; k++)
            {
                y[i][j][k] = 10000 * i + 100 * j + k;
            }
        }
    }

    cout << "\nStatic array display\n";    
    cout << 'i' << '\t' << 'j' << '\t' << 'k' << '\t';
    cout << "&y[i][j][k]" << '\t' << "y[i][j][k]\n\n";
    for (int i = 0; i < DIM1; i++)
    {
        for (int j = 0; j < DIM2; j++)
        {
            for (int k = 0; k < DIM3; k++)
            {
                cout << i << '\t' << j << '\t' << k << '\t';
                cout << &y[i][j][k] << '\t' << y[i][j][k] << endl;
            }
        }
    }
    
    return 0;
}

I think I know what the problem is, but I don't know the solution. Here is the output when I enter 2, 3, and 4 respectively for the dimensions. Note the red lines below. Those are examples of array elements which are not contiguous in memory. Is there a way to declare this array so that this does not happen?

Enter dimension 1 of array: 2
Enter dimension 2 of array: 3
Enter dimension 3 of array: 4

Dynamic array display
i	j	k	&x[i][j][k]	x[i][j][k]

0	0	0	0x3e24c8	0
0	0	1	0x3e24cc	1
0	0	2	0x3e24d0	2
0	0	3	0x3e24d4	3
0	1	0	0x3e24e0	100
0	1	1	0x3e24e4	101
0	1	2	0x3e24e8	102
0	1	3	0x3e24ec	103
0	2	0	0x3e24f8	200
0	2	1	0x3e24fc	201
0	2	2	0x3e2500	202
0	2	3	0x3e2504	203
1	0	0	0x3e2528	10000
1	0	1	0x3e252c	10001
1	0	2	0x3e2530	10002
1	0	3	0x3e2534	10003
1	1	0	0x3e2540	10100
1	1	1	0x3e2544	10101
1	1	2	0x3e2548	10102
1	1	3	0x3e254c	10103
1	2	0	0x3e2558	10200
1	2	1	0x3e255c	10201
1	2	2	0x3e2560	10202
1	2	3	0x3e2564	10203

Static array display
i	j	k	&y[i][j][k]	y[i][j][k]

0	0	0	0x22fee0	0
0	0	1	0x22fee4	1
0	0	2	0x22fee8	2
0	0	3	0x22feec	3
0	1	0	0x22fef0	100
0	1	1	0x22fef4	101
0	1	2	0x22fef8	102
0	1	3	0x22fefc	103
0	2	0	0x22ff00	200
0	2	1	0x22ff04	201
0	2	2	0x22ff08	202
0	2	3	0x22ff0c	203
1	0	0	0x22ff10	10000
1	0	1	0x22ff14	10001
1	0	2	0x22ff18	10002
1	0	3	0x22ff1c	10003
1	1	0	0x22ff20	10100
1	1	1	0x22ff24	10101
1	1	2	0x22ff28	10102
1	1	3	0x22ff2c	10103
1	2	0	0x22ff30	10200
1	2	1	0x22ff34	10201
1	2	2	0x22ff38	10202
1	2	3	0x22ff3c	10203

[Salem]

If all the minor dimensions are static, then you can allocate dynamically, and be contiguous with the result in one easy step.

int (*ptr)[CONST_SIZE] = new int [howmany][CONST_SIZE];
//
delete [] ptr;

If not, then you can allocate like this. It allocates space for the pointers, then space for the array itself. This can be extended to as many dimensions as you need.

#include <iostream>
using namespace std;

int main ( ) {
    const int rows = 3, cols = 5;
    int **arr;

    // allocate
    arr = new int*[rows];
    arr[0] = new int[rows*cols];
    for ( int i = 1 ; i < rows ; i++ ) {
        arr[i] = arr[i-1] + cols;
    }

    // populate
    for ( int r = 0 ; r < rows ; r++ ) {
        for ( int c = 0 ; c < cols ; c++ ) {
            arr[r][c] = r + c;
        }
    }

    // demonstrate
    int *contig = &arr[0][0];
    for ( int r = 0 ; r < rows ; r++ ) {
        for ( int c = 0 ; c < cols ; c++ ) {
            cout << (void*)&arr[r][c] << " "
                 << arr[r][c] << " "
                 << *contig << "  ";
            contig++;
        }
        cout << endl;
    }

    // deallocate
    delete [] arr[0];
    delete [] arr;
}

The results

$ g++ foo.cpp
$ ./a.exe
0x6a0268 0 0  0x6a026c 1 1  0x6a0270 2 2  0x6a0274 3 3  0x6a0278 4 4
0x6a027c 1 1  0x6a0280 2 2  0x6a0284 3 3  0x6a0288 4 4  0x6a028c 5 5
0x6a0290 2 2  0x6a0294 3 3  0x6a0298 4 4  0x6a029c 5 5  0x6a02a0 6 6

[Duoas]

That's because you are actually creating two different types of structure.

In C and C++, arrays are something of a mixed bag.

When you declare [B]int[/B] a[ 10 ][ 5 ]; What is actually allocated is [B]int[/B] a[ 10 * 5 ]; And when you access: a[ 4 ][ 3 ] what that translates to is: *(a + (4 * 10) + 3) In contrast, an array of pointers to arrays is an entirely different thing: [B]int[/B] *a[ 10 ] In C and C++ a pointer can be dereferenced as if it were an array, but whereas before only a calculated offset and a single dereference was needed to access an element, now two dereferences are needed: a[ 4 ][ 3 ] is the same as: *(a[ 4 ] + 3) which is the same as: *(*(a + 4) + 3) Whew.

So to allocate a contiguous memory space you need to multiply the dimensions to get the total amount of memory, then do the offset calculations yourself

int *a = new int[ 10 * 5 ]  // or int *a = new int[ 10 ][ 5 ]

int& elt( int *a, int rows, int cols, int row, int col )
  {
  if ((row >= rows) or (col >= cols)) throw 1;
  return *(a + (row * cols) + col);
  }

elt( a, 10, 5, 4, 3 ) = 42;
cout << elt( a, 10, 5, 4, 3 );

Hope this helps.

[edit] Too slow again...

[VernonDozier]

Hey, thanks guys! I've been having a little trouble getting from two dimensions to three, but I think I may have cracked it. The code may need a little tidying and I'm still playing with it, but it appears to work, at least with my limited testing so far. Here's the allocation code:

int*** x;
    x = new int**[dim1];
    x[0] = new int*[dim2];
    x[0][0] = new int[dim1 * dim2 * dim3];
    for (int j = 1; j < dim2; j++)
         x[0][j] = x[0][j-1] + dim3;

    for (int i = 1; i < dim1; i++)
    {
         x[i] = new int*[dim2];
         x[i][0] = x[i-1][0] + (dim2 * dim3);
         for (int j = 1; j < dim2; j++)
         {
             x[i][j] = x[i][j-1] + dim3;
         }
    }

And the display code is this:

for (int i = 0; i < dim1; i++)
    {
        for (int j = 0; j < dim2; j++)
        {
            for (int k = 0; k < dim3; k++)
            {
                cout << i << '\t' << j << '\t' << k << '\t';
                cout << &x[i][j][k] << '\t' << x[i][j][k] << '\t';
                cout << *(x[0][0] + (i*(dim2*dim3) + j*dim3 + k)) << endl;
            }
        }
    }

The two expressions in red give the same results and the memory seems to be contiguous. Was this about what you guys had in mind? Thanks again.

[Salem]

> x[0] = new int*[dim2];
Should be
x[0] = new int*[dim1*dim2];

Also, for a 3D array, you only need 3 allocations. The rest is just pointer arithmetic.

[VernonDozier]

I don't think I understand what you are suggesting that I do, Salem. Actually, I'm confident that I DON'T understand because this keeps crashing. Here's what I did.

int*** x;
    x = new int**[dim1];
    x[0] = new int*[dim1 * dim2];    
    x[0][0] = new int[dim1 * dim2 * dim3];
    
    int offset = 0;
    for (int i = 0; i < dim1; i++)
    {
        if (i > 0)
        {
            x[i] = new int*[dim1 * dim2];
            x[i] = x[i-1] + (dim2 * dim3);
        }
           
        for (int j = 0; j < dim2; j++)
        {
            x[i][j] = x[0][0] + offset;
            offset++;
        }
    }

From Salem's post, I'm guessing that I don't want lines 9 through 13, or at least I don't want line 11. It doesn't seem to me that I should want it, since I think I only want dim1*dim2 pointers to an integer total and I have them already in line 3. This program crashes at run-time regardless of whether I comment out line 11 or 12. Any ideas? Thanks.

[VernonDozier]

int*** x;
    x = new int**[dim1];
    x[0] = new int*[dim1 * dim2];    
    x[0][0] = new int[dim1 * dim2 * dim3];
    
    int offset = 0;
    for (int i = 0; i < dim1; i++)
    {
        if (i > 0)
        {
            x[i] = new int*[dim1 * dim2];
            x[i] = x[i-1] + (dim2 * dim3);
        }
           
        for (int j = 0; j < dim2; j++)
        {
            x[i][j] = x[0][0] + offset;
            offset = offset + dim3;
        }
    }

This doesn't solve the problem, but I changed line 18 (changed above) from this:

offset++;

to this:

offset = offset + dim3;

which I think is better, but like I said, doesn't solve the problem.

[Duoas]

You know, all those little stars make my head spin. Basically what Salem wants you to do is:

1. Allocate space for all the pointers.
2. Allocate all the space for your ints all at once, in one continuous block of memory.
3. Go through an point all your pointers at the proper spots within that space.

Heh...

[VernonDozier]

O.K., I think I see the strategy a little better now. Thanks again guys. Took a lot of experimentation, but the code below seems to work.

int dim1, dim2, dim3;
    cout << "Enter dimension 1 of array: ";
    cin >> dim1;
    cout << "Enter dimension 2 of array: ";
    cin >> dim2;
    cout << "Enter dimension 3 of array: ";
    cin >> dim3;
    
    int*** x;
    x = new int**[dim1];
    x[0] = new int*[dim1 * dim2];
    x[0][0] = new int[dim1 * dim2 * dim3];
    
    for (int i = 0; i < dim1; i++)
    {
        if (i > 0)
        {
            x[i] = x[i-1] + dim2;
            x[i][0] = x[i-1][0] + (dim2*dim3);
        }
            
        for (int j = 1; j < dim2; j++)
        {
            x[i][j] = x[i][j-1] + dim3;
        }
    }

[Salem]

Found a previous example of mine on another board.
http://cboard.cprogramming.com/showpost.php?p=522326&postcount=11

[Prabakar]

x = new int**[dim1];
x[0] = new int*[dim1 * dim2];
x[0][0] = new int[dim1 * dim2 * dim3];

Mine Mine, So far I have been using for loops for this. I cant imagine how stupid I was. Thanks guys.:)