Help with Pointer Arithmetic

Question

Hi all,

I've been studying C++ for a test and I am currently stuck with pointer arithmetic.

The basic problem is the following:

int numColumns = 3;
int numRows    = 4;

int a[numRows][numColumns];

a[0][0] = 1;
a[0][1] = 2;
a[0][2] = 3;
a[1][0] = 4;
a[1][1] = 5;
a[1][2] = 6;
a[2][0] = 7;
a[2][1] = 8;
a[2][2] = 9;
a[3][0] = 10;
a[3][1] = 11;
a[3][2] = 12;

for (int i=numColumns-1; i>-1;i--)
{
  cout << a[numRows-1][i] << endl;
}

A very simple program which prints the lower "row of the matrix". i.e. 12,11,10.

Now I am trying to do the equivalent with a int*.

What I have been told by my classmates is to think it like this:

array[i][j] == p[numColumns*i+j]

If that is correct, shouldn't the following be equivalent to what I'm looking for:

int* p = reinterpret_cast<int*> a;
for (int i=numColumns-1; i>-1;i--)
{
  cout << p[numColumns*(numRows-1)+i] << endl;
}

Thanks.

Answer 1

Hint: in your original code, the type of a is more similar to int**, so you shouldn't cast it to int*. It is a pointer to pointer to something.

If you want to access it like an 1-D array, then a has to be defined as an 1-D array as well.

Answer 2

@rwong: Really? I thought that multi-dimensionals arrays were just an "abstraction" for us, since the following are equivalent:

int array[3][5];
int array[3*5];

Anyways, I detemined what was wrong. As usual it was not my code, but copy-pasting someone's code and working from there.

What I had was this:

for(int i=numRows-1; i>-1 ;i++)
{
  cout << p[numColumns*numRows-1+i] << endl;
}

Is funny because I did not copy-paste my code from VS, but actually wrote it from scratch to "illustrate" my error.

Lesson to be learnt here ;)

Edit: I'm still not sure about what rwong explained here. Would anyone care to elaborate?

Answer 3

Another way to think about it: since a is similar to an int**, is there a part of a that's similar to an int*?

Answer 4

int array[3][5] is NOT an abstraction (in the C++ language) for int array[3*5]. The standard says that a 2 dimensional array (and N-dimensional arrays in general) are arrays of arrays. That array[3][5] is an array of three elements, where each element is an array containing 5 elements (integers in this case). C++'s type system does make that distinction.

According to the C++ standard, and array T array[N] is a contiguous block of memory containing the N elements of type T. So that means that a multidimensional array, let's say int array[3][5] will be a continuous block of memory containing 3 int[5] arrays, and each int[5] array is a contiguous block of 5 ints.

On my machine, the memory ends up laid out exactly as you would expect - identical to int array[3*5]. The way the memory is treated is different however, due to the type system (which distinguishes between int[] and int[][]). This is why you need to use a reinterpret_cast which essentially tells your compiler "take this memory and without doing any conversion, treat it like this new type".

I'm not completely sure if this memory layout is guaranteed however. I couldn't find anything in the standard stating that arrays can't be padded. If they can be padded (again, I'm not sure) then it's possible that the int[5] array is not actually 5 elements long (a better example would be char[5], which I could see being padded to 8 bytes).

Also there is an appreciable difference between int* and int** since the latter doesn't guarantee contiguous memory.

EDIT: The reason that C++ distinguishes between int[3*5] and int[3][5] is because it wants to guarantee the order of the elements in memory. In C++ int[0][1] and int[0][2] are sizeof(int) apart in memory. However in Fortran, for example, int[0][0] and int[1][0] are sizeof(int) apart in memory because Fortran uses column major representation.

Here's a diagram to help explain:

0 1 2
3 4 5
6 7 8

Can be made into an array that looks like {0,1,2,3,4,5,6,7,8} or an array that looks like: {0,3,6,1,4,7,2,5,8}.