int **a = malloc2d(M, N) // dynamically allocates a 2D array
What is the purpose of having int **a vice int *a. I understand that pointers are needed for dynamic allocation but why have a pointer to a pointer?
For a 3-dimensional array would it be:
int ***a
?
You need a pointer to a pointer for several reasons.
In the example you gave, a double pointer is used to store the 2D array.
A 2D array in C is treated as a 1D array whose elements are 1D arrays (the rows).
For example, a 4x3 array of T (where "T" is some data type) may be declared by: "T mat[4][3]", and described by the following scheme:
+-----+-----+-----+
mat == mat[0] ---> | a00 | a01 | a02 |
+-----+-----+-----+
+-----+-----+-----+
mat[1] ---> | a10 | a11 | a12 |
+-----+-----+-----+
+-----+-----+-----+
mat[2] ---> | a20 | a21 | a22 |
+-----+-----+-----+
+-----+-----+-----+
mat[3] ---> | a30 | a31 | a32 |
+-----+-----+-----+
Another situation, is when you have pass a pointer to a function, and you want that function to allocate that pointer. For that, you must the address of the pointer variable, hence a pointer to a pointer
void make_foofoo(int** change) {
*change = malloc(4);
}
In C, a pointer to type T points to a location where some data of type T is stored. To keep things concrete, I will talk about T = int below.
The most simple use of a pointer could be to point to one value:
int a = 42;
int *pa = &a;
Now, *pa and a are both the same, and equal to 42. Also, *pa and pa[0] are both equivalent: so, for example, you can do:
*pa += 1; /* a is 43 */
pa[0] += 1; /* a is 44 */
a += 1; /* a is 45 */
In fact, the C compiler translates pa[0] to *(pa+0) automatically.
A pointer can point to a location that is inside a sequence of data:
int arr[] = { 1, 2, 3 }; /* 3 ints */
int *parr = arr; /* points to 1 */
Now, our memory looks like this:
+---+---+---+
arr: | 1 | 2 | 3 |
+---+---+---+
+------+ |
| parr | ----+
+------+
parr is a pointer that points to the first element of arr in the picture above. Incidentally, parr also has a box around it, because we need to store the object parr somewhere in the memory. The value of parr is the address of the first element of arr.
Now, we can use parr to access the elements of arr:
arr[0] == parr[0]; /* true */
parr[1]++; /* make arr[1] equal to 3 */
So, pointer can be used to mean, "I point to the first of n elements in a contiguous store of some objects". Of course, one has to know how many objects there are for this scheme to work: but once we remember to do so, it is an extremely convenient way to access memory in C.
Pointer can be made to point to dynamically allocated memory as well:
#include <stdlib.h>
size_t n;
/* now, obtain a value in n at runtime */
int *p = malloc(n * sizeof *p);
If the malloc() call succeeds above, p now points to the first of a contiguous area allocated for 10 ints. We can use p[0] through p[n-1] in our program now.
You probably knew most or all of the above :-), but still, the above helps in understanding what I will say next.
Remember we said that a pointer can point to a contiguous sequence of objects of the same type? The "same type" can be another pointer type as well.
#include <stdlib.h>
int **pp;
pp = malloc(3 * sizeof *pp);
Now, pp points to an int *. Going back to our earlier picture:
+------+------+------+
| | | |
+------+------+------+
+------+ |
| pp | ----+
+------+
And each of the 3 boxes is an int *, which can point to the first element of a contiguous sequence of ints:
for (i=0; i < 3; ++i)
pp[i] = malloc((i + 1) * sizeof *ppi[i]);
Here, we allocated space for one int in pp[0], 2 in pp[1], and 3 in pp[3]:
+------+ +---+
pp -------->| |-------->| |
+------+ +---+---+
| |-------->| | |
+------+ +---+---+---+
| |-------->| | | |
+------+ +---+---+---+
So, pp[0] is a pointer to one int, and that int is the only int in a dynamically allocated block of ints. In other words, pp[0][0] is an int, and points to the top-most "width-3" box above. Similarly, pp[1][0] and pp[1][1] are both valid and are the two boxes below the pp[0][0] box.
The most common use of pointer to pointer is to create a 2-dimensional "array" at runtime:
int **data;
size_t i;
data = malloc(n * sizeof *data);
for (i=0; i < n; ++i)
data[i] = malloc(m * sizeof *data[i]);
Now, assuming that all malloc()s succeed, data[0]...data[n-1] are valid int * values, each pointing to a separate length m contiguous int objects.
But, as I showed above, a pointer to pointer need not have the same "number of elements" in each of its "rows". The most obvious example is argv in main().
By now, as you can guess, a "3-level deep" pointer, such as int ***p; is okay and can be useful in C.
Just for the sake of fun, here's a ***** example:
****)*)Hence we'd have tex[2][3][10][2][10].... which is:
To pass such a data with the ability to modify it, you'd need to pass a int******... fun! xD
(and that's why I like struct's and classes....)
Helps to draw a picture. Imagine a one-dimensional array, where each element contains a pointer. Each of those pointers points to another one-dimensional array. malloc2d isn't a standard library function, but I'm guessing its returning a two-dimensional array constructed that way.
You can use this to create a 2 dimension array, kind of like a mathematical matrix, or a chessboard. So you are able to store a table of data pretty much.
A normal C array is a pointer to a block of memory.
A 2D array is a pointer to a list of pointers to each row of the array.
so, pointer to a pointer.
you only ever have pass the size of a pointer (most often 32 or 64 bits) rather than entire objects.
