Solved

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

Posted on 2003-12-12
12
694 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
Comprehensive Backup Solutions for Microsoft

Acronis protects the complete Microsoft technology stack: Windows Server, Windows PC, laptop and Surface data; Microsoft business applications; Microsoft Hyper-V; Azure VMs; Microsoft Windows Server 2016; Microsoft Exchange 2016 and SQL Server 2016.

 
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 is SQL Server and how does it work?

The purpose of this paper is to provide you background on SQL Server. It’s your self-study guide for learning fundamentals. It includes both the history of SQL and its technical basics. Concepts and definitions will form the solid foundation of your future DBA expertise.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files 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.

896 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

17 Experts available now in Live!

Get 1:1 Help Now