Array pointers

You seem to have forgotten to include the example etc. you were referring to ?

Ah, it's in the link heh. There's a lot of text there. Could you point out the specific part that you have trouble with ?

Thanks for a quick response.

Near the bottom, after "array = (int ***) malloc( 10 * sizeof(int **) );" (which is centred on the page).

I get the first allocating exmaple, but not the sceond.

Cheers,
James

Many thanks, that is perfect. I now understand that. So why do the notes go on to describe yet another (even more confusing) approach? How does the last approach work? It looks like it somehow links the appropriate dimensions together.

Thanks,
James

The idea they present there, is instead of doing multiple small memory allocations (111 in total for a 10x10x10 3D array), you do one big allocation that has enough room for all memory needs for the entire array.

Then it's just a matter of assigning pointers to the right places in that big block of memory, so each points to a different location, and there is no overlap between them.

Hmm ok ... is there any advantage apart from the fewer memory allocations?

Can you possibly go through the assigning poitners to the right places for me in this case as well ... i'm afraid I don't understand it.

Cheers,
James

is there any advantage apart from the fewer memory allocations?

i would say yes.

if you do

   int arr3d[10][10][10];

you have one piece of memory where you don't have to care for allocation and deallocation.

you can think of that memory as a cubus with 1000 little cubes or you can see on it as a 1d array with 1000 elements: imagine a x,y,z coordinate system with the origin at the left-lower-bottom corner of the cube. we start at (0, 0, 0) and go in x-direction right for 10 units. then we go back and 1 unit in y-direction, right again for 10 units, and so on until we have plane 0 of the cube (100 units). then we go up in z-direction for 1 unit and do the same for plane 1. then the same for plane 2 to 9 until all 1000 little cubes were visited. in memory we would not have to go back after 10 units but have 1000 contiguously stored elements.

because of that equivalence we always could use a 1d array instead of a 3d array by simply using a helper function to access a 3d element:

  int get3d(int x, int y, int z, int dimx, int dimy, int dimz, int arr[])
  {
       return arr[z * dimy * dimx + y*dimx + x];
  }

the z*dimx*dimy is the number of (full) x-y-planes we had to consider, the y*dimx is the number of x-rows in the (z+1)-plane and the x is the index in the y-row of (z+1)-plane.

so if we would want  to only have to deal with one allocation we can do:

   int * arr = (int*)malloc(10*10*10*sizeof(int));
   
   int i2_3_5 = get3d(2, 3, 5, 10, 10, 10, arr);

(and of course set3d or more helpers).

the idea of the second approach is the same as i showed. they have one array for all the thousand int elements. a second array for all the 100 pointers pointing to y-rows (that is y-z-plane for x==0) and 10 pointers pointing to origin of x-y-plane in z-direction (== z-axis).

so with helper functions you need 1 allocation/deallocation and you also could use fixed sized array. you could address each plane in z-direction as 2d-array with the right helpers. same you could point anywhere into the 1d array and have a shorter 1d array beginning at the position.

with second approach you need 3 allocations/deallocations and have to calculate 110 pointers. you could use each plane in z-direction as 2d array and you have pointers for each 10 elements array in x-direction.  

with first approach you need 111 allocations/deallocations which might point to non-contiguous memory. so in any case you need correct x,y,z index for access.

i think that amount of (new) pointers make the solution not practicable.

Sara

>>  is there any advantage apart from the fewer memory allocations?
>> 
>> i would say yes.

So, what is that other advantage ? You have only mentioned the advantage of having to do fewer memory allocations/de-allocations, which was already discussed at length ...

the advantage is the contiguous memory which you can much better use than 111 different locations in memory.

Sara

Many thanks for your replies.

sarabande: I have considered using some helper functions and storing it all in a 1d array,  however because in the rest of my code I have 3d deferences like array[x][y][z] I do not want to have to go through and change all these. I believe using the attached code, and the first approach Infinity explained to me will still allow the rest of my code to work unchanged.

Infinity08: Thanks. This makes sense, however is slightly different to the case in the lecture notes (attached). There, there is still 3 mallocs, similar to the original version, going from *** through ** and * to int. This makes sense to me and I can understand how the arrays are represented in memory in this case. Is the case you are explaining the same as the attached? Would array1 array2 and array3 be in the loops in the attached?

Many thanks,
James

array = (int ***) malloc( 10 * sizeof(int **) );
	array[0] = (int **) malloc( 10 * 20 * sizeof( int *) );
	array[0][0] = (int *) malloc( 10 * 20 * 30 * sizeof(int) );
	for ( j = 1  ;  j < 20  ;  ++j ) {
	    array[0][j] = array[0][j-1] + 30;
	}
	for ( i = 1  ;  i < 10  ;  ++i ) {
	    array[i] = array[i-1] + 20;
	    array[i][0] = array[i-1][20-1] + 30;
	    for ( j = 1  ;  j < 20  ;  ++j ) {
		array[i][j] = array[i][j-1] + 30;
	    }
	}

Select allOpen in new window

>> the advantage is the contiguous memory which you can much better use than 111 different locations in memory.

What you refer to, is not the same as what is described in the referenced lecture notes.

Since in the lecture notes, the exact same structure is used (three levels of pointers to represent a 3D array), the convenience of accessing the memory is not different. It's only the memory (de-)allocation that is different.



>>  however is slightly different to the case in the lecture notes (attached). There, there is still 3 mallocs, similar to the original version

The only difference is that they use different memory blocks for the different types (int, int* and int**). The blocks themselves are managed the way I described.

