By Lundin


2017-02-07 16:02:03 8 Comments

The intent of this question is to provide a reference about how to correctly allocate multi-dimensional arrays dynamically in C. This is a topic often misunderstood and poorly explained even in some C programming books. Therefore even seasoned C programmers struggle to get it right.


I have been taught from my programming teacher/book/tutorial that the correct way to dynamically allocate a multi-dimensional array is by using pointer-to-pointers.

However, several high rep users on SO now tell me that this is wrong and bad practice. They say that pointer-to-pointers are not arrays, that I am not actually allocating arrays and that my code is needlessly slow.

This is how I was taught to allocate multi-dimensional arrays:

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

int** arr_alloc (size_t x, size_t y)
{
  int** pp = malloc(sizeof(*pp) * x);
  assert(pp != NULL);
  for(size_t i=0; i<x; i++)
  {
    pp[i] = malloc(sizeof(**pp) * y);
    assert(pp[i] != NULL);
  }

  return pp;
}

int** arr_fill (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      pp[i][j] = (int)j + 1;
    }
  }

  return pp;
}

void arr_print (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", pp[i][j]);
    }
    printf("\n");
  }
}

void arr_free (int** pp, size_t x, size_t y)
{
  (void) y;

  for(size_t i=0; i<x; i++)
  {
    free(pp[i]);
    pp[i] = NULL;
  }
  free(pp);
  pp = NULL;
}


int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int** pp;

  pp = arr_alloc(x, y);
  pp = arr_fill(pp, x, y);
  arr_print(pp, x, y);
  arr_free(pp, x, y);

  return 0;
}

Output

1 2 3
1 2 3

This code works just fine! How could it be wrong?

2 comments

@Basile Starynkevitch 2017-12-13 05:45:52

C doesn't have multidimensional arrays (as a primitive data type). But you could have arrays of arrays (or of other aggregates) and arrays of pointers.

A possible approach is to reason with some abstract data type (perhaps using flexible array members, which is one implementation trick, and you could use other approaches) like in this answer.

We can't suggest any abstract data type, because that depends on the text of your homework, which we don't have. You need to design your abstract data type (on a piece of paper), and later to implement it.

Once you have listed (on a paper or on a board) all the operations needed on your ADT, implementing them is straightforward.

This code works just fine! How could it be wrong?

That sentence is inconsistent (wrong w.r.t. what specifications?) ...

I recommend to compile with all warnings and debug info (e.g. with gcc -Wall -Wextra -g with GCC), to improve your code till you get no warnings, to use the debugger gdb (to understand what is happening in your program) and other tools like valgrind.

@Lundin 2017-12-13 07:49:34

How does that answer the question "what is wrong with this method of dynamically allocating 2D arrays/arrays of arrays"?

@Basile Starynkevitch 2017-12-13 08:02:55

2D arrays don't exist.

@Lundin 2017-12-13 09:29:06

It is a very common industry de facto standard term, meaning array of arrays. Still, the question does not contain an array of arrays, which is the whole point here. If you wish to clutter down this post then at least add something meaningful. It is completely unclear how flexible array members can be a useful solution here or what their benefit would be.

@Basile Starynkevitch 2017-12-13 09:30:46

