Asignación correcta de matrices multidimensionales

Para responder a la pregunta, primero debemos aclarar algunos conceptos. ¿Qué es un array y cómo se puede utilizar? ¿Y cuál es el código en la pregunta, si no es una matriz?

¿Qué es una matriz?

La definición formal de una matriz se encuentra en el estándar C, ISO 9899:2011 6.2.5/20 Tipos.

Un tipo de matriz describe un conjunto no vacío objetos con un tipo de objeto miembro particular, llamado elemento tipo.

En inglés simple, una matriz es una colección de elementos del mismo tipo asignados contiguamente, en celdas de memoria adyacentes.

Por ejemplo, una matriz de 3 enteros int arr[3] = {1,2,3}; se asignaría en la memoria de la siguiente manera:

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

Entonces, ¿qué pasa con la definición formal de una matriz multidimensional? En realidad, es la misma definición que se mencionó anteriormente. Se aplica recursivamente.

Si asignáramos una matriz 2D, int arr[2][3] = { {1,2,3}, {1,2,3} }; se asignaría en memoria así:

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

Lo que tenemos en este ejemplo es en realidad una matriz de matrices. Una matriz que tiene 2 elementos, cada uno de ellos una matriz de 3 enteros.

Un array es un tipo como cualquier otro

Los arrays en C a menudo siguen el mismo tipo de sistema que las variables regulares. Como se muestra arriba, puede tener una matriz de matrices, como puede tener una matriz de cualquier otro tipo.

También puede aplicar el mismo tipo de aritmética de puntero en n-dimensional arrays como en arrays unidimensionales simples. Con matrices unidimensionales regulares, la aplicación de aritmética de puntero debería ser 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
}

Esto fue posible a través del "array decay". Cuando arr se usa dentro de una expresión, se "descompone" en un puntero al primer elemento.

Del mismo modo, podemos usar el mismo tipo de aritmética de puntero para iterar a través de una matriz de matrices, mediante el uso de un puntero de matriz :

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
}

Otra vez hubo decaimiento del arreglo. El variable arr que era de tipo int [2][3] decayó en un puntero al primer elemento. El primer elemento era un int [3] y un puntero a dicho elemento se declara como int(*)[3] - un puntero de matriz.

Para trabajar con matrices multidimensionales es necesario comprender los punteros de matrices y el decaimiento de matrices.

Hay más casos donde los arrays se comportan como variables regulares. El operador sizeof funciona igual para matrices (no-VLA) que para variables regulares. Ejemplos para un sistema de 32 bits:

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

Como cualquier otro tipo, los arrays se pueden usar con funciones de biblioteca y API genéricas. Dado que los arrays cumplen con el requisito de ser asignados contiguamente, podemos por ejemplo copiarlos de forma segura con memcpy:

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

La asignación contigua es también la razón por la que otras funciones de biblioteca estándar similares como memset, strcpy, bsearch y qsort trabajo. Están diseñados para trabajar en matrices asignadas contiguamente. Así que si tienes una matriz multidimensional, puedes buscarla y ordenarla eficientemente con bsearch y qsort, ahorrándote el alboroto de implementar la búsqueda binaria y la clasificación rápida tú mismo y así reinventar la rueda para cada proyecto.

Todas las consistencias anteriores entre matrices y otros tipos es una cosa muy buena que queremos aprovechar, particularmente cuando hacemos genéricos programación.

¿Qué es la cosa de puntero a puntero, si no es una matriz?

Ahora volvamos al código de la pregunta, que usaba una sintaxis diferente con un puntero a puntero. No hay nada misterioso en ello. Es un puntero a puntero a tipo, ni más ni menos. No es una matriz. No es una matriz 2D. Estrictamente hablando, no se puede usar para apuntar a una matriz, ni se puede usar para apuntar a una matriz 2D.

Sin embargo, un puntero a puntero puede ser se usa para apuntar al primer elemento de una matriz de punteros, en lugar de apuntar a la matriz como un todo. Y así es como se usa en la pregunta-como una forma de" emular " un puntero de matriz. En la pregunta, se utiliza para apuntar a una matriz de 2 punteros. Y, a continuación, cada uno de los 2 punteros se utiliza para apuntar una matriz de 3 enteros.

Esto se conoce como una tabla de búsqueda, que es una especie de tipo de datos abstractos (ADT), que es algo diferente del concepto de nivel inferior de matrices planas. El la principal diferencia es cómo se asigna la tabla de consulta:

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

Las direcciones de 32 bits en este ejemplo están inventadas. El cuadro 0x12340000 representa el puntero a puntero. Contiene una dirección 0x12340000 al primer elemento de una matriz de punteros. Cada puntero en esa matriz a su vez, contiene una dirección que apunta al primer elemento en una matriz de enteros.

Y aquí es donde comienzan los problemas.

Problemas con la tabla de consulta version

La tabla de búsqueda está dispersa por toda la memoria del montón. No se asigna memoria contiguamente en celdas adyacentes, porque cada llamada a malloc da una nueva área de memoria, no necesariamente ubicada contiguamente a las otras. Esto a su vez nos da muchos problemas:

