una Asignación correcta de matrices multidimensionales




matriz de caracteres en c (2)

El objetivo de esta pregunta es proporcionar una referencia sobre cómo asignar dinámicamente matrices multidimensionales dinámicamente en C. Este es un tema que a menudo se entiende mal y se explica poco, incluso en algunos libros de programación de C. Por lo tanto, incluso los experimentados programadores de C luchan para hacerlo bien.

Mi profesor / libro / tutorial de programación me enseñó que la manera correcta de asignar dinámicamente una matriz multidimensional es mediante el uso de punteros a punteros.

Sin embargo, varios usuarios de alta reputación en SO ahora me dicen que esto es una mala y mala práctica. Dicen que los punteros a los punteros no son matrices, que en realidad no estoy asignando matrices y que mi código es innecesariamente lento.

Así es como me enseñaron a asignar matrices multidimensionales:

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

Salida

1 2 3
1 2 3

Este código funciona bien! ¿Cómo podría estar mal?


C no tiene matrices multidimensionales. Pero podría tener matrices de matrices (o de otros agregados) y matrices de punteros.

Un posible enfoque es razonar con algún tipo de datos abstractos (tal vez utilizando miembros de matriz flexibles , que es un truco de implementación, y podría usar otros enfoques) como en esta respuesta .

No podemos sugerir ningún tipo de datos abstractos, porque eso depende del texto de su tarea, que no tenemos. Debe diseñar su tipo de datos abstractos (en una hoja de papel) y luego implementarlos.

Una vez que haya enumerado (en un papel o en una pizarra) todas las operaciones necesarias en su ADT, implementarlas es sencillo.

Este código funciona bien! ¿Cómo podría estar mal?

Esa oración es inconsistente (¿qué especificaciones son incorrectas?) ...

Recomiendo compilar con todas las advertencias y la información de depuración (por ejemplo, with gcc -Wall -Wextra -g con GCC ), para mejorar su código hasta que no reciba advertencias, para usar el depurador gdb (para comprender qué está sucediendo en su programa) y otras herramientas como valgrind .


Para responder a la pregunta, primero debemos aclarar algunos conceptos. ¿Qué es una matriz y cómo puede usarse? ¿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 de objetos no vacíos asignados contiguamente con un tipo de objeto miembro particular, llamado tipo de elemento.

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 esta 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 cita arriba. Se aplica recursivamente.

Si asignamos 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 enteros.

Una matriz es un tipo como cualquier otro

Las matrices en C a menudo siguen el mismo sistema de tipo 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 matrices n- dimensionales como en matrices simples unidimensionales. Con matrices unidimensionales regulares, aplicar la aritmética del 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 de "decaimiento de matriz". Cuando arr se usó dentro de una expresión, se "descompuso" en un puntero al primer elemento.

De forma similar, podemos usar el mismo tipo de aritmética de puntero para iterar a través de una matriz de matrices, utilizando 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 decaimiento de la matriz. La 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 matriz y la disminución de la matriz.

Hay más casos en que las matrices se comportan como las variables regulares. El operador sizeof funciona de la misma manera para matrices (que no son VLA) como 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 usar con funciones de biblioteca y API genéricas. Como las matrices cumplen el requisito de ser asignadas contiguamente, 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 cual funcionan otras funciones de biblioteca estándar similares como memset , strcpy , bsearch y qsort . Están diseñados para trabajar en matrices asignadas contiguamente. Por lo tanto, si tiene una matriz multidimensional, puede buscarla y ordenarla eficientemente con bsearch y qsort , ahorrándole la molestia de implementar la búsqueda binaria y ordenarla usted mismo rápidamente y, por lo tanto, reinventar la rueda para cada proyecto.

Todas las consistencias anteriores entre las matrices y otros tipos son algo muy bueno que queremos aprovechar, especialmente al hacer una programación genérica.

¿Cuál es la cosa de puntero a puntero, si no es una matriz?

Ahora para volver al código en la pregunta, que utilizó una sintaxis diferente con un puntero a puntero. No hay nada misterioso al respecto. Es un puntero al puntero para escribir, 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 usarse 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 usa para apuntar a una matriz de 2 punteros. Y luego, cada uno de los 2 punteros se usa para apuntar una matriz de 3 enteros.

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

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

Las direcciones de 32 bits en este ejemplo están compuestas. El cuadro 0x12340000 representa el puntero-a-puntero. Contiene una dirección 0x12340000 al primer elemento en 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 versión de la tabla de búsqueda

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

  • No podemos usar la aritmética del puntero como se espera. Si bien podemos utilizar una forma de aritmética de puntero para indexar y acceder a los elementos en la tabla de búsqueda, no podemos hacerlo utilizando 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. Usado para el primer elemento apuntado, nos daría el tamaño de un puntero. Ninguno de ellos es del tamaño de una matriz.

  • No podemos usar funciones de biblioteca estándar que exceptúe un tipo de matriz ( memcpy , memset , strcpy , bsearch , qsort , etc.). Todas estas funciones asumen que se obtienen matrices como entrada, con datos asignados contiguamente. Llamarlos con nuestra tabla de búsqueda como parámetro daría lugar a errores de comportamiento indefinidos, como fallos del programa.

  • Las llamadas repetidas de malloc para asignar varios segmentos conducen a la fragmentation montón, 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é cuando itera a través de la tabla de búsqueda. El uso eficiente de la memoria caché de datos requiere un bloque contiguo de memoria que se itera de arriba hacia 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 debe calcular dónde hay espacio libre. De manera similar para cada llamada a free (), hay un código de gastos generales que debe ejecutarse. Por lo tanto, como pocas llamadas a estas funciones como sea posible a menudo es preferible, en aras del rendimiento.

¿Las tablas de búsqueda son malas?

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

Una tabla de búsqueda es la elección correcta cuando necesita 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. A menudo se justifica tomar la pérdida de rendimiento de la velocidad de ejecución antes mencionada 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 se debe hacer 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 de forma dinámica?

La forma más sencilla en C moderna es simplemente usar una matriz de longitud variable (VLA). int array[x][y]; donde y son variables dadas valores en tiempo de ejecución, declaración de matriz anterior. Sin embargo, los VLA tienen alcance local y no persisten durante la duración del programa: tienen una duración de almacenamiento automática. Entonces, aunque los VLA pueden ser convenientes y rápidos de usar para matrices temporales, no es un reemplazo universal para la tabla de búsqueda en la pregunta.

Para asignar dinámicamente una matriz multidimensional de forma que se le asigne duración de almacenamiento , debemos utilizar malloc / calloc / realloc. Voy a dar un ejemplo a continuación.

En la C moderna, usaría apuntadores de matriz a un VLA. Puede usar dichos punteros incluso cuando no haya un VLA real presente en el programa. El beneficio de usarlos sobre un type* simple type* o un void* aumenta la seguridad del 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, por lo que es tanto variable como segura a la vez.

Lamentablemente, para utilizar los beneficios de tener un puntero a VLA, no podemos devolver ese puntero como resultado de una función. Entonces, si necesitamos devolver un puntero a la matriz para la persona que llama, debe pasarse como un parámetro (por los motivos descritos en Acceso a la 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ño e intimidante, no se vuelve más complejo 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 ese es un desastre indescriptible de "programación de tres estrellas". Y ni siquiera consideremos 4 dimensiones ...

El código completo de una versión que usa 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;
}




variable-length-array