C crescente gamma dinamica

Question

Ho un programma che legge un elenco "grezza" di entità in-game, e ho intenzione di fare una matrice in possesso di un numero di indice (int) di un numero indeterminato di soggetti, per l'elaborazione di varie cose. Vorrei evitare di usare troppa memoria o CPU per mantenere tali indici ...

Una soluzione rapida e sporca che uso finora è quello di dichiarare, nella funzione di elaborazione principale (messa a fuoco locale) la matrice con una dimensione delle entità massima del gioco, e un altro intero per tenere traccia di quante sono state aggiunte alla elenco. Questo non è soddisfacente, come ogni lista tiene 3000+ array, che non è più di tanto, ma si sente come uno spreco, dal momento che io uso possibile la soluzione per 6-7 liste per le funzioni di variabili.

non ho trovato alcun C (non C ++ o C #) soluzioni specifiche per raggiungere questo obiettivo. Posso utilizzare i puntatori, ma io sono un po 'paura di usarle (a meno che sia il modo possibile solo).

Gli array non lasciare il campo funzione locale (devono essere passato a una funzione, poi scartato), nel caso in cui cambia le cose.

Se i puntatori sono l'unica soluzione, come posso tenere traccia di loro per evitare perdite?

Answer 1

  

posso usare i puntatori, ma io sono un po 'paura di usarle.

Se avete bisogno di una matrice dinamica, non si può sfuggire puntatori. Perché hai paura però? Essi non morde (fino a quando si sta attenti, che è). Non c'è built-in array dinamico in C, non vi resta che scrivere uno voi stessi. In C ++, è possibile utilizzare il built-in std::vector classe. C # e quasi ogni altro linguaggio di alto livello hanno anche un po 'di classe simile che gestisce gli array dinamici per voi.

Se si ha intenzione di scrivere il proprio, di qui qualcosa per iniziare: più dinamica lavoro implementazioni di array da partendo con una serie di alcune (piccole) dimensione di default, quindi ogni volta che si esaurisce lo spazio quando si aggiunge un nuovo elemento , il doppio della dimensione della matrice. Come si può vedere nell'esempio qui sotto, non è molto difficile a tutti: (ho omesso i controlli di sicurezza per brevità)

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

Con esso è altrettanto semplice:

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

Ci sono un paio di opzioni che posso pensare.

1. lista concatenata. È possibile utilizzare una lista collegata di fare una crescente gamma dinamica come cosa. Ma non sarà in grado di fare array[100] senza dover camminare attraverso 1-99 prima. E non potrebbe essere che a portata di mano per l'uso sia.
2. Large Array. È sufficiente creare un array con spazio più che sufficiente per tutto
array
3. Il ridimensionamento. Ricreare l'array una volta che si conosce la dimensione e / o creare un nuovo array ogni volta che si esaurisce lo spazio con un certo margine e copiare tutti i dati per il nuovo array.
4. lista concatenata Array combinazione. Basta usare un array con una dimensione fissa e una volta che si esaurisce lo spazio, creare un nuovo array e link a quella (che sarebbe saggio per tenere traccia della matrice e il link per il prossimo matrice in una struct).

E 'difficile dire quale opzione sarebbe meglio nella vostra situazione. Semplicemente creando una vasta gamma è naturalmente una delle soluzioni più semplici e non si dovrebbe dare problemi molto meno che non sia molto grande.

Answer 3

Come per ogni cosa che sembra più spaventoso in un primo momento di quanto non fosse in seguito, il modo migliore per superare la paura iniziale è quello di immergersi nel disagio dello sconosciuto ! E 'in momenti come quello che impariamo di più, dopo tutto.

Purtroppo, ci sono delle limitazioni. Mentre si sta ancora imparando ad utilizzare una funzione, non si dovrebbe assumere il ruolo di un insegnante, per esempio. Leggo spesso risposte da coloro che apparentemente non sanno come utilizzare realloc (cioè la risposta attualmente accettato! ) dire agli altri come usarlo in modo non corretto, di tanto in tanto con il pretesto che essi hanno gestione degli errori omesso , anche se questo è un errore comune che necessita menzione. Ecco una risposta che spiega come utilizzare correttamente realloc . Prendete nota che la risposta sta memorizzando il valore di ritorno in una variabile diverso al fine di eseguire il controllo degli errori.

Ogni volta che si chiama una funzione, ed ogni volta che si utilizza una matrice, si utilizza un puntatore. Le conversioni si stanno verificando in modo implicito, che semmai dovrebbe essere ancora più spaventosa, come sono le cose che non vediamo che spesso causa la maggior parte dei problemi. Ad esempio, le perdite di memoria ...

Array operatori sono operatori di puntatore. array[x] è davvero una scorciatoia per *(array + x), che può essere suddiviso in: * e (array + x). E 'più probabile che la * è quello che si confonde. Possiamo eliminare ulteriormente l'aggiunta dal problema ipotizzando x essere 0, quindi, diventa array[0] *array perché aggiungendo 0 non cambierà il valore ...

... e così possiamo vedere che *array è equivalente a array[0]. È possibile utilizzare uno in cui si desidera utilizzare l'altra, e viceversa. operatori di matrice sono operatori di puntatore.

malloc, realloc e gli amici non inventano il concetto di un puntatore che hai utilizzato per tutto il tempo; si limitano a utilizzo questo per implementare qualche altra caratteristica, che è una forma diversa di durata di conservazione, più adatto quando si desidera drastici cambiamenti dinamici, in termini di dimensioni .

E 'un peccato che la risposta attualmente accettato anche va contro il chicco di qualche altro consiglio molto ben fondata su StackOverflow , e, allo stesso tempo, perde occasione per introdurre una caratteristica poco conosciuta che brilla proprio per questo caso d'uso: i membri di matrice flessibili! Questo è in realtà un abbastanza rotto risposta ...: (

Quando si definisce la vostra struct, dichiarare la matrice alla fine della struttura, senza alcun limite superiore. Ad esempio:

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

Questo vi permetterà di unire la vostra gamma di int nella stessa allocazione come count, e averli legati come questo può essere molto pratico

sizeof (struct int_list) agirà come se value ha una dimensione di 0, in modo che ti dirà la dimensione della struttura con un elenco vuoto . Hai ancora bisogno di aggiungere la dimensione passato a realloc per specificare la dimensione della vostra lista.

Un altro suggerimento utile è quello di ricordare che realloc(NULL, x) equivale a malloc(x), e possiamo usare questo per semplificare il nostro codice. Ad esempio:

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 ragione per cui ho scelto di usare struct int_list ** come primo argomento non può sembrare immediatamente evidente, ma se si pensa al secondo argomento, le modifiche apportate al value dall'interno push_back non sarebbe visibile alla funzione che stiamo chiamando da, giusto? Lo stesso vale per il primo argomento, e abbiamo bisogno di essere in grado di modificare il nostro array, non solo qui ma , eventualmente anche in qualsiasi altra funzione / s si passa a ...

array inizia indica a niente; è un elenco vuoto. Inizializzazione è la stessa come l'aggiunta ad esso. Ad esempio:

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

P.S. Ricordate di free(array); quando hai finito con esso!

Answer 4

Quando stai dicendo

  

fare una matrice che tiene un numero di indice (int) di un numero indeterminato di entità

si sta in fondo si sta utilizzando dicendo "puntatori", ma che è un puntatore a livello locale invece di puntatore ampia memoria. Visto che siete concettualmente già utilizzando "puntatori" (vale a dire i numeri id che si riferisce a un elemento di un array), perché non basta usare puntatori regolari (cioè numeri ID che fa riferimento a un elemento nella più grande serie: l'intera memoria ).

Al posto degli oggetti memorizzazione di un numero di risorse id, si può farli memorizzare un puntatore invece. Fondamentalmente la stessa cosa, ma molto più efficiente, in quanto si evita di svolta "array + index" in un "puntatore".

I puntatori non fanno paura se si pensa a loro come indice di array per l'intera memoria (che è quello che in realtà sono)

Answer 5

Sulla Matteo Furlans di progettazione, quando ha detto " maggior parte delle implementazioni di array dinamico lavoro di partendo con una serie di alcune (piccole) dimensione di default, quindi ogni volta che si esaurisce lo spazio quando l'aggiunta di un nuovo elemento, il doppio della dimensione della matrice ". La differenza nel " lavori in corso " al di sotto è che non raddoppia in termini di dimensioni, si propone di utilizzare solo ciò che è richiesto. Ho anche omesso i controlli di sicurezza per la semplicità ... anche costruire su brimboriums idea, ho cercato di aggiungere una funzione di cancellazione del codice ...

Il file storage.h assomiglia a questo ...

#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 */

Il file storage.c assomiglia a questo ...

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

Gli sguardi main.c come questo ...

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

guardare avanti per la critiche costruttive a seguire ...

Answer 6

Per creare un array di oggetti illimitati di qualsiasi tipo di 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);
}

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

Questo vettore / matrice può contenere qualsiasi tipo di elemento ed è completamente dinamico taglia.

Answer 7

Beh, credo che se è necessario rimuovere un elemento si farà una copia della matrice disprezzare l'elemento da escludere.

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

Si supponga che getElement2BRemove(), copy2TempVector( void* ...) e fillFromTempVector(...) sono metodi ausiliari per gestire il vettore Temp.