C matriz de crecimiento dinámico

Tengo un programa que lee una lista "en bruto" de entidades en el juego, y tengo la intención de hacer una matriz que contenga un número de índice (int) de un número indeterminado de entidades, para procesar varias cosas. Me gustaría evitar usar demasiada memoria o CPU para mantener tales índices ...

Una solución rápida y sucia que uso hasta ahora es declarar, en la función de procesamiento principal (foco local), la matriz con un tamaño de las entidades máximas del juego y otro número entero para realizar un seguimiento de cuántos se han agregado a la lista. Esto no es satisfactorio, ya que cada lista contiene más de 3000 matrices, lo que no es mucho, pero se siente como un desperdicio, ya que posiblemente usaré la solución para 6-7 listas para diversas funciones.

No he encontrado ninguna solución específica de C (no C ++ o C #) para lograr esto. Puedo usar punteros, pero tengo un poco de miedo de usarlos (a menos que sea la única forma posible).

Las matrices no abandonan el ámbito de la función local (deben pasarse a una función y luego descartarse), en caso de que eso cambie las cosas.

Si los punteros son la única solución, ¿cómo puedo hacer un seguimiento de ellos para evitar fugas?

Puedo usar punteros, pero tengo un poco de miedo de usarlos.

Si necesita una matriz dinámica, no puede escapar de los punteros. ¿Por qué tienes miedo? No morderán (siempre y cuando tengas cuidado, eso es). No hay una matriz dinámica incorporada en C, solo tendrá que escribir una usted mismo. En C ++, puede usar la std::vectorclase integrada . C # y casi todos los demás lenguajes de alto nivel también tienen alguna clase similar que gestiona matrices dinámicas para usted.

Si planea escribir el suyo, aquí hay algo para comenzar: la mayoría de las implementaciones de matriz dinámica funcionan comenzando con una matriz de algún tamaño predeterminado (pequeño), luego, cuando se quede sin espacio al agregar un nuevo elemento, duplique tamaño de la matriz. Como puede ver en el ejemplo a continuación, no es nada difícil: (he omitido los controles de seguridad por brevedad)

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void initArray(Array *a, size_t initialSize) {
  a->array = malloc(initialSize * sizeof(int));
  a->used = 0;
  a->size = initialSize;
}

void insertArray(Array *a, int element) {
  // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed.
  // Therefore a->used can go up to a->size 
  if (a->used == a->size) {
    a->size *= 2;
    a->array = realloc(a->array, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

void freeArray(Array *a) {
  free(a->array);
  a->array = NULL;
  a->used = a->size = 0;
}

Usarlo es igual de simple:

Array a;
int i;

initArray(&a, 5);  // initially 5 elements
for (i = 0; i < 100; i++)
  insertArray(&a, i);  // automatically resizes as necessary
printf("%d\n", a.array[9]);  // print 10th element
printf("%d\n", a.used);  // print number of elements
freeArray(&a);

Hay un par de opciones en las que puedo pensar.

1. Lista enlazada. Puede usar una lista vinculada para crear una matriz que crezca dinámicamente. Pero no podrá hacerlo array[100]sin tener que caminar 1-99primero. Y puede que tampoco sea tan útil para usted usar.
2. Gran variedad. Simplemente cree una matriz con espacio más que suficiente para todo
3. Cambiar el tamaño de la matriz. Recree la matriz una vez que sepa el tamaño y / o cree una nueva matriz cada vez que se quede sin espacio con algún margen y copie todos los datos en la nueva matriz.
4. Combinación de matriz de lista vinculada. Simplemente use una matriz con un tamaño fijo y una vez que se quede sin espacio, cree una nueva matriz y vincúlela (sería conveniente hacer un seguimiento de la matriz y el enlace a la siguiente matriz en una estructura).

Es difícil decir qué opción sería la mejor en su situación. Simplemente crear una gran matriz es, por supuesto, una de las soluciones más fáciles y no debería darle muchos problemas a menos que sea realmente grande.

Al igual que con todo lo que parece más aterrador al principio que después, ¡la mejor manera de superar el miedo inicial es sumergirse en la incomodidad de lo desconocido ! A veces es lo que más aprendemos, después de todo.

Lamentablemente, hay limitaciones. Mientras todavía está aprendiendo a usar una función, no debe asumir el papel de un maestro, por ejemplo. A menudo leo las respuestas de aquellos que aparentemente no saben cómo usarlos realloc(es decir, ¡ la respuesta actualmente aceptada! ) Y les digo a los demás cómo usarlos incorrectamente, ocasionalmente con el pretexto de que han omitido el manejo de errores , a pesar de que este es un error común. que necesita mención Aquí hay una respuesta que explica cómo usar realloccorrectamente . Tenga en cuenta que la respuesta es almacenar el valor de retorno en una variable diferente para realizar la comprobación de errores.

Cada vez que llama a una función, y cada vez que usa una matriz, está usando un puntero. Las conversiones están ocurriendo implícitamente, lo que si algo debería ser aún más aterrador, ya que son las cosas que no vemos que a menudo causan la mayoría de los problemas. Por ejemplo, pérdidas de memoria ...

Los operadores de matriz son operadores de puntero. array[x]es realmente un atajo para *(array + x), que se puede dividir en: *y (array + x). Es muy probable que eso *sea ​​lo que te confunda. Podemos eliminar aún más la suma del problema suponiendo xque se convierte 0, por lo tanto, array[0]en *arrayque la suma 0no cambiará el valor ...

... y así podemos ver que *arrayes equivalente a array[0]. Puede usar uno donde quiera usar el otro, y viceversa. Los operadores de matriz son operadores de puntero.

malloc, reallocy los amigos no inventan el concepto de puntero que has estado usando todo el tiempo; simplemente usan esto para implementar alguna otra característica, que es una forma diferente de duración de almacenamiento, más adecuada cuando desea cambios drásticos y dinámicos en el tamaño .

Es una pena que la respuesta actualmente aceptada también vaya en contra de otros consejos muy bien fundados sobre StackOverflow y, al mismo tiempo, pierda la oportunidad de introducir una característica poco conocida que brilla exactamente para este caso de uso: matriz flexible miembros! Esa es en realidad una respuesta bastante rota ... :(

Cuando defina su struct, declare su matriz al final de la estructura, sin ningún límite superior. Por ejemplo:

struct int_list {
    size_t size;
    int value[];
};

¡Esto le permitirá unir su matriz inten la misma asignación que la suya count, y hacer que se unan así puede ser muy útil !

sizeof (struct int_list)actuará como si valuetuviera un tamaño de 0, por lo que le dirá el tamaño de la estructura con una lista vacía . Aún necesita agregar al tamaño pasado reallocpara especificar el tamaño de su lista.

Otro consejo útil es recordar que realloc(NULL, x)es equivalente a malloc(x), y podemos usar esto para simplificar nuestro código. Por ejemplo:

int push_back(struct int_list **fubar, int value) {
    size_t x = *fubar ? fubar[0]->size : 0
         , y = x + 1;

    if ((x & y) == 0) {
        void *temp = realloc(*fubar, sizeof **fubar
                                   + (x + y) * sizeof fubar[0]->value[0]);
        if (!temp) { return 1; }
        *fubar = temp; // or, if you like, `fubar[0] = temp;`
    }

    fubar[0]->value[x] = value;
    fubar[0]->size = y;
    return 0;
}

struct int_list *array = NULL;

La razón que elegí para usar struct int_list **como primer argumento puede no parecer obvia de inmediato, pero si piensas en el segundo argumento, cualquier cambio realizado valuedesde adentro push_backno sería visible para la función desde la que estamos llamando, ¿verdad? Lo mismo ocurre con el primer argumento, y debemos ser capaces de modificar nuestro array, no solo aquí, sino posiblemente también en cualquier otra función que lo pasamos a ...

arraycomienza apuntando a la nada; Es una lista vacía. Inicializarlo es lo mismo que agregarle. Por ejemplo:

struct int_list *array = NULL;
if (!push_back(&array, 42)) {
    // success!
}

PD: ¡ Recuerdafree(array); cuando hayas terminado con eso!

Sobre la base del diseño de Matteo Furlans , cuando dijo que "la mayoría de las implementaciones de matriz dinámica funcionan comenzando con una matriz de un tamaño predeterminado (pequeño), luego cada vez que se queda sin espacio al agregar un nuevo elemento, duplica el tamaño de la matriz ". La diferencia en el " trabajo en progreso " a continuación es que no duplica su tamaño, apunta a usar solo lo que se requiere. También he omitido las verificaciones de seguridad por simplicidad ... También basándose en la idea de brimboriums , he intentado agregar una función de eliminación al código ...

El archivo storage.h se ve así ...

#ifndef STORAGE_H
#define STORAGE_H

#ifdef __cplusplus
extern "C" {
#endif

    typedef struct 
    {
        int *array;
        size_t size;
    } Array;

    void Array_Init(Array *array);
    void Array_Add(Array *array, int item);
    void Array_Delete(Array *array, int index);
    void Array_Free(Array *array);

#ifdef __cplusplus
}
#endif

#endif /* STORAGE_H */

El archivo storage.c se ve así ...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

/* Initialise an empty array */
void Array_Init(Array *array) 
{
    int *int_pointer;

    int_pointer = (int *)malloc(sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to allocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
        array->size = 0;
    }
}

/* Dynamically add to end of an array */
void Array_Add(Array *array, int item) 
{
    int *int_pointer;

    array->size += 1;

    int_pointer = (int *)realloc(array->array, array->size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer;
        array->array[array->size-1] = item;
    }
}

/* Delete from a dynamic array */
void Array_Delete(Array *array, int index) 
{
    int i;
    Array temp;
    int *int_pointer;

    Array_Init(&temp);

    for(i=index; i<array->size; i++)
    {
        array->array[i] = array->array[i + 1];
    }

    array->size -= 1;

    for (i = 0; i < array->size; i++)
    {
        Array_Add(&temp, array->array[i]);
    }

    int_pointer = (int *)realloc(temp.array, temp.size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
    } 
}

/* Free an array */
void Array_Free(Array *array) 
{
  free(array->array);
  array->array = NULL;
  array->size = 0;  
}

El main.c se ve así ...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

int main(int argc, char** argv) 
{
    Array pointers;
    int i;

    Array_Init(&pointers);

    for (i = 0; i < 60; i++)
    {
        Array_Add(&pointers, i);        
    }

    Array_Delete(&pointers, 3);

    Array_Delete(&pointers, 6);

    Array_Delete(&pointers, 30);

    for (i = 0; i < pointers.size; i++)
    {        
        printf("Value: %d Size:%d \n", pointers.array[i], pointers.size);
    }

    Array_Free(&pointers);

    return (EXIT_SUCCESS);
}

Esperamos con interés la crítica constructiva a seguir ...

Cuando estas diciendo

hacer una matriz que contenga un número de índice (int) de un número indeterminado de entidades

básicamente estás diciendo que estás usando "punteros", pero uno que es un puntero local de toda la matriz en lugar de un puntero de toda la memoria. Dado que conceptualmente ya está utilizando "punteros" (es decir, números de identificación que se refieren a un elemento en una matriz), ¿por qué no simplemente utiliza punteros regulares (es decir, números de identificación que se refieren a un elemento en la matriz más grande: toda la memoria )

En lugar de que sus objetos almacenen números de identificación de recursos, puede hacer que almacenen un puntero. Básicamente lo mismo, pero mucho más eficiente ya que evitamos convertir "array + index" en un "puntero".

Los punteros no dan miedo si los considera como un índice de matriz para toda la memoria (que es lo que realmente son)

Para crear una matriz de elementos ilimitados de cualquier tipo:

typedef struct STRUCT_SS_VECTOR {
    size_t size;
    void** items;
} ss_vector;


ss_vector* ss_init_vector(size_t item_size) {
    ss_vector* vector;
    vector = malloc(sizeof(ss_vector));
    vector->size = 0;
    vector->items = calloc(0, item_size);

    return vector;
}

void ss_vector_append(ss_vector* vec, void* item) {
    vec->size++;
    vec->items = realloc(vec->items, vec->size * sizeof(item));
    vec->items[vec->size - 1] = item;
};

void ss_vector_free(ss_vector* vec) {
    for (int i = 0; i < vec->size; i++)
        free(vec->items[i]);

    free(vec->items);
    free(vec);
}

Y cómo usarlo:

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT {
    int id;
} apple;

apple* init_apple(int id) {
    apple* a;
    a = malloc(sizeof(apple));
    a-> id = id;
    return a;
};


int main(int argc, char* argv[]) {
    ss_vector* vector = ss_init_vector(sizeof(apple));

    // inserting some items
    for (int i = 0; i < 10; i++)
        ss_vector_append(vector, init_apple(i));


    // dont forget to free it
    ss_vector_free(vector);

    return 0;
}

Este vector / matriz puede contener cualquier tipo de elemento y tiene un tamaño completamente dinámico.

Bueno, supongo que si necesita eliminar un elemento, hará una copia de la matriz despreciando el elemento que se excluirá.

// inserting some items
void* element_2_remove = getElement2BRemove();

for (int i = 0; i < vector->size; i++){
       if(vector[i]!=element_2_remove) copy2TempVector(vector[i]);
       }

free(vector->items);
free(vector);
fillFromTempVector(vector);
//

Suponga eso getElement2BRemove(), copy2TempVector( void* ...)y fillFromTempVector(...)son métodos auxiliares para manejar el vector temporal.