C dinámicamente creciente variedad

https://stackoverflow.com/questions/3536153

30-09-2019
|

Pregunta

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

Una solución rápida y sucia utilizo hasta ahora es para declarar, con la función principal de procesamiento (enfoque local) la matriz con un tamaño de las entidades máximo de juego, y otro número entero para mantener un registro de cuántas se han añadido a la lista. Esto no es satisfactoria, ya que cada lista tiene 3000 + matrices, que no es mucho, pero se siente como un desperdicio, ya que voy posible uso de la solución durante 6-7 listas para variar funciones.

I no han encontrado ninguna C (no C ++ o # c) soluciones específicas para lograr esto. Puedo usar punteros, pero yo soy un poco de miedo de usarlos (a menos que sea la única forma posible).

Las matrices no dejar el ámbito local de la función (que se han de pasar a una función, entonces se desechan), en caso de que cambia las cosas.

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

Solución

I pueden usar punteros, pero yo soy un poco de miedo de usarlos.

Si necesita una matriz dinámica, no se puede escapar de los punteros. Por qué tienen miedo, aunque? No van a morder (siempre y cuando se tiene cuidado, que es). No hay incorporado en matriz dinámica en C, usted solo tiene que escribir uno usted mismo. En C ++, puede utilizar el incorporado en la std::vector clase. C # y casi todos los demás lenguajes de alto nivel también tiene un poco de clase similar que gestiona matrices dinámicas para usted.

Si usted planea escribir su propia, de aquí algo para empezar: más dinámica de trabajo implementaciones de matriz por comenzar con una serie de cierto tamaño predeterminado (pequeño), entonces cada vez que se queda sin espacio cuando se añade un nuevo elemento , el doble del tamaño de la matriz. Como se puede ver en el siguiente ejemplo, que no es muy difícil en absoluto: (He omitido los controles de seguridad para abreviar)

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

Su uso es tan sencillo:

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

Otros consejos

Hay un par de opciones que se me ocurre.

lista enlazada. Puede utilizar una lista enlazada para hacer una matriz de crecimiento dinámico como la cosa. Sin embargo, usted no será capaz de hacer array[100] sin tener que caminar a través 1-99 primero. Y puede ser que no sea tan útil para su uso tampoco.
array grande. Basta con crear una matriz con más que suficiente espacio para todo
cambio de tamaño. Volver a crear la matriz una vez que se conoce el tamaño y / o crear una nueva matriz cada vez que se queda sin espacio con cierto margen y copiar todos los datos a la nueva matriz.
lista enlazada combinación de matriz. Sólo tiene que utilizar una matriz con un tamaño fijo y una vez que se queda sin espacio, crear una nueva matriz y enlace a ese (que 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 mejor en su situación. Simplemente creando una gran matriz es por supuesto una de las soluciones más fáciles y no debe darle muchos problemas a menos que sea muy grande.

Como con todo lo que parece en un primer momento más aterrador de lo que era 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 se aprende más, después de todo.

Por desgracia, hay limitaciones. Mientras que todavía está aprendiendo a utilizar una función, no debe asumir el papel de un maestro, por ejemplo. Suelo leer las respuestas de los que aparentemente no saben cómo utilizar realloc (es decir, la respuesta corrientemente aceptada! ) decir a los demás cómo utilizar de manera incorrecta, de vez en cuando con el pretexto de que han omitido el tratamiento de errores , a pesar de que esto es un error común que necesita mención. Aquí es una respuesta que explica cómo utilizar correctamente realloc . Tomar nota de que la respuesta está almacenando el valor de retorno en un diferente variables con el fin de llevar a cabo la comprobación de errores.

Cada vez que se llama a una función, y cada vez que se utiliza una matriz, que está utilizando un puntero. Las conversiones se producen de forma implícita, que en todo caso debe ser aún más aterrador, ya que son las cosas que no vemos que a menudo causa la mayoría de los problemas. Por ejemplo, pérdidas de memoria ...

Operadores de matriz son los operadores de puntero. array[x] es realmente un acceso directo para *(array + x), que se pueden dividir en: * y (array + x). Es más probable que la * es lo que confunde. Podemos eliminar además la adición del problema asumiendo x ser 0, por lo tanto, se convierte en array[0] *array debido a la adición de 0 no cambiará el valor ...

... y por lo tanto podemos ver que *array es equivalente a array[0]. Puede utilizar uno en el que desea utilizar la otra, y viceversa. Operadores de matriz son los operadores de puntero.

malloc, realloc y amigos no inventan el concepto de un puntero que se ha estado usando todo el tiempo; se limitan a uso para poner en práctica esta alguna otra característica, que es una forma diferente de la duración de almacenamiento, más adecuado cuando se desea drásticas, los cambios dinámicos en el tamaño .

Es una pena que la respuesta aceptada actualmente también va a contrapelo de la algún otro consejo muy fundados en StackOverflow , y al mismo tiempo, pierde la oportunidad de introducir una característica poco conocida que brilla precisamente para este caso de uso: miembros de la matriz flexibles! Eso es en realidad un bastante roto respuesta ...: (

Al definir su struct, declara la matriz al final de la estructura, sin ningún límite superior. Por ejemplo:

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

Esto permitirá a unir su gama de int en la misma asignación como su count, y haberlos obligado como esto puede ser muy útil

sizeof (struct int_list) actuará como si value tiene un tamaño de 0, por lo que le dirá el tamaño de la estructura con una lista vacía . Todavía es necesario añadir al 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 el 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 elegimos utilizar struct int_list ** como primer argumento no puede parecer obvio, pero si se piensa en el segundo argumento, cualquier cambio realizado en value desde dentro push_back no sería visible a la función que estamos llamando desde, ¿Derecha? Lo mismo ocurre con el primer argumento, y tenemos que ser capaces de modificar nuestra array, no sólo aquí pero posiblemente también en cualquier otra función / s pasamos a ...

array comienza señala en nada; es una lista vacía. Inicializando que es lo mismo que sumar a la misma. Por ejemplo:

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

P.S. Recuerde free(array); cuando haya terminado con él!

Cuando usted está diciendo

crea un arreglo que contiene un número de índice (int) de un número indeterminado de entidades

básicamente está diciendo que está utilizando "punteros", pero que es un puntero de la lista de todo el local en lugar de puntero en toda la memoria. Puesto que usted es conceptualmente ya el uso de "punteros" (es decir, los números de identificación que se refiere a un elemento de una matriz), ¿por qué no sólo tiene que utilizar punteros regulares (es decir, los números de identificación que se refiere a un elemento de la mayor gama: toda la memoria ).

En lugar de los objetos que almacenan unos números de identificación de recursos, puede hacer que se almacenan un puntero en su lugar. Básicamente lo mismo, pero mucho más eficiente ya que evitar convertir "array + índice" en un "puntero".

Los punteros no son de miedo si se piensa en ellos como índice de la matriz para toda la memoria (que es lo que realmente son)

Sobre la base de Matteo Furlans diseño, cuando dijo: " mayoría de las implementaciones de matriz dinámica de trabajo, comenzando con una gran variedad de cierto tamaño predeterminado (pequeño), entonces cada vez que se queda sin espacio cuando la adición de un nuevo elemento, el doble del tamaño de la matriz ". La diferencia en el " trabajo en progreso " a continuación es que no lo hace el doble de tamaño, se pretende utilizar sólo lo que se requiere. También he omitido los controles de seguridad para la construcción de la simplicidad ... También en brimboriums idea, he tratado de añadir una función de borrado al código ...

El archivo storage.h se parece a esto ...

#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 parece a esto ...

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

Las miradas MAIN.C como este ...

#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 ...

Para crear una matriz de elementos ilimitadas de cualquier clase de 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 utilizarlo:

// 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 artículo y es completamente dinámico de tamaño.

Bueno, supongo que si es necesario eliminar un elemento que hará una copia de la matriz despreciando el elemento a ser excluido.

// 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);
//

Supongamos que getElement2BRemove(), copy2TempVector( void* ...) y fillFromTempVector(...) son métodos auxiliares para manejar el vector temp.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow