Trouble understanding pointers.

[rich_m]

I have just managed to understand pointers, but still have some doubts.

I know that

Code: Select all

int* i;

Is a pointer that can hold the address of an integer.

Now by allocating memory to this pointer I can create a dynamic array, and access it using this pointer. My understanding till here is clear.

Now suppose I wanted a 2D array, I could create an array of pointers. say

Code: Select all

int* i[10];

But here I have the second dimension fixed to 10.

Could I have somthing like

Code: Select all

int** i;

, if "yes", how do I allocate memory to it and access a specific element.?????

[Zacariaz]

Try this, it is kinda fun:
http://cslibrary.stanford.edu/104/

[pcmattman]

Code: Select all

int **i = (int**) malloc( [firstdim] * [secdim] * sizeof( int ) );

I'm pretty sure that will work... If not, I probably should go get some coffeeto stop this insane rambling.

[rich_m]

How about accessing a particular element?

[pcmattman]

Code: Select all

i[2][4];

The malloc part just gets some memory for the entire list (firstdim is the first dimension, secdim is the second).

[AndrewAPrice]

I would use:

Code: Select all

int *i;

Then to allocate:

Code: Select all

i = new int[x * y];

then to access an element use:

Code: Select all

i[x + y * arraywidth];

Basically, it is possible to have a pointer to a list of pointers,

If you want to do it your way, you'd have to do a pointer to a pointer like this:

Code: Select all

int **i;

Allocate it like this:

Code: Select all

i = new int[width];
for(int x = 0; x < width; x++)
{
   i[x] = new [height];
}

Then you can access it as:

Code: Select all

i[x][y]

And for 3 dimensions, you could declare:

Code: Select all

int ***i;

and declare as:

Code: Select all

i[x][y] = new int[depth];

But I personally find my first method more convenient since I can just call delete once. If you use a pointer to a pointer, you have deallocate each one pointer within the main pointer first.

[DeletedAccount]

To be honest ...,
It is syntatically correct .... I also had the same doubt ... although
int **a; is syntatically correct it is somewhat semantically ambiguous...
To understand what i mean try declaring a int a[4][4] array and
try pass in to function having this prototype int my_func(int **a);
I sure you will get some warnings and may get a Seg fault at times.....

int **a intrepretation depends upon compiler to compiler .. This was
the mistake i made in a coding contest :-Me and my partner got the
algorithm right :(ours was the best algo , Still we failed to coz of
this pesky issue...) . This is my understanding .. may not entirely correct....

[Aali]

if you declare an array as int a[4][4], its really just a one-dimensional array where the compiler does the magic for you.

int **a (and whatever ugly-ish code you need to make that look like a two-dimensional array) is an array of arrays at best, a serious error in the programmers mind at worst

[dave]

if you declare an array as int a[4][4], its really just a one-dimensional array where the compiler does the magic for you.

This is completely incorrect.

If you declare int a[4][4] it is actually equivalent to int **a. The difference between the two statements is in the first you tell the compiler your memory requirements and in the second one you are required to allocate your memory.

the [] operator represents a level of indirection.

As an example:

int *a == int a[]
int **b == int b[][]
int ***c == int c[][][]
...

By knowing this we can see that int a[] is not equivalent to int b[][]. Now there is a one to one transform that can map a 1D array to a 2D array and vice versa.

2D -> 1D is [(y * max_y) + x]
1D -> 2D is [x % max_y][ x/max_y]

To understand what i mean try declaring a int a[4][4] array and
try pass in to function having this prototype int my_func(int **a);
I sure you will get some warnings and may get a Seg fault at times.....

int **a intrepretation depends upon compiler to compiler ..

The interpretation of int **a is well defined. As far as the function call is concerned, everything is correct. Your Seg Fault was a problem with your programming and not anything to do with the compiler.

[Candy]

if you declare an array as int a[4][4], its really just a one-dimensional array where the compiler does the magic for you.

This is completely incorrect.