The solution is not in flexible array members, but in defining and implementing some abstract data type. In this answer I am using flexible array members, but the OP could use some other approach. I am not even trying to guess what is the original problem of OP and what abstract data type he should consider (because I don't have the text of the homework given to OP).

@Lundin 2017-12-13 09:36:35

Rather, you are using a C90 "mangled array", which is not a modern C, we've had pointers to VLA for almost 20 years. Further, the ADT solution suffers from very poor access times, since you effectively block any possibility of data cache use when iterating through the container. And it isn't possible to grab blocks of data from the matrix either. Although I agree that the ADT is a good solution system design-wise, the performance will be very poor.

@Basile Starynkevitch 2017-12-13 09:40:01

I don't see how the ADT solution suffers from poor access times. The functions could be inlined if efficiency is a concern.

@Lundin 2017-12-13 09:45:58

It will most likely not get inlined by the compiler. Even if it was and this doesn't screw up cache access, you still have multiple extra branches per iteration, killing performance.

@Bob__ 2018-10-10 09:03:37

I think that this answer could be improved (if you are still interested in) by showing a minimal implementation and the use cases were an abstract data type could be used (while a VLA cant), like as a member of a struct or in an array or simply as a return value.

@Et7f3XIV 2019-01-18 00:11:00

we can malloc un big table for instance 301x301 and we can do math for acces the logically (200, 100) with the index 100 * 300 + 200. With this logic we can have a unique call to malloc and with this math trick that we can hide in MACROs to access like before. And because it is contigus we can use memset or calloc to empty (and not having to create ou own function: like arr_alloc and arr_free in the first message)

@Eric Postpischil 2019-08-08 20:30:43

“C don't have multidimensional arrays” is akin to saying C does not have negative numbers. Check the grammar; there are no negative constants. You can only use positive constants and apply the unary - operator. Of course C does have negative numbers, and it does have multidimensional arrays. Both are simply built from primitives instead of being primitives themselves.

@Lundin 2017-02-07 16:02:03

In order to answer the question, we should first clear up some concepts. What is an array and how can it be used? And what is the code in the question, if not an array?


What is an array?

The formal definition of an array is found in the C standard, ISO 9899:2011 6.2.5/20 Types.

An array type describes a contiguously allocated non-empty set of objects with a particular member object type, called the element type.

In plain English, an array is a collection of items of the same type allocated contiguously, in adjacent memory cells.

For example an array of 3 integers int arr[3] = {1,2,3}; would be allocated in memory like this:

+-------+-------+-------+
|       |       |       |
|   1   |   2   |   3   |
|       |       |       |
+-------+-------+-------+

So what about the formal definition of a multi-dimensional array? Actually, it is the very same definition as cited above. It applies recursively.

If we would allocate a 2D array, int arr[2][3] = { {1,2,3}, {1,2,3} }; it would get allocated in memory like this:

+-------+-------+-------+-------+-------+-------+
|       |       |       |       |       |       |
|   1   |   2   |   3   |   1   |   2   |   3   |
|       |       |       |       |       |       |
+-------+-------+-------+-------+-------+-------+

What we have in this example is actually an array of arrays. An array which has 2 items, each of them an array of 3 integers.


An array is a type like any other

Arrays in C often follow the same type system as regular variables. As shown above, you can have an array of arrays, like you can have an array of any other type.

You can also apply the same kind of pointer arithmetic on n-dimensional arrays as on plain one-dimensional arrays. With a regular one-dimensional arrays, applying pointer arithmetic should be trivial:

int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.

for(size_t i=0; i<3; i++)
{
  printf("%d ", *ptr); // print contents.
  ptr++; // set pointer to point at the next element.
}

This was made possible through "array decay". When arr was used inside an expression, it "decayed" into a pointer to the first element.

Similarly, we can use the very same kind of pointer arithmetic to iterate through an array of arrays, by using an array pointer:

int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.

for(size_t i=0; i<2; i++)
{
  printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
  ptr++; // set pointer to point at the next element
}

Again there was array decay. The variable arr which was of type int [2][3] decayed into a pointer to the first element. The first element was an int [3] and a pointer to such an element is declared as int(*)[3] - an array pointer.

Understanding array pointers and array decay is necessary in order to work with multi-dimensional arrays.


There are more cases where arrays behave just like regular variables. The sizeof operator works just the same for (non-VLA) arrays as for regular variables. Examples for a 32 bit system:

int x; printf("%zu", sizeof(x)); prints 4.
int arr[3] = {1,2,3}; printf("%zu", sizeof(arr)); prints 12 (3*4=12)
int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr)); prints 24 (2*3*4=24)


Like any other type, arrays can be used with library functions and generic APIs. Since arrays fulfil the requirement of being allocated contiguously, we can for example safely copy them with memcpy:

int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));

Contiguous allocation is also the reason why other similar standard library functions like memset, strcpy, bsearch and qsort work. They are designed to work on arrays allocated contiguously. So if you have a multi-dimensional array, you can efficiently search it and sort it with bsearch and qsort, saving you the fuss of implementing binary search and quick sort yourself and thereby re-inventing the wheel for every project.

All of the above consistencies between arrays and other types is a very good thing that we want to take advantage of, particularly when doing generic programming.


What is the pointer-to-pointer thing, if not an array?

Now to get back to the code in the question, which used a different syntax with a pointer-to-pointer. There is nothing mysterious about it. It is a pointer to pointer to type, no more no less. It is not an array. It is not a 2D array. Strictly speaking, it cannot be used to point at an array, nor can it be used to point at a 2D array.