• No podemos usar la aritmética del puntero como se esperaba. Si bien podemos usar una forma de aritmética de puntero para indexar y acceder a los elementos en la tabla de búsqueda, no podemos hacerlo usando array puntero.

• No podemos usar el tamaño del operador. Utiliza el puntero a puntero, que nos daría el tamaño de un puntero a puntero. Usado para el primer elemento apuntado, nos daría el tamaño de un puntero. Ninguna de ellas tiene el tamaño de una matriz.

• No podemos usar funciones de biblioteca estándar que exceptuen un tipo array (memcpy, memset, strcpy, bsearch, qsort y así sucesivamente). Todas estas funciones asumen que obtienen matrices como entrada, con datos asignados contiguamente. Llamarlos con nuestra tabla de búsqueda como parámetro resultaría en errores de comportamiento indefinidos, como bloqueos del programa.

• Las llamadas repetidas de malloc para asignar varios segmentos conducen a la fragmentación de heap , que a su vez resulta en un mal uso de la memoria RAM.

• Dado que la memoria está dispersa, la CPU no puede utilizar la memoria caché cuando itera a través de la tabla de búsqueda. El uso eficiente de la caché de datos requiere un trozo de memoria contiguo que se itera de arriba a abajo. Esto significa que la tabla de búsqueda, por diseño, tiene un tiempo de acceso significativamente más lento que una matriz multidimensional real.

• Para cada llamada a malloc (), el código de la biblioteca que administra el montón tiene que calcular dónde hay espacio libre. De manera similar para cada llamada a free(), hay un código de sobrecarga que tiene que ser ejecutado. Por lo tanto, tan pocas llamadas a estas funciones como sea posible a menudo es preferible, por el bien de rendimiento.

¿Las mesas de consulta son malas?

Como podemos ver, hay muchos problemas con las tablas de búsqueda basadas en punteros. Pero no todos son malos, es una herramienta como cualquier otra. Solo tiene que ser utilizado para el propósito correcto. Si está buscando una matriz multidimensional, que debería usarse como una matriz, las tablas de búsqueda son claramente la herramienta equivocada. Pero pueden ser utilizados para otros fines.

Una tabla de búsqueda es la elección correcta cuando necesite que todas las dimensiones tengan tamaños completamente variables, individualmente. Tal contenedor puede ser útil cuando, por ejemplo, se crea una lista de cadenas C. Entonces, a menudo se justifica tomar la pérdida de rendimiento de velocidad de ejecución mencionada anteriormente para ahorrar memoria.

Además, la tabla de búsqueda tiene la ventaja de que puede volver a asignar partes de la tabla en tiempo de ejecución sin la necesidad de reasignar una matriz multidimensional completa. Si esto es algo que debe hacerse con frecuencia, la tabla de búsqueda podría incluso superar a la matriz multidimensional en términos de velocidad de ejecución. Por ejemplo, se pueden usar tablas de búsqueda similares cuando se implementa una tabla hash encadenada.

¿Cómo asignar correctamente una matriz multidimensional dinámicamente entonces?

La forma más fácil en C moderna es simplemente usar un array de longitud variable (VLA). int array[x][y]; donde x y y son variables con valores dados en tiempo de ejecución, declaración de matriz anterior. Sin embargo, VLAs tienen locales alcance y no persisten durante toda la duración del programa - tienen duración de almacenamiento automático. Por lo tanto, si bien VLAs puede ser conveniente y rápido de usar para arreglos temporales, no es un reemplazo universal de la tabla de búsqueda en la pregunta.

Para asignar realmente una matriz multidimensional dinámicamente, de modo que obtenga la duración de almacenamiento asignada, tenemos que usar malloc/calloc/realloc. Voy a dar un ejemplo a continuación.

En C moderno, usarías punteros de matriz a un VLA. Puede utilizar estos punteros incluso cuando no hay VLA real presente en el programa. El beneficio de usarlos sobre un simple type* o un void* es una mayor seguridad de tipo. El uso de un puntero a un VLA también le permite pasar las dimensiones de la matriz como parámetros a la función utilizando la matriz, lo que hace que sea variable y tipo seguro a la vez.

Desafortunadamente, para usar los beneficios de tener un puntero a VLA, no podemos devolver ese puntero como resultado de una función. Así que si necesitamos devolver un puntero a la matriz al llamador, debe pasarse como parámetro (por las razones descritas en El acceso dinámico a la memoria solo funciona dentro de la función). Esta es una buena práctica en C, pero hace que el código sea un poco difícil de leer. Se vería algo como esto:

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);
}

Si bien esta sintaxis con un puntero a un puntero de matriz podría parecer un poco extraña e intimidante, no se vuelve más compleja que esto incluso si agregamos más dimensiones:

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);
}

Ahora compare ese código con el código para agregar una dimensión más a la versión de la tabla de búsqueda:

/* 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;
}

Ahora eso es un desastre no leído de "programación de tres estrellas". Y ni siquiera consideremos 4 dimensiones...

El código completo de una versión usando matrices 2D verdaderas

#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;
}