No, he actually is correct.

If you declare int a[4][4] it is actually equivalent to int **a. The difference between the two statements is in the first you tell the compiler your memory requirements and in the second one you are required to allocate your memory.

the [] operator represents a level of indirection.

As an example:

int *a == int a[]
int **b == int b[][]
int ***c == int c[][][]

No.

By knowing this we can see that int a[] is not equivalent to int b[][]. Now there is a one to one transform that can map a 1D array to a 2D array and vice versa.

2D -> 1D is [(y * max_y) + x]
1D -> 2D is [x % max_y][ x/max_y]

The only thing your compiler does with an array with more than one index is perform this calculation for you. IF you go out of bounds on one of the indexes you might still index within the table but at an unpredictable location.

To understand what i mean try declaring a int a[4][4] array and
try pass in to function having this prototype int my_func(int **a);
I sure you will get some warnings and may get a Seg fault at times.....

int **a intrepretation depends upon compiler to compiler ..

The interpretation of int **a is well defined. As far as the function call is concerned, everything is correct. Your Seg Fault was a problem with your programming and not anything to do with the compiler.

*cough* That's true, but it just isn't an int **. An int ** is a pointer to an "int *", which means that the contents of your pointer are only a pointer in size. If you dereference it twice when it actually points to an int[][], you dereference the first integer in the array.

[dave]

As an example:

int *a == int a[]
int **b == int b[][]
int ***c == int c[][][]

let me clarify, I am simply saying these are equivalent in terms that the variable name represents the same thing a pointer to an int, a pointer to a pointer to an int, etc...

when you do int a[4][4] the variable is actually a pointer to a pointer to an int not a pointer to an int . By calling it 1D you are removing a level of indirection, hence you are calling it a pointer to an int .

The fact that the compiler may allocate a linear portion of memory and possibly collapse it to a 1D array does not remove the fact it requires 2 levels of indirection to access the data.

My point is the original poster is trying to learn about pointers. What everyone is telling him about is a special case where the memory is allocated by the compiler at compile time. The fact is it is two dimensional due to the fact it requires to levels of indirection.

Take the sample code which prints the addresses of the different levels of indexing. Notice when you allocate it on you own it requires two levels of indirections, which shows that the preallocated compiler variable is a special case. Also notice the index notation used on v2 even though it was declared unsigned int **v2. This demonstrates what I mean by the fact the above expressions are equivalent.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

void main()
{
	unsigned int   x, y;
	unsigned int   v1[4][4];
	unsigned int **v2;

	// lets initialize v1
	for( x = 0; x < 4; x++ )
		for( y = 0; y < 4; y++ )
			v1[x][y] = (x* 4) + y;

	// lets allocate memory for v2
	v2 = (unsigned int**) malloc( sizeof(int*) * 4 );
	for( x = 0; x < 4; x++ )
		v2[x] = (unsigned int*) malloc( sizeof(int) * 4 ); 

	// lets initialize v2
	for( x = 0; x < 4; x++ )
		for( y = 0; y < 4; y++ )
			v2[x][y] = (x* 4) + y;

	// Print addresses of the Compiler allocated memory vs Dynamic Allocation
	printf( "compiler                dynamic\r\n" );
	printf( "========================================\r\n" );
	for( x = 0; x < 4; x++ )
	{
		printf( "v1[%u]: %#08X    \t", x, &v1[x] );
		printf( "v2[%u]: %#08X\r\n", x, &v2[x] );
		for( y = 0; y < 4; y++ )
		{
			printf( "v1[%u][%u]: %#08X\t", x, y, &v1[x][y] );
			printf( "v2[%u][%u]: %#08X\r\n", x, y, &v2[x][y] );
		}
	}

	// free memory
	for( x = 0; x < 4; x++ )
		free( v2[x] ); 
	free(v2);
}

[Candy]

As an example:

int *a == int a[]
int **b == int b[][]
int ***c == int c[][][]