A pointer-to-pointer can however be used to point at the first element of an array of pointers, instead of pointing at the array as whole. And that is how it is used in the question - as a way to "emulate" an array pointer. In the question, it is used to point at an array of 2 pointers. And then each of the 2 pointers is used to point at an array of 3 integers.

This is known as a look-up table, which is a kind of abstract data type (ADT), which is something different from the lower level concept of plain arrays. The main difference is how the look-up table is allocated:

+------------+
|            |
| 0x12340000 |
|            |
+------------+
      |
      |
      v
+------------+     +-------+-------+-------+
|            |     |       |       |       |
| 0x22223333 |---->|   1   |   2   |   3   |
|            |     |       |       |       |
+------------+     +-------+-------+-------+
|            | 
| 0xAAAABBBB |--+
|            |  | 
+------------+  |  
                |
                |  +-------+-------+-------+
                |  |       |       |       |
                +->|   1   |   2   |   3   |
                   |       |       |       |
                   +-------+-------+-------+

The 32 bit addresses in this example are made-up. The 0x12340000 box represents the pointer-to-pointer. It contains an address 0x12340000 to the first item in an array of pointers. Each pointer in that array in turn, contains an address pointing at the first item in an array of integers.

And here is where the problems start.


Problems with the look-up table version

The look-up table is scattered all over the heap memory. It is not contiguously allocated memory in adjacent cells, because each call to malloc() gives a new memory area, not necessarily located adjacently to the others. This in turn gives us lots of problems:

  • We can't use pointer arithmetic as expected. While we can use a form of pointer arithmetic to index and access the items in the look-up table, we can't do so using array pointers.

  • We can't use the sizeof operator. Used on the pointer-to-pointer, it would give us the size of a pointer-to-pointer. Used to the first item pointed at, it would give us the size of a pointer. Neither of them is the size of an array.

  • We can't use standard library functions that excepts an array type (memcpy, memset, strcpy, bsearch, qsort and so on). All such functions assume to get arrays as input, with data allocated contiguously. Calling them with our look-up table as parameter would result in undefined behavior bugs, such as program crashes.

  • Repeated calls of malloc to allocate several segments leads to heap fragmentation, which in turn results in poor use of RAM memory.

  • Since the memory is scattered, the CPU cannot utilize cache memory when iterating through the look-up table. Efficient use of the data cache requires a contiguous chunk of memory which is iterated through from top to bottom. This means that the look-up table, by design, has significantly slower access time than a real multi-dimensional array.

  • For each call to malloc(), the library code managing the heap has to calculate where there is free space. Similarly for each call to free(), there is overhead code which has to be executed. Therefore, as few calls to these functions as possible is often preferable, for the sake of performance.


Are look-up tables all bad?

As we can see, there are a lot of problems with pointer-based look-up tables. But they aren't all bad, it is a tool like any other. It just has to be used for the right purpose. If you are looking for a multi-dimensional array, which should be used as an array, look-up tables are clearly the wrong tool. But they can be used for other purposes.

A look-up table is the right choice when you need all dimensions to have completely variable sizes, individually. Such a container can be handy when for example creating a list of C strings. It is then often justified to take the above mentioned execution speed performance loss in order to save memory.

Also, the look-up table has the advantage that you can re-alloce parts of the table in run-time without the need to re-allocate a whole multi-dimensional array. If this is something that needs to be done frequently, the look-up table might even outperform the multi-dimensional array in terms of execution speed. For example, similar look-up tables can be used when implementing a chained hash table.


How to properly allocate a multi-dimensional array dynamically then?

The easiest form in modern C is to simply use a variable-length array (VLA). int array[x][y]; where x and y are variables given values in run-time, prior array declaration. However, VLAs have local scope and do not persist throughout the duration of the program - they have automatic storage duration. So while VLAs may be convenient and fast to use for temporary arrays, it is not an universal replacement to the look-up table in the question.

To truly allocate a multi-dimensional array dynamically, so that it gets allocated storage duration, we have to use malloc()/calloc()/realloc(). I'll give one example below.

In modern C, you would use array pointers to a VLA. You can use such pointers even when no actual VLA is present in the program. The benefit of using them over a plain type* or a void* is increased type-safety. Using a pointer to a VLA also allows you to pass the array dimensions as parameters to the function using the array, making it both variable and type safe at once.

