C matriz de crecimiento dinámico

Question

C matriz de crecimiento dinámico

Tengo un programa que lee una lista "cruda" de entidades en el juego, y tengo la intención de hacer una matriz que contiene 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 utilizo 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áximas, y otro entero para realizar un seguimiento de cuántas tienen se ha añadido 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 que use la solución para 6-7 listas para diferentes funciones.

No he encontrado ninguna solución específica para 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 manera posible).

Los arrays no abandonan el ámbito de la función local (se pasan a una función y luego se descartan), 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?

106

c dynamic-arrays

Author: Balkania, 2010-08-21

Source

4 answers

Se me ocurren un par de opciones.

Lista Enlazada. Puede utilizar una lista vinculada para hacer una matriz de crecimiento dinámico como cosa. Pero usted no será capaz de hacer array[100] sin tener que caminar a través de 1-99 primero. Y podría no ser tan útil para que usted lo use tampoco.
Gran matriz. Simplemente cree una matriz con espacio más que suficiente para todo
Redimensionar matriz. Vuelva a crear la matriz una vez que conozca el tamaño y / o cree una nueva matriz cada vez que se quede sin espacio con algún margen y copiar todos los datos a la nueva matriz.
Combinación de matriz de lista enlazada. Simplemente use una matriz con un tamaño fijo y una vez que se quede sin espacio, cree una nueva matriz y vincule a ella (sería prudente realizar 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 darle muchos problemas a menos que sea muy grande.

9

Author: Wolph,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-08-21 03:31:44

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

Desafortunadamente, hay limitaciones. Mientras todavía estés aprendiendo a usar una función, no deberías asumir el papel de un profesor, por ejemplo. A menudo leo respuestas de aquellos que aparentemente no saben cómo usar realloc (es decir, el respuesta actualmente aceptada!) diciéndole a otros cómo usarlo incorrectamente, ocasionalmente bajo el pretexto de que han omitido el manejo de errores, a pesar de que este es un escollo común que debe mencionarse. Aquí hay una respuesta que explica cómo usar realloc correctamente. Tenga en cuenta que la respuesta es almacenar el valor devuelto en una variable diferente para realizar la comprobación de errores.

Cada vez que llame a una función, y cada vez que use una matriz, estás usando un puntero. Las conversiones están ocurriendo implícitamente, lo que en todo caso debería ser aún más aterrador, ya que son las cosas que no vemos las que a menudo causan la mayoría de los problemas. Por ejemplo, fugas de memoria...

Los operadores de matriz son operadores de puntero. {[5] } es realmente un atajo para *(array + x), que se puede dividir en: * y (array + x). Lo más probable es que el * es lo que te confunde. Podemos eliminar aún más la adición del problema asumiendo x que es 0, así, array[0] se 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 los 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, la más adecuada cuando desee cambios drásticos y dinámicos en el tamaño .

Es una pena que la respuesta actualmente aceptada también vaya en contra del grano de algunos 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: miembros de matriz flexible! Esa es en realidad una bastante rota respuesta... :(

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 de int en la misma asignación que su count, y tenerlos unidos de esta manera puede ser muy útil!

sizeof (struct int_list) actuará como si value tuviera un tamaño de 0, por lo que le dirá el tamaño de la estructura con una lista vacía. Todavía necesita agregar al tamaño pasado a realloc para especificar el tamaño de su lista.

Otro un consejo práctico 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 por la que elegí usar struct int_list ** como el primer argumento puede no parecer inmediatamente obvia, pero si piensas en el segundo argumento, cualquier cambio realizado en value desde push_back no sería visible para la función desde la que estamos llamando, ¿verdad? Lo mismo ocurre con el primer argumento, y necesitamos poder modificar nuestro array, no solo aquí sino posiblemente también en cualquier otra función/s la pasamos a ...

array comienza apuntando a nada; es una lista vacía. Inicializar es lo mismo que añadirle. Por ejemplo:

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

P.d. Recuerde:free(array); ¡cuando termines con eso!

6

Author: autistic,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-08-07 14:31:19

Cuando dices

Hacer una matriz que contiene 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á usando "punteros" (es decir, números de identificación que se refieren a un elemento en una matriz), ¿por qué no solo usa punteros regulares (es decir, números de identificación que se refieren a un elemento en la matriz más grande: el todo memoria).

En lugar de que sus objetos almacenen un número de ID 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 dan miedo si piensas en ellos como índice de matriz para toda la memoria (que es lo que realmente son)

2

Author: Lie Ryan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-08-21 03:44:24

score 173 · Accepted Answer

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 uno usted mismo. En C++, puede utilizar el std::vector clase. C# y casi cualquier otro lenguaje de alto nivel también tienen alguna clase similar que administra matrices dinámicas para usted.

Si lo haces planee escribir el suyo propio, aquí hay algo para comenzar: la mayoría de las implementaciones de matrices dinámicas funcionan comenzando con una matriz de un tamaño predeterminado (pequeño), luego cuando se quede sin espacio al agregar un nuevo elemento, duplique el tamaño de la matriz. Como se puede ver en el ejemplo a continuación, no es muy difícil en absoluto: (He omitido las comprobaciones de seguridad para la 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);