• C

Double dimensional array formula *(*(arr+i)+j) confusion

Ok, we all know since time in memorial that double dimensional arrays are essentinally pointers to pointers and arr[i][j] is equivalent to *(*(arr+i)+j)  where address of arr is de-referenced twice to get to the location desired. But, when u check memory address given by arr, it points to a linear sequence where all values of all dimensions are placed side-by-side. So, the first time u de-reference *(arr+i) u get the value at this address which is basically a 'value in array' instead of an address of an array, and so when this expression is dereferenced second time it should crash. Why is this and why do we all believe in the pointer-to-pointer interpretation of 2D array when its all values and not addresses??
gottahaveanswersAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

sunnycoderCommented:
Hi gottahaveanswers,

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

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

to get to [i][j], you need to access the ith * in a ... and in the array pointed to by a[i], you need to refer to jth element

consider the overall organization

a =    ptr0           ptr1           ptr2      .....                ptr9
           |                 |                |                                 |
           \/               \/               \/                                \/
        int[10]         int[10]       int[10]                         int[10]

a is the beginning address of a
a + i is the address of the ith element
*(a+i) is the address of array of 10 ints
*(a+i) + j is the address of jth element in this array
*(*(a+i) + j ) is the value of the jth element of this array

Hope this clears up your confusions
skypalaeCommented:
Hi gottahaveanswers,

Writing 'int array[m][n];' creates linear chunk of memory. It's in fact one dimensional array except the compiler knows how to translate its indexing (it's (m*n)+n respectively). Same is with higher dimensional arrays. So you oughta know that double dimensional array is not a pointer to array of pointers, since you create it on your own (using malloc()).

Cheers!
sunnycoderCommented:
Questions Asked: 4
Questions Open: 3
Questions Graded: 1
Questions Deleted: 0
Last 10 Grades Given: A

and the acepted answer is CVed one ... thats a bad record ... You should take time to maintain your questions
Making Bulk Changes to Active Directory

Watch this video to see how easy it is to make mass changes to Active Directory from an external text file without using complicated scripts.

skypalaeCommented:
Mistake ... that 'since' in my last sentence should be replaced by 'until' i think.
But the point stays the same.



We all know since time in memorial that double dimension arrays are NOT pointers to pointers until you make them on your own.

S.
sunnycoderCommented:
another thing... the representation in my first post is fundamentally different from

a[10][10]

a is the address of beginning of array
a+i is the address of ith element... what this element is depends on value of i (read about row major and column major ordering?)
*(a+i) is the value at that location

*(a+i)+j is that value+j

*(*(a+i) + j )
is trying to derefernce that value and is likely to crash ...

So it seems that your confusion was due to representation of arrays ...

>we all know since time in memorial that double dimensional arrays are essentinally pointers to pointers
thats a way to visulaize them but there is fundamental difference in organization as I just posted
ssnkumarCommented:
gottahaveanswers,

The fundamental thing you should know in C is that, C doesn't have multi-dimentional arrays!
The only thing it has got is a single dimentional array and the multi-dimentional array declaration just creates an impression that you are using a multi-dimentional array.....though it is a single dimentional array.......so, that you can go ahead with logic of multi-dimentional arrays problems!!
This is implementation related detail, which an user of C need not know and go ahead assuming that it provides multi-dimentional array.....
ssnkumarCommented:
gottahaveanswers,

The fundamental thing you should know in C is that, C doesn't have multi-dimentional arrays!
The only thing it has got is a single dimentional array and the multi-dimentional array declaration just creates an impression that you are using a multi-dimentional array.....though it is a single dimentional array.......so, that you can go ahead with logic of multi-dimentional arrays problems!!
This is implementation related detail, which an user of C need not know and go ahead assuming that it provides multi-dimentional array.....
Kent OlsenDBACommented:

This has been a fun thread.  :)  Too bad I got here late.

Hi gottahaveanswers,