Unfortunately, in order to use the benefits of having a pointer to VLA, we can't return that pointer as a function result. So if we need to return a pointer to the array to the caller, it must be passed as a parameter (for the reasons described in Dynamic memory access only works inside function). This is fine practice in C, but makes the code a bit hard to read. It would look something like this:

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

While this syntax with a pointer to an array pointer might look a bit strange and intimidating, it doesn't get more complex than this even if we add more dimensions:

void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
  *aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
  assert(*aptr != NULL);
}

Now compare that code with the code for adding one more dimension to the look-up table version:

/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
  int*** ppp = malloc(sizeof(*ppp) * x);
  assert(ppp != NULL);
  for(size_t i=0; i<x; i++)
  {
    ppp[i] = malloc(sizeof(**ppp) * y);
    assert(ppp[i] != NULL);
    for(size_t j=0; j<y; j++)
    {
      ppp[i][j] = malloc(sizeof(***ppp) * z);
      assert(ppp[i][j] != NULL);
    }
  }

  return ppp;
}

Now that is one unreadble mess of "three-star programming". And lets not even consider 4 dimensions...


The full code of a version using true 2D arrays

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

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

void arr_fill (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      array[i][j] = (int)j + 1;
    }
  }
}

void arr_print (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", array[i][j]);
    }
    printf("\n");
  }
}

int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int (*aptr)[x][y];

  arr_alloc(x, y, &aptr);
  arr_fill(x, y, *aptr);
  arr_print(x, y, *aptr);
  free(aptr); // free the whole 2D array

  return 0;
}

@yano 2017-02-07 16:39:38

just to be clear, your final solution here relies on support for VLAs, which came about in C99?

@Lundin 2017-02-08 07:28:25

@yano Yes, VLAs were introduced 18 years ago.

@Lundin 2017-02-08 07:31:30

@DavidBowling This was written specifically for questions about how to correctly allocate multi-dimensional arrays dynamically. Array decay and array versus pointer etc were already covered by fairly good "canonical duplicates".

@user694733 2017-02-15 14:45:27

Well written and needed answer. But one thing bugs me: Why mention bsearch/qsort? Those are intended to operate on single dimension. If you use them to sort pointers on first dimension of p2p array, it works as well as sorting rows on 2D array, assuming user defines appropriate comparison function and gives valid arguments.

@Lundin 2017-02-15 15:16:36

@user694733 Well of course you could dodge the problem by handling the access in the passed function, bsearch/qsort are quite flexible. But suppose that you would for example want to search/sort through a generic chunk of raw data. You can do this just fine by passing a n-dimensional array to bsearch/qsort. Or suppose you have a n-dimensional array of uint32_t and want to search for individual byte values. Sort pixels in a graphical bitmap by color etc etc.

@Lundin 2017-02-15 15:17:05

Another point here is that if you pass a true n-dimensional array to those functions, it will still work, because int array[x][y][z] is actually a single dimension array. It is a 1D array of x items with type int [y][z].

@user694733 2017-02-16 06:49:01

OK, I see what you mean. I was going to suggest that you that add to the answer, but maybe it's not that necessary. It's already a long answer, and main point is more important.

@StoryTeller - Unslander Monica 2017-02-19 08:15:45

"saving you the fuss of implementing binary search and quick sort yourself" - nitpick, but qsort isn't obligated to be implemented as quicksort. That sentence may mislead people into thinking things about the memory/time footprint of the function that they shouldn't.

@Nikos 2017-03-17 13:40:41

@Lundin This is a very valuable page. A couple questions to make sure i understood all. 1. int (*aptr)[x][y] declares a pointer named aptr to an array of x rows and y columns, right? 2. The argument int(**aptr)[x][y] in the function expects a pointer to a pointer to an (VLA) array of x rows and y columns. 3. By malloc()ing such an array we eliminate the (potential) disadvantage of a VLA, ie. the fact that it has automatic storage class, and then the array behaves more like a true malloced array on the heap. Am i correct?

@Lundin 2017-03-17 15:18:10

@RestlessC0bra 1) Correct, although the definition of what's "rows" and what's "columns" lies in the application. The C standard only requires that there are y contiguous segments of x contiguous variables of the given type. 2) Correct. 3) Indeed - a pointer to a VLA does not necessarily have to point at an object with automatic storage duration, or even to a VLA. A pointer of the form type (*name)[n] where n is a run-time value, can be set to point to any array of the same type and size, no matter where it is allocated.

