¿Cómo se almacena una matriz 2D dinámica en la memoria?

Question

¿Cómo se almacena una matriz 2D en la memoria?

Pensé en el siguiente enfoque, donde las filas se almacenan como bloques contiguos de memoria.

| _ __ _ __ _ __ || _ __ _ __ _ __ | __ _ __ __ _ | _ __ _ __ _ _ | ... | _ __ _ __ _ __ |

Los elementos son accesados ​​como (i, j) -> n * i + j, donde n es la dimensión de la matriz (suponiendo que sea nxn).

Pero, ¿qué sucede si quiero agregar una nueva columna al mismo? Tendría que actualizar cada elemento (n + 1) th en cada fila y también cambiarlos a la derecha, pero eso es muy costoso desde el punto de vista computacional.

Otra opción sería copiar la matriz en una nueva ubicación y actualizar las filas con los elementos de la nueva columna sobre la marcha. Pero eso tampoco es demasiado eficiente si la matriz es grande.

Y, finalmente, la tercera opción que pensé es asignar una cantidad fija de memoria para cada fila y cuando agregue una nueva columna, no es necesario que cambie las filas a la derecha.

No puedo tener espacios en la memoria, por lo que todos los bloques deben estar contiguos.

No estoy pidiendo una implementación en C usando punteros y la memoria RAM real, solo tengo curiosidad acerca de un enfoque teórico de almacenar una matriz dinámica 2d en la memoria para que sea fácil agregar nuevas filas o columnas para ello.

¿Hay otros enfoques más eficaces?

Answer 1

Si sabe que está creando una matriz 2D que expandirá, un enfoque sería asignar más tamaño que el que necesita en cada dimensión. No perder de vista el tamaño real y el tamaño asignado, y cuando el tamaño real es mayor que lo que se ha asignado, haga lo siguiente:

• el doble del tamaño de la asignación
• copiar todos los datos de la matriz de edad de la uno nuevo
• libre de la matriz de edad

Esto sería una extensión de 2D de una técnica común para la asignación de matrices 1D dinámicos.

Answer 2

Si necesita que las matrices se expandan y sean contiguas en la memoria, una forma de lograr esto es simplemente usar una matriz de 1d y 'falso' la 2ª dimensión.

Si su matriz 1d inicial tiene más espacio del que requieren todas sus matrices 2d, no requerirá que se mueva en la memoria (evitando posibles huecos). Sin embargo, dependiendo de cómo lo implemente, una inserción que hace crecer uno de los suborganismos puede requerir la reorganización de los elementos posteriores (también podría tener lagunas en su matriz, pero creo que esto viola el requisito de no vacíos).

Si realmente necesita 2 dimensiones, entonces la respuesta de Greg es el camino a seguir. Si conoce el tamaño de sus datos para empezar, lo hace mucho más fácil.