int** vs int[const][const] differences

Question

I was writing a code the other day and I found it rather strange, that int** and int[][] does not behave the same way. Can anyone point out the differences between them? Below is my sample code, which fails with a segmentation fault, if I pass constant size 2d array, while it does work fine when I pass a dinamically allocated 2d array.

I am confused mainly because ant int[] array works the same as int*.

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

void sort_by_first_row(int **t, int n, int m)
{
    int i, j;


    for(i = m-1 ; i > 0 ; --i)
    {
        for(j = 0 ; j < i; ++j)
        {

            if(t[0][j] < t[0][j+1])
            {
                int k;  
                for(k = 0 ; k < n ;++k)
                {
                    int swap;
                    swap = t[k][j];
                    t[k][j] = t[k][j+1];
                    t[k][j+1] = swap;
                }
            }
        }
    }
}

int main(void) {
    int i, j;
    /* Working version */   
    /*int **t;

    t =(int**) malloc(3*sizeof(int*));
    for(i = 0; i  < 3; ++i)
    {
        t[i] = (int*) malloc(6*sizeof(int));
    }*/

    /*WRONG*/
    int t[3][6];

    t[0][0] = 121;
    t[0][1] = 85;
    t[0][2] = 54;
    t[0][3] = 89;
    t[0][4] = 879;
    t[0][5] = 11;

    for( i = 0; i < 6; ++i )
        t[1][i] = i+1;

    t[2][0] = 2;
    t[2][1] = 4;
    t[2][2] = 5;
    t[2][3] = 3;
    t[2][4] = 1;    
    t[2][5] = 6;                

    sort_by_first_row(t, 3, 6);

    for(i = 0; i < 3; ++i)
    {
        for(j = 0; j < 6; ++j)
            printf("%d ", t[i][j]);
        printf("\n");
    }
    return 0;
}

So based on the below answers I realize, that a multidimensional array is stored continuously in a row major order. After some modification, the below code works:

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

void sort_by_first_row(int *t, int n, int m)
{
    int i, j;


    for(i = m-1 ; i > 0 ; --i)
    {
        for(j = 0 ; j < i; ++j)
        {

            if(t[j] < t[j+1])
            {
                int k;  
                for(k = 0 ; k < n ;++k)
                {
                    int swap;
                    swap = t[k*m + j];
                    t[k*m + j] = t[k*m + j+1];
                    t[k*m + j+1] = swap;
                }
            }
        }
    }
}

int main(void) {
    int i, j;
    /* Working version */   
    /*int **t;

    t =(int**) malloc(3*sizeof(int*));
    for(i = 0; i  < 3; ++i)
    {
        t[i] = (int*) malloc(6*sizeof(int));
    }*/

    /*WRONG*/
    int t[3][6];

    t[0][0] = 121;
    t[0][1] = 85;
    t[0][2] = 54;
    t[0][3] = 89;
    t[0][4] = 879;
    t[0][5] = 11;

    for( i = 0; i < 6; ++i )
        t[1][i] = i+1;

    t[2][0] = 2;
    t[2][1] = 4;
    t[2][2] = 5;
    t[2][3] = 3;
    t[2][4] = 1;    
    t[2][5] = 6;                

    sort_by_first_row(t, 3, 6);

    for(i = 0; i < 3; ++i)
    {
        for(j = 0; j < 6; ++j)
            printf("%d ", t[i][j]);
        printf("\n");
    }
    return 0;
}

My new question is this: How to modify the code, so that the procedure works with int[][] and int** also?

Answer 1

int** is quite different from int[][]. int** is simply a pointer to a pointer and would appear like the following:

in reality, you can access the entire multidimensional array with simply int* pointing to the first element, and doing simple math from that.

Here is the result of the separate allocations (in your commented code):

However when you allocate a multidimensional array, all of the memory is contiguous, and therefore easy to do simple math to reach the desired element.

int t[3][6];
int *t = (int*) malloc((3 * 6) * sizeof(int));  // <-- similarly

This will result in a contiguous chunk of memory for all elements.

You certainly can use the separate allocations, however you will need to walk the memory differently.

Hope this helps.

Answer 2

int t[3][6] is very nearly the same thing as int t[18]. A single contiguous block of 18 integers is allocated in both cases. The variable t provides the address of the start of this block of integers, just like the one-dimensional case.

Contrast this with the case you have marked as "working", where t gives you the address of a block of 3 pointers, each of which points to a block of memory with 6 integers. It's a totally different animal.

The difference between t[3][6] and t[18] is that the compiler remembers the size of each dimension of the array, and automatically converts 2D indices into 1D offsets. For example, the compiler automatically converts t[1][2] into *(t + 1*6 + 2) (equivalent to t[8] if it were declared as a one-dimensional array).

When you pass a multi-dimensional array to a function, there are two ways to handle it. The first is to declare the function argument as an array with known dimension sizes. The second is to treat your array like a 1D array.

If you are going to declare the size of your array, you would declare your function like this:

void sort_by_first_row(int t[][6], int n)

or this

void sort_by_first_row(int t[3][6])

You either have to declare all array dimension sizes, or you can leave out the first size. In both cases, you access elements of t using t[i][j]; you've given the compiler enough information to do the offset math that converts from 2D notation to a 1D index offset.

If you treat it as a 1D array, you have to pass the array dimensions and then do the offset math yourself.

Here's a full working example, where f and f2 both generate the same output:

void f(int* t, int m, int n)
{
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        std::cout << t[i * n + j] << " ";
std::cout << std::endl;
}

void f2(int t[][6], int m)
{
for (int i = 0; i < m; i++)
    for (int j = 0; j < 6; j++)
        std::cout << t[i][j] << " ";
std::cout << std::endl;
}

int main()
{
int t[3][6];
int val = 1;
for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < 6; j++)
    {
        t[i][j] = val;
        val++;
    }
}

f(&(t[0][0]), 3, 6);
f2(t, 3);

return 0;
}

One thing to note is the hack-ish way I had to pass t to f. It's been a while since I wrote in C/C++, but I remember being able to pass t directly. Maybe somebody can fill me in on why my current compiler won't let me.

Answer 3

A int ** is a pointer to a pointer to an int, and can be a pointer to an array of pointers to arrays of ints. A int [][] is a 2-dimensional array of ints. A two-dimensional array is exactly the same as a one-dimensional array in C in one respect: It is fundamentally a pointer to the first object. The only difference is the accessing, a two-dimensional array is accessed with two different strides simultaneously.
Long story short, a int[][] is closer to an int* than an int**.

Answer 4

Realize that int **t makes t a pointer to a pointer, while int t[3][6] makes t an array of an array. In most cases, when an array is used in an expression, it will become the value of the address of its first member. So, for int t[3][6], when t is passed to a function, the function will actually be getting the value of &t[0], which has type pointer to an array (in this case, int (*)[6]).

The type of what is being pointed at is important for how the pointer behaves when indexed. When a pointer to an object is incremented by 5, it points to the 5th object following the current object. Thus, for int **t, t + 5 will point to the 5th pointer, while for int (*t)[M], t + 5 will point to the 5th array. That is, the result of t + 5 is the same as the result of &t[5].

In your case, you have implemented void sort_by_first_row(int **t, int n, int m), but you are passing it an incompatible pointer. That is, the type of &t[0] (which is what t will become in main) is not the same as what the function wants, a int **t. Thus, when the sorting function starts to use that address, it will think its indexing into pointers, when the underlying structure is an array of arrays.