There are some good posts here.  Things are slow here at the office, so I'm gonna add anoth $0.02 to the discussion.

Array addressing can be "right to left" or "left to right".  Most languages, including C, are "left to right" so that when you increment the rightmost index, you increment the memory location by the size of the arrayed item.  When you increment the first (or any index except the rightmost) you change memory locations by the width of the sturcture.  Consider a simple character array of 6x2.

char CharArray[6][2];

In memory this is 12 consecutive bytes that the C language treats as a matrix.  We tend to think of CharArray as a structure that looks like this:

AB
CD
EF
GH
IJ
KL

When, in fact, it is contiguous memory that looks like this:

ABCDEFGHIJKL

CharArray[0][0] is the first position in the table (an 'A').
CharArray[0][1] is the second position in the table (a 'B').
CharArray[1][0] is the third position in the table (a 'C').  etc...

As I said, increment the rightmost index moves a single position in memory (when using chars).  Incrementing the leftmost index moves the width of the rightmost index.

The general form of this evalution is:

Offset = ((LeftIndex * RightIndexPositions) + RightIndex) * sizeof (array item type);

This same logic extends to all arrays of more than 2 dimensions:

char NewCharArray[3][4][5];

Offset == ((LeftIndex * MiddleIndexPositions * RightIndexPositions) + (MiddleIndex * RightIndexPositions) + RightIndex) * sizeof (array item type);

There are a lot of ways to programmatically produce the offset, perhaps the cleanest is a recursive function.  Here's an entire program that will compute the offset 1,3,2,4,6,1 into "char BigCharArray[3][4][5][6][7][8]";


#include <stdlib.h>

int BigCharArrayLimits[7] = {8, 7, 6, 5, 4, 3, 0};  /* Note - items are backwards for convenience  */
int BigCharArrayOffset[6] = {1, 6, 4, 2, 3, 1};     /* Note - these items are in the same order  */

int ComputeOffset (int *Limit, int *Index);
int ComputeSubOffset (int *Limit, int *Index, int Current);

int ComputeOffset (int *Limit, int *Index)
{
    return ComputeSubOffset (Limit, Index, *Index);
}

int ComputeSubOffset (int *Limit, int *Index, int Current)
{
  if (*Limit == 0)  /*  We've gone through the entire table */
    return 0;
  printf ("index=%6d of %6d, Current = %6d\n", *Index, *Limit, Current);
  return  ComputeSubOffset (Limit+1, Index+1, Current * (*Limit)) + Current * (*Index);
}

main ()
{
  printf ("Array[1][3][2][4][6][1] is at %d\n", ComputeOffset (BigCharArrayLimits, BigCharArrayOffset));
}


It would look better as a class so that ComputeSubOffset() could be hidden, but this is a C forum, not C++.  ")


Hi Sunny,

Things are back to normal, huh?  re:  http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20822860.html#9926371

:)

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ssnkumarCommented:
gottahaveanswers,

Why don't you provide feedback?
If you are no more interested in this discussion, then close this Q.

-ssnkumar
varunhomeCommented:
Hi,
This is regarding the question asked at the very beginning of the post. I have written a detailed article on using multi-dimensional pointers in C++. It should be helpful to resolve all doubts unambiguously.

The obvious issue here is that while compiler automatically allocates memory for arrays, memory for pointers must be dynamically allocated. The exact syntax for doing it is described in the article on my home page:

Article link:
http://www.geocities.com/varunhostel/TechnicalArticles/PointerArticle/PointerArticle_Intro.html

Some of the questions relevant to the post answered in the article are:

Chapter 9: How do I dynamically allocate memory for a 3-dimensional pointer equivalent to an array a[2][3][4]?

Chapter 6: To what extent can I inter-change pointer and array syntax in C++?

Chapter 11: How do I decipher very long function pointer declarations? Is there a standard approach for it?

Chapter 11: What is the difference between the two declarations: int *ptr[5] and int (*ptr) [5]?
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.