How do 2D arrays in C become 1D arrays?

Question

I would appreciate if someone could explain to me the following behavior:

Say I declare a static 2D array

float buffer[NX][NY];

Now, if I want to populate this array, I have notice that it could be done this way:

initarray(buffer, NX, NY);

#define INITDATAVAL 0.5

void initarray(void *ptr, int nx, int ny)
{
  int i, j;

  float *data = (float *) ptr;

  for (i=0; i < nx*ny; i++)
    {
      data[i] = INITDATAVAL;
    }
}

My question is, if buffer is a 2D array, how can it be used as a 1D array once it is passed to initarray function? I am struggling to understand it...

When 2D arrays are statically allocated, the memory allocated is contiguous, but could this way be used if buffer is dynamically allocated instead?

Answer 1

A 2D array with 3 x 4 elements (i.e. a matrix) looks like this in memory:

A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4

Since the underlying storage is continuous, one can simply convert the array to a pointer to the first element and access all elements using a single offset (this 'cast', which is called 'decaying' in such a context, happens automatically when buffer is passed to initarray).

(In this sample, the compiler would translate an expression such as buffer[n][m] to buffer + n*NY+m Basically, 2D arrays are just a comfortable notation for 2D data stored in 1D arrays).

Answer 2

For a start, initarray should take a float* argument, not void*.

When you convert an array to a pointer, you lose type information about the dimension. You're really converting it to a pointer to the first element, and acknowledging that storage is contiguous.

char foo [2][2] = { {'a','b'}, {'c','d'} }; // Stored as 'a', 'b', 'c', 'd'

You can retain dimension information with templates.

template <int W, int H>
void initarray (float (&input)[W][H]) {
    for (int x = 0; x < W; ++x) {
        for (int y = 0; y < H; ++y) {
            input [x][y] = INITDATAVAL;
        }
    }
}

int main () {
    float array [3][4];
    initarray (array);
}

Here, input is a reference to an array of the given type (and dimensionality is part of the full type). Template argument deduction will instantiate an overload of initarray with W=3, H=4. Sorry for the jargon, but that's how it works.

Incidentally, you will not be able to call this version of initarray with a pointer argument, but you can provide overloads if you want. I often write things like this

extern "C" void process (const char * begin, const char * end);

template <typename N>
void process (const char * (&string_list) [N]) {
    process (string_list, string_list + N);
}

The idea is to provide the most-general possible interface, implement it once in a separate translation unit or library, or whatever, and then provide friendlier, safer interfaces.

const char * strings [] = {"foo", "bar"};
int main () {
    process (strings);
}

Now if I change strings, I don't have to change the code elsewhere. I also don't have to think about irritating details like whether I have maintained NUMBER_OF_STRINGS=2 correctly.