Solved

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

Posted on 2003-12-12
12
691 Views
Last Modified: 2010-04-15
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??
0
Comment
Question by:gottahaveanswers
  • 3
  • 3
  • 2
  • +2
12 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9926770
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
0
 
LVL 4

Expert Comment

by:skypalae
ID: 9926776
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!
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9926795
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
0
 
LVL 4

Expert Comment

by:skypalae
ID: 9926818
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.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9926821
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
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 8

Expert Comment

by:ssnkumar
ID: 9927292
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.....
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 9927294
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.....
0
 
LVL 45

Accepted Solution

by:
Kdo earned 250 total points
ID: 9929215

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

:)
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 10028173
gottahaveanswers,

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

-ssnkumar
0
 

Expert Comment

by:varunhome
ID: 14792123
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]?
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
port mapped I/o query 10 137
C++ vs C compilers 13 155
Handling string inputs in C/Linux 23 167
UPD maximums on Red Hat 6 102
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
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…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
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.

708 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

12 Experts available now in Live!

Get 1:1 Help Now