Heap allocate a 2D array (not array of pointers)

Question

I am writing C code and I would like to heap allocate 512*256 bytes. For my own convenience I would like to be able to access the elements with the syntax array[a][b]; no arithmetic to find the right index.

Every tutorial I see online tells me to create an array of pointers that point to arrays of the rows I want in my array. This means that each subarray needs to be malloc'd and free'd individually. I am interested in a solution that only requires one call to malloc and one call to free.(Thus all elements are contiguous) I think this is possible because I will not be constructing a jagged array.

I would appreciate if anyone could share the syntax for declaring such an array.

Solution 1

Well, if you want to allocate array of type, you assign it into a pointer of that type.

Since 2D arrays are arrays of arrays (in your case, an array of 512 arrays of 256 chars), you should assign it into a pointer to array of 256 chars:

char (*arr)[256]=malloc(512*256);
//Now, you can, for example:
arr[500][200]=75;

(The parentheses around *arr are to make it a pointer to array, and not an array of pointers)

Solution 2

This is easy assuming you don't need compatibility with the ancient C89 standard (among current C compilers, only MSVC and a few embedded-target compilers are that backwards). Here's how you do it:

int (*array)[cols] = malloc(rows * sizeof *array);

Then array[a][b] is valid for any a in [0,rows) and b in [0,cols).

In the language of the C standard, array has variably-modified type. If you want to pass the pointer to other functions, you'll need to repeat this type in the function argument list and make sure that at least the number of columns is passed to the function (since it's needed as part of the variably-modified type).

Edit: I missed the fact that OP only cares about a fixed size, 512x256. In that case, C89 will suffice, and all you need is:

int (*array)[256] = malloc(512 * sizeof *array);

The exact same type can be used in function argument lists if you need to pass the pointer around between functions (and also as a function return type, but for this use you might want to typedef it... :-)

Solution 3

If you allocate the array like this, it requires two calls to free, but it allows array[a][b] style syntax and is contiguous.

char **array = malloc(512 * sizeof(char *));
array[0] = malloc(512*256);
for (int i = 1; i < 512; i++)
    array[i] = array[0] + (256 * i);

See array2 here for more information: http://c-faq.com/aryptr/dynmuldimary.html

Solution 4

Since you know the size of the array ahead of time, you could create a struct type that contains a 521x256 array, and then dynamically allocate the struct.

Solution 5

It is possible to dynamically allocate the same kind of multidimensional array that

static char x[512][256];

gives you, but it's a wee tricky because of type decay. I only know how to do it with a typedef:

typedef char row[512];
row *x = malloc(sizeof(row) * 256);

This only lets you determine the size of the second dimension at runtime. If both dimensions can vary at runtime, you need a dope vector.

View more solutions

Comments

[Richard J. Ross III]

Is C++ an option? You could create a simple C++ objects that overloads the indexing operator.

[Ed S.]

@RichardJ.RossIII: Is that really a valid response to a question of "how do I do this in C?" (realizing that you did leave it as a comment). I'll take C over C++ any day thank you.

[Richard J. Ross III]

@EdS. while you may prefer C, C++ is better in quite a few situations, and this would be one of them. I left it as a comment simply to determine if it would be an option.

[Ed S.]

@RichardJ.RossIII: C++ is better for allocating a 2d array? huh? I don't think so, this is easily doable in C, no C++ operator overloading required.

[R.. GitHub STOP HELPING ICE]

See my answer; unlike the others it actually does what you ask for.

[zwol]

You can combine the two allocations by putting the data block immediately after the dope vector. Requires a certain amount of fiddly typecasting but isn't that hard. However, your code as shown has a serious bug: you allocate space for 512 chars, and then you treat that as enough space for 512 char *s. This is just about guaranteed to walk off the end of the allocation and crash.

[Richard J. Ross III]

Interesting solution, is there any way you could figure out how to do this with a dynamic array?

[Sergey Kalinichenko]

@RichardJ.RossIII Unfortunately, this does not work with dynamically-sized arrays, because typedef needs compile-time constants for both dimensions. The best you can do is to make one dimension fixed and the other dynamic, but it wouldn't make it completely dynamic.

[asaelr]

You are right in the general case, but the OP only wants 512*256 array.

[R.. GitHub STOP HELPING ICE]

The typedef is unnecessary and actually it's harmful to put both dimensions in the typedef since you're stuck using (*a) all over the place instead of just plain a. If you just put the number of columns, it would work a lot better. And of course with C99, you can make the type variably-modified; I believe this is even valid in a typedef as long as the typedef has block scope rather than file scope.

[R.. GitHub STOP HELPING ICE]

+1, somehow I missed that you posted this while I was writing my answer. :-)

[R.. GitHub STOP HELPING ICE]

Missed this one too. Note that unless you're limited to C89, both dimensions can vary; you just need to use a variably-modified pointer type.

[R.. GitHub STOP HELPING ICE]

This is not a two-dimensional array but an array of pointers. It has some advantages (you can permute the rows in O(1) instead of O(cols)) and other disadvantages (each access is more expensive since it goes through an extra level of indirection; it takes more memory; etc.). In any case, if you take this approach, consider Zack's suggestion to use just a single malloc. That simplifies your error handling (no partial failure case to cleanup from) and ensures memory locality.

[Paul]

This is exactly what I was looking for. Thank you.

[Kos]

Note that since C99 the dimensions no longer have to be known in compile time. You can have n,m read from stdin and declare a char arr[n][m] or, in this case, a char (*arr)[n].

[Paul]

Actually, this answer is excellent. Although I only need 512*256 now, I could easily see this requirement changing in the future.

[sacheie]

I love the general case approach, but haven't been able to understand one thing. Does it still require looping through the outer array to free all the inner one's pointers? Or is only one call to free() required?

[R.. GitHub STOP HELPING ICE]

@sacheie: You can only call free exactly once for each malloc; this is always true. array is not an array of pointers but an array of arrays. Each array[i] decays to a pointer to its first element, but array[i] is an array.