reales - C matriz de crecimiento dinámico

matriz bcg pdf

Question

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

Una solución rápida y sucia que uso hasta ahora es declarar, en la función de procesamiento principal (enfoque local) la matriz con un tamaño de las entidades de juego máximo, y otro 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, que no es mucho, pero se siente como un desperdicio, ya que es posible usar la solución para 6-7 listas para funciones variables.

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

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

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

Answer 1

Puedo usar punteros, pero tengo miedo de usarlos.

Si necesita una matriz dinámica, no puede escapar de los punteros. ¿Por qué tienes miedo sin embargo? 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 clase incorporada std::vector . C # y casi todos los demás lenguajes de alto nivel también tienen una 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), y cada vez que se agota el espacio al agregar un nuevo elemento, duplica el tamaño de la matriz. Como puede ver en el siguiente ejemplo, no es muy difícil en absoluto: (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 = (int *)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 = (int *)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);

Answer 2

Al igual que con todo lo que parece más aterrador al principio que lo que fue más tarde, la mejor manera de superar el miedo inicial es sumergirse en la incomodidad de lo desconocido . Es en momentos como el que aprendemos más, después de todo.

Desafortunadamente, hay limitaciones. Mientras todavía estás aprendiendo a usar una función, no debes asumir el papel de un maestro, por ejemplo. A menudo leo las respuestas de aquellos que aparentemente no saben cómo usar el realloc (es decir, la respuesta actualmente aceptada ), diciéndoles a otros cómo usarlo incorrectamente, ocasionalmente bajo el disfraz de que han omitido el manejo de errores , aunque esto es algo común trampa que necesita mención. Aquí hay una respuesta que explica cómo usar realloc correctamente . 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 llamas a una función, y cada vez que utilizas una matriz, estás usando un puntero. Las conversiones están ocurriendo implícitamente, que en todo caso deberían ser aún más aterradoras, ya que son las cosas que no vemos las que a menudo causan más problemas. Por ejemplo, la memoria pierde ...

Los operadores de matriz son operadores de puntero. array[x] es realmente un acceso directo para *(array + x) , que se puede dividir en: * y (array + x) . Lo más probable es que * sea ​​lo que te confunde. Podemos eliminar aún más la adición del problema suponiendo que x es 0 , por lo tanto, array[0] convierte en *array porque agregar 0 no cambiará el valor ...

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

malloc , realloc y amigos no inventan el concepto de un 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 se desean cambios de tamaño drásticos y dinámicos .

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

Cuando defines tu struct , declara tu matriz al final de la estructura, sin ningún límite superior. Por ejemplo:

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

Esto le permitirá unir su matriz de int en la misma asignación que su count , y tenerlos atados así puede ser muy útil .

sizeof (struct int_list) actuará como si el value tuviera 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 el tamaño pasado a realloc para 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]->count = y;
    return 0;
}

struct int_list *array = NULL;

La razón por la que elegí usar struct int_list ** como primer argumento puede no parecer obvio inmediatamente, pero si piensas en el segundo argumento, cualquier cambio realizado en el value desde push_back no sería visible para la función a la que llamamos, ¿derecho? Lo mismo ocurre con el primer argumento, y necesitamos poder modificar nuestra array , no solo aquí, sino posiblemente también en cualquier otra función / es que la pasemos a ...

array comienza señalando a nada; es una lista vacía Inicializarlo es lo mismo que agregarlo. Por ejemplo:

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

Answer 3

Cuando estas diciendo

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

básicamente dice que está utilizando "punteros", pero uno que es un puntero local de matriz en lugar de un puntero de memoria. Dado que conceptualmente ya está utilizando "punteros" (es decir, números de identificación que se refiere a un elemento en una matriz), ¿por qué no utiliza punteros regulares (es decir, números de id que se refiere 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 recurso, puede hacer que almacenen un puntero en su lugar. Básicamente lo mismo, pero mucho más eficiente ya que evitamos convertir "matriz + índice" en un "puntero".

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

Answer 4

Hay un par de opciones en las que puedo pensar.

1. Lista enlazada. Puede usar una lista vinculada para hacer una matriz de crecimiento dinámico como una cosa. Pero no podrás hacer la array[100] sin tener que pasar primero por 1-99 . Y puede que tampoco sea tan útil para ti.
2. Gran variedad Simplemente crea una matriz con espacio más que suficiente para todo
3. Ajuste de tamaño del conjunto. Vuelva a crear 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 a la nueva matriz.
4. Combinación de combinación de listas vinculadas. Simplemente use una matriz con un tamaño fijo y una vez que se quede sin espacio, cree una nueva matriz y vincule con esa (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 variedad es, por supuesto, una de las soluciones más fáciles y no debería causarle muchos problemas a menos que sea realmente grande.

Answer 5

Urbanize es una biblioteca muy buena y extremadamente flexible para hacer exactamente esto: https://github.com/NateSeymour/urbanize

ptr_list list = create_list(sizeof(mystruct));
mystruct item;
list_add(list, item);

// After using:
list_destroy(list);