Asignar correctamente matrices multidimensionales

Para responder a la pregunta, primero debemos aclarar algunos conceptos. ¿Qué es una matriz y cómo se puede utilizar? ¿Y cuál es el código de la pregunta, si no 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 Types .

Un tipo de matriz describe un conjunto de objetos no vacíos asignados de forma contigua con un tipo de objeto miembro particular, llamado tipo de elemento.

En términos sencillos, una matriz es una colección de elementos del mismo tipo asignados de forma contigua en celdas de memoria adyacentes.

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

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

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

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

+-------+-------+-------+-------+-------+-------+
|       |       |       |       |       |       |
|   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 números enteros.

Una matriz es un tipo como cualquier otro.

Las matrices en C suelen seguir el mismo sistema de tipos que las variables regulares. Como se muestra arriba, puede tener una matriz de matrices, al igual que puede tener una matriz de cualquier otro tipo.

También puede aplicar el mismo tipo de aritmética de punteros en matrices de n dimensiones que en matrices unidimensionales simples. Con matrices unidimensionales regulares, aplicar la aritmética de punteros 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 gracias a la "desintegración de la matriz". Cuando arrse usaba dentro de una expresión, "decayó" hasta convertirse en un puntero al primer elemento.

De manera similar, podemos usar el mismo tipo de aritmética de punteros para iterar a través de una matriz de matrices, usando 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
}

Nuevamente hubo deterioro de la matriz. La variable arrque era de tipo int [2][3]se descompuso 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.

Es necesario comprender los punteros de la matriz y la descomposición de la matriz para poder trabajar con matrices multidimensionales.

Hay más casos en los que las matrices se comportan como variables normales. El sizeofoperador funciona igual para matrices (no VLA) que para variables regulares. Ejemplos para un sistema de 32 bits:

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

Como cualquier otro tipo, las matrices se pueden utilizar con funciones de biblioteca y API genéricas. Dado que las matrices cumplen con el requisito de asignarse de forma contigua, podemos, por ejemplo, copiarlas 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 también es la razón por la que otras funciones de biblioteca estándar similares como memset, y funcionan. Están diseñados para funcionar en matrices asignadas de forma contigua. Entonces, si tiene una matriz multidimensional, puede buscarla y ordenarla de manera eficiente con y , ahorrándose la molestia de implementar la búsqueda binaria y la clasificación rápida usted mismo y, por lo tanto, reinventar la rueda para cada proyecto.strcpybsearchqsortbsearchqsort

Todas las coherencias anteriores entre matrices y otros tipos son algo muy bueno que queremos aprovechar, especialmente cuando hacemos programación genérica.

¿Qué es eso de puntero a puntero, sino 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 para apuntar a una matriz 2D.

Sin embargo, se puede utilizar un puntero a puntero para señalar el primer elemento de una matriz de punteros, en lugar de apuntar a la matriz en su totalidad. Y así es como se usa en la pregunta: como una forma de "emular" un puntero de matriz. En la pregunta, se utiliza para señalar una serie de 2 punteros. Y luego cada uno de los 2 punteros se usa para apuntar a una matriz de 3 números enteros.

Esto se conoce como 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 simples. 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 0x12340000cuadro representa el puntero a puntero. Contiene una dirección 0x12340000al primer elemento de una serie de punteros. Cada puntero en esa matriz, a su vez, contiene una dirección que apunta al primer elemento de una matriz de números enteros.

Y aquí es donde empiezan los problemas.

Problemas con la versión de la tabla de consulta.

La tabla de búsqueda está esparcida por toda la memoria del montón. No se asigna memoria de forma contigua en celdas adyacentes, porque cada llamada a malloc()proporciona una nueva área de memoria, no necesariamente ubicada junto a las demás. Esto a su vez nos genera muchos problemas:

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

• No podemos usar el operador sizeof. Usado en el puntero a puntero, nos daría el tamaño de un puntero a puntero. Acostumbrado al primer elemento señalado, nos daría el tamaño de un puntero. Ninguno de ellos tiene el tamaño de una matriz.

• No podemos usar funciones de biblioteca estándar que exceptúen un tipo de matriz ( ,,, memcpyetc. ) . Todas estas funciones suponen obtener matrices como entrada, con datos asignados de forma contigua. Llamarlos con nuestra tabla de búsqueda como parámetro daría como resultado errores de comportamiento no definidos, como fallas del programa.memsetstrcpybsearchqsort

• Las llamadas repetidas a mallocpara asignar varios segmentos provocan la fragmentación del montón , lo que a su vez da como resultado un uso deficiente de la memoria RAM.

• Dado que la memoria está dispersa, la CPU no puede utilizar la memoria caché al iterar a través de la tabla de búsqueda. El uso eficiente de la caché de datos requiere una porción de memoria contigua que se repite 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 general que debe ejecutarse. Por lo tanto, a menudo es preferible la menor cantidad posible de llamadas a estas funciones, por razones de rendimiento.

¿Son todas malas las tablas de consulta?

Como podemos ver, existen muchos problemas con las tablas de búsqueda basadas en punteros. Pero no todas son malas, es una herramienta como cualquier otra. Sólo tiene que usarse para el propósito correcto. Si está buscando una matriz multidimensional que deba usarse como matriz, las tablas de búsqueda son claramente la herramienta equivocada. Pero se pueden utilizar para otros fines.

Una tabla de consulta es la elección correcta cuando necesita que todas las dimensiones tengan tamaños completamente variables, individualmente. Un contenedor de este tipo puede resultar útil, por ejemplo, al crear una lista de cadenas C. Entonces, a menudo está justificado tomar la pérdida de rendimiento de la velocidad de ejecución mencionada anteriormente para ahorrar memoria.

Además, la tabla de búsqueda tiene la ventaja de que puede reasignar 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 utilizar tablas de búsqueda similares al implementar una tabla hash encadenada.

Entonces, ¿cómo asignar correctamente una matriz multidimensional de forma dinámica?

La forma más sencilla en C moderno es simplemente utilizar una matriz de longitud variable (VLA). int array[x][y];donde xy yson variables a las que se les dan valores en tiempo de ejecución, antes de la declaración de matriz. Sin embargo, los VLA tienen alcance local y no persisten durante la duración del programa; tienen una duración de almacenamiento automático. Entonces, si bien los VLA pueden ser convenientes y rápidos de usar para matrices temporales, no son un reemplazo universal de la tabla de búsqueda de la pregunta.

Para asignar realmente una matriz multidimensional de forma dinámica, de modo que se le asigne una duración de almacenamiento , tenemos que usar malloc()// . Daré un ejemplo a continuación.calloc()realloc()

En C moderno, usaría punteros de matriz a un VLA. Puede utilizar dichos punteros incluso cuando no haya ningún VLA real presente en el programa. El beneficio de usarlos en lugar de uno simple type*o uno void*es una mayor seguridad de tipografía. 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 que usa la matriz, lo que la hace variable y segura a la vez.

Desafortunadamente, para aprovechar los beneficios de tener un puntero a VLA, no podemos devolver ese puntero como resultado de la función. Entonces, si necesitamos devolver un puntero a la matriz a la persona que llama, debe pasarse como un parámetro (por las razones descritas en El acceso a memoria dinámica 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 puede 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;
}

Eso sí que es un lío ilegible de "programación de tres estrellas". Y ni siquiera consideremos las 4 dimensiones...

El código completo de una versión que utiliza matrices 2D reales.

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

Feb 07 '2017 16:02 Lundin