>> Would array1 array2 and array3 be in the loops in the attached?

Indeed.

yes, i didn't refer to the lecture notes cause i find a solution like first approach as unacceptable. even the second approach with three mallocs and two loops for pointer assignment is - in my opinion - very ugly and not good code.

james_h_1023, can't you go with an array[10][20][30] ?

Sara

I assume that the point is to understand what the lecture notes are talking about. It might not be the best approach in practical situations, but a theoretical understanding is necessary nevertheless.

Thanks for responses again.

This is both an exercise in understanding the theoretical underpinnings of arrays and pointers more and an exercise in making my code more flexible. At the moment I have many arrays with dimensions all set at compile time which I would like to be able to set at run-time. This is why I am opting to replace array[10][10][10] with either *array or ***array (which ever turns out to be the best; if there is a best).

sarablande: can you please elaborate on why you think the first approach is unacceptable, and the three mallocs and two loops approach is not good code?

Infinity08: what do you think is the best approach to practically replace array[10][10][10] with something so I only need change it in where the variable is declared (and appropriately in a 'constructor/destructor' doing some mallocing and freeing).

Moreover, I am always striving to make my code more efficient. Therefore, it is nice if my programme (as I basically simulate something for a long time) is quick. Are there any advantages efficiency wise over a one dimensional array to a three dimensional array (assuming they are both allocated in one contiguous block negating any cache locality advantages). I understand that array[x][y][z] is turned into *(*(*(array+x)+y)+z) by the compiler, so this would be comparable to a helper function when using a one dimensional array. Therefore, I understand that both would be the same as both just effectively deference to a one dimensional array anyways.

Apologies, if going slightly off topic, but I am learning a *lot*!

Cheers,
James
confusing.png

I didn't mean to submit that, I hadn't finished!

Ok, so understanding the code attached still ...

Infinity: your example, as I understand is attached to this post, right? This makes sense, and would imply some loop could used like this:

for (i=0; i<10; i++) {
    array[i][0] = array[(i+1)*10];
}

Select allOpen in new window

Although that doesn't quite seem right with a 2d deference on the left and a 1d on the right.

However, trying to relate this to the example, my image in the previous post ... A is what I think line 5 is doing in the attached code. This doesn't seem right. Surely one would want something more like B. I think the key in your case and in the above code is the (i+1)*10 where 10 is the length of a dimension. There seems to be nothing like that in the lecture notes case.

Cheers,
James

array = (int ***) malloc( 10 * sizeof(int **) );
	array[0] = (int **) malloc( 10 * 20 * sizeof( int *) );
	array[0][0] = (int *) malloc( 10 * 20 * 30 * sizeof(int) );
	for ( j = 1  ;  j < 20  ;  ++j ) {
	    array[0][j] = array[0][j-1] + 30;
	}
	for ( i = 1  ;  i < 10  ;  ++i ) {
	    array[i] = array[i-1] + 20;
	    array[i][0] = array[i-1][20-1] + 30;
	    for ( j = 1  ;  j < 20  ;  ++j ) {
		array[i][j] = array[i][j-1] + 30;
	    }
	}

Select allOpen in new window

ok.png

I suppose linked to my comment "Although that doesn't quite seem right with a 2d deference on the left and a 1d on the right." is also the question "how does and when does the compiler know that [] is fine and [][] is fine?"

Cheers,
James

Ahhhhhhhhh I think I have got it. The bit I thought I wasn't getting was that in the examples that make sense to me there is a

(i*dimension)

Select allOpen in new window

key part, which moves along like your first 2d example. This wasn't in the code in the lecture notes, however I was forgetting that each iteration through the loop the previous iteration had already incremented along 30, so the next time was 30 along, ready for another 30 (if that makes sense).

Many thanks for your comments regarding a decision between dynamically allocating, statically allocated and helper functions as well.

Many thanks indeed,
James

>> the previous iteration had already incremented along 30, so the next time was 30 along, ready for another 30 (if that makes sense).

It does make sense :)


>> Many thanks indeed,

Glad to be of assistance !

cheers :)
You've been helping me a lot recently!

in c  to establish a dynamic 3d array (dynamic in the sense that you can have individual dimensions for every dimension) you need 111 pointers.

that is  an extreme difference to a 3d array with fixed dimensions where y ou don't need a pointer at all but only

   int arr3d[10][20][30];

in c++ you could make a own class for 3d array which would allow you to have

   Array3d arr3d(10, 20, 30);

and have same access than with fixed array.

in c you don't have those possibilties to encapsulate but you could use a structure like

  typedef struct tagArray3d
  {
      int xdim;
      int ydim;
      int zdim;
      int * pi;
  } Array3d;

which would allow you to store the properties and data of a dynamic 3d array.

you would need helpers for create, get, set, free where always a pointer to this structure was passed. but beside of that the access to the 3d array is straight forward, can be fully tested and is reusable in other code.

if on the other hand you add new code for any 3d array to your sources which would create and assign 111 pointers in order to only get the same functionality as with 1 statement and fixed-dimensioned array, you have a - possible working - solution which i would call 'ugly' because of the many individual code added.

if you want to go with that nevertheless i would recommend to move the creation and freeing into functions like

int create3DArray(int **** arr3d, int zdim, int ydim, int xdim);
int free3DArray(int *** arr3d, int zdim, int ydim);

which would be called like

  int *** array = 0;
  if (create3dArray(&array,  10, 20, 30) != 0)
      return error();
  ...
  free3DArray(array, 10, 20);

that also would give you the chance to reuse the 3d array.

Sara