strings - Asignación correcta de matrices multidimensionales

matrices en programacion

Question

La intención de esta pregunta es proporcionar una referencia sobre cómo asignar correctamente las matrices multidimensionales dinámicamente en C. Este es un tema a menudo mal entendido y mal explicado incluso en algunos libros de programación en C. Por lo tanto, incluso los programadores experimentados de C luchan por hacerlo bien.

Mi maestro de programación / libro / tutorial me enseñó que la forma 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 práctica incorrecta y mala. Dicen que los punteros a 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?

Answer 1

Para responder a la pregunta, primero debemos aclarar algunos conceptos. ¿Qué es una matriz y cómo se puede usar? ¿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 de forma contigua con un tipo de objeto miembro particular, denominado 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 citó anteriormente. Se aplica de forma recursiva.

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 tipos 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 que en matrices unidimensionales simples. Con matrices unidimensionales regulares, la aplicación de 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 gracias a la "descomposición de la matriz". Cuando arr se usaba dentro de una expresión, "decaía" en un puntero al primer elemento.

De manera similar, podemos usar el mismo tipo de aritmética de puntero 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 una disminución de la matriz. La variable arr que era del tipo int [2][3] decayó en un puntero al primer elemento. El primer elemento fue 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 trabajar con matrices multidimensionales.

Hay más casos en los que las matrices se comportan igual que las variables regulares. El operador sizeof funciona igual para arreglos (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)); 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, las matrices se pueden usar con funciones de biblioteca y API genéricas. Dado que 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 que 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 eficientemente y ordenarla con bsearch y qsort , ahorrándole la molestia de implementar la búsqueda binaria y ordenarla rápidamente y, por lo tanto, reinventar la rueda para cada proyecto.

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

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

Ahora para volver al código en la pregunta, que usaba una sintaxis diferente con un puntero a puntero. No hay nada misterioso al respecto. Es un puntero a puntero para escribir, ni más ni menos. No es una matriz. No es una matriz 2D. Estrictamente hablando, no puede usarse para apuntar a una matriz, ni puede apuntar a una matriz 2D.

Sin embargo, un puntero a puntero se puede utilizar 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 luego, cada uno de los 2 punteros se usa para apuntar a 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 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 para el 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 consulta

La tabla de búsqueda está dispersa por toda la memoria de almacenamiento dinámico. No se asigna memoria de forma contigua en las celdas adyacentes, porque cada llamada a malloc() proporciona una nueva área de memoria, no necesariamente ubicada adyacente a las demás. 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 punteros de matriz.

• No podemos usar el operador sizeof. Utilizado 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 es del tamaño de una matriz.

• No podemos usar funciones de biblioteca estándar que exceptúen un tipo de matriz ( memcpy , memset , strcpy , bsearch , qsort , etc.). Todas estas funciones asumen obtener 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 bloqueos del programa.

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

• Como la memoria está dispersa, la CPU no puede utilizar la memoria caché cuando recorre la tabla de búsqueda. El uso eficiente de la memoria caché de datos requiere una porción contigua de memoria 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 realizar tan pocas llamadas a estas funciones como sea posible, en aras del rendimiento.

¿Las tablas 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 usarse para el propósito correcto. Si está buscando una matriz multidimensional, que debe usarse como una matriz, las tablas de búsqueda son claramente la herramienta incorrecta. Pero pueden usarse para otros fines.

Una tabla de consulta es la opción correcta cuando necesita que todas las dimensiones tengan tamaños completamente variables, individualmente. Tal contenedor puede ser útil cuando, por ejemplo, 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 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 al conjunto multidimensional en términos de velocidad de ejecución. Por ejemplo, se pueden usar tablas de búsqueda similares al implementar una tabla hash encadenada.

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

La forma más fácil en la C moderna es simplemente usar una matriz de longitud variable (VLA). int array[x][y]; donde x e y son variables con valores dados en tiempo de ejecución, declaración de matriz previa. 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, aunque los VLA pueden ser convenientes y rápidos de usar para matrices 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 se le asigne la duración del almacenamiento , tenemos que usar malloc() / calloc() / realloc() . Daré un ejemplo a continuación.

En la C moderna, usaría punteros de matriz para un VLA. Puede usar estos punteros incluso cuando no haya un VLA real en el programa. El beneficio de usarlos sobre un type* simple type* o un void* es una mayor seguridad de tipos. 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 al mismo tiempo.

Desafortunadamente, para usar 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 a la persona que llama, debe pasarse como un parámetro (por las razones descritas en el 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 así:

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

Ahora que es un lío indescifrable 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;
}

Answer 2

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

Un posible enfoque es razonar con algún tipo de datos abstractos (tal vez usando 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 implementarlo.

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é palabras equivocadas?) ...

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