Variable sized matrix in C

Question

Is there any way to create a variable sized doubly-scripted array in C (not C++, just C)? I know that to create a variable sized singly-scripted array, you just use a pointer, e.g.

float *array;
array = (float *) calloc(sizeof(float), n);

creates a singly-scripted array of floats of size n. Is there something similar that I can do for doubly-scripted arrays?

Answer 1

The comp.lang.c FAQ has a good section on this.

Answer 2

You can do almost the same thing for multi dimensional arrays.

float **array;
array = calloc(sizeof(float*), n);
for(int i = 0; i < n; i++)
{
    array[i] = calloc(sizeof(float), n);
}

Answer 3

If you want a matrix with n rows and m columns then you can use a linear array of length m*n to represent this, where each index i represents

row = i  / n
col = i  % n

and the inverse mapping

i  = row * n  + col

Most algebra packages that use matrices like matlab actually use this representation, because it generalizes well to any dimension (you could generalize this to a 3-dimensional matrix just as well).

Answer 4

There are no double-scripted arrays in C; there are only arrays of arrays. E.g. this:

int a[3][3];

Should read as "array of 3 arrays of 3 ints", not as "array of 3x3 ints". This is immediately visible from types of expressions - e.g. a[0] is a valid expression, and its type is int[3].

For array types, array size is part of the type, and therefore must be known at compile-time. Therefore, while you can have a type "pointer to arrays" to make one dimension dynamic, the remaining ones would still have to be fixed:

int (*p)[3] // pointer to arrays of 3 ints each

There are two traditional workarounds:

1. Just use a single-dimensional dynamic array of width x height elements, and calculate 1D indices from 2D coordinates as (y * width + x) yourself.

2. Use pointer to pointers:

   int** a = malloc(sizeof(int*) * height);
   for (i = 0; i < height; ++i) a[i] = malloc(sizeof(int) * width);
   a[0][0] = 123;
   ...
   

   The problem here is that your array needs not be rectangular anymore, and you can't really enforce it. Performance-wise, it's also worse than a single contiguous block of memory.

In C99, you can also use variable-length arrays:

void foo(int width, int height) {
    int a[width][height];
    ...
}

Answer 5

No, that's not possible. As an alternative, allocate a single array, and define an indexing function that takes your coordinate and returns an index into the array.

int Index(int i, int j, int numCols)
{ 
    return i * numCols + j;
}

int numRows = 100;
int numCols = 200;

float *data = malloc(sizeof(float) * numRows * numCols);

data[Index(34, 56, numCols)] = 42.0f;

Answer 6

You can use C99 variable-length arrays (works with gcc):

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

void foo(size_t rows, size_t cols, float array[rows][cols])
{
    printf("%f\n", array[2][3]);
}

int main(void)
{
    size_t rows = 4;
    size_t cols = 5;
    float (*array)[cols] = calloc(sizeof (float), rows * cols);
    array[2][3] = 42;
    foo(rows, cols, array);
}

Answer 7

I'm surprised no-one has pointed out the 'obvious' alternative which preserves the single contiguous allocation for the main matrix, but has the vector of pointers to give double subscripting. (I suppose that means it isn't obvious, after all.)

float **array2d = malloc(sizeof(*array2d) * height);
float  *array1d = malloc(sizeof(*array1d) * height * width);

for (i = 0; i < height; ++i)
    array2d[i] = &array1d[i * width];

Now you can write 2-D array accesses as usual:

array2d[0][0] = 123.0;

Clearly, we also need to check the memory allocation.