Correctly allocating multi-dimensional arrays

Question

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?

Answer 1

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.