Solved

Array pointers

Posted on 2011-02-24
23
368 Views
Last Modified: 2012-05-11
Hi *,

Another question regarding pointers! Oh I do love them ...

Here are some lecture notes on some pointer array stuff. (I am unsure on the legalities of copy-pasting the text in here.) I can follow it all up to where there are descriptions of allocating the memory for a 3 dimensional array. The first example makes sense. however, the last example which is 'much more efficient' is a mystery to me.

Can someone explain to me how it is working? Hopefully with some diagrams. I have tried drawing diagrams, although end up with squares connected with many lines to many squares as if a I had squashed a spider on my desk. Also, why is it much more efficient? Is this in terms of time to allocate, or time when accessing them later? (Surely, the latter doesn't make sense.)

Many thanks,
James
0
Comment
Question by:James_h1023
  • 10
  • 9
  • 4
23 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 34972570
You seem to have forgotten to include the example etc. you were referring to ?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34972582
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 ?
0
 
LVL 4

Author Comment

by:James_h1023
ID: 34972672
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
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 500 total points
ID: 34972877
>> I get the first allocating exmaple, but not the sceond.

So, if I understand you right, you understand these parts :

>> array = (int ***) malloc( 10 * sizeof(int **) );

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

but not this one :

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

Correct ?

If so, you have to realise that all of that code belongs together, and is necessary to allocate memory for a 3D dynamically allocated array.

The way to look at it, is in layers : a 3D array is an array of 2D arrays. And a 2D array is an array of 1D arrays.

Allocating memory for a 1D array is straightforward :

        int* array1d = (int*) malloc(10 * sizeof(int));


For a 2D array, you look at it as an array of 1D arrays. So, first you allocate memory for the "outermost" array :

        int** array2d = (int**) malloc(10 * sizeof(int*));

This memory has room for 10 pointers to a 1D array. So, array2d is an array of 10 1D arrays. We need to also allocate memory for each of these 1D arrays. For example, for the first, we'd do just as before :

        array2d[ 0 ] = (int*) malloc(10 * sizeof(int));

This is usually done in a loop for convenience, so it'll take the form :

        int** array2d = (int**) malloc(10 * sizeof(int*));
        for (i = 0; i < 10; ++i) {
                array2d[ i ] = (int*) malloc(10 * sizeof(int));
        }

At this point, we have allocated all memory for a 2D array.


A 3D array is an array of 2D arrays. So, we first allocate memory for the outermost array :

        int*** array3d = (int***) malloc(10 * sizeof(int**));

Now, for each item in that array, we need to allocate memory for a 2D array. We'll do this just as before. For the first for example, we'd get :

        array3d[ 0 ] = (int**) malloc(10 * sizeof(int*));
        for (j = 0; j < 10; ++j) {
                array3d[ 0 ][ j ] = (int*) malloc(10 * sizeof(int));
        }

This is exactly the same as what we did before for a 2D array.

We need to do this for every item, so for convenience, it is usually done in yet another loop. That would make it :

        int*** array3d = (int***) malloc(10 * sizeof(int**));
        for (i = 0; i < 10; ++i) {
                array3d[ i ] = (int**) malloc(10 * sizeof(int*));
                for (j = 0; j < 10; ++j) {
                        array3d[ i ][ j ] = (int*) malloc(10 * sizeof(int));
                }
        }

Does that help clarify things ?
0
 
LVL 4

Author Comment

by:James_h1023
ID: 34974171
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
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34974226
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.
0
 
LVL 4

Author Comment

by:James_h1023
ID: 34974376
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
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 34974490
>> Hmm ok ... is there any advantage apart from the fewer memory allocations?

Apart from having to do fewer allocations and de-allocations, not really. There might be a slight advantage in cache locality, but that depends in the memory manager.


>> 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.

Ok. Say you need to allocate memory for 10 arrays, each of 10 ints. You'd need room in memory for a total of 100 ints. Instead of doing 10 allocations for 10 ints each, you could do one big allocation for all 100 ints :

        int* memory_block = (int*) malloc(10 * 10 * sizeof(int));

Now, you only have a big block of allocated memory, but you need to split it up into 10 separate arrays. The first array starts at the start of the memory block :

        int* array1 = &memory_block[0];

This first array contains 10 ints, so that corresponds to the first 10 ints in the memory block.

The next 10 ints in the memory block can be assigned to the second array. This second array would than start at the 11th int in the memory block (and would go on up till and including the 20th int) :

        int* array2 = &memory_block[10];

The third array would start at the 21st int in the memory block, up till and including the 30th :

        int* array3 = &memory_block[20];

etc.
0
 
LVL 32

Expert Comment

by:sarabande
ID: 34978384
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





0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34978414
>>  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 ...
0
 
LVL 32

Expert Comment

by:sarabande
ID: 34978776
the advantage is the contiguous memory which you can much better use than 111 different locations in memory.

Sara
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 4

Author Comment

by:James_h1023
ID: 34978858
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;
	    }
	}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34978901
>> 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.
0
 
LVL 32

Expert Comment

by:sarabande
ID: 34981226
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
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34981279
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.
0
 
LVL 4

Author Comment

by:James_h1023
ID: 34986983
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
0
 
LVL 4

Author Comment

by:James_h1023
ID: 34987001
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];
}

Open 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;
	    }
	}

Open in new window

ok.png
0
 
LVL 4

Author Comment

by:James_h1023
ID: 34987004
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
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 500 total points
ID: 34987509
>> 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).

If you want to be able to access it using array[ i ][ j ][ k ], then you either need a statically allocated 3D array (ie. int array[10][10][10]), or a dynamically allocated 3D array with three levels of pointers (ie. int*** array), or a mix of both.

You cannot, for example, have a 1D array with custom offset management that still uses the [] operator.


>> 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.

Pretty much, yes.

Note that in choosing between statically allocated and dynamically allocated approaches, the trade-off is in general about flexibility vs. convenience. With obviously differences in allocation overhead, memory layout, and where the memory is allocated (stack vs. heap eg.).
In other words, there's no simple one-fits-all answer. Which approach you use depends on your specific situation.


>> Infinity: your example, as I understand is attached to this post, right?

I'm not sure I know what you're referring to.

My explanation in http:#34974490 was a general description of how you can use one allocated block of memory to replace several allocations. This can be applied in the case of a 3D array, just like in the lecture notes.


>> 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.

What this line does :

>>           array[0][j] = array[0][j-1] + 30;

is simply partition the block of memory in blocks of 30 ints, and properly setting the pointers to such consecutive blocks of 30 ints.

Specifically, array[0][0] points to the start of a block of 10*20*30 ints (let's call the address x, ie. array[0][0] == x).
array[0][1] will then be set to (x + 30), or in other words : it will point to the second block of 30 ints.
array[0][2] will then be set to (x + 2*30), or in other words : it will point to the third block of 30 ints.
array[0][3] will then be set to (x + 3*30), or in other words : it will point to the fourth block of 30 ints.
etc.
array[1][0] will then be set to (x + 20*30), or in other words : it will point to the twenty-first block of 30 ints.
array[1][1] will then be set to (x + 20*30 + 30), or in other words : it will point to the twenty-second block of 30 ints.
etc.
array[9][19] will then be set to (x + 9*20*30 + 19*30), or in other words : it will point to the two-hundreth (and last) block of 30 ints.


0
 
LVL 4

Author Comment

by:James_h1023
ID: 34991982
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)

Open 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
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34992242
>> 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 !
0
 
LVL 4

Author Closing Comment

by:James_h1023
ID: 34992257
cheers :)
You've been helping me a lot recently!
0
 
LVL 32

Expert Comment

by:sarabande
ID: 34996019
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


0

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
pgpool-II on Ubuntu 14.04... ARGH! 5 809
C#, VS15, StructLayout 1 116
Passing a array as parameter - C 2 77
Need example 5 100
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now