let me clarify, I am simply saying these are equivalent in terms that the variable name represents the same thing a pointer to an int, a pointer to a pointer to an int, etc...

when you do int a[4][4] the variable is actually a pointer to a pointer to an int not a pointer to an int . By calling it 1D you are removing a level of indirection, hence you are calling it a pointer to an int .

The compiler is not creating a pointer to a pointer to an int, the compiler has a pointer to an int with a special operation that changes the indexing of the pointer. You can cast any int * to an int[4][] and then use it to address the target area as if it were that kind of array, but you only get ONE pointer. Don't pretend it's a "pointer to a pointer" since you can't dereference it and expect to get a pointer.

My point is the original poster is trying to learn about pointers. What everyone is telling him about is a special case where the memory is allocated by the compiler at compile time. The fact is it is two dimensional due to the fact it requires to levels of indirection.

There are no two levels of indirection, it's a special construct that allows you to pretend.

Take the sample code which prints the addresses of the different levels of indexing. Notice when you allocate it on you own it requires two levels of indirections, which shows that the preallocated compiler variable is a special case. Also notice the index notation used on v2 even though it was declared unsigned int **v2. This demonstrates what I mean by the fact the above expressions are equivalent.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

void main()
{
	unsigned int   x, y;
	unsigned int   v1[4][4];
	unsigned int **v2;

	// lets initialize v1
	for( x = 0; x < 4; x++ )
		for( y = 0; y < 4; y++ )
			v1[x][y] = (x* 4) + y;

	// lets allocate memory for v2
	v2 = (unsigned int**) malloc( sizeof(int*) * 4 );
	for( x = 0; x < 4; x++ )
		v2[x] = (unsigned int*) malloc( sizeof(int) * 4 ); 

sizeof(v1) is 4*4*sizeof(int). sizeof(v2) is sizeof(int **) + 4 * sizeof(int *) + 4 * 4 * sizeof(int). Also, in your second case, not all rows need to be equal, whereas in the first case your compiler uses that information.

All indices except for the first are treated special and need to be constant. It does not construct an array of pointers at all, these are derived from the initial pointer using the above-described special operation.

[dave]

Lets keep it in the context of the original posters intent, in which case int a[4][4] is a special case.

He wants to learn pointers and making the assumption all compilers allocate memory the same way is naive and leads to poor programming practices.

The compiler designer has taken a shortcut/optimization; However, the fact that if you were to print the value of v1[2] (from sample above) it prints an address, which shows it requires two levels of indirection.

Whether int a[4][4] is stored as one or two levels is irrelevant. He should always assume int a[4][4] or int **a require two levels and not one level because if you were to say define a function void myfunc( int **b ) you have no clue as to how b was allocated and assuming it is 1D would cause all kinds of havoc.

[jnc100]

I must agree with Candy here. If you create an array such as

Code: Select all

int arr[4][4]

then by accessing arr by itself you do not get a pointer to int[4] but rather get &arr[0][0]. i.e. the compiler creates an array of size 16 * sizeof(int) and then calculates offsets into it from an expression of the form int[x][y] given that it knows the maximum size of each dimension (it only really needs to know one). A search can verify that, given the definition above, arr[16] == arr[4][4]

If, on the other hand, you define a type as

Code: Select all

int **arr

then arr is a pointer to the start of an array of int * which is of unknown size. Therefore, if you try and access arr[4][4] from there you will get the fourth element of the array of int* and then get the fourth element of the array which that points to. You may well get a compiler warning, however.

Passing a type of int[4][4] to a function expecting int ** would not produce the expected result, because the receiving function has no idea as to the dimensions of the original array.

Regards,
John

[dave]

I am not disagreeing with candy about the compiler allocating as a linear chunk of memory or that the compiler allocates a pointer to int (or whatever data type). I am simply saying it is a poor assumption on the part of the programmer to think that an int a[4][4] is not equivalent to a pointer to pointer to an int. Where as if you assumed it was a pointer to an int the code would not work without proper casting at minimum.