@Nikos 2017-03-17 15:48:37

@Lundin A great advantage of this technique (i don't remember if you mentioned) is that we can allocate a multidimensional array in contiguous memory locations (like a normal compiled one) which doesn't happen when we would malloc() such an array. Now we have the best of both worlds. Amazing! Thank you very much indeed friend.

@Lundin 2017-03-17 15:58:10

@RestlessC0bra If it isn't allocated in contiguous memory, it is not an array. The essence of this whole post was to straighten our that incorrect belief.

@Toby 2017-04-06 10:03:26

@Lundin Great write-up! Always impressed by the comprehensiveness of your C knowledge and your ability to explaining things so well!

@Seek Addo 2017-04-11 17:06:10

@Lundin since when did you realise you were doing it wrong and acquired all this deep understanding.? Well written answer, worth following your page,i have learnt alot. I have always had the wrong idea, i thought the pointer-to-pointer was faster and efficient.

@Ilja Everilä 2017-05-03 08:51:34

I have to agree with @user694733, and add that the whole "We can't use standard library functions that excepts an array type (memcpy, memset, strcpy, bsearch, qsort and so on)." sounds too broad. memcpy, qsort etc. work nicely for array of pointer to T, or in other words pointer to pointer to T pointing to first element of such. While you'd make "shallow" copies only, it is very useful for strings for example. For some situations sorting an array of pointers can be beneficial, compared to moving arrays around. Still, an excellent writeup.

@chux - Reinstate Monica 2017-05-05 19:43:50

Alternative to *aptr = malloc( sizeof(int[x][y]) );, use *aptr = malloc(sizeof **aptr); to match the idiomatically correct pointer = malloc(sizeof *pointer);.

@M.M 2017-12-13 05:55:21

You say "The formal definition of an array is found..." but then you quote the formal definition of array type. In fact the standard doesn't formally define array anywhere.

@Ajay Brahmakshatriya 2017-12-13 05:58:44

Instead of having a pointer to int[x][y], wouldn't it be better to have a pointer to int[y]? Saves an extra dereference while using (mainly avoids confusion). I agree it strips the outermost size information.

@Lundin 2017-12-13 07:47:41

@AjayBrahmakshatriya Yes that's a common trick, but I didn't use it on purpose here, as the reader might be unfamiliar with array pointers in the first place.

@Andrew Henle 2017-12-14 15:37:56

Repeated calls of malloc to allocate several segments leads to heap fragmentation, which in turn results in poor use of RAM memory It's almost trivial to dynamically allocate an N-dimensional "array" with only N+1 calls to malloc(), and it's possible though not trivial to allocate one with a single call.

@Varad Bhatnagar 2018-03-22 15:58:26

Thank you for such a detailed answer. Cleared all my misconceptions.

@ thoron 2018-10-17 21:44:57

@Lundin int (*arr)[5]; printf("%d\n", &arr[0]); printf("%d\n", &arr[1]); It prints 0 and 20 Is it possible when you do type (*ptr)[x][y] you set step size(++ptr) as y * sizeof(type)? When I tried same thing in 2D array I observed same thing.

Related Questions

Sponsored Content

47 Answered Questions

88 Answered Questions

[SOLVED] How do I remove a particular element from an array in JavaScript?

  • 2011-04-23 22:17:18
  • Walker
  • 6087306 View
  • 7588 Score
  • 88 Answer
  • Tags:   javascript arrays

41 Answered Questions

[SOLVED] Loop through an array in JavaScript

37 Answered Questions

[SOLVED] Deleting an element from an array in PHP

  • 2008-12-15 20:28:55
  • Ben
  • 2429179 View
  • 2349 Score
  • 37 Answer
  • Tags:   php arrays unset

33 Answered Questions

[SOLVED] For-each over an array in JavaScript?

47 Answered Questions

[SOLVED] How to check if an object is an array?

34 Answered Questions

[SOLVED] Create ArrayList from array

16 Answered Questions

[SOLVED] How to insert an item into an array at a specific index (JavaScript)?

10 Answered Questions

[SOLVED] How to Sort Multi-dimensional Array by Value?

30 Answered Questions

[SOLVED] How to append something to an array?

Sponsored Content